简介

背景

问题引入

在我们的日常生活中，业务系统随处可见，例如医疗系统、自动控制系统等等。这些系统中的工作日志记录了流程活动中各个阶段的运行时间和关联数据，包含了业务活动实际运转的流程。充分挖掘并合理使用这些信息，能够提高商业自动化的运行效率，降低企业运营成本。

由于传统的流程设计方法过分依赖于理想化的流程，因此在流水线瓶颈、工作环境等因素的影响下，日常的业务可能无法按照理想流程进行 [1]。

定义

流程挖掘的核心是从管理系统内的事件日志中提取信息，从而去发现、监控和改进真实流程（即非假定流程）。—— From Springer Link 流程挖掘是指从商业活动的保存的数据中提取结构化、可解释的流程的方法。[1]

研究领域

流程挖掘主要分为三个方面 [5]：

流程发现（discovery）：基于事件日志获取知识，构建流程模型；
一致性检查（conformance）：检验事件日志和流程模型的一致性，发现真实流程中存在的问题，并分析原因；
流程优化（enhancement）：优化流程设计，包括工作时间、等待时间、瓶颈等，提高流程的流畅程度，进而提高业务效率。

其中，流程发现是流程挖掘领域中最受关注的方向。接下来分别介绍上述三个方面，并介绍几种常用的流程发现算法。

流程发现

流程发现需要解决的问题和研究挑战如下：

解决问题：流程如何执行？高频路径是什么？路径中各个事件是怎样分布的？
研究挑战：多流程噪声、多重复事件、多数据类型、多进程变体。在实践中，以上常见情况为流程发现带来了挑战。

这里简单介绍几种经典的流程发现的方法。

Alpha Miner [6]

Alpha Miner 是第一个在事件日志与流程模型之间架起桥梁的算法。输入事件日志，输出 Petri 网模型。基于给定日志，确定事件之间的顺序关系（足迹，footprint），包括紧邻$>L$ 、因果$\rightarrow_L$ 、无关 $# L$、并行并行 $|_L$ 四种基本关系，进而还原事件流程。

紧邻：x>y 当且仅当存在一条轨迹使得活动 x 后面紧跟着 y；
因果：x->y 当且仅当 x>y 且非 y>x；
并行：x||y 当且仅当 x>y 且 y>x；
无关：x#y 当且仅当非 x>y 且非 y>x.

例如在日志 L= {, , } 中，其中的紧邻关系有 a>b, b>c, c>d, a>c, c>b, b>d, a>e, e>d；进而绘制 petri net，如下图所示：

Alpha Miner 方法简单，可以通过理解流程步骤之间的关系和因果关系，完全基于事件日志构建流程模型，能够处理发现流程中存在的并发。例如下图，Alpha Miner 能够找出从 A 到 C 的流程，并将它们作为单独的轨迹，然后，利用它们之间的关系将它们重组到一个模型中。

但因为其在特殊情况下受限的性能，包括处理噪声、不频繁/不可见/重名任务（例如上图中会把两个轨迹标记为独立的事件）、复杂路由结构（例如短循环 e.g. ）等，同时没有考虑事件频率，无法获取长距离依赖。在实践中并不适用。

Heuristic miner [7]

Heuristic Miner 是 Alpha Miner 的改进版本，被应用于挖掘噪声数据中的流程行为。

该方法包括三个步骤：

根据事件日志统计依赖（紧邻关系）频次，并计算活动之间的依赖度量（包括短循环）；

这里直接引用 alpha miner 中紧邻的概念。给定一个事件日志 L = [ 5 , 10 , 10 , 1 , 1 , 10 , 2 , 1 ]，其中 <> 里表示的是活动序列即轨迹，后面的数字表示轨迹的频次。那么，在事件日志 L 中的直接跟随关系集合为 L = {(a,e), (a,b), (b,c), (c,e), (a,c), (c,b), (b,e), (a,d), (d,e), (d,d)}。再根据直接跟随关系集合中对应的频次，建立一个依赖/频次表，如下所示：

进而计算依赖度量，公式如下：
根据频次表和依赖度量建立依赖图，根据设定阈值除去活动连接，以删去噪声；
建立因果矩阵，处理不可观测任务（AND/XOR），处理长距离依赖关系（例如在下面的例子中，在执行活动 c 之后，存在活动 d 和活动 e 之间的选择。然而，d 和 e 之间的选择是由之前的 a 和 b 之间的选择“控制”的。）。

相比于 Alpha Miner，Heuristic Miner 利用了事务的频率信息，对噪声敏感，能够处理长度为 1 和长度为 2 的短循环；处理 AND/XOR （即完全依赖/完全独立）和不可观测任务；处理长距离依赖关系。由于其良好的适用性，Heuristic Miner 是目前被使用最广泛的流程挖掘方法。缺点在于，由于需要设定阈值来决定连接，不能较好地处理非常见路径。

