基于行为轮廓和逻辑Petri网的模型修复方法

doi:10.11772/j.issn.1001-9081.2022070980

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (8): 2527-2536.DOI: 10.11772/j.issn.1001-9081.2022070980

• 计算机软件技术 • 上一篇

基于行为轮廓和逻辑Petri网的模型修复方法

张昊宇¹, 王丽丽¹^,²()

^1.安徽理工大学数学与大数据学院, 安徽淮南 232001
^2.安徽省煤矿安全大数据分析与预警技术工程实验室(安徽理工大学), 安徽淮南 232001

收稿日期:2022-07-07 修回日期:2022-12-12 接受日期:2022-12-13 发布日期:2023-01-15 出版日期:2023-08-10
通讯作者: 王丽丽
作者简介:张昊宇（1998—），男，安徽合肥人，硕士研究生，主要研究方向：Petri网、模型修复；
基金资助:
国家自然科学基金资助项目(61572035);安徽省高校优秀人才支持计划项目(gxyqZD2020020);安徽省重点研究与开发计划项目(2022a05020005)

Model repair method based on behavioral profile and logical Petri nets

Haoyu ZHANG¹, Lili WANG¹^,²()

^1.School of Mathematics and Big Data，Anhui University of Science and Technology，Huainan Anhui 232001，China
^2.Anhui Province Engineering Laboratory for Big Data Analysis and Early Warning Technology of Coal Mine Safety （Anhui University of Science and Technology），Huainan Anhui 232001，China

Received:2022-07-07 Revised:2022-12-12 Accepted:2022-12-13 Online:2023-01-15 Published:2023-08-10
Contact: Lili WANG
About author:ZHANG Haoyu， born in 1998， M. S. candidate. His research interests include Petri nets， model repair.
Supported by:
National Natural Science Foundation of China(61572035);Anhui Province University Excellent Talents Support Program(gxyqZD2020020);Anhui Provincial Key Research and Development Program(2022a05020005)

摘要/Abstract

摘要：

现实中的业务流程不断发生变化，需要对初始的业务流程模型进行修复以更好地表示实际业务流程。模型修复的关键步骤是分析现实日志和模型间的偏差，目前寻找偏差的方法主要采用对齐重演技术，未从行为的角度定量分析抽象的结构。因此，提出了一种通过行为轮廓分析日志和模型偏差的方法，并在此基础上进一步给出了基于逻辑Petri网的模型修复方法。首先，基于行为轮廓计算日志和模型间的服从度以识别偏差迹；然后，在偏差迹中依据偏差三元组集从偏差活动中选择逻辑变迁；最后，基于逻辑变迁设置逻辑函数，并通过添加新的分支或重构新的结构来修复原模型。对修复模型的适应度和精确度进行了验证，仿真实验结果表明，在尽可能保持修复模型与原始模型相似的基础上，相较于Fahland方法与Goldratt方法，所提修复方法在适应度都为1的情况下，得到的修复模型具有更高的精确度。

关键词: 行为轮廓, 业务流程, 逻辑Petri网, 过程挖掘, 模型修复

Abstract:

In the circumstance of the real business process changing constantly， the original business process model needs to be repaired to better represent the real business process. The key step of model repair is to analyze the deviation between the real log and the model. However， the current methods to find the deviation mainly use the alignment repetition technique， and do not quantitatively analyze the abstract structure from the perspective of behavior. Therefore， a method of analyzing deviation between log and model by behavioral profile was proposed， and based on the above， a model repair method was further proposed on the basis of logical Petri nets. Firstly， based on the behavioral profile， the compliance between the log and the model was calculated to identify the deviation trace. Secondly， the logic transitions were selected from deviant activities through the deviant triple set in the deviation trace. Finally， the logic function was set based on the logic transitions， and the original model was repaired by adding new branches or reconstructing new structures. The fitness and precision of the repair models were verified. Simulation results show that when the all finesses are 1， the repair model obtained by the proposed repair method has higher precision compared with Fahland method and Goldratt method， on the basis of maintaining the similarity between the repair model and original model as much as possible.

Key words: behavioral profile, business process, logical Petri net, process mining, model repair

中图分类号:

TP301.1

张昊宇, 王丽丽. 基于行为轮廓和逻辑Petri网的模型修复方法[J]. 计算机应用, 2023, 43(8): 2527-2536.

