Heuristic Miner（启发式挖掘算法）是在2003年被A.J.M.M. Weijters 所提出来，并在2006年进行完善，是一种继Alpha算法之后又一经典的流程发现算法，接下来，我们将详细地介绍这一算法。
01 背景介绍
现代的工作流管理系统是由显式的流程模型驱动的，也就是说，为了制定给定的工作流流程，需要一个完全指定的工作流设计。 创建工作流设计是一个复杂的耗时的过程，通常，实际的工作流过程和管理层所感知的过程之间存在差异。 因此，提出了一种可重新发现(rediscovering)工作流模型的技术。 该技术使用工作流日志来发现实际执行的工作流过程。 工作流日志包含有关发生事件的信息。 我们假设这些事件是完全有序的，每个事件指的是单个案例中正在执行的一个任务。 这些信息可以很容易地从业务信息系统中提取出来。
已有提出的流程发现算法如Alpha算法是不能够处理噪声的，对短循环和长循环也无法处理。 为此，一种更为先进的Heuristic Miner算法被提出，用于解决这些问题。
02 算法介绍
算法大致分为四个步骤： （1）构造一个依赖/频次表(D/F表);（2）建立活动的依赖度量表; (3)根据依赖/频次表和活动的依赖度量表建立依赖图;（4）将依赖图转化为WF-Net。
1 构建一个依赖/频次表
这里使用了Alpha算法中定义的四种基本关系之一的直接跟随关系(也叫紧邻关系)，定义如下：
再根据直接跟随关系集合中对应的频次，建立一个依赖/频次表，如下所示。
2 建立活动的依赖度量表
首先，给出了依赖度量的定义，如下所示。
下表中展示了事件日志L的依赖度量。
3 根据依赖/频次表和活动的依赖度量表建立依赖图
根据步骤1的依赖/频次表和步骤2的活动依赖度量表建立依赖图，下面2图表示了在不同阈值设置下生成的依赖图（左图设置阈值为0.7，右图设置阈值为0.9）。
4 将依赖图转化为WF-Net
将步骤3中的两个依赖图转化为Petri网如下两图所示。
以上为Heuristic Miner算法如何从一个事件日志转化为Petri网流程模型的简单示例。 下面我们具体来看看Heuristic Miner算法是怎么解决之前流程发现算法存在的问题。
03 解决问题
1噪声的处理(阈值参数设置)
通过第2部分中的算法流程，我们可以完成对噪声处理。 但是，在实际业务流程中，我们不知道轨迹<AD>是否为真的噪声还是低频率模式，为了处理这个问题，Heuristic Miner中设置了三个阈值参数：
(1)依赖阈值(the Dependency threshold)；
(2) 积极观察阈值(the Positive observations threshold);
(3)相对最佳阈值(the Relative to best threshold).
通过这些阈值，我们认为（i）依赖性度量高于依赖性阈值，以及（ii）频次高于积极观察阈值的活动的依赖关系，以及（iii）活动依赖度量与“最佳”依赖性度量的差值小于相对最佳阈值。 在实际情况下（具有数千条轨迹、低频轨迹和一些噪声的事件日志），这些参数对于了解流程的主要行为或细节非常有用。
2 处理短循环
对于长度为1的短循环，采用下方公式来判断活动是否存在自循环。
对于长度为2的短循环，采用下方公式来判断是否存在长度为2的短循环。
特别注意 ： 一个长度为1的循环C与一个并发流程A相结合，可以很容易地生成类似CAC的模式。 为了防止误判断为长度为2的短循环，我们先计算下方公式，然后再计算上方公式。 这样，在搜索长度为2的循环之前，我们将捕获长度为1的循环构造中的所有活动。
3 处理AND/XOR-split/join和不可观测活动
上图中所示的事件日志L1=[<A,B,C,D>,<A,B,C,D>,<A,C,B,D>,<A,C,B,D>,<A,E,D]的流程模型是一个Petri网。
在执行第一个任务A之后，可以选择是同时执行B和C（即并行或以任何顺序），或者只执行活动E。 如果并行执行B和C，就需要添加了两个不可观测（non-observable）的活动（AND-split 和AND-join）,注： 不可观测变迁也可叫作无声变迁、静默变迁等。 挖掘这些不可观测的活动很困难，因为它们不存在于事件日志中。
为了避免对不可观测进行显式建模。 在HeuristicsMiner中，我们不使用Petri网来表示流程模型，而是使用所谓的因果矩阵(Causal Matrix)。 作为一个例子，我们展示了上图的Petri网到因果矩阵表示的转换,下图为因果矩阵。
通过因果矩阵可以完成对不可观测活动的识别，此外，通过下方公式完成对AND-split和AND-XOR的区分。
4 处理长距离依赖关系
上图显示了一个长距离依赖关系构造。 在执行活动D之后，存在活动E和活动F之间的选择。 然而，E和F之间的选择是由之前的B和C之间的选择“控制”的。 显然，这种非局部行为是很难挖掘的，因为主要基于直接跟随关系(a>Wb)的挖掘方法。 Heuristics Miner中定义的a>>>W b关系将很好地挖掘出此关系，定义如下：
04 总结
Heuristic Miner算法将轨迹的频次考虑在内，具有以下优势：
（1）对噪声敏感；
（2） 能够处理长度为1和长度为2的短循环；
（3）处理AND/XOR-split/join 和不可观测活动；
（4）处理长距离依赖关系。
