Abstract: Conformance checking is an important task in the field of process mining to discover the differences and commonalities between business process behaviors and observed behaviors.Alignment is one of the current standard conformance checking techniques,which accurately locates deviations between observed and modeled behavior.However,as event logs grow in size and complexity,alignment is often time-consuming and difficult to return in a reasonable amount of time.Therefore,a distributed conformance checking method based on process model decomposition was proposed.All kinds of process models were uniformly transformed into process tree models,and the process tree was decomposed into sub-trees by using the structural characteristics of the process tree to reduce the search space of the alignment method.The optimal alignment of trace and sub-models was calculated on the distributed platform Spark to speed up the calculation of alignment.The experiments were compared on several logs.The proposed method had been implemented in PM4PY and Spark distributed environment,and could be used as a framework in combination with other conformance checking methods.The proposed method was compared with the existing alignment method based on A* and Token replay method through public event logs.Experimental results showed that the proposed method could improve the efficiency of calculating event log conformance.

Key words: conformance checking, process tree, alignment, decomposition, distributed computing

摘要： 合规性检查是流程挖掘领域的一项重要任务,旨在发现业务流程日志行为和模型行为之间的差异和共性。对齐(Alignment)是当前合规性检查的标准技术之一,能精确定位日志行为和模型行为之间的偏差。然而,随着事件日志规模和复杂程度的增长,对齐通常非常耗时且难以在合理的时间内返回结果。为此,提出一种基于流程模型分解的分布式合规性检查方法,首先,将各类流程模型统一转换为流程树模型,并利用流程树的结构特性将流程树分解为子树,以减少对齐方法的搜索空间;其次,在分布式平台Spark上计算轨迹和子模型的最优对齐,从而加快对齐的计算;最后,通过多个日志进行实验对比。所提方法均已在PM4PY和Spark分布式环境中实现,并且可以作为一种框架与其他合规性检查方法结合使用。通过公开日志数据集将所提方法与已有基于A*的对齐方法和托肯重演方法进行对比,实验结果表明所提方法可以提高业务流程合规性检查的计算效率。

关键词: 合规性检查, 流程树, 对齐, 分解, 分布式计算