【过程挖掘算法6】Split Miner

Split Miner是继Inductive Miner又一先进的过程挖掘算法，是在2018年由Adriano Augusto提出来的。接下来，我们将详细地介绍这一算法。

 1.背景介绍

        从事件日志中自动发现流程模型的问题在过去二十年中得到了深入的研究。尽管有丰富的应用领域，但最先进的模型发现算法比如Inductive Miner，当应用于真实的业务流程时，会避免两种反复出现的缺陷：（i）产生大量的类似意大利面一样的模型；（ii）产生的流程模型要么不适合事件日志（低拟合度），要么过于概括（低精度）。事实证明，在这些质量维度之间以稳健且可扩展的方式进行权衡是难以实现的。

        本文介绍了一种自动化的流程发现方法，鉴于对发现分裂网关(split gateways)的关注，提出的方法被称为Split Miner，它可以生成简单的流程模型，具有较低的复杂度和一致的高且平衡的适应度和精度，同时实现比最先进的方法更快的执行时间。Split Miner结合了一种新的方法来过滤由事件日志产生的直接跟随关系图(DFG），以及一种识别分割网关组合的方法，该组合能够准确地捕获DFG中相邻节点之间的并发性、冲突和因果关系。SplitMiner也是一种自动进程发现方法，可以保证生成无死锁的并发进程模型，同时不限于生成块结构的进程模型。

2. Split Miner算法介绍

该算法的大致流程如下图所示，以一个事件日志作为输入，返回一个BPMN模型，共分为6步。

1. 首先构造一个DFG，与启发式挖掘算法(Heuristic Miner)不同的是，Split Miner算法不会立即过滤DFG，它分析去删除其中的自循环和短循环关系，并发现两个活动之间的同步关(Concurrency）。
2. 在DFG中，同步关系为存在两个活动之间，例如a和b，显示为两个弧：一个从a到另一个从b,和从b到a，这意味着因果关系和并发性是混合的。为了解决这个问题，每当发现a和b之间可能存在类似同步关系时，就会从DFG中删除这两个任务之间的弧，这被称为：(pruned DFG)修剪DFG（PDFG）。
3. 在第三步中，在PDFG上应用过滤算法，以达到平衡适应度和精度，保持较低的控制流复杂度。
4. 在第四步中，为过滤后的PDFG中具有多个输出弧的每个活动发现拆分网关(split gateways)。
5. 类似地，在第五步中，从具有多个传入弧的任务中发现join网关。
6. 最后，如果发现任何一个OR-joins连接，它们将被删除（只要可能）。

2.1 删除自循环和短循环关系

在DFG中如果存在自循环，则活动a后面直接跟随活动a，则a存在自循环。

给定两个活动a和b，如果满足以下条件，则存在一个短循环：

条件1保证了活动a、b不存在自循环， 实际上，如果我们考虑一个模型，它包含一个自循环a和一个正常任务b之间的并发性，那么在流程执行期间记录的轨迹可能包含子跟踪<a、 b，a>（。放弃满足条件1的后一种情况，我们使用条件2来确保活动a，b是存在短循环的。

自循环从DFG中移除，并在最后在输出BPMN模型中恢复。

2.2 修剪DFG（PDFG）

给定一个DFG和两个任务a、b，如果下列三个条件成立：假设a和b是同步的（a||b）：

条件3实际上描述了一个a||b，边e1=（a，b）和e2=（b，a）的存在意味着a和b可以以任何顺序出现。然而，这不足以假设并发性，因为这种关系可能在三种情况下成立：（i）a和b形成一个短循环；（ii）a和b同时存在；或者（iii）e1或e2非常罕见，因此可以忽略。条件4避免了情况（i）。

条件5背后的思想是，两个任务同时进行，|a→ b |和| b→ a |应尽可能接近，即两个交错的观察频率相似。因此，ε的值越小，并发关系就必须越平衡才能被捕获。反过来，设置ε接近于1将捕获所有可能的并发关系。

无论何时找到a||b、 我们将e1和e2从E中移除，因为不存在因果关系，而是存在并发性。另一方面，如果我们发现e1或e2代表不频繁的行为，我们会删除两条边中频率最低的一条。这一步的输出是一个修剪过的DFG。

2.3 过滤算法

       为了从PDFG导出一个合理、简单和准确的BPMN过程模型，后者必须满足三个特性。首先，PDFG的每个节点必须位于从单个起始节点（源）到单个结束节点（接收器）的路径上。此属性对于确保可靠的流程模型（无死锁和不缺少同步）是必需的。其次，对于每个节点，其从source到sink的路径必须是具有最大容量的路径。在我们的上下文中，路径的容量是路径最不频繁边的频率。此属性旨在最大化适应度，因为路径的容量与可在该路径上重放的记录道数匹配。第三，PDFG的边数必须最小。该属性使CFC最小化，精度最大，因为边缘数与分支因子（用于计算CFC）和允许行为量成正比。

        为了满足这三个特性，设计了Dijkstra最短路径算法的变体.Dijkstra算法和我们的算法之间的主要区别如下：（i）在探索图的过程中，我们不传播路径的长度，而是传播路径的容量；（ii）Dijkstra解决了最小化问题，而我们解决了最大化问题。此外，由于我们希望确保每个节点都可以从源到达，并且可以到达sink（即在从源到接收器的路径上），因此我们执行了双宽度优先探索：向前（源到接收器）和向后（接收器到源）。在正向探索过程中，对于PDFG的每个节点，我们会发现其最大源到节点容量（正向容量），以及授予此类正向容量的传入边缘（最佳传入边缘）。同样，在反向探索过程中，我们发现最大节点到接收器容量（反向容量）和输出边（最佳输出边）。通过该算法，我们满足了第一和第二个属性，并对PDFG中保留的最大边数设置了一个限制，即始终小于2 | T |（即每个节点最多有一条传入边和一条传出边）。然而，有限的边数可能会减少最终模型可以重播的行为量，从而降低其适应度。为了在适应度和精度之间达成平衡，我们引入了一个频率阈值，让用户平衡这两个指标。精确地说，我们计算每个节点最频繁的传入和传出边缘频率的η百分位数，并保留那些频率超过阈值的边缘。重要的是要注意，百分位数并没有占据Ep中所有边的频率，否则我们只会保留所有边的η百分比。

2.4-2.5 过滤后的PDFG到BPMN流程模型

        我们分别将活动集和边集初始化为过滤后的PDFG的节点集，以及过滤后的PDFG的边集加上两条新边：一条连接开始事件和DFG的前源，另一条连接DFG的前接收器和结束事件（第6行）。最后，创建一组空的网关，将通过以下三个步骤进行填充：拆分发现(split discovery)、加入发现(join discovery)和ORs替换。

拆分发现：

给定一个PDFG=(T, Ep) 和一个节点a

定义 后继节点集 successor，定义 future和cover。一个后继结点的future集合中的元素为该后继节点与其他后继节点存在并发关系的活动。如果后继节点是一个活动，那个该后继节点的cover集合中的元素就是是活动本身；如果后继节点是一个网关，那么它的cover就是在遍历网关之后才遍历的一组任务。

•  XOR-Split

当对比完之后，如果X集合中后继节点的数≥2时，为X集合中的后继节点添加XOR-split

• AND-Split

 加入发现：

共有单入口-单出口片段，single-entry single-exit (SESE) fragments

1.trivial fragment：由一条边组成

2.polygon：一系列片段 （ a polygon is a sequence of fragments ）

3.bound: 所有子片段共享两个公共节点的片段，

            一个是bound的入口，另一个是bound的出口；

4.rigid: 不属于上述类型的片段

ORs替换：

这里不做赘述。

3.工具插件

将Split Miner（以下简称SM）实现为一个独立的Java应用程序。该工具将MXML或XES格式的事件日志以及阈值作为输入，并输出一个BPMN过程模型。

参考链接为：http://apromore.org/platform/tools.

运行界面插件图为：

4.总结

Split Miner，它可以生成简单的流程模型，具有较低的复杂度和一致的高且平衡的适应度和精度，同时实现比最先进的方法更快的执行时间。

Split Miner结合了一种新的方法来过滤由事件日志产生的直接跟随关系图(DFG），以及一种识别分割网关组合的方法，该组合能够准确地捕获DFG中相邻节点之间的并发性、冲突和因果关系。

SplitMiner也是一种自动进程发现方法，可以保证生成无死锁的并发进程模型，同时不限于生成块结构的进程模型。

参考文献：Augusto A, Conforti R, Dumas M, et al. Split miner: automated discovery of accurate and simple business process models from event logs[J]. Knowledge and Information Systems, 2019, 59(2): 251-284.

下一讲将介绍最近将对已有的过程挖掘算法进行总结。

如需进行相关的了解或者交流，欢迎私信或者加入QQ群：