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

2023-08-01赵百威谢志伟石胜飞

智能计算机与应用 2023年4期

赵百威，韩珣，谢志伟，石胜飞

（1 哈尔滨工业大学计算学部，哈尔滨 150001； 2 四川警察学院智能警务四川省重点实验室，四川泸州 646000；3 黑龙江农垦职业学院，哈尔滨 150025）

0 引言

工业4.0 的背景下，越来越多的制造企业通过各类信息系统来管理企业中的业务流程，这些系统产生的大量日志数据成为可操作的信息资源。作为一个数据驱动的方法，流程挖掘（Process Mining）从信息系统的事件日志中获取过程知识，发现、监测和改进实际系统行为模式［1］，并能自动发现业务流程和许多额外的流程增强技术。目前，流程挖掘的研究主要有3 个方面，即：流程发现、一致性检验和流程增强。现已在医疗、金融领域得到初步的应用［2－4］。与此同时，在制造业领域中也备受关注。文献［5－12］中初步介绍了制造业中流程挖掘的应用前景。文献［13－14］中分别就衡量产品质量和预测制造流程中的工作负载方面进行了应用实例分析。文献［15－16］提出了针对中小型的制造企业，通过流程挖掘来预测流程的结束时间。利用流程挖掘中的一致性检验技术，可以对制造企业生产流程中异常流程进行诊断，提高产品的质量和生产的效率。现如今，亦有数目可观的制造企业正致力于通过一致性检验算法来改进自身的生产流程。文献［17－18］中提出了面向一致性检验算法的智能生产流程日志采集方案。文献［19－21］中介绍了针对制造企业生产流程应用一致性检验技术提出的流程评价方案。文献［22］分别在数据流方面和运行时间方面对制造企业流程进行分析，诊断出偏离模型的异常流程。

一致性检验作为流程挖掘中的一部分，与过程发现从日志信息中获取可能的流程模型不同的是，一致性检验的主要目标是判断流程模型和日志数据之间的匹配关系。一致性检验不仅可以为这些企业诊断出可能存在问题的生产制造流程，同时也可以作为由过程发现获得的流程模型的一种评测方案。近些年来，流程发现取得了显著进展，大量的过程发现算法以及各种模型的表达方式陆续得以提出［23－28］，一致性检验在衡量这些流程模型方面也发挥着重要的作用。

本文将从如何定量体现模型与日志之间的拟合度以及如何定量地评测流程模型入手，总结介绍了近几年来常规一致性检验算法以及特定应用场景下的近似算法和在线算法的现状，随后还详细论述了近几年来这些算法的研究进展，并指出未来亟需探讨解决的研究问题。

1 流程挖掘中对模型进行评价的指标

在进行流程模型和流程日志之间的一致性检验时，需要对模型与日志中的拟合关系进行量化表示，主要通过4 个方面来展现［29］，拟做阐释分述如下。

（1）Fitness：最常用的衡量指标，表现流程模型对流程日志的重现能力。重现能力越强，Fitness指标越高。

（2）Precision：用于衡量模型的精度。模型越复杂，精度越高，但是为了防止过拟合现象，通常需要和Simplicity一起来得到综合评价。

（3）Generalization：用于衡量模型的泛化度。主要是针对由统一模型产生的非训练数据，检测模型对这些数据的辨别能力。

（4）Simplicity：用于衡量模型的简化程度。主要是为了防止过拟合现象的产生，在考虑模型的前3 个指标的同时，同时也要兼顾模型的复杂程度（简化程度）。

2 一致性检验算法综述

目前常见的一致性检验算法主要可以分为3类：基于token 重演的一致性检验算法，基于日志中活动行为模型的一致性检验算法和基于模型和日志对齐的一致性检验算法。

2008年，文献［30］较早地提出了一种一致性检验的方案。根据fitness指标和适当性（行为的适当性与结构的适当性）来对业务流程是否按照合理的模型执行做出量化表示，自此之后依据fitness指标来衡量模型与业务流程之间的拟合程度逐渐成为一种业界认可的通用方案。

目前，常见的一致性检验算法主要是考虑模型的Fitness指标，最早提出的方案就是直接在模型中模拟重现日志的生成路径，通过重现的过程来判断日志数据与模型之间的拟合度、即Token Based Replay。这种方式旨在针对用Petri Net 来表示的模型去进行一致性检验。主要步骤是：基于Petri Net中的转移函数，先将日志解析为token 的形式，然后依据转移函数来重现这些token 序列，通过统计重现后的missing tokens、consumed tokens、remaining tokens 和produced tokens 等各类别中的数量，由此来计算fitness指标。这种基于Token 重演的算法在甫一面世时，取得了较为明显的效果，但是近些年来，随着各种一致性检验算法的相继提出，已逐渐退出了公众视野。但要指出的是，当日志中存在较长流程时，这种算法相较于其他算法也仍然有着更高的稳定性。接下来，Alessandro 等人［31］针对token based replay 算法进行优化，通过使用后向的重现算法再加上缓存日志后缀的方案缓解了token based replay 这种方案的运行速度，同时选用决策树来诊断问题的根源，提高诊断信息的可解释性。

基于日志中活动行为模式的一致性检验算法在最近一段时间比较引发关注的是Log Skeleton 算法［32］。该算法最初用于过程发现，当时的学术界普遍认同“一个表现能力较强的模型，其fitness指标应该较高”，即能够准确判断出日志数据中trace 是否是由该模型产生。 Log Skeleton 算法认为可以准确地完成日志数据的分类任务的模型，具备更强的模型表达能力。通过获取日志数据中活动之间的关系来表现流程模型：equivalence，always after，always before，directly follow 和never together。 Log Skeleton算法的核心更像是一个分类的任务，算法的结果类似于提取日志之中的共性特征。因此，在开源库pm4py［33］一致性检验模块中，通过对比流程模型和流程日志之间关系的差异计算fitness指标。这种检测方法较为简单，同时具备一定的可解释性，但是这种做法默认所有的活动之间的关联关系都是等价的，可能会导致不同重要程度的日志活动出现偏差时对整体流程上产生影响的差异。王媛媛等人［34］提出一种基于扩展足迹矩阵的一致性检验的方案，主要是针对Petri Net 表示出的模型，获取日志以及模型的扩展足迹矩阵，矩阵中的元素表示活动之间的扩展次序关系，这些扩展关系包括直接跟随关系、直接因果关系、间接因果关系、排他（互斥）关系和并行关系，通过对模型的重现，可以得到模型的扩展足迹矩阵，将日志的扩展足迹矩阵和模型的扩展足迹矩阵进行对比，通过2 个矩阵中的差异来表示偏差的出现，这种思想类似于前面提到的基于Log Skeleton 的一致性检验算法，也是具备较强的可解释性，基于得到的扩展足迹矩阵也可以较为方便地进行模型的修正。

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

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］提出一种较为高效地计算对齐过程中偏差定位的算法，提高了在线对齐算法的性能。现已证实这种基于对齐的各种算法具备较高的准确率，但是尽管研究中对算法进行了优化，以及提高了算法的运行效率，但是与前文提及的算法相比，在运行效率方面却仍未表现出明显优势。除此之外，这种算法也仍然面临着冷启动的问题有待进一步的研究解决。