Repair method for process models with concurrent structures based on token replay

doi:10.11772/j.issn.1001-9081.2021122154

Abstract

Abstract:

Process mining can build process model according to event logs generated by enterprise information management system. There always exist some deviations between the process model and event logs when the actual business process changes. At this time， the process model needs to be repaired. For the process model with concurrent structures， the precision of some existing repairing methods will be reduced because of the addition of self-loops and invisible transitions. Therefore， a method for repairing process models with concurrent structures was proposed on the basis of logic Petri net and token replay. Firstly， according to the relationship between the input-output places of the sub-model and event logs， the insertion position of the sub-model was determined. Then， the deviation positions were determined by a token replay method. Finally， a method was designed to repair the process models based on logical Petri net. The correctness and effectiveness of this method were verified by carrying out simulations on ProM platform， and the proposed method was compared with Fahland’s and other methods. The results show that the precision of this method is about 85%， which is increased by 17 and 11 percentage points respectively compared with those of Fahland’s and Goldratt methods， In the terms of simplicity， the proposed method does not add any self-loop or invisible transition， while Fahland’s and Goldratt methods add some self-loops and invisible transitions. All of the fitting degrees of the three methods are above 0.9， and the fitting degree of Goldratt method is slightly lower. The above verifies that the model repaired by the proposed method has higher fitness and precision.

Key words: process model, concurrent structure, model repair, logic Petri net, token replay

摘要：

过程挖掘可以根据企业信息系统生成的事件日志建立业务过程模型。当实际业务过程发生变化时，过程模型与事件日志之间会产生偏差，这时需要对过程模型进行修正。对于含有并行结构的过程模型修复，由于加入自环和不可见变迁等因素，有些现有的修正方法的精度会降低。因此提出一种基于逻辑Petri网和托肯重演的并行结构过程模型修复方法。首先根据子模型的输入输出库所与日志的关系，确定子模型的插入位置；然后通过托肯重演的方式确定偏差所在位置；最后根据基于逻辑Petri网提出的方法进行过程模型的修复。在ProM平台上进行了仿真实验，验证了该方法的正确性和有效性，并与Fahland等方法进行对比分析。结果表明，所提方法的精度达到85%左右，相比Fahland、Goldratt方法分别提高了17和11个百分点；在简洁度方面该算法没有增加自环和不可见变迁，而Fahland和Goldratt方法均增加了不可见变迁和自环；三种方法的拟合度均在0.9以上，而Goldratt方法略低一些。以上证明用所提方法修正后的模型具有更高的拟合度和精度。

关键词: 过程模型, 并行结构, 模型修复, 逻辑Petri网, 托肯重演

CLC Number:

TP311

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.

白二净, 李晓岩, 杜玉越. 基于托肯重演的并行结构过程模型修复方法[J]. 《计算机应用》唯一官方网站, 2023, 43(2): 499-506.

Figures/Tables 17

References 22

1	W M P VAN DER AALST， STAHL C. Modeling Business Process： a Petri Net Oriented Approach［M］. Cambridge： MIT Press， 2011：13-75. 10.7551/mitpress/8811.001.0001
2	CONFORTI R， DUMAS M， GARCÍA-BAÑUELOS L， et al. BPMN Miner： automated discovery of BPMN process models with hierarchical structure［J］. Information Systems， 2016， 56：284-303. 10.1016/j.is.2015.07.004
3	刘聪，程龙，曾庆田，等. 基于Petri网的分层业务过程挖掘方法［J］. 计算机集成制造系统， 2020， 26（6）：1525-1537. 10.13196/j.cims.2020.06.009
	LIU C， CHENG L， ZENG Q T， et al. Petri net-based hierarchical business process mining［J］. Computer Integrated Manufacturing Systems， 2020， 26（6）：1525-1537. 10.13196/j.cims.2020.06.009
4	CAO B， YIN J W， DENG S G， et al. Graph-based workflow recommendation： on improving business process modeling［C］// Proceedings of the 21st ACM International Conference on Information and Knowledge Management. New York： ACM， 2012：1527-1531. 10.1145/2396761.2398466
5	W M P VAN DER AALST， WEIJTERS A， MARUSTER L. Workflow mining： discovering process models from event logs［J］. IEEE Transactions on Knowledge and Data Engineering， 2004， 16（9）：1128-1142. 10.1109/tkde.2004.47
6	WEN L J， W M P VAN DER AALST， WANG J M， et al. Mining process models with non-free-choice constructs［J］. Data Mining and Knowledge Discovery， 2007， 15（2）：145-180. 10.1007/s10618-007-0065-y
7	WEN L J， WANG J M， W M P VAN DER AALST， et al. Mining process models with prime invisible tasks［J］. Data and Knowledge Engineering， 2010， 69（10）：999-1021. 10.1016/j.datak.2010.06.001
8	WEIJTERS A J M M， W M P VAN DER AALST. Rediscovering workflow models from event-based data using little thumb［J］. Integrated Computer Aided Engineering， 2003， 10（2）：151-162. 10.3233/ica-2003-10205
9	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
10	BERGENTHUM R， DESEL J， MAUSER S， et al. Synthesis of Petri nets from term based representations of infinite partial languages［J］. Fundamenta Informaticae， 2009， 95（1）：187-217. 10.3233/fi-2009-147
11	ADRIANSYAH A. Aligning observed and modeled behavior［D］. Eindhoven： Technische Universiteit Eindhoven， 2014：139-149.
12	ROZINAT A， W M P VAN DER AALST. Conformance checking of processes based on monitoring real behavior［J］. Information System， 2008， 33（1）：64-95. 10.1016/j.is.2007.07.001
13	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：446-468. 10.31577/cai_2021_2_446
14	王聘，刘伟，杜玉越. 基于逻辑数据Petri网的业务过程建模与分析［J］. 计算机集成制造系统， 2017， 23（5）：991-930. 10.13196/j.cims.2017.05.001
	WANG P， LIU W， DU Y Y. Business process modeling and analysis based on logical data Petri net［J］. Computer Integrated Manufacturing Systems， 2017， 23（5）： 991-930. 10.13196/j.cims.2017.05.001
