基于对齐的BPMN 2.0模型符合性检测算法

汪玉泉; 闻立杰; 闫志强

doi:10.7544/issn1000-1239.2017.20160756

基于对齐的BPMN 2.0模型符合性检测算法

¹(清华大学软件学院北京 100084)
²(首都经济贸易大学信息学院北京 100070) (272269222@qq.com)

基金项目: 国家重点研发计划项目(2016YFB1001101)；国家自然科学基金项目(61472207，61325008，61402301)

详细信息

中图分类号: TP315
计量
- 文章访问数: 1267
- HTML全文浏览量: 5
- PDF下载量: 560
出版历程
- 发布日期: 2017-08-31

Alignment Based Conformance Checking Algorithm for BPMN 2.0 Model

¹(School of Software, Tsinghua University, Beijing 100084)
²(School of Information, Capital University of Economics and Business, Beijing 100070)

摘要

摘要: 符合性检测方法作为比较和关联事件日志与流程模型的技术，是三大核心流程挖掘技术之一，可用于量化符合性和诊断偏差.BPMN 2.0模型具有丰富的表达能力，能够表达多实例、子流程、边界事件、OR网关等多种复杂模式，但是目前还没有针对这些复杂模式的BPMN 2.0模型符合性检测算法.针对该问题，提出了基于对齐的BPMN 2.0模型符合性检测算法Acorn，该算法支持上述多种复杂模式.在深入分析BPMN 2.0模型中多种复杂模式的具体语义并分析其具体使能情况的基础上，Acorn算法引入对齐操作，利用A\+*搜索算法寻找到代价最小的匹配轨迹，同时引入虚拟代价和预估代价来对A\+*算法进行搜索空间的优化，最后根据最佳匹配轨迹来计算模型与日志的契合度.实验表明，Acorn算法能够正确有效地计算带有复杂模式的BPMN 2.0模型与日志之间的契合度，且虚拟代价和预估代价的引入，大大减少了搜索空间，有效提高了算法的运行速度.
- BPMN 2.0模型 /
- 复杂模式 /
- A\+*搜索 /
- 符合性检测 /
- 对齐
Abstract: Process mining is an emerging discipline providing comprehensive sets of tools to provide fact-based insights and to support process improvements. This new discipline builds on process model-driven approaches and data-centric analysis techniques such as machine learning and data mining. Conformance checking approaches, i.e., techniques to compare and relate event logs and process models, are one of the three core process mining techniques. It is shown that conformance can be quantified and that deviations can be diagnosed. BPMN 2.0 model has so powerful expression ability that it can express complex patterns like multi-instance, sub-process, OR gateway and boundary event. However, there is no existing conformance checking algorithm supporting such complex patterns. To solve this problem, this paper proposes an algorithm (Acorn) for conformance checking for BPMN 2.0 model, which supports aforesaid complex patterns. The algorithm uses A\+* algorithm to find the minimum cost alignment, which is used to calculate fitness between BPMN 2.0 model and the log. In addition, virtual cost and expected cost are introduced for optimization. Experimental evaluations show that Acorn can find the best alignment by exploiting the meanings of BPMN 2.0 elements correctly and efficiently, and the introduction of virtual cost and expectation cost indeed reduces the search space.
- BPMN 2.0 model /
- complex pattern /
- A\+* search /
- conformance checking /
- alignment

HTML全文

参考文献(0)

施引文献(31)

期刊类型引用(11)

1.	周显春，喻佳. 基于图神经网络的人工自然语言语义挖掘仿真. 计算机仿真. 2024(01): 344-348 . 百度学术
2.	孟祥福，田友发，张霄雁. 基于LightGBM模型的肺腺癌免疫相关基因筛选与患者生存率预测. 生物医学工程学杂志. 2024(01): 70-79 . 百度学术
3.	陈伟，周丽华，王亚峰，王丽珍，陈红梅. 异质信息网络中基于解耦图神经网络的社区搜索. 计算机科学. 2024(03): 90-101 . 百度学术
4.	万齐智，万常选，胡蓉，刘德喜，刘喜平，廖国琼. 面向研究问题的深度学习事件抽取综述. 自动化学报. 2024(11): 2079-2101 . 百度学术
5.	刘超，孔兵，杜国王，周丽华，陈红梅，包崇明. 高阶互信息最大化与伪标签指导的深度聚类. 浙江大学学报(工学版). 2023(02): 299-309 . 百度学术
6.	杨成波，周丽华，黄亚群，杨宇迪. 异质网络中基于关键词属性的Truss社区搜索. 计算机应用研究. 2023(06): 1708-1714 . 百度学术
7.	白明昌. 基于折叠路径聚合的属性网络节点嵌入方法. 计算机工程. 2023(07): 76-84 . 百度学术
8.	谢小杰，梁英，王梓森，刘政君. 基于图卷积的异质网络节点分类方法. 计算机研究与发展. 2022(07): 1470-1485 . 本站查看
9.	王宏琳，杨丹，聂铁铮，寇月. 自注意力机制的属性异构信息网络嵌入的商品推荐. 计算机研究与发展. 2022(07): 1509-1521 . 本站查看
10.	盛妍，朱龙珠，丁毛毛，刘鲲鹏，刘海龙. 面向电力服务情绪识别的图卷积网络方法研究. 电子器件. 2022(04): 959-963 . 百度学术
11.	李琳，梁永全，刘广明. 基于重启随机游走的图自编码器. 计算机应用研究. 2021(10): 3009-3013 . 百度学术