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

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]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	李汉伦, 任建国. P2P网络中基于特征行为检测的恶意代码传播模型[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2125-2131.
[3]	陈海龙, 杨畅, 杜梅, 张颖宇. 基于边界自适应SMOTE和Focal Loss函数改进LightGBM的信用风险预测模型[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2256-2264.
[4]	刘亚平, 张惠珍, 张莉, 刘优优. 带时间窗同时送取货选址路径问题及其烟花算法求解[J]. 《计算机应用》唯一官方网站, 2022, 42(7): 2292-2300.
[5]	邓世权, 叶绪国. 基于深度Q网络的多目标任务卸载算法[J]. 《计算机应用》唯一官方网站, 2022, 42(6): 1668-1674.
[6]	王杰科李琳张海龙郑利平. 虚拟现实大空间下多虚拟目标被动触觉交互方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[7]	侯守明贾超兰张明敏. 用于虚拟现实系统的眼动交互技术综述[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[8]	孙海燕陈云博封丁惟王通蔡兴泉. 基于注意力模型和轻量化YOLOv4的林业害虫检测方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[9]	周玉清韩晓龙. 双循环策略下岸桥与跨运车的联合调度[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[10]	张斯, 张必山, 马忠军. 传染病在多层星型耦合网络上的资源控制[J]. 《计算机应用》唯一官方网站, 2022, 42(5): 1547-1553.
[11]	屈景怡杨柳陈旭阳王茜. 基于时空序列的Conv-LSTM航班延误预测模型[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[12]	吴晴晴, 周丽华, 寸轩懿, 杜国王, 姜懿庭. 异质信息网络中基于有向无环图的影响力最大化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 895-903.
[13]	蔡兴泉封丁惟王通孙辰孙海燕. 基于时间注意力机制和EfficientNet的视频暴力行为检测[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[14]	张京, 朱爱红. 基于遗传算法和粒子群优化的列车自动驾驶速度曲线优化方法[J]. 《计算机应用》唯一官方网站, 2022, 42(2): 599-605.
[15]	申明尧, 韩萌, 杜诗语, 孙蕊, 张春砚. 融合XGBoost和Multi-GRU的数据中心服务器能耗优化算法[J]. 《计算机应用》唯一官方网站, 2022, 42(1): 198-208.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 15

相关文章 15

编辑推荐

Metrics