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

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