基于Petri网的批量迹与过程模型校准

• 作者: 刘伟 杜玉越 田银花 韩咚
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: Petri网 过程挖掘 日志模型 过程模型 批量迹 校准
• 年，卷（期）: 2018,（3）
• 所属期刊栏目: 软件技术与理论
• 页码范围: 611-627
• 页数: 17页
• 分类号: TP311
• 字数: 13655字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2018.00611

摘要

校准是事件日志中迹与过程模型之间一致性检查的重要手段,可以精确定位偏差出现位置.但已有校准方法一次只能计算一条迹与过程模型之间的校准,若计算m条迹与过程模型之间的校准,需调用m次该方法,做大量重复工作.针对该问题,基于Petri网提出了一种过程模型与m条迹之间的批量校准方法——AoPm(Alignments of Process Model and m Traces)方法,调用A+或A++算法同时得到多条迹与模型之间的最优校准.以一个给定完备事件日志集和过程模型为例,基于区域的过程发现算法,挖掘事件日志中所有迹的日志模型;发现日志模型与过程模型的日志移动、模型移动和同步移动,并得到其乘积系统;计算乘积Petri网的可达图,得到变迁系统.提出了计算最优校准的A+算法及A++算法,可分别得到日志中所有迹与过程模型之间的一个最优校准和所有最优校准.对AoPm方法的时间复杂度和空间复杂度进行了理论分析,并与已有校准方法进行比较.当计算m条迹与过程模型之间的最优校准时,AoPm方法计算乘积、变迁系统次数和所占用空间都是传统方法的1/m.给出并验证了变迁系统中必定能找到日志中任意一条迹与过程模型的一个校准、一个最优校准和所有最优校准的定理,并提出了日志同步网的概念,证明了A+算法和A++算法的正确性.基于ProM平台、人工网上购物模型及生成日志集,对AoPm方法进行了仿真实验,并与传统校准方法进行比较分析.实验结果表明,在处理批量迹与过程模型的校准时,AoPm方法比传统校准方法在计算变迁系统的运行时间和占用空间上,分别有指数级和多项式级的降低.AoPm方法应用于实际复杂问题的模型与日志,说明了其适应性与健壮性.AoPm方法突破了以往每次只对一条迹和过程模型进行校准的限制,首次实现了批量迹与模型之间的校准,提高了事件日志中迹与过程模型之间的一致性检查效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘伟	山东科技大学信息科学与工程学院	50	301	8.0	16.0
2	杜玉越	山东科技大学信息科学与工程学院	51	313	9.0	15.0
3	田银花	山东科技大学信息科学与工程学院	10	15	3.0	3.0
7	韩咚	山东科技大学矿业与安全工程学院	9	22	3.0	4.0