基于联合发生类的业务过程挖掘方法

李 娟，王丽丽，刘祥伟

（安徽理工大学 数学与大数据学院，安徽 淮南 232001）

1 引言

过程挖掘的目的在于从事件日志中提取信息构建流程过程模型，合理的流程模型能够对日志中的行为进行重演.目前，过程发现技术面临问题是事件日志往往不能包含一个业务过程模型的所有信息（如不完整日志）.这将导致所挖掘的流程模型与实际业务流程不一致，达不到企业或者客户的期望.造成日志不完整的原因有很多，其中最常见的原因是并行结构的出现，因为大量并行活动的交互不能在执行日志中展现.文献[1]提供了几种度量维度(合适度、精度、泛化)评估所挖掘的流程模型与日志的一致性程度，如是否明确的表达活动之间的因果关系和并行关系，是否体现了所提供信息的所有可以观察的行为.在工作流管理系统领域里，已经提出相关过程发现技术去发现业务过程模型.文献[2]提供一种算法，通过捕获业务过程日志将业务过程非结构化得到业务流程图满足日志中活动依赖关系和执行情况.实验证明此技术更容易引入工作流系统还可以对实际业务流程进行评估.实际的工作流过程和管理所执行的业务过程往往存在差异，然而创建工作流设计是一个复杂耗时的过程，文献[3]提出一种算法从日志中的活动之间发生顺序来推断业务过程模型.显然该方法具有一定局限性只能发现简单的业务流程模型.随后许多技术对此算法进行拓展，文献[4]提出一种能够检测到Petri网中活动之间依赖关系，其中包括显式依赖和隐式依赖，实验结果表明该方法在非自由选择结构的挖掘中能够显著提高业务过程模型的合适性.为了从事件日志中发现并发行为模式，文献[5]提出一种基于事件的概率分析，使用事件发生的次数、频率和规律性指标确定系统中可能出现的并发行为可以帮助业务过程设计人员更好改进业务流程模型.从事件日志中提出控制流和相关数据参数的算法在文献[6]提出，演示了运用条件偏序图(CPOG)将事件日志可视化揭示业务过程中控制流和数据流之间隐藏的相互作用，为新的过程挖掘开辟道路.感知挖掘算法[7]能够处理不完整日志，采用分而治之的方法递归处理所有日志构建流程模型.文献[8]使用了遗传算法发现过程树从而减少搜索空间并且用户在最终的业务过程模型中可以选择自己需要的业务流程模型质量维度.

本文从新的角度提出联合发生类概念从不完整日志中能够构建合理的业务过程模型.从日志中检测出每个活动的不变优先集、不变后续集、不变发生活动集，最后得到活动的联合发生类推测出具有强因果关系的活动类.再运用删除活动函数找出日志中隐藏的活动之间的因果关系和并发关系用于完善业务过程模型，提高过程模型的合适度.提出的联合发生挖掘算法已经在Prom中实现，实验结果表明与其他算法比较该算法能够在不完整日志中或执行迹较少的情况下构建出更合理的业务过程模型.

2 基本概念

定义1[9]满足下列条件的三元组N=(S,T;F)称作一个网：

定义2[9]设N=(S,T;F)为一个网，对于x∈S∪T,记

称·x为x的前集或输入集，x·为x的后集或输出集.称·x∪x·为元素 x的外延.

定义3[10]（行为轮廓）令S=(N,M0)是一个网系统，其中N=(S,T;F)且T'⊆T是一个变迁集.一对变迁(x,y)∈(T'×T')若满足下面条件之一：

（1）严格序→：当且仅当x≻y,y≯x.

（2）排他序+：当且仅当x≯y,y≯x.

（3）较差序||： 当且仅当x≻y,y≻x.

（4）严格逆序→-1：当且仅当 x≯y,y≻x.

以上几种关系构成了网N的行为轮廓，记作BP={→,+,||}.

定义4[10]（完整日志）N是一个合理工作流网，λ是N的工作流日志.λ是N的完整工作流日志必须满足下面两个条件：

（1）对 N 中任一个工作流日志 λ'：→λ'⊆→λ.

（2）N中的每一个活动都在日志λ中出现.

定义5[10]（不变优先集和不变后继集）在日志λ的每一条迹σk中总是出现在活动a之前（之后）的活动集，称为a的不变优先集记为InvPred(a.λ)（a的不后继变集 InvSucc(a,λ)）.其中

定义6[10]（不变发生活动集）在日志λ中活动a的不变发生活动集是指当a发生时，该活动集总是和活动a一起发生.记为Oi(a)=InvPred(a,λ)∪InvSucc(a,λ)∪{a}

例如，日志 λ 中有条迹 σ1=＜x,a,b,d,e,a,c,a,b,y＞，σ1=＜x,d,e,a,b,y＞.在日志λ中对活动a运用前集和后集函数可得，

