基于加权流关系的流程相似性算法

doi:10.3969/j.issn.0372-2112.2019.12.020

电子学报 ›› 2019, Vol. 47 ›› Issue (12): 2596-2601.DOI: 10.3969/j.issn.0372-2112.2019.12.020

基于加权流关系的流程相似性算法

段瑞, 方欢, 詹悦

安徽理工大学数学与大数据学院, 安徽淮南 232001

收稿日期:2018-12-09 修回日期:2019-02-25 出版日期:2019-12-25
- 通讯作者:
- 方欢
- 作者简介:
- 段瑞男,1993年3月出生于安徽省涡阳县.现为安徽理工大学数学与大数据学院硕士研究生.主要研究方向为业务流程过程挖掘,Petri网理论与应用.E-mail:85768312@qq.com;詹悦女,1994年3月出生于安徽省安庆市太湖县.现为安徽理工大学数学与大数据学院硕士研究生.主要研究方向为Petri网理论与应用.E-mail:2272350170@qq.com
- 基金资助:
- 国家自然科学基金 (No.61472003，No.61402011，No.61572035）; 安徽省自然科学基金 (No.1608085QF149）; 安徽省高校优秀青年人才基金 (No.gxyqZD2018038）; 安徽省博士后基金 (No.2018B288）

Process Similarity Algorithm Based on Weighted Flow Relationship

DUAN Rui, FANG Huan, ZHAN Yue

Dept of Mathematics and Big Data, Anhui University of Science and Technology, Huainan, Anhui 232001, China

Received:2018-12-09 Revised:2019-02-25 Online:2019-12-25 Published:2019-12-25
- Corresponding author:
- FANG Huan
- Supported by:
- National Natural Science Foundation of China (No.61472003, No.61402011, No.61572035); Natural Science Foundation of Anhui Province (No.1608085QF149); Fund for Distinguished Young Talents in Higher Education of Anhui Province (No.gxyqZD2018038); Postdoctoral Foundation of Anhui Province (No.2018B288)

摘要/Abstract

摘要： 为了提高从企业模型库中检索模型的效率，提出一种基于加权流关系的相似性算法，记作WF.首先，本文设计加权流关系集的生成算法，生成算法通过广度优先搜索方法遍历除输出库所外的所有节点及流关系，为每个流关系唯一分配权重，生成加权流关系集；其次，WF算法基于加权流关系集计算出加权变迁集，并依据WF相似性定义计算相似性；最后，通过实验及算法的时间复杂度分析比较表明：算法是正确且唯一确定结果的，且WF算法具有良好的性能.

关键词: Petri网, 加权流关系, 加权变迁, 流程相似性

Abstract: In order to improve the efficiency of retrieving models from enterprise model library, a similarity algorithm based on weighted flow relationship is proposed, regarded as WF. Firstly, this paper designs a weighted flow relationship set generation algorithm. The generation algorithm traverses all nodes and flow relationships except the output place by breadth-first search method. The weight is assigned to each flow relationship to generate a weighted flow relationship set. Secondly, the WF algorithm calculates the weighted transition set based on the weighted flow relationship set, and calculates the similarity according to the WF similarity definition. Finally, through experimental and analyzing the time complexity of the algorithm results show that the proposed algorithm is correct and unique to determine the result and the algorithm has good performance.

Key words: Petri nets, weighted flow relationship, weighted transition, process similarity

中图分类号:

TP301

段瑞, 方欢, 詹悦. 基于加权流关系的流程相似性算法[J]. 电子学报, 2019, 47(12): 2596-2601.

DUAN Rui, FANG Huan, ZHAN Yue . Process Similarity Algorithm Based on Weighted Flow Relationship[J]. Acta Electronica Sinica, 2019, 47(12): 2596-2601.

参考文献

[1] Becker M,Laue R.A comparative survey of business process similarity measures[J].Computers in Industry,2012,63(2):148-167.
[2] Wang J,Jin T,Wong R K,et al.Querying business process model repositories[J].World Wide Web-internet & Web Information Systems,2014,17(3):427-454.
[3] 王子璇,闻立杰,汪抒浩,等.基于变迁标签图编辑距离的过程模型相似性度量[J].计算机集成制造系统,2016,22(2):343-352. WANG Zi-xuan,WEN Li-jie,WANG Shu-hao,et al.Similarity measurement for process models based on transition-labeled graph edit distance[J].Computer Integrated Manufacturing Systems,2016,22(2):343-352.(in Chinese)
[4] 董子禾,闻立杰,黄浩未,等.基于触发序列集合的过程模型行为相似性算法[J].软件学报,2015,26(3):449-459. DONG Zi-he,WEN Li-jie,HUANG Hao-wei,et al.Behavioral similarity algorithm for process models based on firing sequence collection[J].Journal of Software,2015,26(3):449-459.(in Chinese)
[5] WANG Jian-min,HE Teng-fei,WEN Li-jie.A behavioral similarity measure between labeled petri nets based on principal transition sequences[A].On the Move to Meaningful Internet Systems:OTM 2010[C].Berlin,Germany:Springer-Verlag,2010.394-401.
[6] Zha H,Wang J,Wen L,et al.A workflow net similarity measure based on transition adjacency relations[J].Computers in Industry,2010,61(5):463-471.
[7] 殷明,闻立杰,王建民,等.基于变迁紧邻关系重要性的流程相似性算法[J].计算机集成制造系统,2015,21(2):344-358. YIN Ming,WEN Li-jie,WANG Jian-min,et al.Process similarity algorithm based on importance of transition adjacent relations[J].Computer Integrated Manufacturing Systems,2015,26(3):449-459.(in Chinese)
[8] Weidlich M,Emendling J,Weske M.Efficient consistency measurement based on behavioral profiles of process models[J].IEEE Transactions on Software Engineering,2011,37(3):410-429.
[9] 汪抒浩,闻立杰,魏代森,等.基于任务最短跟随距离矩阵的流程模型行为相似性算法[J].计算机集成制造系统,2013,19(8):1822-1831. WANG Shu-hao,WEN Li-jie,WEI Dai-seng,et al.SSDT matrix-based behavioral similarity algorithm for process models[J].Computer Integrated Manufacturing Systems,2013,19(8):1822-1831.(in Chinese)
[10] Montani S,Leonardi G,Quaglini S,et al.A knowledge-intensive approach to process similarity calculation[J].Expert Systems with Applications,2015,42(9):4207-4215.

[1]	孟飞翔, 雷英杰, 雷阳, 申晓勇. 基于直觉模糊Petri网的混合推理方法[J]. 电子学报, 2017, 45(8): 1937-1946.
[2]	于汪洋, 黄昭, 方贤文. 电子商务业务流程网的可达分析方法[J]. 电子学报, 2017, 45(7): 1731-1739.
[3]	方贤文, 陶小燕, 刘祥伟. 基于微分Petri网的业务流程模块适配方法[J]. 电子学报, 2017, 45(4): 777-781.
[4]	潘理, 郑红, 刘显明, 杨勃. 基于Petri网局部性的极大冲突集枚举算法[J]. 电子学报, 2016, 44(8): 1858-1863.
[5]	杜玉越, 朱鸿儒, 王路, 刘伟. 一种基于逻辑Petri网的过程挖掘方法[J]. 电子学报, 2016, 44(11): 2742-2751.
[6]	孟飞翔, 雷英杰, 余晓东, 雷阳. 基于直觉模糊Petri网的知识表示和推理[J]. 电子学报, 2016, 44(1): 77-86.
[7]	潘理, 郑红, 郭观七, 刘显明. 基于蚁群优化的时间Petri网及其在柔性制造系统调度优化中的应用[J]. 电子学报, 2014, 42(8): 1531-1537.
[8]	杜玉越, 薛洁, 李彦成. 基于服务簇的服务组合替换与分析[J]. 电子学报, 2014, 42(11): 2231-2238.
[9]	王小艺, 唐丽娜, 刘载文, 许继平. 藻类水华形成机理的模糊Petri网优化建模研究[J]. 电子学报, 2013, 41(1): 68-71.
[10]	梅晓勇, 李师贤, 黄昌勤, 郑小林. 一种支持组合事务的执行语义分析方法[J]. 电子学报, 2012, 40(7): 1386-1396.
[11]	刘衍珩;张婧;王健. TrANTHOCNET:信任性蚁群自组织路由算法[J]. 电子学报, 2012, 40(2): 319-326.
[12]	曹政才;赵会丹;王永吉. 基于模糊Petri网推理的半导体生产线投料控制策略[J]. 电子学报, 2011, 39(7): 1545-1550.
[13]	朱俊;郭长国;吴泉源. 基于CPN的服务交互行为关键属性的运行时确保机制[J]. 电子学报, 2011, 39(5): 1064-1071.
[14]	李信鹏;赵文;刘殿兴;袁崇义;张世琨;王立福. 基于RFID发现服务的一种供应链建模技术[J]. 电子学报, 2010, 38(2A): 107-116.
[15]	曹政才;余红霞;乔非 . 基于Petri网与遗传算法的半导体生产线建模与优化调度[J]. 电子学报, 2010, 38(2): 340-344.

基于加权流关系的流程相似性算法

Process Similarity Algorithm Based on Weighted Flow Relationship

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics