一种适用于多样性环境的业务流程挖掘方法

摘要

本发明公开了一种适用于多样性环境的业务流程挖掘方法。主要步骤包括：(1)基于领域知识的日志分类：根据领域知识将日志中的执行实例分组从而形成多个子日志；(2)利用多种挖掘算法准备优质初始种群；(3)基于遗传算法的流程模型整合，得到优化的业务流程模型。本发明的有益效果在于：其通过日志分类能够降低日志的多样性，简化挖掘算法的应用环境，让挖掘算法的特征和优势得到充分发挥；同时，其通过调整适应值函数的权重分布，使得最终的挖掘结果具有较高的综合质量。

说明书

技术领域

本发明属于业务流程的挖掘技术领域，具体的说，涉及一种适用于多样性环境的业务 流程挖掘方法。

背景技术

企业通过扩大、合并和收购等发展后，往往在全国各地拥有诸多子公司。同一类业务 流程在各子公司内独立建立和维护，这常常导致企业内部的同一类业务流程拥有多个不同 的版本，给企业的统一管理带来严峻的挑战。为了统一地构建和管理这些业务流程，需要 从这些不同版本流程的运行日志中重新挖掘出统一的业务流程。

实际上，挖掘统一的业务流程并非易事。尤其是对一个规模庞大的企业来说，由于其 子公司众多，每个子公司内部的环境(如：规章制度)不同，业务流程也各不相同，这将 导致运行日志具有多样性。而现有的流程挖掘算法各有特色，解决某一方面问题的同时， 无法处理另一方面的问题。因此，使用现有的流程挖掘方法无法完美地处理运行日志的多 样性问题。因此，研究一种普适性的能够处理多样性日志的流程挖掘方法成为了一项挑战。

已有的处理多样性日志的业务流程挖掘方法是采用各种聚类方法对运行日志中的执行 实例进行聚类，然后对每一类执行实例采用某种已有的挖掘算法得到相应的流程模型。采 用这种方式获得的流程都是局部的业务流程，如何将它们整合成完整的业务流程仍是有待 解决的问题。而且，对聚类后的每一类执行实例也只是随机使用一种挖掘算法，因此，得 到的未必是最好的业务流程模型。

发明内容

为了克服现有技术的不足，本发明提供一种适用于多样性环境的业务流程挖掘方法。 本发明的方法适用于针对企业内部的同一类业务流程存在大量且各异的不同版本，需要重 新从运行日志中挖掘得到统一的业务流程，以实现业务流程的统一管理的场景；同时本发 明方法也适用于尚不清楚运行日志的特征时，需得到高质量业务流程模型的场景。

本发明方法首先基于领域知识对日志中的执行实例进行分类，从而解决日志多样 性的问题。分类后的子日志能够使后续的流程挖掘算法的特点和优势得以充分发挥。对每 一类子日志施用多种已有的挖掘算法产生一组流程模型作为遗传算法的初始种群，借助遗 传算法的优化能力从中挖掘得到高质量的业务流程模型。从各子日志得到的多种挖掘结果 既提高了遗传算法初始种群的质量，而且初始种群具备遗传多样性，避免了遗传操作的近 亲结缘，从而提高了最终挖掘结果的质量，加快了遗传算法的收敛速度。本发明的技术方 案具体描述如下。

一种适用于多样性环境的业务流程挖掘方法，包括以下步骤：

(1)基于领域知识进行日志分类

通过分析活动所处理的数据对象中的属性信息，利用领域知识对日志中的执行实 例进行分类，从而产生多个子日志；

(2)利用多种挖掘算法准备优质初始种群

利用多种挖掘算法对分类后的各子日志进行挖掘得到流程模型，作为遗传算法的 优质初始种群；其中：所述挖掘算法包括α算法、Heuristic算法和Region-based挖掘 算法；

(3)基于遗传算法整合流程模型

利用遗传算法，将步骤(2)得到的优质初始种群进行整合，从而得到最终的流程模型； 遗传算法中，其适应性函数的计算式为 fitness＝w_l*Fr+w₂*Pe+w₃*Gv+w₄*Sm；

其中，Fr,Pe,Gv和Sm分别表示流程模型在重现度、精确度、通用性和简单性四方面 的计算值；w₁,w₂,w₃和w₄分别表示相应四个质量指标的权重，其根据用户的偏好设置。

本发明中，基于领域知识进行日志分类的具体流程如下：首先抽取流程中活动所处理 的数据对象，由领域专家根据数据对象中属性的取值，利用经验知识给出分类类别以及判 断条件；然后以原始日志和分类条件为输入，采用基于领域知识的日志分类算法，逐一扫 描日志中的执行实例，将其一一归入相应的类中，从而将原日志划分成多个子日志。

本发明的有益效果在于：

(1)实施针对多样性日志的业务流程挖掘方法得到的流程模型的综合质量优于使用 单一流程挖掘算法得到的流程模型；

