基于感知成本的流程模型与事件日志有效对齐

doi:10.11772/j.issn.1001-9081.2021081378

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (10): 3154-3161.DOI: 10.11772/j.issn.1001-9081.2021081378

基于感知成本的流程模型与事件日志有效对齐

李多芹¹, 方贤文¹, 王丽丽¹^,², 邵叱风³

^1.安徽理工大学数学与大数据学院, 安徽淮南 232001
^2.嵌入式系统与服务计算教育部重点实验室(同济大学), 上海 201804
^3.安徽科技学院信息与网络工程学院, 安徽蚌埠 233030

收稿日期:2021-08-02 修回日期:2021-11-15 接受日期:2021-11-25 发布日期:2022-01-07 出版日期:2022-10-10
通讯作者: 方贤文
作者简介:第一联系人：李多芹（1996—），女，安徽淮南人，硕士研究生，主要研究方向：Petri网、过程挖掘
方贤文（1975—），男，河南信阳人，教授，博士，CCF会员，主要研究方向：Petri网、可信软件、业务流程变化域分析； duoqin_li@126.com
王丽丽（1982—），女，安徽安庆人，副教授，博士研究生，主要研究方向：Petri 网、业务流程挖掘
邵叱风（1995—），男，安徽合肥人，硕士研究生，CCF会员，主要研究方向：Petri网、过程挖掘、模型修复、模型优化。
基金资助:
国家自然科学基金资助项目(61402011);安徽省自然科学基金资助项目(1508085MF111);安徽理工大学研究生创新基金资助项目(2019CX2068)

Effective alignment of process model with event logs based on perceived cost

Duoqin LI¹, Xianwen FANG¹, Lili WANG¹^,², Chifeng SHAO³

^1.School of Mathematics and Big Data，Anhui University of Science and Technology，Huainan Anhui 232001，China
^2.Key Laboratory of Embedded System and Service Computing，Ministry of Education （Tongji University），Shanghai 201804，China
^3.College of Information and Network Engineering，Anhui Science and Technology University，Bengbu Anhui 233030，China

Received:2021-08-02 Revised:2021-11-15 Accepted:2021-11-25 Online:2022-01-07 Published:2022-10-10
Contact: Xianwen FANG
About author:LI Duoqin, born in 1996， M. S. candidate. Her research interests include Petri nets， process mining.
FANG Xianwen, born in 1975， Ph. D.， professor. His research interests include Petri nets， trusted software， business process change domain analysis.
WANG Lili, born in 1982， Ph. D. candidate， associate professor.Her research interests include Petri nets， business process mining.
SHAO Chifeng, born in 1995，M. S. candidate. His research interests include Petri nets， process mining， model repair， model optimization.
Supported by:
National Natural Science Foundation of China(61402011);Anhui Provincial Natural Science Foundation(1508085MF111);Graduate Innovation Fund of Anhui University of Science and Technology(2019CX2068)

摘要/Abstract

摘要：

现存的成本函数没有考虑到业务流程中各活动在现实情境中的不同的重要程度，于是在模型与日志的对齐过程中可能会导致对齐成本严重偏离感知成本。针对这一问题，基于业务流程中行为的典型流特征提出了重要同步成本函数的概念，并在该函数下给出一种能够提升效率的对齐方法。首先，基于感知成本的概念定义重要同步成本函数；接着，依据日志迹以及流程模型中行为的典型流特征来确定用以分割流程模型与日志迹的重要匹配子序列；最后，基于重要同步成本函数来对齐分割后的子流程和对应的日志迹子序列，并将分段对齐的结果进行合并得到最终的对齐结果。实验部分从准确率和效率两方面进行验证所提方法：在准确率方面，与现存的标准成本函数和最大同步成本函数相比，所提成本函数下的对齐准确率最高提升了17.44个百分点，且当事件日志包含混合噪声时，所提成本函数下的平均对齐准确率最高，为88.67%；在对齐效率方面则通过比较对齐所耗时间来验证，现存两种函数的平均耗时分别为1.58 s和2.21 s，而所提方法为0.63 s，效率分别提升了150.79%和250.79%。实验结果表明所提方法能在满足准确率需求的同时提升对齐的效率。

关键词: 标准成本函数, 最大同步成本函数, 典型流特征, 感知成本, 重要同步成本函数, 有效对齐

Abstract:

