韩 咚,田银花,杜玉越,张 琴

(1.山东科技大学 矿业与安全工程学院，山东 青岛 266590；2.山东科技大学 智能装备学院，山东 泰安 271000；3.山东科技大学 计算机科学与工程学院，山东 青岛 266590)

0 引言

过程挖掘的理念是通过从事件日志中提取出有价值的信息，从而发现、监控和改进实际业务过程[1-5]。过程挖掘的研究对于实施新的业务过程以及分析、改进已实施的业务过程具有非常重要的意义，是近年来相关领域国内外研究的热点[6-8]。过程挖掘主要包括过程发现、合规性检查、过程增强等应用类型。其中，合规性检查将事件日志中的事件与过程模型中的活动进行对比，旨在找到观察行为和建模行为之间的共性和差异[9-13]。

在众多合规性检查方法中，对齐观察行为和建模行为成为衡量记录系统运行行为的事件日志和过程模型一致性的重要手段[14-16]。对齐方法的主旨在于发现过程模型与事件日志之间存在的偏差。通常情况下，包含偏差数最少的对齐被认为是最优对齐。有关最优对齐的查找方法是NP-hard问题，时间复杂度和空间复杂度均较高。在过程挖掘研究领域，对齐方法已得到广泛的研究与应用[17-21]。已有大量关于对齐方法及类似方法的文献呈现了此类方法的思想、动机以及解决的问题。

Cook等[22]提出一种比较迹与过程模型来量化相似度的方法。该方法虽然是基于状态空间的分析方法，但因其使用了启发规则简化搜索空间，从而产生了错误的对齐结果，以致于只能部分支持重复变迁和不可见变迁。……