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

1. 背景介绍

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

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

为了获得80%的模型，传统的方法是在发现模型之前对日志进行全局过滤，这种方法很难识别不频繁的行为，可能产生不理想的流程模型。

因此，一个能快速过滤不常见行为并发现合理的80%流程模型的流程发现算法Inductive Miner-Infrequent(IMi)应运而生。其主要思想是：在IM的所有步骤中引入了不常见行为过滤器，以便对不频繁行为进行局部过滤。

2.算法介绍

在应用IM算法时，事件日志中的轨迹和事件频率被IM忽略，但被IMi考虑在内，以区分频繁和不频繁的行为。为此，IMi算法需要预先设定一个参数K，K为用户设置的过滤阈值，用于区分频繁和不频繁的行为。该方法首先不改变地应用IM算法的步骤。只有当IM算法操作失败时将返回一个花型模型时，才会应用过滤器。具体而言，IMi算法包括在以下三个步骤中应用过滤器：

(1)操作符上的过滤器和切割选择步骤；(2)基本案例上的过滤器；(3)日志分割上的过滤器。

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

(1) 启发式方法过滤

L₁=[áa, b, c, a, b, eñ⁵⁰, áa, b, f, eñ¹⁰⁰, ád, e, fñ¹⁰⁰, ád, f, eñ¹⁰⁰,ád, e, d, fñ¹]

说明：与Heuristic Miner中使用方法类似，IMi对直接跟随图进行过滤，使其仅包含最频繁的边。与e的其他输出边相比，边（e，d）相对不频繁，所以边<e,d>被过滤掉。如果一个节点的输出边的频率小于该节点最强输出边的频率的k倍，则该节点的输出边太不频繁。在切割×、→和循环之前，在IMi中过滤掉所有不常见的边被过滤掉。

图a 带有一条不频繁边的直接跟随图，黑色虚线为IM算法中顺序切分运算符的结果，但对(e,d)产生了错误切分

(2)  最终跟随关系图

L₂=[á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)。

图b 直接跟随图

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

图c  最终跟随图

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

在这个例子中，使用最终遵循的图允许IMi处理不频繁的行为。

活动的不频繁发生仍然会增加不频繁边缘的频率，但每个边缘最多增加1。最终跟随图放大了所有其他行为，因此使用最终跟随图→ 切割检测提高了对不频繁行为的鲁棒性。

2.2 基本案例上的过滤器

(1) 单个活动

L₁=[áeñ¹⁰⁰, áañ¹⁰⁰, áa,añ¹⁰⁰, áa, a, añ¹⁰⁰]

L₂=[áeñ¹, áañ¹⁰⁰, áa,añ¹, áa, a, añ¹]

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

在L1中，所有的轨迹都很频繁,花型模型(flower model)显然是最好的选择。然而，在L2中，只有<a>是频繁的，a最能代表频繁的行为。选择任一选项都会影响质量维度：若选择一个花型模型，L2会牺牲精确度；若选择<a>,L1会牺牲拟合度。

只有当日志中a的每个轨迹平均出现次数足够接近1(取决于相对阈值k)时，IMi才会发现a。

(3) 空轨迹

L=[áa,b,dñ¹⁰⁰, áa,c,dñ¹⁰⁰, áa,dñ]

L₁=[ áañ²⁰¹]

L₂=[áeñ¹, ábñ¹⁰⁰, ácñ¹⁰⁰]

L₃=[ádñ²⁰¹]

对于L2: ×(e,...)

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

2.3 日志分割上的过滤器

对于每个操作符，我们描述了可以检测到的违规类型，以及如何通过IMi对其进行过滤，如示例所示。在这些例子中，∑1={a}，∑2={b}是所选择的切割，L1、L2是要创建的子日志。

X: 违反×运算符的行为是在单个轨迹中存在来自多个子树的活动。例如，轨迹t1=áa，a，a，b，a，a，a，añ 包含来自∑1和∑2的活动。∑1解释了大多数活动，是最频繁的。所有不来自∑1的活动都被认为是不频繁的，并被丢弃：áa，a，a，a，a，a，añ∈L1。

→: 违反→ 运算符是指根据子树出现的无序事件。例如，在轨迹t2=áa，a，a，a，b，b，b，a，bñ中，最后一个a出现在b之后，这违反了→. 过滤不频繁的行为是一个优化问题：轨迹将以最少的事件删除方式进行拆分。在t2中，划分áa，a，a，añ∈L1，áb，b，b，bñ∈L2丢弃的事件最少。

∧：并行运算符允许其子树的任何行为序列。因此，没有违反∧的行为，并且在拆分日志时既不能检测到也不能过滤不频繁的行为。

?：违反？运算符是当轨迹不是以循环体开始或结束时：例如？（a，b）被所有不以a开头和结尾的轨迹所违反。对于轨迹的每个这样的无效开头或结尾，一个空轨迹会被添加到L1以增加所得到的模型的拟合度。考虑轨迹t3=áb，a，bñ，则[áeñ², áañ¹]⊆L1和[ábñ²]⊆L2

3.总结

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