凡得热点

Inductive Miner(归纳式挖掘）是一种基于流程树的算法，并在其基础上衍生了各种变体算法，比如Indcutive Miner-Infrequency，Inductive Miner-Lifecycle等。接下来，我们将详细地介绍这一基本的Inductive Miner算法。

1 背景介绍

▼ 已有流程发现算法比较

上表总结了之前已有的流程发现算法的特点。从表中可以看出，现有的流程发现算法不能保证在有限的时间内(没有死锁和其他异常)得到的流程模型是fitting(表示所有的行为)和soundness(合理的)。

因此，需一个更综合的方法保证合理性和拟合度，并且在有限的时间内得到块结构(block-structured)模型，Inductive Miner算法应用而生。

2 思想介绍

Indcutive Miner算法主要采用分而治之的思想，将发现一个日志L的过程模型问题分解为发现通过拆分日志L得到n个子日志的n个子过程模型问题。其具体的做法是如下： a)选择最适合日志L的切分运算(顺序、并发、循环、排他)；b)将日志L中的活动通过切分运算划分为不相交的集合；c)使用这些集合将日志L拆分为子日志L1, L2,…, Ln。通过上述步骤递归挖掘这些子日志L1, L2,…, Ln，直到子日志只包含一个活动。

在介绍算法之前，我们先引入四种切分运算符，分别如下：

 

 

 

 

 

上图中的每个小圆圈代表每个子流程，四种运算符的详细规则如下：

排他运算符的规则为一个子流程A与另一个子流程B两个之间没有任何关联，一个子流程A中的活动的后继活动不能在另一个子流程B中，一个子流程B中的活动的后继活动不能在另一个子流程A中，两者互不关联；

顺序运算符的规则为从一个子流程A到另一个子流程B有出边，但是无入边，两者总体上只有一方到另一方;

并发运算符的规则为一个子流程A既有到另一个子流程的出边，也有另一个子流程B到这个子流程A的入边。两者彼此交叉，并行存在;

循环运算符的规则为一个活动从子流程A出发，到达另一个子流程B中，再由B重现回到A。总结为起于此终于此。

3 主要步骤

1.将事件日志转化为直接跟随活动图(DFG）

假设存在事件日志L = {<a, b, c>,<a,c,b>,<a,d,e>,<a,d,e,f,d,e>},将其转化为直接跟随活动关系图如下：

 

2 .切分DFG

 

其中图中a,b,c,d依次进行的切分操作为顺序切分，排他切分，并发切分，循环切分用流程语言可表示为：

 

 

3 .将上述过程转化为流程树语言

发现模型： M= →(a, X(∧(b, c), Q (→ (d,e),f)))，其中Q表示循环运算符。

最终生成的流程树如下图所示：

4.流程树转化为Petri网

按照上述流程树转化为Petri网规则转化第3步流程树为下述Petri网：

4 总结

Inductive Miner算法得到的流程模型能够完全拟合事件日志中的行为，但还存在以下不足：

（1）没有考虑事件日志中直接跟随活动关系的频次；

（2） 生成的模型中不可见变迁行为增多，使得流程模型精确度降低。