校准是事件日志中迹与过程模型之间一致性检查的重要手段,可以精确定位偏差出现位置.但已有校准方法一次只能计算一条迹与过程模型之间的校准,若计算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方法突破了以往每次只对一条迹和过程模型进行校准的限制,首次实现了批量迹与模型之间的校准,提高了事件日志中迹与过程模型之间的一致性检查效率.%Alignment is a main method of conformance checking between a trace in the event log and the process model,and can fix the locations of the deviations accurately.But the existing alignment method can obtain the alignments between only one trace and the process model.This method must be applied for m times if the alignments between m traces and the process model are required,and a lot of repetitive tasks have to be done.To resolve such problem,alignments of process models and m traces named AoPm are presented based on Petri nets,and this method can achieve the optimal alignments between the batch traces of an event log and the process model at the same time by calling A+ or A++ algorithm.Taking a given complete event log set and a process model for example,the follow tasks were done:all of the traces in the event log were translated into an event model by an iterative algorithm for applying the theory of regions in process mining;moves on logs,moves on models and synchronous moves were found,and a product system of the event net and the process net was built.The reachable graph of the product Petri net was yielded,and the transition system of the product was built.An optimal alignment between every trace in the original event log and the process model could be obtained by A+ algorithm,and all optimal alignments between every trace in the original event log and the process model could be obtained by A++ algorithm.The time complexity and space complexity of AoPm method were analyzed theoretically and compared with the existing alignment method.It was concluded that the iteration times and the memory of the product systems and the transition systems were reduced m-fold using AoPm method than the traditional alignment method when computing the optimal alignments between m traces and the process model.The theorems of finding an alignment,an optimal alignment and all of the optimal alignments were proposed in the transition system,the log-synchronous net was presented,and the correctness of A+ and A++ algorithms could be explained.The simulations of AoPm method were carried out and compared with the traditional alignment methods based on ProM platform,the artificial model on online shopping and the generated event logs.The experiment results showed that the time taken to compute transition systems of AoPm method was reduced exponentially and the space complexity had a polynomial decline than the traditional alignment method.To show the adaptability and robustness of the proposed approach to logs and models with real-life complexity,several real-life logs and models were analyzed.AoPm method breaks through the thought of the alignment between only one trace and the process model,realizes the alignments between batch traces in the event log and the process model,and improves the efficiency of conformance checking between traces in the event log and the process model.
展开▼
