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

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

（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 的一致性检验算法，也是具备较强的可解释性，基于得到的扩展足迹矩阵也可以较为方便地进行模型的

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

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