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

校准是事件日志中迹与过程模型之间一致性检查的重要手段,可以精确定位偏差出现位置.但已有校准方法一次只能计算一条迹与过程模型之间的校准,若计算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方法突破了以往每次只对一条迹和过程模型进行校准的限制,首次实现了批量迹与模型之间的校准,提高了事件日志中迹与过程模型之间的一致性检查效率.

事件日志的批量迹与过程模型的多视角对齐方法

在业务过程发现的一致性检测中,现有事件日志与过程模型的多视角对齐方法一次只能获得一条迹与过程模型的最优对齐;并且最优对齐求解中的启发函数计算复杂,以致最优对齐的计算效率较低。为此,提出一种基于迹最小编辑距离的、事件日志的批量迹与过程模型的多视角对齐方法。首先选取事件日志中的多条迹组成批量迹,使用过程挖掘算法得到批量迹的日志模型;进而获取日志模型与过程模型的乘积模型及其变迁系统,即为批量迹的搜索空间;然后设计基于Petri网变迁序列集合与剩余迹的最小编辑距离的启发函数来加快A^(*)算法;最后设计可调节数据和资源视角所占权重的多视角代价函数,在乘积模型的变迁系统上提出批量迹中每条迹与过程模型的多视角最优对齐方法。仿真实验结果表明,相比已有工作,在计算批量迹与过程模型间的多视角对齐时,所提方法占用更少的内存空间和使用更少的运行时间。该方法提高了最优对齐的启发函数计算速度,可以一次获得批量迹的所有最优对齐,进而提高了事件日志与过程模型的多视角对齐效率。