(2)实施基于领域知识的日志分类方法对降低日志多样性，优化挖掘结果起到显著 作用。

针对某通信公司真实日志的实际应用结果表明：针对多样性日志，本发明的方法是切 实可行的，该方法能能够让大规模企业针对大量不同版本的流程的运行日志，挖掘得到统 一的业务流程，有利于企业的业务流程管理。同时，本发明的方法能够综合已有挖掘算法 的特征和优势，使最终流程模型的综合质量优于使用单一挖掘算法得到的流程模型。

附图说明

图1适用于多样性环境的高效业务流程挖掘方法框架。

图2基于领域知识的日志分类算法。

图3五种控制流结构的流程树表示。

图4流程树的杂交过程示意图。

图5流程树的变异过程示意图。

图6实验结果：SoFi方法与AlphaForGA、HeuForGA和RegForGA方法比较

图7实验结果：SoFi方法与SoFiNoClassify和GA方法比较

具体实施方式

下面结合附图阐述本发明技术方案。本发明提供的一种适用于多样性环境的高效业务 流程挖掘方法的框架示意图如图1所示。

(1)基于领域知识的日志分类方法

日志分类是根据分类条件将日志中的执行实例(一串活动序列)分组从而形成多个子日 志。分类能够降低日志的多样性，简化挖掘算法的应用环境，让挖掘算法的特征和优势得 到充分发挥。运行日志中记录了与活动有关的信息，如：活动的执行者、执行时间或活动 所处理的数据信息。这些数据信息对流程日志分类具有重要的指导意义。因此，在本方法 中，将通过分析日志中的数据信息，利用领域知识对日志进行分类。首先，抽取出流程中 活动所处理的数据对象，数据对象中包含诸多属性及其取值。把它交给领域专家，让其根 据经验知识给出分类类别以及判断条件。然后利用日志分类算法对日志中的执行实例进行 分类。

基于日志数据信息和领域知识的日志分类算法如图2所示。算法的输入为一个运行日志 Log和一组基于领域知识的分类条件Conditions。算法的输出为分类后的一组子日志SLogs。 算法第1行至第4行创建并初始化子日志。因为Conditions中的每个分类条件对应一个子日 志，因此子日志的个数等于分类条件的个数。第5行至第12行扫描Log中的执行实例，并将 它们归到对应的子日志中。第6行d＝getDataObject(a)是对于日志中的每一个执行实例a获 取其对应的数据对象d。第8行至第10行判断是否满足某个分类条件，若满足则将执行实 例a加入到对应的子日志中。

(2)利用多种挖掘算法准备优质初始种群

由于各种流程挖掘算法均有各自的特色和适用范围，因此，为每一类子日志选择适合 的挖掘算法依然是一个挑战。

为了解决这个问题，将多种流程挖掘算法施加于各类子日志，以增强算法遇到合适日 志的可能性。挖掘结果通过后期的遗传算法进行整合与优化。多种挖掘结果既提高了遗传 算法初始种群的质量，而且初始种群具备遗传多样性，能避免遗传操作的近亲结缘，从而 提高最终挖掘结果的质量，加速遗传算法的收敛。例如，可选用α算法、Heuristic算法和 Region-based挖掘算法来为各子日志挖掘流程模型。α算法利用活动之间的二元关系来构 造Petri网模型，模型中不带重复活动和不可见活动，因此结果模型相对简单。Heuristic算法 的优点是可以处理日志噪声，其关键是阈值的设定。由于Heuristic算法只能根据活动的出现 频率来判断噪声，因此有些正确的活动可能会被当作噪声过滤掉，导致重现度降低。 Region-based挖掘算法产生的模型侧重反映日志中出现过的执行实例，因此该算法得到的流 程模型的重现度较高但复杂度也较高。对于每一个子日志，三种挖掘算法都得到三个不同 的流程模型。将它们连同其它子日志的挖掘结果一起作为遗传算法的初始种群，利用遗传 算法的优化能力最终挖掘得到完整的高质量流程模型。

(3)基于遗传算法的流程模型整合

准备好优质种群后，借助遗传算法的优化能力剔除劣质流程，整合优质流程最终得到 优化的业务流程模型。首先，对初始种群中的流程模型使用适应值函数计算每个流程模型 的质量，按照一定比例选择其中质量最优的多个流程模型无需任何改变直接保留到下一代。 其余流程模型使用锦标赛方法选出并进行杂交、变异后进入下一代，没有被选中的质量较 差的模型被淘汰。继续使用适应值函数计算流程模型的质量，与前面的过程一样，高质量 的流程模型直接保留到下一代，其余模型使用遗传操作产生，如此迭代下去，直到满足终 止条件，挖掘过程停止。通过这种精英选择和遗传操作，每一代种群中的最优流程模型的 质量会变得越来越好，末代种群中质量最高的流程模型即是最终挖掘结果。遗传算法的关 键是：流程模型的表示方式；评价流程模型的适应值函数；遗传算子(杂交、变异)。