[8] 扩展了 Heuristics Miner，提出了 Fodina Miner，该方法对噪声具有鲁棒性，能够识别重复活动，同时允许插入用户选择以优化发现流程，它避免了 Heuristics Miner 产生的某些类型的死锁。然而，当应用于现实生活中的事件日志时，Fodina Miner 生成的模型往往大型且不可靠。

Genetic Miner [9]

Genetic Miner 主要动机是从这种算法执行的全局搜索中获益。通过选择支持这些结构的内部表示来解决这些非平凡的结构，噪声问题由遗传算法解决。这些算法对噪声具有鲁棒性。遗传方法的主要挑战是定义一个好的适应度度量，因为它指导遗传算法执行的全局搜索。

Genetic Miner 分为以下四步：

初始化族群：随机创建初始群体，群体中每一个个体是指一个流程模型，在每一代中可能有成百上千的个体；
选择：计算每个个体的适应度，适应度函数决定了与日志相关的个体质量，具有最高的适应度值的流程模型将会被移动到下一代，适应度低的模型被淘汰。
繁殖：使用选出的父代个体去创造新的后代，使用两种遗传操作：交叉和变异。
结束（迭代）：利用上一代的优势模型和繁殖出的后代创造出新的一代，计算这一代中模型的适应度。迭代下去，直到找到一个令人满意的解决方案即具有期望适应度的模型。

Genetic Miner 鲁棒性强，能够处理噪声和不完备性，但是由于引入了模型评估指标，使得模型发现缓慢，甚至不能得到满意的模型。

在 Genetic Miner 的基础上，[10] 又提出了 Evolutionary Miner，主要的区别在使用了流程树来代替因果依赖网，适应度计算也是在流程树上发生，并综合考虑了四个质量维度，从而更好地发现流程模型。

Fuzzy Miner [11]

在日志中存在大量相关的事件，例如任务标签中存在句法或语义相似度较高的词汇；流程拓扑的结构相关性；或是位置相关的活动等等，对于非结构化的数据，需要引入聚类进行处理。Fuzzy Miner 首次将流程挖掘和聚簇结合，包括以下操作：

删除不重要的边；

引入两种度量：significance(sign)，衡量事件的重要性，常用事件发生频率；correlation(corr)，衡量两个事件的相关性，常用紧邻频率或事件相似性。综合考量二者$u t i l(A, B)=u r \cdot \operatorname{sig}(A, B)+(1-u r) \cdot \operatorname{cor}(A, B)$ ，正则化后利用阈值co选出重要的边。例如，在下图的实例中，P -> A 和 R -> A 被选出。
将高度相关的节点聚成一个节点，对重要性较低节点（victim node）和重要性较强的节点（cluster node）分别处理：

对于 victim node：
- 找到相关性最高的邻居（即连接的节点）；
- 如果这个邻居是一个集群节点，就把受害者加入这个集群；
- 否则，创建一个新的集群节点，并将当前节点添加为其第一个元素。
对于 cluster node：
- 检查所有的前任或所有的后任是否也是集群节点。
- 如果所有的前任节点或后继节点是集群，则与关联度最高的节点合并，并转到下一个簇。
- 如果集群的前集和后集都包含普通节点，该节点不操作。
- 删除孤立的节点集群。
Fuzzy Miner 基于 ProM 框架，不能转换为其他类型的流程建模语言，如业务流程挖掘符号（BPMN）或业务流程执行语言（BPEL），此外，Fuzzy Miner 方法不能保证模型的合理性。

一致性检查

一致性检查的目的是评估流程模型的质量，有以下标准 [12]：

适应性：模型能够提取出日志中包含的事件；
泛化性：能够接受与之前日志事件相关的类似事件，避免过拟合；
简单：模型应尽可能的简单；
精确：避免引入与使用的日志无关的事件，避免欠拟合；

除了制定评估标准以外，在一致性检查的应用领域，例如流程检测，也受到研究者的广泛关注。二者的区别在于，一致性检测是在事件发生后，对完整的日志进行分析；一致性检测是在事件发生时，利用部分日志进行实时监测。

流程优化

流程优化是利用相关信息对流程模型进行扩展。例如，GPS 系统在会重点关注拥挤的街道，以提供更加便利的路径规划路线。流程挖掘模型通过事件日志中的时间戳，利用机器学习方法和统计数据优化流程模型，提升效率 [12]。

在分析模型的过程中，流程优化主要思考以下方面：case 平均吞吐时间、转换和驻留时间、流程瓶颈、最重要的活动和资源、工作时间和等待时间。

应用

流程挖掘被广泛应用于诸多领域。据文献 [21] 中的统计数据显示，在 2002~2019 年流程挖掘应用相关的出版物中，超过 28% 的文献为医疗服务领域。占比最高的六个领域分别为：医疗服务、信息技术、制造业、教育、金融、物流，占比之和达到近 80%。

数据集

Event Data

链接：http://www.processmining.org/event-data.html

简介：包含 BPI（Business Process Intelligence）Challenge 2011~2019 的所有竞赛数据，包括 .csv 和 .xes 两种格式，应用场景和竞赛名如下：

