标题：Alignments Between Batch Traces and Process Models Based on Petri Nets
作者：Tian, Yin-Hua ;Du, Yu-Yue ;Han, Dong ;Liu, Wei
作者机构：[Tian, Yin-Hua ;Du, Yu-Yue ;Liu, Wei ] College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao; Shandon 更多
来源：Jisuanji Xuebao/Chinese Journal of Computers
摘要：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.
© 2018, Science Press. All right reserved.