Abstract: Currently,the wildly used method of conformance checking is alignment-based conformance checking.This kind of conformance checking used search method to find the optimal alignment between process model and trace.Our goal is to speed up the calculating process of conformance checking.The idea of beam search was introduced for reducing the number of states searched to speed up the algorithm,which would lead to the failure of searching for optimal alignment eventually.To fix this problem,a frequency-based cost function was calculated.With this cost function,the alignment process would tend to find alignments with high frequency,thus the better alignment scheme could be find.The experiment results showed that the proposed idea of beam search and new cost function could successfully accelerate the alignment algorithm and get a relatively accurate alignment.

Key words: conformance checking, algorithm speed up, accurate, beam search, cost functionconformance checking, algorithm speed up, accurate, beam search, cost function

摘要： 当前的过程一致性检测的主流方法是基于计算过程模型与日志数据的对齐方案的,该方法的基本思路是使用搜索的方法来找到最优的对齐方案。通过在搜索的过程中引入束搜索的思想,对搜索过程中遇到的状态进行删减,通过减少参与搜索的状态来对搜索过程进行加速,但是束搜索对状态的删减可能会导致最终不能够搜索到最优的对齐方案,最终的计算结果是对最终对齐方案的一个估计值。为了得到更优的对齐方案,提出一种新的基于频繁度的成本函数用于对齐。该成本函数通过倾向于优先选择更频繁出现的事件进行对齐,从而提高对齐效果,帮助更准确地找到最优对齐方案。实验证明,引入束搜索思想和计算新的成本函数的方法能够对搜索对齐方案进行加速,并获得较为准确的对齐结果。

关键词: 一致性检测, 算法加速, 准确, 束搜索, 成本函数