Inductive Miner

一、文章速览

1.论文信息

题目-作者-时间-出版社-引用

Leemans, S.J., Fahland, D., & Aalst, W.M. (2013). Discovering Block-Structured Process Models from Event Logs - A Constructive Approach. Petri Nets.

2.背景

现有的流程发现技术不能同时保证可靠性、适应性、重新发现能力和有限的运行时间。

3.方法

提供了一个可扩展的框架，可以从任何给定的日志中发现一组可靠的、符合所观察到的行为的块结构流程模型。采用***分而治之***的方法，根据切将日志分割，得到的n个子日志的n个子过程。

4.概述

B '的工作原理是将日志中的活动划分为多个集合，然后在这些集合上分割日志。selectB '粘附于B，这保证了对任何输入日志的可靠性、适应度和框架的终止性。

基于流程树，具有正确性和健壮性
为了使框架更具可扩展性，使用了一个待给定的首选项功能select来选择首选的日志划分。
此外，还描述了在日志中重新发现一个特殊过程模型所需的最小信息。
然后我们提供一个多项式时间算法从任何给定的日志发现一个合理，拟合，块结构的模型。
返回一个等效于日志的流程模型的语言模型，包括不可见的行为。

5.未来工作

可以删除第6.4节的模型限制2，它要求考虑到长度为2的循环，且满足更强完整性要求的情况下，循环运算符最左边分支的开始和结束活动集必须是不相交的。

此外，在日志上使用另一个增强的完备性假设，可能不需要no-τ限制。

我们计划进行一项经验研究，以将B’算法与现有技术进行比较。可以在构建直接跟随图前。通过过滤直接跟随关系来处理日志中的噪声行为。

二、算法描述（重点在第3小节）

1.基础知识

block-structured workflow net: 块结构的工作流网络是一种分层的工作流网络，可以将其递归分为具有单个入口和出口点的部分。
process trees：流程树是块结构工作流网的紧凑抽象表示。叶子表示活动，而所有其他节点表示运算符。流程树描述一种语言，操作员描述其子树的语言将如何组合。
- 流程树M的递归式定义：
  
  τ是沉默活动(silent activity)。操作符包括’x,→,∧,循环’。循环符打不出，用@代替
- 流程树M的语言L(M)：
- 操作符的语言连接函数(language join function)：
  - ’x,→,@'
  - ’∧’
    
    其中，{t1, · · · , tn}≃表示迹t1到tn是交叉序；f是一个双射函数，将t的每个事件映射到ti中的一个事件，并且t(i)是t的第i个元素。例如<a, c, d, b> ∈ {<a, b>, <c, d>}≃。

2.算法框架B

给定一组日志的过程树运算符，我们定义一个框架B以使用分而治之的方法发现一组过程模型。

（1）给定一个日志L，B搜索将L拆分成较小的日志L1···Ln，这些子日志与运算符combined结合可以再次产生L。（2）然后，它对找到的划分进行递归并返回找到的模型的笛卡尔积。当L不能再分时，递归结束。

**select：**输入日志，返回一组首选的日志划分。

定义1： （存疑）

3.算法实现B’

算法B '，它是框架B的细化，B '避免构造完整的集合P。B '的中心思想是直接根据日志中活动的顺序来计算一个日志划分，在G(L)(直接跟随图directly-follows graph)结构中找到指示“支配”操作符的行为。

日志L = {<a, b, c>, <a, c, b>, <a, d, e>, <a, d, e, f, d, e>}的直接流图：

**排他选择切(exclusive choice cut)：**每个Σi都有一个开始节点和结束节点，Σi≠Σj之间没有边，如图3所示(左)。
**序列切(sequence cut)：**集Σ1···Σn是有序的,任何两个节点a∈Σi，b∈Σj，i< j，都有一个沿G (L)的边的从a到b的路径，但反之不成立，参见图3(上)。
**并行切(parallel cut)：**每个Σi都有一个开始节点和结束节点，Σi、Σj中任取两个元素之间都是互相连接，图3(下)。
循环切(loop cut)：在循环切割中，Σ1具有G(L)的所有起点和所有终点，不同Σi、Σj的节点之间没有边；Σ1和Σi(其中i>1)之间的边要么源于Σ1的结束节点，要么终结于Σ1的开始节点，参见图3(右)。