【过程发现算法2】Inductive Miner-InFrequency(基于频次的归纳式挖掘算法）

Inductive Miner-Infrequency(基于频次的归纳式挖掘）是在上一节Inductive Miner的基础上进行改进的算法，由sander改进并完善，接下来，我们将详细地介绍这个算法。

1. 背景介绍

关于infrequent的解释：在大多数现实生活中的事件日志中，一些轨迹很少被采用，或者轨迹的不同之处仅在于不经常发生的活动。

如果模型中包含不常见的行为，可能会牺牲简单性(simplicity)，如果模型中排除不常见的行为，可能会牺牲适合性(fitness)。幸运的是，帕累托原则(the Pareto principle,也称为8020规则)通常适用于事件日志。通常，80%的观察到的行为可以用一个模型来解释，这个模型只占描述所有行为所需模型的20%，80%模型展示了过程中的“高速公路”。

为了获得80%的模型，传统的方法是在发现模型之前对日志进行全局过滤。

在本文中，我们提出了这种方法的扩展，称为Inductive Miner - infrequent (IMi)，旨在快速发现一个合理的80%模型。我们在IM的所有步骤中引入了不常见行为过滤器(infrequent behaviour filters)，这样就可以在本地过滤不常见的行为。

2.算法介绍

具体做法：通过在IM的所有步骤中添加不常见的行为过滤器来引入IMi。

轨迹和事件的频率被IM忽略，但被IMi考虑在内，以区分频繁和不频繁的行为.

参数：K：表示用户定义的介于0和1之间的阈值，用于区分频繁和不频繁的行为

1.操作符上的过滤器和切割选择步骤；

2.基本案例上的过滤器

3.日志分割上的过滤器。

2.1  操作符上的过滤器和切割选择步骤

(1)启发式方法过滤

  L1=[<a, b, c, a, b, e, >50, <a, b, f, e >100, <d, e, f >100, <d, f, e >100, <d, e, d, f >1]

 说明：

IMi过滤只包含最频繁边的直接跟随图。如图a所示，与e的其他输出边相比，边(e，d)相对不频繁，所以边<e,d>被过滤掉。如果一个节点的输出边的频率小于该节点最强输出边的频率的k倍，则该节点的输出边太不频繁。在切割×、→和循环之前，在IMi中过滤掉所有不常见的边缘被过滤掉。

(2) 最终跟随关系图

  L2=[<a, c, d, e, b>, <a, b, a, e , d, c>, <a, e, c, b, d>, <a, d, b, c, e >]

说明：如下图b所示， 由于b的所有输出边缘都具有频率1，因此k的任何值都不能过滤边(b，a)。

若采用图c的最终跟随图，则能有效地过滤掉边<b,a>。

类似于弱序关系，IMi使用最终跟随图，这是直接跟随关系的传递闭包:当且仅当a后面跟b在日志中的某处时，才存在边(a，b)。

2.2 基本案例上的过滤器

(1) 单个活动

说明：如图所示， 分割的子过程L1和L2重演一个过程模型，则存在如下问题：

在L1中，所有的轨迹都很频繁,(flower model)花型模型显然是最好的选择。然而，在L2中，只有<a>是频繁的，a最能代表频繁的行为。

选择任一选项都会影响质量维度：若选择<a>,L1会牺牲fitness，若选择一个花型模型，L2会牺牲精度precision。只有当日志每个轨迹中a的平均出现次数足够接近1(取决于相对阈值k)时，IMi才会发现a。

(2) 空轨迹

说明：事件日志L通过分割运算符得到三个子日志L1，L2，L3，子日志L2中存在一条空轨迹，其频次远远小于其他的轨迹的频次，如果不采用过滤，将会影响模型精度。 

2.3 日志分割上的过滤器

 说明：在日志上进行的分割，四个符号依次表示：选择、顺序、并发、循环，在日志层面四种切分运算符满足的格式如图中所示。

3.工具插件

(1)使用prom6运行的插件svn下载地址：prom - Revision 46111: /Packages/InductiveMinerDeprecated/Trunk (tue.nl)

运行插件界面图：

(2）使用pm4py调用Inductive Miner算法的链接地址：

PM4Py - Process Mining for Python (fraunhofer.de)

 4.总结

IMi通过引入了不常见行为过滤器，将轨迹和事件的频次考虑在内，区分频繁和不频繁的行为，在三个层面上应用了行为过滤器，相比于基础的Inductive Miner,更能精准地发现过程模型。

参考文献：Leemans S J J, Fahland D, Van Der Aalst W M P. Discovering block-structured process models from event logs containing infrequent behaviour[C]//International conference on business process management. Springer, Cham, 2013: 66-78.

下一讲将介绍最基础的过程挖掘算法Heuristic Miner（启发式挖掘算法）。

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