Haoyu ZHANG, Lili WANG. Model repair method based on behavioral profile and logical Petri nets[J]. Journal of Computer Applications, 2023, 43(8): 2527-2536.

图/表 25

图1 Petri网模型PM

Fig.1 Petri net model PM

表1 实际事件日志

Tab. 1 Real event log

迹	活动	迹	活动
$σ 1$	$a, b, c, d, e, j, k, l, o$	$σ 6$	$a, b, c, d, e, j, m, l, n, o$
$σ 2$	$a, b, d, c, e, j, m, n, o$	$σ 7$	$a, f, h, i, j, k, l, o$
$σ 3$	$a, f, g, h, i, j, k, l, o$	$σ 8$	$a, g, i, j, k, l, o$
$σ 4$	$a, f, c, d, i, j, k, l, o$	$σ 9$	$a, g, f, h, i, j, k, l, o$
$σ 5$	$a, b, c, d, e, j, k, n, l, o$

表1 实际事件日志

Tab. 1 Real event log

迹	活动	迹	活动
$σ 1$	$a, b, c, d, e, j, k, l, o$	$σ 6$	$a, b, c, d, e, j, m, l, n, o$
$σ 2$	$a, b, d, c, e, j, m, n, o$	$σ 7$	$a, f, h, i, j, k, l, o$
$σ 3$	$a, f, g, h, i, j, k, l, o$	$σ 8$	$a, g, i, j, k, l, o$
$σ 4$	$a, f, c, d, i, j, k, l, o$	$σ 9$	$a, g, f, h, i, j, k, l, o$
$σ 5$	$a, b, c, d, e, j, k, n, l, o$

图2 Goldratt方法修复后模型PM'

Fig.2 Repair model PM' by Goldratt method

图3 Goldratt方法修复模型的适应度与精确度

Fig. 3 Fitness and precision of Goldratt method for repairing model

图4 逻辑Petri网示例图

Fig. 4 Example diagram of logical Petri net

图5 BPMN模型

Fig.5 BPMN model

图6 Petri网模型M1

Fig.6 Petri net model M1

表2 Log1的服从度结果

Tab. 2 Compliance results of Log1

迹	CBC	MBC
$σ 1 = a, b, c, d, e, j$	1.00	1.00
$σ 3 = a, f, g, h, i, j$	1.00	1.00
$σ 4 = a, f, c, d, i, j$	0.76	0.78

表2 Log1的服从度结果

Tab. 2 Compliance results of Log1

迹	CBC	MBC
$σ 1 = a, b, c, d, e, j$	1.00	1.00
$σ 3 = a, f, g, h, i, j$	1.00	1.00
$σ 4 = a, f, c, d, i, j$	0.76	0.78

图7 M1的修复模型

Fig.7 Repair model of M1

图8 Petri网模型M2

Fig.8 Petri net model M2

表3 Log2的服从度结果

Tab. 3 Compliance results of Log2

迹	CBC	MBC	迹	CBC	MBC
$σ 1 = j, k, l, o$	1.00	1.00	$σ 5 = j, k, n, l, o$	0.83	0.84
$σ 2 = j, m, n, o$	1.00	1.00	$σ 6 = j, m, l, n, o$	0.83	0.84

表3 Log2的服从度结果

Tab. 3 Compliance results of Log2

迹	CBC	MBC	迹	CBC	MBC
$σ 1 = j, k, l, o$	1.00	1.00	$σ 5 = j, k, n, l, o$	0.83	0.84
$σ 2 = j, m, n, o$	1.00	1.00	$σ 6 = j, m, l, n, o$	0.83	0.84

表4 σ5和σ6的不合规反馈

Tab. 4 σ5 and σ6 non-conformance feedback

迹

服从度违反三元组

$σ 5 =$

$j, k, n, l, o$

（j，m， $»$ ），（n，m， $»$ ），（l，n，+），（n，l，+），（k，n，+），

（n，k，+）

$σ 6 =$

$j, m, l, n, o$

（j，k， $»$ ），（l，k， $»$ ），（m，l，+），（l，m，+），（l，n，+），

（n，l，+）

表4 σ5和σ6的不合规反馈

Tab. 4 σ5 and σ6 non-conformance feedback

迹

服从度违反三元组

$σ 5 =$

$j, k, n, l, o$

（j，m， $»$ ），（n，m， $»$ ），（l，n，+），（n，l，+），（k，n，+），

（n，k，+）

$σ 6 =$

$j, m, l, n, o$

（j，k， $»$ ），（l，k， $»$ ），（m，l，+），（l，m，+），（l，n，+），

（n，l，+）

图9 M2的修复模型

Fig.9 Repair model of M2

图10 Petri网模型M3

Fig.10 Petri net model M3

表5 Log3的服从度结果

Tab. 5 Compliance results of Log3

迹	CBC	MBC
$σ 3$ = $a, f, g, h, i$	1.00	1.00
$σ 7$ = $a, f, h, i$	1.00	1.00
$σ 8$ = $a, g, i$	1.00	1.00
$σ 9$ = $a, g, f, h, i$	0.84	0.84

表5 Log3的服从度结果

Tab. 5 Compliance results of Log3

迹	CBC	MBC
$σ 3$ = $a, f, g, h, i$	1.00	1.00
$σ 7$ = $a, f, h, i$	1.00	1.00
$σ 8$ = $a, g, i$	1.00	1.00
$σ 9$ = $a, g, f, h, i$	0.84	0.84

表6 Log3中部分不合规迹的MCC结果

Tab. 6 MCC results of some non-conformance traces inLog3

迹	MCC
$σ 7$ = $a, f, h, i$	0.80
$σ 8$ = $a, g, i$	0.80

表6 Log3中部分不合规迹的MCC结果

Tab. 6 MCC results of some non-conformance traces inLog3

迹	MCC
$σ 7$ = $a, f, h, i$	0.80
$σ 8$ = $a, g, i$	0.80

表7 Log3中σ7~σ9的不合规反馈

Tab. 7 Non-conformance feedback of σ7 - σ9 in Log3

迹	服从度违反三元组
$σ 7 = a, f, h, i$	（a，g， $»$ ），（f，g，→），（h，g，→ ^-¹），（i，g， $»$ ）
$σ 8 = a, g, i$	（a，f， $»$ ），（g，h，→），（g，f，→ ^-¹），（i，h，→ ^-¹）
$σ 9 = a, g, f, h, i$	（a，f，→），（f，g，→），（f，a，→ ^-¹），（g，f，→ ^-¹）

表7 Log3中σ7~σ9的不合规反馈

Tab. 7 Non-conformance feedback of σ7 - σ9 in Log3

迹	服从度违反三元组
$σ 7 = a, f, h, i$	（a，g， $»$ ），（f，g，→），（h，g，→ ^-¹），（i，g， $»$ ）
$σ 8 = a, g, i$	（a，f， $»$ ），（g，h，→），（g，f，→ ^-¹），（i，h，→ ^-¹）
$σ 9 = a, g, f, h, i$	（a，f，→），（f，g，→），（f，a，→ ^-¹），（g，f，→ ^-¹）

图11 M3的修复模型

Fig.11 Repair model of M3

图12 本文方法PM的修复模型

Fig.12 Repair model of PM by the proposed method

图13 修复模型的适应度与精度比较结果

Fig.13 Comparison results of fitness and precision of repair models

图14 Petri网模型M4

Fig.14 Petri net model M4

图15 M4的修复模型

Fig.15 Repair model of M4

图16 使用Fahland方法修复M4后的模型

Fig.16 Model after repairing M4 using Fahland method

图17 使用Goldratt方法修复M4后的模型

Fig.17 Model after repairing M4 using Goldratt method

图18 本文方法与两种修复方法的适应度和精确度比较

Fig.18 Comparison of fitness and precision between the proposed method and two repair methods

参考文献 29

1	FAHLAND D， W M P van der AALST. Model repair — aligning process models to reality［J］. Information Systems， 2015， 47： 220-243. 10.1016/j.is.2013.12.007
2	BUIJS J C A M， B F van DONGEN， W M P van der AALST. On the role of fitness， precision， generalization and simplicity in process discovery［C］// Proceedings of the 2012 OTM Confederated International Conferences "On the Move to Meaningful Internet Systems"， LNCS 7565. Berlin： Springer， 2012： 305-322.
3	PEGORARO M， UYSAL M S， W M P van der AALST. Conformance checking over uncertain event data［J］. Information Systems， 2021， 102： No.101810. 10.1016/j.is.2021.101810
4	ZHONG H， MEI H. Mining repair model for exception-related bug［J］. Journal of Systems and Software， 2018， 141： 16-31. 10.1016/j.jss.2018.03.046
5	W M P van der AALST. Process discovery from event data： relating models and logs through abstractions［J］. WIREs Data Mining and Knowledge Discovery， 2018， 8（3）： No.e1244. 10.1002/widm.1244
6	van DONGEN B， CARMONA J， CHATAIN T， et al. Aligning modeled and observed behavior： a compromise between computation complexity and quality［C］// Proceedings of the 2017 International Conference on Advanced Information Systems Engineering， LNCS 10253. Cham： Springer， 2017： 94-109.
7	W van der AALST， ADRIANSYAH A， van DONGEN B. Replaying history on process models for conformance checking and performance analysis［J］. WIREs Data Mining and Knowledge Discovery， 2012， 2（2）： 182-192. 10.1002/widm.1045
8	ROZINAT A， W M P van der AALST. Conformance checking of processes based on monitoring real behavior［J］. Information Systems， 2008， 33（1）： 64-95. 10.1016/j.is.2007.07.001
9	BLOEMEN V， van ZELST S， W van der AALST， et al. Aligning observed and modelled behaviour by maximizing synchronous moves and using milestones［J］. Information Systems， 2022， 103： No.101456. 10.1016/j.is.2019.101456
10	S J van ZELST， BOLT A， HASSANI M， et al. Online conformance checking： relating event streams to process models using prefix-alignments［J］. International Journal of Data Science and Analytics， 2019， 8（3）： 269-284. 10.1007/s41060-017-0078-6
11	SCHUSTER D， S J van ZELST. Online process monitoring using incremental state-space expansion： an exact algorithm［C］// Proceedings of the 2020 International Conference on Business Process Management， LNCS 12168. Cham： Springer， 2020： 147-164. 10.1007/978-3-030-58666-9_9
12	SANI M F， S J van ZELST， W M P van der AALST. Conformance checking approximation using subset selection and edit distance［C］// Proceedings of the 2020 International Conference on Advanced Information Systems Engineering， LNCS 12127. Cham： Springer， 2020： 234-251.
13	van der AA H， LEOPOLD H， REIJERS H A. Efficient process conformance checking on the basis of uncertain event-to-activity mappings［J］. IEEE Transactions on Knowledge and Data Engineering， 2020， 32（5）： 927-940. 10.1109/tkde.2019.2897557
14	ZHANG X， DU Y Y， QI L， et al. An approach for repairing process models based on logic Petri nets［J］. IEEE Access， 2018， 6： 29926-29939. 10.1109/access.2018.2843137
15	XU Y H， DU Y Y， QI L， et al. A logic Petri net-based model repair approach by constructing choice bridges［J］. IEEE Access， 2019， 7： 18531-18545. 10.1109/access.2019.2896079
16	XU Y H， DU Y Y， LUAN W J， et al. Repairing process models with logical concurrent and casual relations via logical Petri nets［J］. IEEE Access， 2018， 6： 56340-56355. 10.1109/access.2018.2872640
17	BAI E J， SU N， LIANG Y， et al. Method for repairing process models with selection structures based on token replay［J］. Computing and Informatics， 2021， 40（2）： 446-468. 10.31577/cai_2021_2_446
18	REISSNER D， ARMAS-CERVANTES A， CONFORTI R， et al. Scalable alignment of process models and event logs： an approach based on automata and S-components［J］. Information Systems， 2020， 94： No.101561. 10.1016/j.is.2020.101561
19	KO J， COMUZZI M. Keeping our rivers clean： information-theoretic online anomaly detection for streaming business process events［J］. Information Systems， 2022， 104： No.101894. 10.1016/j.is.2021.101894
20	LEEMANS S J J， W M P van der AALST， BROCKHOFF T， et al. Stochastic process mining： earth movers’ stochastic conformance［J］. Information Systems， 2021， 102： No.101724. 10.1016/j.is.2021.101724
21	HE Z Y， DU Y Y， QI L， et al. A model repair approach based on Petri nets by constructing free-loop structures［J］. IEEE Access， 2019， 7： 24214-24230. 10.1109/access.2019.2899963
22	盛梦君. 基于行为轮廓的模块化流程模型修复方法［D］. 淮南：安徽理工大学， 2021：28-44. 10.3969/j.issn.1672-1098.2021.02.013
	SHENG M J. Modular process model repair method based on behavioral profile［D］. Huainan： Anhui University of Science and Technology， 2021：28-44. 10.3969/j.issn.1672-1098.2021.02.013
23	FAHLAND D， W M P van der AALST. Repairing process models to reflect reality［C］// Proceedings of the 2012 International Conference on Business Process Management， LNCS 7481. Berlin： Springer， 2012： 229-245.
24	POLYVYANYY A， W M P van der AALST， HOFSTEDE A H M T， et al. Impact-driven process model repair［J］. ACM Transactions on Software Engineering and Methodology， 2016， 25（4）： No.28. 10.1145/2980764
25	DIEDRICH F， JANSEN K. Improved approximation algorithms for scheduling with fixed jobs［C］// Proceedings of the 2009 20th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia， PA： SIAM， 2009： 675-684. 10.1137/1.9781611973068.74
26	W M P van der AALST. Making work flow： on the application of petri nets to business process management［C］// Proceedings of the 2002 International Conference on Application and Theory of Petri Nets， LNCS 2360. Berlin： Springer， 2002： 1-22.
27	WEIDLICH M， POLYVYANYY A， DESAI N， et al. Process compliance analysis based on behavioural profiles［J］. Information Systems， 2011， 36（7）： 1009-1025. 10.1016/j.is.2011.04.002
28	WANG Z， LUAN W J， DU Y Y， et al. Composition and application of extended colored logic Petri nets to E-commerce systems［J］. IEEE Access， 2020， 8： 36386-36397. 10.1109/access.2020.2974883
29	吴哲辉. Petri网导论［M］. 北京：机械工业出版社， 2006： 1-26.
	WU Z H. Introduction to Petri Nets［M］. Beijing： China Machine Press， 2006： 1-26.

[1]	叶盛, 王菁, 辛建峰, 王桂玲, 郭陈虹. 云边环境下微服务组合系统的动态演化方法[J]. 《计算机应用》唯一官方网站, 2023, 43(6): 1696-1704.
[2]	白二净, 李晓岩, 杜玉越. 基于托肯重演的并行结构过程模型修复方法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 499-506.
[3]	李多芹, 方贤文. 基于行为轮廓定义目标规则的流程建模推荐方法[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 223-229.
[4]	孙慧明, 杜玉越. 针对多并发三角形二度循环结构的过程模型挖掘方法[J]. 计算机应用, 2019, 39(3): 851-857.
[5]	罗浩宇陈旺虎. 基于社会网络特征的云服务副本放置策略[J]. 计算机应用, 2013, 33(08): 2143-2146.
[6]	曹帅王淑营刘述雅. 面向产业链协同SaaS平台的业务流程定制技术[J]. 计算机应用, 2013, 33(05): 1450-1455.
[7]	邓式阳杜玉越. 基于逻辑Petri网的Web服务簇模型[J]. 计算机应用, 2012, 32(08): 2328-2337.
[8]	杨书新李淑芝张永进. 基于BPEL的流程数据竞争问题研究[J]. 计算机应用, 2010, 30(07): 1959-1961.
[9]	叶玉全卜英勇罗柏文黄剑飞. 基于Petri网的采购业务流程建模及仿真优化[J]. 计算机应用, 2009, 29(10): 2871-2874.
[10]	铁菊红彭辉阿都建华. 基于并行组合模拟退火算法的过程挖掘[J]. 计算机应用, 2009, 29(05): 1389-1392.
[11]	李淑芝杨书新王继升. 基于树型二重结构编码遗传算法的服务选择[J]. 计算机应用, 2008, 28(12): 3017-3020.
[12]	黄红梅章云. 基于同步管理器的过程挖掘算法[J]. 计算机应用, 2008, 28(12): 3235-3239.
[13]	黄红梅章云. 一种发现非确定选择平行关系的过程挖掘算法[J]. 计算机应用, 2008, 28(11): 2922-2925.
[14]	方江雄何红波李义兵. 基于SOA和BPM的ERP系统的研究与实现[J]. 计算机应用, 2007, 27(5): 1264-1267.
[15]	曾贵荣葛世伦. 基于BPEL4WS的Web服务整合研究[J]. 计算机应用, 2007, 27(11): 2733-2735.

基于行为轮廓和逻辑Petri网的模型修复方法

Model repair method based on behavioral profile and logical Petri nets

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 25

参考文献 29

相关文章 15

编辑推荐

Metrics