The different importance of the activities in the business process in real world is not taken into account by the existing cost functions， so that in the alignment process of model and log， alignment cost may deviates from perceived cost significantly. To solve this problem， a concept of important synchronization cost function was proposed based on the typical flow characteristic of the behaviors in business processes， and an alignment method that can improve efficiency was proposed under this function. Firstly， the important synchronization cost function was defined based on the concept of perceived cost. Then， the important matching sub-sequence to segment the process model and the log trace was determined according to the log trace and the typical flow characteristic of the behaviors in the process model. Finally， based on the important synchronization cost function， the segmented sub-process and the corresponding log trace subsequence were aligned， and the segmented alignment results were combined to obtain the final alignment result. The experiments were carried out to verify the proposed method from the perspectives of accuracy and efficiency. In terms of accuracy， compared with the existing standard cost function and maximum synchronous cost function， the proposed cost function improved the alignment accuracy by up to 17.44 percentage points， and when the event log contained mixed noise， the proposed cost function had the highest average alignment accuracy of 88.67%. The efficiency of alignment was verified by comparing the time consumed by alignment. The average time of the existing two functions were 1.58 s and 2.21 s respectively， while that of the proposed method was 0.63 s， which was improved by 150.79% and 250.79% respectively. Experimental results show that the proposed method can satisfy the accuracy demand and improve the efficiency of alignment at the same time.

Key words: standard cost function, maximum synchronization cost function, typical flow characteristic, perceived cost, important synchronization cost function, effective alignment

中图分类号:

TP391.9

李多芹, 方贤文, 王丽丽, 邵叱风. 基于感知成本的流程模型与事件日志有效对齐[J]. 计算机应用, 2022, 42(10): 3154-3161.

Duoqin LI, Xianwen FANG, Lili WANG, Chifeng SHAO. Effective alignment of process model with event logs based on perceived cost[J]. Journal of Computer Applications, 2022, 42(10): 3154-3161.

图/表 12

图1 商品购买流程P

Fig. 1 Commodity purchase process P

表1 图1中各个字母指代的活动

Tab. 1 Activities referred to letters in Fig. 1

标识符	活动名称	标识符	活动名称
a	选择商品	f	选择不使用优惠券
b	查看店铺优惠	g	进入付款界面
c	领取优惠券	h	填写收货地址
d	选择使用优惠券	i	选择配送方式
e	选定优惠券	j	付款

图2 迹σ在标准成本函数（γ1）和最大同步成本函数（γ2）下的最优对齐

Fig. 2 Optimal alignments of trace σ under standard cost function （γ1） and maximum synchronous cost function （γ2）

图3 流程中行为的典型流示意图

Fig. 3 Schematic diagram of typical flow of behaviors in a process

图4 迹σ在重要同步成本函数下的最优对齐γ3

Fig. 4 Optimal alignment γ3 of trace σ under important synchronization cost function

图5 本文方法框架

Fig. 5 Framework of the proposed method

图6 图1中流程模型根据Simp分割后的子流程

Fig. 6 Sub-processes after segmentation of process model in Fig. 1 based on Simp

图7 不服从日志中仅包含缺失噪声时的对齐结果比较

Fig. 7 Alignment results comparison when non-conformance log trace only contains missing noise

图8 不服从日志中仅包含错位噪声时的对齐结果比较

Fig. 8 Alignment results comparison when non-conformance log trace only contains dislocated noise

图9 不服从日志中仅包含冗余噪声时的对齐结果比较

Fig. 9 Alignment results comparison when non-conformance log trace only contains redundant noise

图10 不服从日志中包含混合噪声时的对齐结果比较

Fig. 10 Alignment results comparison when non-conformance log trace contains mixed noise

图11 不服从日志中包含混合噪声时的对齐耗时对比

Fig. 11 Comparison of alignment time when non-conformance log trace contains mixed noise

参考文献 15

1	VAN ZELST S J， BOLT A， VAN DONGEN B F. Tuning alignment computation： an experimental evaluation［C］// Proceedings of the International Workshop on Algorithms and Theories for the Analysis of Event Data 2017 — Satellite Event of the Conferences： 38th International Conference on Application and Theory of Petri Nets and Concurrency and 17th International Conference on Application of Concurrency to System Design. Aachen： CEUR-WS.org， 2017： 6-20. 10.1007/978-3-319-57861-3
2	VAN DER AALST W M P， 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
3	SONG W， XIA X X， JACOBSEN H A， et al. Efficient alignment between event logs and process models［J］. IEEE Transactions on Services Computing， 2017， 10（1）： 136-149. 10.1109/TSC.2016.2601094
4	TAYMOURI F， CARMONA J. A recursive paradigm for aligning observed behavior of large structured process models［C］// Proceedings of the 2016 International Conference on Business Process Management， LNCS 9850. Cham： Springer， 2016： 197-214.
5	田银花，杜玉越，韩咚，等. 基于Petri网的事件日志与过程模型对齐方法［J］. 计算机集成制造系统， 2019， 25（4）：809-829.
	TIAN Y H， DU Y Y， HAN D， et al. Aligning event logs and process models based on Petri nets［J］. Computer Integrated Manufacturing Systems， 2019， 25（4）：809-829.
6	韩咚，田银花，杜玉越，等. 基于Petri网可达图的业务对齐方法［J］. 计算机集成制造系统， 2020， 26（6）：1589-1606. 10.13196/j.cims.2020.06.016
	HAN D， TIAN Y H， DU Y Y， et al. Business alignments based on reachable graphs of Petri nets［J］. Computer Integrated Manufacturing Systems， 2020， 26（6）：1589-1606. 10.13196/j.cims.2020.06.016