Hospital Billing

链接：https://data.4tu.nl/articles/dataset/Hospital_Billing_-_Event_Log/12705113/1

论文：https://doi.org/10.1007/978-3-319-59536-8_34

简介：该数据从某地区医院 ERP 系统的财务模块中获取。事件日志是三年内记录的流程实例的随机样本，共有 10 万个 trace ，包含与医院提供的医疗服务计费相关的事件，每个 trace 记录了为医疗服务缴费而执行的活动，不包含有关医院提供的实际医疗服务的信息，每个日志中包含多个属性，如流程的“state”、“caseType”等。

Road Traffic Fine Management Process

链接：https://data.4tu.nl/articles/dataset/Road_Traffic_Fine_Management_Process/12683249/1

论文：https://doi.org/10.1007/s00607-015-0441-1

简介：管理道路交通罚款的信息系统的真实事件日志。

Environmental permit application process (‘WABO’)

链接：https://data.4tu.nl/articles/dataset/Environmental_permit_application_process_WABO_CoSeLoG_project_Municipality_5/12714542

论文：http://repository.tue.nl/780920

简介：该数据来自 NWO 项目编号 638.001.211 下执行的 CoSeLoG 项目，这些日志记录了在荷兰的 5 个不同的匿名城市中建筑许可申请流程的执行情况。这些流程的记录具有可类比性，不同事件日志中的活动标签指的是在五个城市中执行的相同活动。事件日志包含关于案例/跟踪和事件级别的额外数据。总共有 16 个跟踪级别属性，其中包括许可证组成的部分、计划的结束日期和负责的参与者。事件属性包含活动标签、执行的时间戳和涉及的人力资源。此外，还包括有关计划执行日期和到期日期的信息。另外，事件可能包含额外的流程数据。一些属性包含荷兰语术语和短语。

NASA Crew Exploration Vehicle (CEV) Software Event Log

链接：https://data.4tu.nl/articles/dataset/NASA_Crew_Exploration_Vehicle_CEV_Software_Event_Log/12696995

论文：https://arxiv.org/abs/1710.09323

简介：可扩展事件流（XES）软件事件日志是通过使用现有工具对 NASA 的乘员探索飞行器（CEV）进行扫描获得的。该事件日志包含方法调用级别的事件，描述了 CEV 详尽单元测试套件的一次运行，并记录下来。该日志中的生命周期信息与方法调用（start）和返回（complete）相对应，并捕获了一个方法调用的层次。数据集还附上了这个事件日志的一个稍加预处理的变体，其中每个单元测试方法的执行被表示为一个单独的 trace。

课程资源

参考文献

[1] van der Aalst, W., & Weijters, A. (2004). Process mining: A research agenda. Computers in Industry, 53 (3), 231–244.

[2] dos Santos Garcia, C., Meincheim, A., Junior, E. R. F., Dallagassa, M. R., Sato, D. M. V., Carvalho, D. R., … & Scalabrin, E. E. (2019). Process mining techniques and applications–A systematic mapping study. Expert Systems with Applications, 133, 260-295.

[3] van der Aalst, W. (2012a). Process mining: Overview and opportunities. ACM Transactions on Management Information Systems, 3 (2), 1–17.

[4] van der Aalst, W. M., & Carmona, J. (2022). Process Mining Handbook.

[5] Rosa, M. L., Aalst, W. M. P. V. D., Dumas, M., & Milani, F. P. (2017). Business process variability modeling: A survey. ACM Comput. Surv., 50 (1), 2:1–2:45.

[6] van der Aalst, W., Weijters, T., & Maruster, L. (2004). Workflow mining: Discovering process models from event logs. IEEE Transactions on Knowledge and Data Engineering, 16 (9), 1128–1142.

[7] Weijters, A. J. M. M., & van der Aalst, W. M. P. (2003). Rediscovering workflow models from event-based data using Little Thumb. Integrated Computer-Aided Engineering, 10(2), 151-162.

[8] vanden Broucke, S. K., & De Weerdt, J. (2017). Fodina: A robust and flexible heuristic process discovery technique. decision support systems, 100, 109-118.

[9] van der Aalst, W. M., Medeiros, A. K., & Weijters, A. J. (2005, June). Genetic process mining. In International conference on application and theory of petri nets (pp. 48-69). Springer, Berlin, Heidelberg.

[10] Márquez-Chamorro, A. E., Resinas, M., Ruiz-Cortés, A., & Toro, M. (2017). Run-time prediction of business process indicators using evolutionary decision rules. Expert Systems with Applications, 87 , 1–14.

[11] Günther, C. W., & van der Aalst, W. M. P. (2007). Fuzzy mining –Adaptive process simplification based on multi-perspective metrics. In Lecture notes in computer science (pp. 328–343). Springer Berlin Heidelberg.

[12] van der Aalst, W. (2016). Process mining: Data science in action . Springer Berlin Heidelberg.

RexKing6's Note

流程/过程挖掘

简介

背景