①流程模型表示方式

本方法采用流程树作为流程模型的表示方式。流程树中的节点分为叶子节点和非叶子 节点。叶子节点(也称为活动节点)表示活动，非叶子节点(也称为操作节点)表示流程的控制 流结构，如：顺序、选择、互斥选择、并行和循环等.为了简化流程树结构，规定每个节点 最多包含2个叶子节点。使用流程树表示的流程模型是一种"块结构"的流程模型，其最大 的好处是流程可避免死锁。五种控制流结构的流程树表示方法如图3所示。其中，分别表 示顺序、选择、互斥选择、并行和循环结构。

②适应值函数

一般的流程挖掘算法只能兼顾某些方面的质量指标。例如，使用Region-based挖掘算 法产生的流程模型的重现度和精确度较好，但是模型的通用性和简单性较差。而遗传算法 通过适应值函数能在挖掘的过程中监控流程模型四个方面的质量指标。本方法采用设置权 重的方式将四个质量指标(重现度、精确度、通用性和简单性)综合起来，使得产生的结 果模型具有较高的综合质量。适应值函数的计算公式为：

fitness＝w₁*Fr+w₂*Pe+w₃*Gv+w₄*Sm

其中，Fr,Pe,Gv和Sm分别为流程模型在重现度、精确度、通用性和简单性四方面的 计算值。w₁,w₂,w₃和w₄分别是四个质量指标的权重。用户可以根据自己的偏好设置流程模 型在这四方面的权重。

③适用于流程树的遗传算子

利用适应值函数计算当前所有流程模型的适应值，按照一定比例，将适应值最高的多 个流程模型直接保留到下一代。其余的流程使用锦标赛方法选出并通过杂交变异产生。具 体方法如下：

(a)杂交

参与杂交的两棵流程树随机选择各自的子树进行交换。杂交过程如图4所示。

(b)变异

变异分为三种情况：节点变异、删除节点、添加活动节点。

节点变异包括操作节点(非叶子节点)变异和活动节点(叶子节点)变异。对于操作节点， 改变其代表的控制流结构类型；对于活动节点，改变其代表的活动类型。删除节点指随机 选择流程树中的一个节点，将其连同其所有的子节点一起删除。添加活动节点指随机产生 一个活动节点，将它添加到任意一个操作节点下。杂交过程如图5所示。

(4)实验分析

本发明的方法已经在某通讯公司项目(MCM20123011)中得到应用。采用该公司3个省 市的发文流程日志，设计了五个实验方案。

1)按照本专利方法SoFi为分类后的各子日志分别施用α算法、Heuristic算法和Region-based 算法为GA优化器准备初始种群。

2)对分类后的各子日志施用同一种挖掘算法为GA优化器准备初始种群。使用α算法、 Heuristic算法和Region-based算法各进行一次。三次实验分别用AlphaForGA、HeuForGA 和RegForGA表示。

3)对原始日志直接施用α算法、Heuristic算法和Region-based算法为GA优化器准备初始种 群，用SoFiNoClassify表示。

4)对原始日志直接施用GA算法进行挖掘。

5)对原始日志直接施用α算法、Heuristic算法和Region-based算法，对挖掘结果计算适应 值。

方案1的SoFi方法和方案2中的AlphaForGA、HeuForGA和RegForGA方法的流程 模型适应值变化过程如图6所示。SoFi方法的流程模型适应值比AlphaForGA、HeuForGA 和RegForGA方法的流程模型均更快的收敛，并且最终结果模型的适应值优于AlphaForGA、 HeuForGA和RegForGA方法的结果模型。这是因为相比单一的挖掘算法，SoFi方法对每 个子日志施用各种不同的挖掘算法增加了子日志遇到合适算法的可能性，提高了初始种群 的质量。

方案1、方案3和方案4的流程模型适应值变化过程如图7所示。图7中，SoFi方法 的流程模型适应值比SoFiNoClassify方法和GA方法的流程模型均更快的收敛，并且最终 结果模型的适应值优于SoFiNoClassify方法和GA方法的结果模型。SoFi方法对原始日志 分类的好处是降低了日志多样性，使传统挖掘算法的特征和优势得到充分发挥，从而得到 更好的初始种群，因此，最终流程模型的综合质量更好。

方案5对原始日志直接施用α、Heuristic和Region-based算法得到三个流程模型。先 计算它们四个方面的模型质量，再使用适应值函数计算流程模型适应值，计算结果如表1 所示。SoFi方法获得的流程模型除简单性外，其余维度的质量计算值均优于以上三种挖掘 算法，综合适应值也优于这三种挖掘算法。

表1实验结果数据：SoFi方法与单一算法比较

实验表明，SoFi方法能够整合各种挖掘算法的优势，使最终流程模型的综合质量均优 于任何参与其中的单一挖掘算法。