7	BLOEMEN V， VAN ZELST S J， VAN DER AALST W M P， et al. Maximizing synchronization for aligning observed and modelled behaviour［C］// Proceedings of the 2018 International Conference on Business Process Management， LNCS 11080. Cham： Springer， 2018： 233-249.
8	SANI M F， VAN ZELST S J， VAN DER AALST W M P. Repairing outlier behaviour in event logs using contextual behaviour［J］. Enterprise Modelling and Information Systems Architectures， 2019， 14： No.5. 10.1007/978-3-319-93931-5_9
9	张力雯，方贤文. 基于对齐处理与偏差检测的业务流程适合度分析［J］. 计算机集成制造系统， 2020， 26（6）：1573-1581. 10.13196/j.cims.2020.06.014
	ZHANG L W， FANG X W. Business process fitness analysis based on alignment processing and deviation detection［J］. Computer Integrated Manufacturing Systems， 2020， 26（6）：1573-1581. 10.13196/j.cims.2020.06.014
10	WEIDLICH M， MENDLING J. Perceived consistency between process models［J］. Information Systems， 2012， 37（2）：80-98. 10.1016/j.is.2010.12.004
11	王前东. 一种带匹配路径约束的最长公共子序列长度算法［J］. 电子与信息学报， 2017， 39（11）：2615-2619. 10.11999/JEIT170092
	WANG Q D. A matching path constrained longest common subsequence length algorithm［J］. Journal of Electronics and Information Technology， 2017， 39（11）：2615-2619. 10.11999/JEIT170092
12	JOUCK T， DEPAIRE B. PTandLogGenerator： a generator for artificial event data［C］// Proceedings of the BPM Demo Track 2016 Co-located with the 14th International Conference on Business Process Management. Aachen： CEUR-WS.org， 2016： 23-27.
13	JOUCK T， DEPAIRE B. Generating artificial data for empirical analysis of control-flow discovery algorithms［J］. Business and Information Systems Engineering， 2019， 61（6）：695-712. 10.1007/s12599-018-0541-5
14	DE LEONI M， VAN DER AALST W M P. Data-aware process mining： discovering decisions in processes using alignments［C］// Proceedings of the 28th Annual ACM Symposium on Applied Computing. New York： ACM， 2013：1454-1461. 10.1145/2480362.2480633
15	BAZHENOVA E， BUELOW S， WESKE M. Discovering decision models from event logs［C］// Proceedings of the 2016 International Conference on Business Information Systems， LNBIP 255. Cham： Springer， 2016： 237-251.

[1]	闫文杰, 党东月. 基于特征自适应提取的宽度量子态层析模型[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3861-3866.
[2]	王一帆, 林绍福, 李云江. 基于区块链和零知识证明的高速公路自由流收费方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3741-3750.
[3]	何长久, 杨婧涵, 周丕宇, 边昕烨, 吕明明, 董迪, 付岩, 王海鹏. 基于Transformer和门控循环单元的肽序列理论串联质谱图预测方法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3958-3964.
[4]	刘哲旭张澳冰樊智勇. 飞机狭小空间虚拟维修姿态分层求解方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	苗荣华孙奕程王森武燕婷杜明鲍劲松. DTOps：数字孪生系统开发运维一体化方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[6]	王中钰, 钱晓东. 基于改进期望最大化算法的供应链网络边连接规则优化[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3386-3395.
[7]	王昱, 关智慧, 李远鹏. 基于轨迹预测和分布式MADDPG的无人机集群追击决策[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3623-3628.
[8]	阚绪康, 史格非, 杨雪榕. 基于动态特征点滤除与关键帧选择优化的ORB-SLAM2算法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3185-3190.
[9]	陈廷伟, 张嘉诚, 王俊陆. 面向联邦学习的随机验证区块链构建[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2770-2776.
[10]	黄梦源, 常侃, 凌铭阳, 韦新杰, 覃团发. 基于层间引导的低光照图像渐进增强算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1911-1919.
[11]	符五久周林邓建杰游泳. 分数阶自治动力学系统初值问题的递推公式及其应用[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	封筠, 毕健康, 霍一儒, 李家宽. 轻量化沥青路面裂缝图像分割网络PIPNet[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1520-1526.
[13]	沈涵, 王中生, 周舟, 王长元. 基于多应用场景的改进DV-Hop定位模型[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1219-1227.
[14]	马源源, 解蕾蕾, 董南, 刘娜. 考虑用户能动性和流动性的舆情传播模型[J]. 《计算机应用》唯一官方网站, 2024, 44(2): 619-627.
[15]	郭呈史春秀梅顺峰张熠. 基于大数据的复杂系统智能建模方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

基于感知成本的流程模型与事件日志有效对齐

Effective alignment of process model with event logs based on perceived cost

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 15

相关文章 15

编辑推荐

Metrics