基于过程结构树的流程间差别检测算法

doi:10.3969/j.issn.0372-2112.2018.04.014

电子学报 ›› 2018, Vol. 46 ›› Issue (4): 862-870.DOI: 10.3969/j.issn.0372-2112.2018.04.014

基于过程结构树的流程间差别检测算法

曹斌, 安卫士, 王佳星, 范菁

浙江工业大学计算机科学与技术学院, 浙江杭州 310023

收稿日期:2016-10-16 修回日期:2017-04-27 出版日期:2018-04-25
- 作者简介:
- 曹斌男.1985年5月出生,山西孟县人,博士、讲师、CCF会员,主要研究领域为业务流程管理、大数据.E-mail:bincao@zjut.edu.cn;安卫士 男.1990年4月出生,河南郸城县人,硕士生、CCF学生会员,主要研究领域为业务流程管理;王佳星 女,1990年11月出生,浙江海宁人,博士生、CCF学生会员,主要研究领域为工作流
- 基金资助:
- 国家自然科学基金 (No.61602411，No.61572437）; 国家重点研发计划 (No.2016YFB1001403）; 浙江省重大科技专项重点工业项目 (No.2015C01029）; 杭州市重大科技创新项目 (No.20152011A03）

A Difference Detection Algorithm for Process Models Based on Process Structure Tree

CAO Bin, AN Wei-shi, WANG Jia-xing, FAN Jing

Department of Computer Science and Technology, Zhejiang University of Technology, Hangzhou, Zhejiang 310023, China

Received:2016-10-16 Revised:2017-04-27 Online:2018-04-25 Published:2018-04-25
- Supported by:
- National Natural Science Foundation of China (No.61602411, No.61572437); National Key Research and Development Program of China (No.2016YFB1001403); Key Science and Technology Project of Zhejiang Province (Key Industry Program) (No.2015C01029); Major Technological Innovation Project of Hangzhou (No.20152011A03)

摘要/Abstract

摘要： 流程模型差别检测是业务流程管理的关键技术之一.针对流程模型大多是由图结构建模，而流程图模型中有多种类型节点，因此经典的图编辑距离方法无法直接应用于流程差别检测的问题，提出了基于过程结构树的流程间差别检测算法.算法首先将流程模型转化为基于任务节点的过程结构树；然后采用分治思想快速获得流程间的最佳对等节点映射集合；最后基于节点映射集合生成一个近似最小代价编辑操作序列来表示两个流程的差别.实验结果表明，本文算法在准确率和效率两方面都能满足实际的应用需求.

关键词: 业务流程管理, 流程差别检测, 过程结构树, 编辑操作序列

Abstract:

Detecting difference between process models is one of the key technologies in business process management. The classical graph edit distance cannot directly be used to detect the difference between process models because there are many kinds of nodes in a process model. To solve this problem, we present an algorithm for detecting difference between process models based on process structure tree. Firstly, the process models are converted to their corresponding task based process structure trees (TPSTs). Then the divide and conquer strategy is used to obtain the optimal mapped node set between two TPSTs. Finally, an edit script with approximate minimum cost is generated based on the mapped nodes, which is considered as the difference between two process models. The experimental results show that this algorithm can meet the real requirements in terms of precision and efficiency.

Key words: business process management, process difference detection, process structure tree, edit script

中图分类号:

TP311

曹斌, 安卫士, 王佳星, 等. 基于过程结构树的流程间差别检测算法[J]. 电子学报, 2018, 46(4): 862-870.

CAO Bin, AN Wei-shi, WANG Jia-xing, et al. A Difference Detection Algorithm for Process Models Based on Process Structure Tree[J]. Acta Electronica Sinica, 2018, 46(4): 862-870.

参考文献

[1] WEBER B,RINDERLE S,REICHERT M.Change Patterns and Change Support Features in Process-Aware Information Systems[M].Berlin Heidelberg Germany:Springer,2007,574-588.
[2] LA ROSA M,DUMAS M,UBA R.Merging business process models[A].On the Move to Meaningful Internet Systems:Confederated International Conferences[C].Greece:DBLP,2010.96-113.
[3] POLYVYANYY A,VANHATALO J,VÖLZER H.Simplified computation and generalization of the refined process structure tree[J].International Workshop on Web Services and Formal Methods,2010,6551(3):25-41.
[4] VANHATALO J,VÖLZER H,LEYMANN F.Faster and more focused control-flow analysis for business process models through SESE decomposition[J].Lecture Notes in Computer Science,2007,4749:43-55.
[5] ZHANG K,STATMAN R,SHASHA D.On the editing distance between unordered labeled trees[J].Information Processing Letters,1992,42(3):133-139.
[6] KUHN H W.The Hungarian method for the assignment problem[J].Naval Research Logistics,2005,52(1):7-21.
[7] DIJKMAN R.Diagnosing differences between business process models[A].International Conference on Business Process Management[C].Germany:Springer-Verlag,2008.261-277.
[8] DIJKMAN R.A classification of differences between similar business processes[A].Enterprise Distributed Object Computing Conference[C].IEEE,2007.37.
[9] LIU K,YAN Z,WANG Y,et al.Efficient syntactic process difference detection using flexible feature matching[A].Asia Pacific Business Process Management Conferences[C].Germany:Springer,2014.103-116.
[10] YAN Z,WANG Y,WEN L,et al.Efficient behavioral difference detection between business process models[A].Otm Conferences[C].Germany Berlin Heidelberg:Springer,2014.220-236.
[11] Küster J M,GERTH C,FÖRSTER A,et al.Detecting and resolving process model differences in the absence of a change log[A].International Conference on Business Process Management[C].USA:ACM,2008.244-260.
[12] CAO J,YAO Y,WANG Y.Mining change operations for workflow platform as a service[J].World Wide Web,2015,18(4):1071-1092.

[1]	高慧敏, 王云鹤, 卞闯, 李向涛. 基于混合进化算法的特征选择方法研究[J]. 电子学报, 2023, (): 1-18.
[2]	范伟, 周魏, 文俊浩. 基于异构图的双通道交叉自适应对比学习推荐[J]. 电子学报, 2023, (): 1-10.
[3]	王桐, 李必信, 王东东. 一种基于MAAT两步匹配的架构多层次变更检测方法[J]. 电子学报, 2023, 51(3): 694-700.
[4]	薄莉莉, 朱程, 李斌, 孙小兵. 文件信息增强的方法级软件缺陷定位[J]. 电子学报, 2023, 51(3): 613-621.
[5]	曹阳, 高旻, 余俊良, 范琪琳, 荣文戈, 文俊浩. 基于双图混合随机游走的社会化推荐模型[J]. 电子学报, 2023, 51(2): 286-296.
[6]	张颖辉, 张艳梅, 张志成, 姜淑娟, 丁艳茹, 袁冠. 基于深度强化学习的类集成测试序列生成方法[J]. 电子学报, 2023, 51(2): 455-466.
[7]	钱忠胜, 成轶伟, 俞情媛, 张丁, 姚昌森, 秦朗悦. 基于关键边概率与路径层接近度的多路径覆盖测试[J]. 电子学报, 2023, (): 1-9.
[8]	龚雪鸾, 陈艳姣, 王涛, 曹雨欣. SeqGANPass：使用序列生成式对抗网络进行口令猜测[J]. 电子学报, 2023, (): 1-6.
[9]	张帅, 高旻, 文俊浩, 熊庆宇, 唐旭. 基于自监督学习的去流行度偏差推荐方法[J]. 电子学报, 2022, 50(10): 2361-2371.
[10]	李雪莹, 王田路, 梁鹏, 王翀. 基于系统模型的用户评论中非功能需求的自动分类[J]. 电子学报, 2022, 50(9): 2079-2089.
[11]	王飞扬, 冀鹏欣, 孙笠, 危倩, 李根, 张忠宝. 一种基于深度学习的动态社交网络用户对齐方法[J]. 电子学报, 2022, 50(8): 1925-1936.
[12]	李辉, 张建朋, 陈福才. 基于流式分析的大规模网络重叠社区发现算法[J]. 电子学报, 2022, 50(8): 1951-1958.
[13]	钱忠胜, 宋佳, 俞情媛, 成轶伟, 孙志旺. 利用函数影响力的相似程序间测试用例重用与生成[J]. 电子学报, 2022, 50(7): 1696-1707.
[14]	王飞扬, 冀鹏欣, 孙笠, 危倩, 李根, 张忠宝. 一种基于深度学习的动态社交网络用户对齐方法[J]. 电子学报, 0, (): 1-12.
[15]	刘杰, 游品鸿, 田明, 刘金凤. 基于局部投影的视差图像拼接平滑优化[J]. 电子学报, 2022, 50(6): 1451-1456.

基于过程结构树的流程间差别检测算法

A Difference Detection Algorithm for Process Models Based on Process Structure Tree

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics