Model repair method based on behavioral profile and logical Petri nets

doi:10.11772/j.issn.1001-9081.2022070980

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (8): 2527-2536.DOI: 10.11772/j.issn.1001-9081.2022070980

• Computer software technology • Previous Articles Next Articles

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)

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

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

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

通讯作者: 王丽丽
作者简介:张昊宇（1998—），男，安徽合肥人，硕士研究生，主要研究方向：Petri网、模型修复；
基金资助:
国家自然科学基金资助项目(61572035);安徽省高校优秀人才支持计划项目(gxyqZD2020020);安徽省重点研究与开发计划项目(2022a05020005)

Abstract

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

摘要：

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

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

CLC Number:

TP301.1

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.

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

Figures/Tables 25

Fig.1 Petri net model PM

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$

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$

Fig.2 Repair model PM' by Goldratt method

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

Fig. 4 Example diagram of logical Petri net

Fig.5 BPMN model

Fig.6 Petri net model M1

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

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

Fig.7 Repair model of M1

Fig.8 Petri net model M2

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

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

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，+）

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，+）

Fig.9 Repair model of M2

Fig.10 Petri net model M3

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

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

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

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

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

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

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，→ ^-¹）

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，→ ^-¹）

Fig.11 Repair model of M3

Fig.12 Repair model of PM by the proposed method

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

Fig.14 Petri net model M4

Fig.15 Repair model of M4

Fig.16 Model after repairing M4 using Fahland method

Fig.17 Model after repairing M4 using Goldratt method

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

References 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]	Hua HUANG, Ziyi YANG, Xiaolong LI, Chuang LI. Predictive business process monitoring method based on concept drift [J]. Journal of Computer Applications, 2024, 44(10): 3167-3176.
[2]	Sheng YE, Jing WANG, Jianfeng XIN, Guiling WANG, Chenhong GUO. Dynamic evolution method for microservice composition systems in cloud-edge environment [J]. Journal of Computer Applications, 2023, 43(6): 1696-1704.
[3]	Erjing BAI, Xiaoyan LI, Yuyue DU. Repair method for process models with concurrent structures based on token replay [J]. Journal of Computer Applications, 2023, 43(2): 499-506.
[4]	Duoqin LI, Xianwen FANG. Process modeling recommendation method based on behavioral profile definition target rules [J]. Journal of Computer Applications, 2022, 42(1): 223-229.
[5]	SUN Huiming, DU Yuyue. Process model mining method for multi-concurrent 2-loops of triangles [J]. Journal of Computer Applications, 2019, 39(3): 851-857.
[6]	XU Tao, MENG Ye. Importance sorting method of organizational enities based on trace clustering [J]. Journal of Computer Applications, 2016, 36(5): 1284-1289.
[7]	SHI Mei-hong CAO Kai-duan CHEN Liang WANG Quan-feng. Method of process pattern mining based on probability statistics of adjacent event [J]. Journal of Computer Applications, 2011, 31(05): 1378-1381.
[8]	qian deFu. Study of VO process based on migrating workflow system in VBE [J]. Journal of Computer Applications, 2010, 30(2): 394-397.
[9]	. Study of data race for process based on BPEL [J]. Journal of Computer Applications, 2010, 30(07): 1959-1961.
[10]	. Modeling and simulation optimization of purchasing process based on Petri net [J]. Journal of Computer Applications, 2009, 29(10): 2871-2874.
[11]	. Process mining based on parallel recombination simulated annealing algorithm [J]. Journal of Computer Applications, 2009, 29(05): 1389-1392.
[12]	. Web service selection based on genetic algorithm with tree dual-structure code [J]. Journal of Computer Applications, 2008, 28(12): 3017-3020.
[13]	Hong-Mei Huang Yun ZHANG. Process mining algorithm based on synchronized-manager [J]. Journal of Computer Applications, 2008, 28(12): 3235-3239.
[14]	Hong-mei HUANG Yun ZHANG. Process mining algorithm to discover non-certain choice and parallel relation [J]. Journal of Computer Applications, 2008, 28(11): 2922-2925.
[15]	Guo-feng ZHANG Jun HE Cong-fu XU. BPEL based method for general security control module design [J]. Journal of Computer Applications, 2008, 28(11): 2926-2928.

Model repair method based on behavioral profile and logical Petri nets

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 25

References 29

Related Articles 15

Recommended Articles

Metrics