基于托肯重演的并行结构过程模型修复方法

doi:10.11772/j.issn.1001-9081.2021122154

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (2): 499-506.DOI: 10.11772/j.issn.1001-9081.2021122154

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

基于托肯重演的并行结构过程模型修复方法

白二净¹, 李晓岩¹, 杜玉越²()

^1.青岛黄海学院大数据学院，山东青岛 266427
^2.山东科技大学计算机科学与工程学院，山东青岛 266590

收稿日期:2021-12-22 修回日期:2022-05-16 接受日期:2022-07-15 发布日期:2022-09-23 出版日期:2023-02-10
通讯作者: 杜玉越
作者简介:白二净（1981—），女，河北保定人，副教授，硕士，主要研究方向：过程挖掘、Petri网
李晓岩（1982—），女，山东平度人，副教授，硕士，主要研究方向：过程挖掘、Petri网；
基金资助:
国家自然科学基金资助项目(61973180)

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

Erjing BAI¹, Xiaoyan LI¹, Yuyue DU²()

^1.School of Data Science，Qingdao Huanghai University，Qingdao Shandong 266427，China
^2.College of Computer Science and Engineering，Shandong University of Science and Technology，Qingdao Shandong 266590，China

Received:2021-12-22 Revised:2022-05-16 Accepted:2022-07-15 Online:2022-09-23 Published:2023-02-10
Contact: Yuyue DU
About author:BAI Erjing， born in 1981， M. S.， associate professor. Her research interests include process mining， Petri nets.
LI Xiaoyan， born in 1982， M. S.， associate professor. Her research interests include process mining， Petri nets.
Supported by:
National Natural Science Foundation of China(61973180)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP311

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

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.

图/表 17

图1 逻辑Petri网模型

Fig.1 Logic Petri net model

图2 工作流网模型WFN1

Fig.2 Workflow net model WFN1

表1 重演σ1的托肯值变化表

Tab.1 Change table of token in σ1 replay

变迁	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

图3 WFN1的过程树PT1

Fig.3 Process tree PT1 of WFN1

图4 WFN1修复模型

Fig.4 Repaired model of WFN1

图5 工作流网模型WFN2

Fig.5 Workflow net model WFN2

图6 工作流网模型WFN?

Fig.6 Workflow net model WFN?

图7 WFN2修复模型

Fig.7 Repaired model of WFN2

图8 胃肠道疾病患者治疗过程模型

Fig.8 Process model of treatment of patients with gastrointestinal diseases

表2 符号与行为的对应关系

Tab. 2 Corresponding relationship between symbols and activities

符号	行为	符号	行为
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	治疗效果评估

图9 Fahland方法修复后的模型

Fig.9 Model repaired by Fahland’s method

图10 Goldratt方法修复后的模型

Fig.10 Model repaired by Goldratt method

图11 本文方法修复后的模型

Fig.11 Model repaired by the proposed method

表3 事件日志

Tab. 3 Event logs

日志	迹数	事件数	活动数	迹长度
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

表4 三种方法的简洁度对比

Tab. 4 Comparison of simplicity among three methods

方法	库所	不可见变迁	自环	弧数
本文方法	8	0	0	12
Fahland方法	11	12	7	46
Goldratt方法	0	1	7	16

图12 三种方法的拟合度对比

Fig.12 Fitting degree comparison among three methods

图13 三种方法的精度对比

Fig.13 Precision comparison among three methods

参考文献 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

[1]	孙慧明, 杜玉越. 针对多并发三角形二度循环结构的过程模型挖掘方法[J]. 计算机应用, 2019, 39(3): 851-857.
[2]	唐朝胜, 刘世洪, 程杰仁. 状态和数据双因素驱动的决策支持系统模型复合方法[J]. 计算机应用, 2017, 37(2): 581-586.
[3]	秦志光宋旭耿技陈伟. 基于马尔可夫的Web应用生存性模型[J]. 计算机应用, 2013, 33(02): 400-403.
[4]	李明刘士仪年福忠. 基于时序描述逻辑的Web服务本体语言过程模型语义[J]. 计算机应用, 2013, 33(01): 266-269.
[5]	邓式阳杜玉越. 基于逻辑Petri网的Web服务簇模型[J]. 计算机应用, 2012, 32(08): 2328-2337.
[6]	许杰麻军平何虎. 基于VLIW DSP 加密与认证算法的实现[J]. 计算机应用, 2012, 32(06): 1650-1653.
[7]	田宝华李宝峰. 二维离散小波提升变换算法的并行结构设计[J]. 计算机应用, 2011, 31(12): 3366-3369.
[8]	惠斌武陈明锐杨登攀. Web应用系统性能测试研究与应用[J]. 计算机应用, 2011, 31(07): 1769-1772.
[9]	韩炫雷航. 考虑环境因素的软件可靠性增长模型[J]. 计算机应用, 2011, 31(07): 1759-1761.
[10]	杨建书吴尽昭周瑾. 基于CSP的OWL-S语义分析与建模[J]. 计算机应用, 2010, 30(8): 2173-2176.
[11]	刘斌杜栓柱黎巎. 一种适合于电子政务中业务处理的过程模型[J]. 计算机应用, 2007, 27(8): 2072-2076.
[12]	王冬平王清贤罗军勇李炳龙. BMP图像碎片重组中的候选权重方法[J]. 计算机应用, 2007, (12): 3062-3065.
[13]	范敏，黄席樾，石为人. 基于Web挖掘的过程模型及算法[J]. 计算机应用, 2005, 25(03): 646-648.

基于托肯重演的并行结构过程模型修复方法

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 17

参考文献 22

相关文章 13

编辑推荐

Metrics