Abstract: To calculate the optimal alignments for process models with loops as efficiently and accurately as possible,based on an existing conformance checking method for no-loop models that guaranteed the accuracy,a heuristic search-based method for process models with loops was proposed,which could be regarded as finding the proper loop unfolding scenario that achieved the best aligning level for a given process trace.As a loop in the process model corresponds to repeated events in the process traces,a process trace was decomposed into a set of subsequences according to where repeated events occur.Then,the optimal alignments between the process models was computed after unfolding a loop and the process traces with progressively increasing subsequence.The aligning level between the process trace and the process model after unfolding each loop could be obtained.The aligning level was used as heuristic information (the loop unfolding scenario with high aligning level would be unfold first) to efficiently guide the search for the loop unfolding scenario.Experimental results showed that the heuristic search-based method could not only reduce the number of search spaces but also reach the accuracy rate of 99.8% under the condition that deviations in the event log are non-model activities,which verified the effectiveness of the proposed method.

Key words: process traces, unfolding loops, search spaces, optimal alignments, heuristic search

摘要： 为了尽可能高效、准确地计算带循环模型的最优对齐,鉴于已有可保证准确性的无循环模型的一致性检测方法,提出带循环模型的一致性检测方法,其将带循环模型的一致性检测问题转化为寻找与给定事件序列一致性程度最高的循环展开过程。该方法利用过程模型中的循环对应事件序列中重复事件的特点,提出将事件序列按重复事件出现节点分解为若干子序列;将展开循环后(无循环)的过程模型与子序列逐渐递增的事件序列进行最优对齐计算,得到各循环展开情况与事件序列的匹配程度;以匹配程度作为启发信息,优先针对匹配程度高的展开情况继续展开,直到找到与事件序列最匹配的循环展开过程。实验结果表明,启发式搜索策略能有效减少搜索空间,在事件日志中的新增变异为非模型活动的情况下,准确率达到998%,验证了方法的有效性。

关键词: 事件序列, 循环展开, 搜索空间, 最优对齐, 启发式搜索