15	ZHANG X Z， DU Y Y， QI L， et al. Repairing process models containing choice structures via logic Petri nets［J］. IEEE Access， 2018， 6：53796-53810. 10.1109/access.2018.2870727
16	POLYVYANYY A， W M P VAN DER AALST， HOFSTEDE A， et al. Impact driven process model repair［J］. ACM Transactions on Software Engineering and Methodology， 2017， 25（4）： No.28. 10.1145/2980764
17	王振，杜玉越，亓亮. 扩展颜色逻辑Petri网及其可达性分析［J］. 山东科技大学学报（自然科学版）， 2020， 39（3）：84-98. 10.16452/j.cnki.sdkjzk.2020.03.010
	WANG Z， DU Y Y， QI L. Extended colored logic Petri net and its reachability analysis［J］. Journal of Shandong University of Science and Technology （Natural Science）， 2020， 39（3）：84-98. 10.16452/j.cnki.sdkjzk.2020.03.010
18	WANG J M， SONG S X， LIN X M， et al. Cleaning structured event logs： a graph repair approach［C］// Proceedings of the IEEE 31st International Conference on Data Engineering. Piscataway： IEEE， 2015：30-41. 10.1109/icde.2015.7113270
19	祁宏达，杜玉越，刘伟. 一种基于可达标识的过程模型修复方法［J］.山东科技大学学报（自然科学版）， 2017， 36（1）：118-124. 10.3969/j.issn.1672-3767.2017.01.015
	QI H D， DU Y Y， LIU W. Process model repairing method based on reachable markings［J］. Journal of Shandong University of Science and Technology （Natural Science）， 2017，36（1）：118-124. 10.3969/j.issn.1672-3767.2017.01.015
20	杜玉越，孙亚男，刘伟. 基于Petri网的模型偏差域识别与模型修正［J］. 计算机研究与发展， 2016， 53（8）：1766-1780. 10.7544/issn1000-1239.2016.20160099
	DU Y Y， SUN Y N， LIU W. Petri nets based recognition of model deviation domains and model repair［J］. Journal of Computer Research and Development， 2016， 53（8）：1766-1780. 10.7544/issn1000-1239.2016.20160099
21	WITTEN I H， FRANK E. Data Mining： Practical Machine Learning Tools and Techniques［M］. 2nd ed. San Francisco： Morgan Kaufmann Publishers Inc.， 2005. 10.1186/1475-925x-5-51
22	W M P VAN DER AALST. Process Mining： Discovery， Conformance and Enhancement of Business Processes［M］. Berlin： Springer， 2011：1-10. 10.1007/978-3-642-19345-3

变迁	M（p₁）	M（p₂）	M（p₃）	M（p₄）	M（p₅）	M（p₆）	M（p₇）	M（p₈）	M（p₉）	M（p₁₀）
start	1	0	0	0	0	0	0	0	0	0
t₁	0	1	0	0	0	0	0	0	0	0
t₂	0	0	1	1	1	0	0	0	0	0
t₃	0	0	0	1	1	1	0	0	0	0
t₄	0	0	0	0	1	1	1	0	0	0
t₆	0	0	0	0	1	0	0	-1	1	0
t₇	0	0	0	0	1	0	0	-1	0	1
end	0	0	0	0	1	0	0	-1	0	0

变迁	M（p₁）	M（p₂）	M（p₃）	M（p₄）	M（p₅）	M（p₆）	M（p₇）	M（p₈）	M（p₉）	M（p₁₀）
start	1	0	0	0	0	0	0	0	0	0
t₁	0	1	0	0	0	0	0	0	0	0
t₂	0	0	1	1	1	0	0	0	0	0
t₃	0	0	0	1	1	1	0	0	0	0
t₄	0	0	0	0	1	1	1	0	0	0
t₆	0	0	0	0	1	0	0	-1	1	0
t₇	0	0	0	0	1	0	0	-1	0	1
end	0	0	0	0	1	0	0	-1	0	0

符号	行为	符号	行为
a	门诊挂号处	o	胃肠道护理门诊
b	登记注册	p	外科门诊
c	网上预约	q	心电图
e	获取预约号	r	实验室检查
f	叫号	s	咨询医生
g	问诊	t	入院
h	胃镜检查	u	手术
i	查看结果	v	出院
j	出院	y	胃肠道彩超
k	肠胃科	z	腹部超音波检查
l	X射线扫描	za	血常规
m	CT扫描	zb	生化检查
n	核磁共振	zc	治疗效果评估

符号	行为	符号	行为
a	门诊挂号处	o	胃肠道护理门诊
b	登记注册	p	外科门诊
c	网上预约	q	心电图
e	获取预约号	r	实验室检查
f	叫号	s	咨询医生
g	问诊	t	入院
h	胃镜检查	u	手术
i	查看结果	v	出院
j	出院	y	胃肠道彩超
k	肠胃科	z	腹部超音波检查
l	X射线扫描	za	血常规
m	CT扫描	zb	生化检查
n	核磁共振	zc	治疗效果评估

日志	迹数	事件数	活动数	迹长度
L₁	1 034	22 448	26	7~22
L₂	1 343	29 096	26	7~22
L₃	1 675	35 916	26	6~22
L₄	1 957	42 362	26	6~22
L₅	2 297	49 392	26	6~22
L₆	2 510	53 928	26	6~22