定义7[10]（联合发生类）设是上的一个二元关系，定义，是粗粒度的等价关系，称是联合发生关系，称等价类为联合发生类.同一个联合发生类的两个活动具有很强的因果关系记作.

定义8[10]（过滤函数）活动集X⊆T,迹σ1∈λ，函数øX(σi)表示在迹σi中过滤掉活动X后得到的迹.如 ø(a,b)(σ1)=＜x,d,e,c,a,b,y＞.

通过上面引入Petri网和联合发生类的相关概念，下面介绍运用联合发生挖掘算法从不完整日志中构建合理的业务流程模型.

3 联合发生挖掘算法

从不完整日志或者较少的迹中直接构建业务流程模型是粗糙的，不能反映真实业务流程的实际运行情况.基于第二部分的基础知识，下面提出一种联合发生的挖掘算法，尽可能挖掘隐藏在日志中更多有用的活动之间关系来构建更加合理的业务流程模型.首先检测不完整日志中所有联合发生类找出具有强因果关系活动对.再利用过滤函数找出隐藏在日志中活动之间关系.最后得出所有活动之间的关系表构建业务流程模型.算法的具体步骤如下：

输入：日志 λ={σ1,σ2,σ3…σn}.

输出：合理工作流网N.

1.对不完整日志中的每一个活动，运用定义4和定义5计算活动的不变优先集和不变后继集.根据定义6计算出每个活动a∈T的不变发生活动集.Oi(a)=InvPred(a,λ)∪InvSucc(a,λ)∪{a}.

2.根据步骤1和2绘制发生不变量活动集表，其中包含InvPred，InvSucc和Oi.

3.根据发生不变量活动集表得出活动关系矩阵，并且从该矩阵中找出联合发生类COci.

4.同一个联合发生类的活动a,b∈COci具有很强的因果关系用a⇒b表示.

5.根据定义8运用过滤函数øX(σi)将联合发生类COci里的具有很强因果关系的活动过滤掉发现不完整日志中存在隐藏活动之间关系.

6.绘制日志中的活动之间关系表.

7.构建业务过程模型.

下面通过实例分析验证联合发生挖掘算法的可行性.

4 实例分析

为了验证上述算法的可行性，下面运用算法构建出不完整日志 λ={σ1,σ2,σ3,σ4,σ5}的模型.其中

以活动B为例计算活动B的不变优先集、不变后继集、不变发生活动集.

表1 活动集发生不变量

同理可得日志 λ={σ1,σ2,σ3,σ4,σ5}中其他活动的不变优先集、不变后继集、不变发生活动集.

计算结果见表1.根据表1的不变发生活动集可以得到活动之间的关系矩阵，在关系矩阵中两个活动在不变发生活动集中就用1表示.具体的活动关系矩阵见

图1 活动之间关系矩阵

在活动之间关系矩阵中可以明显看到6个联合发生不变量，在图1中用方框表示出了，其中COci={B,C}可以观察到B∈COci，当活动B出现在日志λ={σ1,σ2,σ3,σ4,σ5}中时，活动 C 也出现在日志 λ={σ1,σ2,σ3,σ4,σ5}中.且他们都是以 B,C 顺序发生在日志中所以B,C是强因果关系对B⇒C.同理还有两个联合发生不变量COci={D}，COci={A,E,F,G,H,I}.强因果关系对A⇒E,E⇒F,F⇒H,H⇒I，COci={J}.COci={K,L,M}强因果关系对K⇒L,L⇒M，COci={N}.

根据算法步骤6运用过滤函数øX(σi)发现日志中隐藏的活动对之间关系.从日志 λ={σ1,σ2,σ3,σ4,σ5}中运用过滤函数删除活动B,C可得：

从过滤后的日志σ'1，σ'3中可以得出F||D,

从过滤后的日志σ'4，σ'3中可以得出J+K，A→K,A→J.

同理运用过滤函数在日志 λ={σ1,σ2,σ3,σ4,σ5}删除活动对E,F可得：

从过滤后日志σ"1，σ"3可以得出C→D,D→B.

运用联合发生类可以得到在原日志中不易被发现发现的活动对关系F||D，J+K，A→J,C→D,C→D,D→B再结合行为轮廓知识得出原日志明显活动对关系可以得出活动之间关系表，呈现在表2.

根据活动之间关系表可以构建该业务过程模型.

图2 运用联合发生类挖掘算法得到合理业务流程模型

5 结论

本文提出一种从不完整日志中挖掘业务过程模型的新方法，是以活动之间联合发生关系为基础，将日志中活动划分为联合发生类用来推断在不完整日志中丢失的因果关系和并行关系，明显地提高了业务过程模型的合适度.相关实验表明，该方法提出的概念和算法在其他相关的发现领域具有重要作用.尽管此方法在处理不完整日志具有明显的优势，局限性在于不易发现模型中短循环结构，在以后的学习中会进一步优化算法，找到更合理的方法从事件日志中发现活动之间关系构建更合理的业务过程模型.