流程挖掘一致性检验算法研究综述

流程挖掘一致性检验算法研究综述一文创作于：2023-08-16 04:20:48，全文字数：16909。

2012年，文 献［35］ 中 提 出 一 种 基 于 对 齐（Alignment）的一致性检验。 这种方案更像是在处理字符串的编辑距离，自从提出以来，就一直受到学术界的青睐，且被公认为是迄今为止效率最高的一致性检验算法。 算法通过计算move in log、move in model、both move 和illegal move 这4 种移动方式在进行比对时出现的次数来计算模型和日志之间的拟合度。 这个最初的算法在面对日志与模型之间出现偏差时，虽然可以得到两者之间的偏差，但是没有考虑到日志中不同event 之间出现偏差的影响程度，这一问题已然在后续的优化研究中得到了有效解决。 文献［36］中提出一种基于cost 的一致性检验，通过对原始的Petri Net 进行扩展，加入转移的cost来区分不同活动的重要程度。 这也是目前获得广泛认可的一种方案。 这种基于对比的一大类一致性检验算法存在的普遍问题是算法具备较差的扩展性。另一个问题是，如果需要和前文提到的算法一样具备提供精确的偏差定位信息时，就要在算法的执行过程中花费额外的内存空间来存储对比过程中各个步骤得到的中间信息。 文献［37］中针对扩展性给出了一个方案，核心思想是把模型和日志都表现成自动机的形式，这样可以减少对公共片段进行处理时造成的时间消耗。 通过启发式的A?6?算法［38］来保证日志中的轨迹和模型中轨迹的最佳对齐。 另一种方案是将模型分解为一组自动机，这些自动机组合在一起可以完整地表示出流程模型，通过对这些自动机进行单独处理，在算法的执行时间上得到了明显改善。 王颖等人［39］提出的算法把对齐方案进行了扩展，并未考虑流程是否按照模型中的流程轨迹来执行，同时还把流程中的每个活动对应的属性是否符合模型中的赋值规则也一并进行了研究。 算法仍是根据Petri Net 构建状态转移空间，使用A?6?算法来搜索最接近的目标轨迹。 这种综合考虑执行流程和规则约束的一致性检验方案具有更加广阔的应用场景，却仍然需要面对严重的算法耗时问题。

3 近似算法

目前，常见的一致性检验算法普遍存在的一个问题是算法耗时严重。 究其原因，主要是这些算法都是以返回最为准确的拟合度这一思想作为基础提出的。 为了准确地计算得出最终结果，将会花费大量的计算时间，例如前文提到的Alignment Based Conformance Checking 中，就需要在模型中搜索最接近的合法化路径，如此一系列的操作在保证算法结果准确度的同时，却会造成很高的时间开销，这样严重的耗时问题在面对一些可能随着时间推演而不断改进的模型时，会忽略日志的时效信息。 同时，某些应用场景下并不需要提供较为准确的拟合指标，一种常见的方案是计算拟合度的上下限。 在此基础上，随即就提出了许多近似一致性检验算法。

Lee 等人［40］提出了一种基于划分模型的算法，将复杂的、含有并发的模型按块划分为简单的子模型，通过融合分解模型的一致性检验结果来确定整个复杂模型的指标。 在面对较为复杂的模型时，会涉及到更加复杂的搜索空间，通过这种将模型划分成较为简单的模型板块的做法，可以显著降低搜索时的时间开销。 文献［41］首先对日志进行分析，统计日志中活动序列的出现概率；基于日志的前缀，通过用户确定前缀的扩展长度，分析日志中前缀的后续动作的出现概率，据此概率来确定拟合度的范围区间。 文献［42］提出一种通过采样的方法来近似估算模型与日志之间的拟合度。 与前面提到的算法不同的是，该模型面对的应用场景是把重点放在日志整体与流程模型的一致性上，而不是聚焦在单一的某一个流程上。 与筛选出和模型有偏差的异常流程相比较来说，这种算法能够更好地对流程模型进行评测。

4 在线算法

前面提到的一系列算法都是以“日志中所有的流程都已经结束”这一前提条件为基础的，但是在实际的应用场景中，往往面对的是一些仍在进行中的数据，对于这些不完整的日志流程，前文论述的离线算法的表现往往不尽如人意，所以很多学者着眼于研发在线的一致性检验算法。 文献［43－44］中分析了在线一致性检验算法对制造企业的重要作用。将在线一致性检验算法与离线算法相比，最主要的区别就是需要算法在未知后续活动序列的情况下对整个案例进行评估［45］，下面就系统总结了近几年来在线的一致性检验算法的研究成果。

2018年，文献［46］中提出一种较为经典的在线一致性检验算法框架。 同时提出不再使用fitness这个唯一的指标作为一致性检验算法的结果。 因为在线算法并不像离线算法那样可以确定后续完整的日志，也无法确定后续的活动，所以除了使用fitness之外，还将使用completeness来判断案例是否已经完成，confidence来表示前面参数的可信度。 考虑到在线算法的特点，就需要解决冷启动的问题。 算法使用由某一模型推衍的多种由不同的模型阶段产生的不同长度的不同案例来解决冷启动问题。 算法离线得对初始模型进行解析，得到用于在线一致性检验算法的流程模型，首先对初始模型进行转换，去除模型中的循环，依据定义的行为模式，构造三元组（B，P，F）。 这里，B为满足规定的行为模式的集合，P为任意模式b在出现前的行为模式的个数区间，F（b） 为从任意b开始、到流程结束，需要的不同行为模式的最少个数。 框架中主要使用日志活动间的行为模型，算法需要认为确定行为模式的类别、即日志活动之间的关系，通过将日志流转化为行为模式流。 算法统计在到达某一个行为模式时，前面已经观测到的合法以及不合法的行为模式的个数。 算法以更新行为模式的个数、计算拟合度指标、释放内存为总体的框架。 这种算法框架中可以由用户自己定义具体行为模型，有一定的扩展性，但是算法需要离线做的前置工作较为复杂，并不是所有的流程模型都可以适配这种算法框架。

Lee 等人［47］提出一种基于隐马尔可夫模型的在线一致性检验算法。 由于在计算拟合度指标时，对于当前处理的日志活动，其前期所有的日志活动以及当前的活动本身都会对拟合度产生影响，算法将数据流处理的过程看作是隐马尔可夫链。 整个算法受文献［8］启发，也通过增加在线算法的拟合度指标来更为确切地表示流程与模型之间的拟合度。算法通过离线对模型进行解析，得到状态转移矩阵、初始状态描述、定义用于表示拟合程度的计算函数来构造用于在线一致性检验算法的隐马尔可夫模型。 以日志流、构造得到的隐马尔可夫模型、状态的距离矩阵作为输入，算法以更新状态估计、计算拟合度指标、释放内存为总体框架。 算法可以在保证准确率的同时，降低对内存的需求。

Zelst 等人［48］提出一种基于前缀对齐的一致性检验技术，前面提及了基于alignment 的离线一致性检验算法，该算法主要思想与离线的算法相似，研究中主要针对，在面对illegal move 时寻找其他路径的优化搜索算法以及在线算法中对内存使用和算法优化之间的折中选择方面。 文献［49］提出一种针对多方面对齐的在线一致性检验算法，可以从多个角度对进行中的流程加以分析。 文献［50］提出一种较为高效地计算对齐过程中偏差定位的算法，提

提醒您：因为《流程挖掘一致性检验算法研究综述》一文较长还有下一页，点击下面数字可以进行阅读！

《流程挖掘一致性检验算法研究综述》在线阅读地址：流程挖掘一致性检验算法研究综述