凡得热点

1 背景介绍

现代的工作流管理系统是由显式的流程模型驱动的，也就是说，为了制定给定的工作流流程，需要一个完全指定的工作流设计。 创建工作流设计是一个复杂的耗时的过程，通常，实际的工作流过程和管理层所感知的过程之间存在差异。 因此，提出了一种可重新发现(rediscovering)工作流模型的技术。 该技术使用工作流日志来发现实际执行的工作流过程。 工作流日志包含有关发生事件的信息。 我们假设这些事件是完全有序的，每个事件指的是单个案例中正在执行的一个任务。 这些信息可以很容易地从业务信息系统中提取出来。

已有提出的流程发现算法如Alpha算法是不能够处理噪声的，对短循环和长循环也无法处理。 为此，一种更为先进的Heuristic Miner算法被提出，用于解决这些问题。

2 算法介绍

算法大致分为四个步骤： （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算法是怎么解决之前流程发现算法存在的问题。

3 解决问题

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关系将很好地挖掘出此关系，定义如下：

4 总结

Heuristic Miner算法将轨迹的频次考虑在内，具有以下优势：

（1）对噪声敏感；

（2） 能够处理长度为1和长度为2的短循环；

（3）处理AND/XOR-split/join 和不可观测活动；

（4）处理长距离依赖关系。