基于不完备日志联合发生关系的行为变化挖掘方法

方 欢，孙书亚，方贤文

(1.安徽理工大学 数学与大数据学院，安徽 淮南 232001;2.滁州学院 数学与金融学院，安徽 滁州 239001)

0 引言

随着大数据技术的蓬勃发展，业务流程管理及优化在企业的日常管理中发挥着越来越重要的作用。但业务流程可能随着时间的推移而不断地发生演变，变化原因包括法规、政策、用户需求和软件维护等因素。这些因素在影响业务流程发生变化的同时，也可能会改变系统的业务能力和行为，因此高效、正确地识别和挖掘业务流程变化，对保障业务系统的行为安全具有较高的应用价值。

现有针对流程变化分析的相关研究主要集中在变化域定位、变化传播分析以及变化挖掘上。业务流程变化域(change region)定位的相关研究主要通过比对系统实际日志和系统参考模型之间的矛盾或不一致之处，来定位和识别系统参考模型发生的结构变化[1-6]；而业务流程的变化传播分析则在变化域研究的基础上，进一步研究流程的部分变化对整个流程、或其他关联流程产生的影响[7-11]。除了变化域和变化传播方面的研究，近年来涌现的基于日志挖掘的业务流程系统变化分析研究得到了诸多科研工作者的青睐[12-16]。业务变化挖掘融合了过程挖掘和适应性流程管理[17-21]两方面的研究内容，通过日志的过程挖掘技术来发现或收集流程管理系统所实施的变化操作。如文献[12]研究了在已知流程变体的情况下，挖掘与流程变体适合度最高的过程模型;文献[13]提出一个研究设计来测试嵌套深度对实验中变化模式使用的认知复杂性的影响;文献[14]提出一种在自适应流程管理系统中挖掘变化日志的方法，通过流程挖掘所发现的变化流程提供了所有变化总的概述，其结果反过来又可以作为各种流程行为改进的基础;文献[15]提出一种从事件日志集合中提取可变的过程片段的方法，并提出一个新的过程片段定义，称为形态学片段以支持组合性和灵活性。然后，提出了直接从过程事件日志中提取形态片段的算法，还提出支持用于检测和分类形态片段以便重用的算法;文献[16]从行为轮廓的角度出发，通过比对系统实际日志和参考模型，来定位和挖掘系统模型可能发生的结构变化，并总结了几种经典的变化结构模式。

这些研究方法大都是从业务流程原始参考模型已知[1-7,9,12-13,16]的角度出发，但在实际应用场景中，大多数业务流程由于业务融合、软件维护等诸多原因，因此实际应用的模型与原始参考模型不一致，或者原始参考模型初始未知。因此，有必要在系统参考模型未知情况下对业务流程的变化进行挖掘与分析。

本文的主要贡献：①在系统参考模型未知的情况下，依据系统不完备日志和业务基本变化类型，得到日志行为轮廓关系和变迁活动之间的发生不变集；②依据变迁活动的发生不变集，得到业务系统中活动之间的日志联合发生关系；③通过比对系统日志的联合发生关系，推导系统的行为关系变化，给出系统日志的删除(delete)、插入(insert)和移动(move)变化操作挖掘方法，实现了“日志—日志”的变化挖掘。

1 研究动机

要实现“日志—日志”的系统变化挖掘，需要了解系统的历史日志信息和当前实际系统日志信息。为了简化描述，记历史日志为Lhis、当前系统日志为Lact、y(L)为日志L映射为字母集。

下面以一个简单的例子，从完备日志和不完备日志两个角度，分别探讨单个活动变化操作可能引起的系统日志行为关系变化。所谓完备日志，是指日志包含所有业务活动和所有活动间可能的行为关系，反之，则为不完备日志。

(1)若Lhis={EAFB,EFAB,IGCDJH,ICGDJH,ICDGJH}，Lact={EAFB,EFAB,IGCDH,ICGDH,ICDGH}，且Lhis与Lact为完备日志，则y(Lhis)={A,B,C,D,E,F,G,H,I,J}，y(Lact)={A,B,C,D,E,F,G,H,I}，y(Lhis)-y(Lact)={J}。显然，Lact是由Lhis执行变化操作DeleteJ获取的，系统行为的相应变化则是由DeleteJ的执行而引起，可以通过日志行为轮廓关系的计算得到。

(2)若Lhis={EAFB,EFAB,IGCDJH,ICGDJH}，Lact={EAFB,EFAB,IGCJH,ICGJH}，且Lhis与Lact为不完备日志，y(Lhis)-y(Lact)={D}。由于是在不完备日志条件下，无法区分D到底是由于Delete操作引起(原因1)，还是由于日志的不完备性引起(原因2)。另外，由于日志的不完备性，两种变化原因(原因1和2)所引起的系统行为关系变化仅通过日志行为轮廓关系无法计算得出。

可以看出，在不完备日志条件下，系统变化无法仅通过日志行为关系计算得到，因此研究系统行为变化的“日志—日志”检测和挖掘方法十分必要。基于此，本文提出基于日志联合发生关系与行为轮廓相结合的方法，用于实现不完备事件日志下行为变化的分析和挖掘。

2 基本定义

本文中系统日志均由工作流Petri网系统[17]产生，有关工作流Petri网系统的相关概念在此不做赘述，下面给出一些基本概念和记号说明。

定义1[18]事件日志。设T为活动变迁集合，σ∈T*是一条事件轨迹，L∈B(T*)是一个事件日志，其中B(T*)为迹的多重集。

定义2[19]日志行为轮廓。设Lp=n1,…,nm为流程模型P=(A,a1,a0,C,F,T)中的一条日志，变迁对(x,y)∈(AL×AL)至多存在下面两种关系的一种：

(1)严格序关系→L，当且仅当x≻Ly,yLx；

(2)交叉序关系‖L，当且仅当x≻Ly,y≻Lx。

这两种关系的集合BPL={→L,‖L}为日志中的行为轮廓。

定义3变化操作。L为一个事件日志，事件迹σ∈L，日志中的活动集合记为S，Delete、Insert和Move分别指日志中活动的删除变化操作、插入变化操作和移动变化操作，并将3种变化操作记为C=(Delete,Insert,Move)。其中Delete、Insert和Move具体操作如下所示(∀ai∈S,σi∈L(i=1,2,…,n))：

(1)Delete：Delete(σi,ai)是指将活动ai从迹σi中进行删除。

(2)Insert：Insert(σi,ai)是指将活动ai插入到迹σi中的任意位置；Insert(σi,a1,a2,a3)指在迹σi中，把活动a1插入到a2和a3之间。

(3)Move：Move(σi,a1,a2,a3)是指在迹σi中将活动a1从当前位置移动到活动a2之后a3之前。

在日志L中，变化操作Delete、Insert和Move的执行导致相关活动发生了行为变化，发生行为变化的活动的集合称为系统行为变化集，记为CS(changed sets)。

定义4[20]迹处理运算符。设L为T上的日志(a∈T，∃σk=x1,x2,…,xn∧σk∈L∧a∈σk)：

(1)τ(xi,σk)给出了σi中元素xi的活动名称。

(2)Pos(a,σk)={p,q,r,…,s}，如τ(xp,σk)=a,…,τ(xs,σk)=a。

(3)Pred(xi,σk)=τ(xi-1,σk),i∈{2,3,…,n}。

(4)Succ(xi,σk)=τ(xi+1,σk),i∈{1,2,…,n-1}。

在定义4中，函数Pred及函数Succ分别提供了活动xi的前继和后继；函数Predset是迹中发生在活动标识符a之前的活动集合的公共部分；相反，Succset是指发生在活动标识符a之后的活动集合的公共部分。

下面举例对上述定义进行说明：设日志L包含3条迹：σ1=x,a,b,d,e,c,a,b,y，σ2=x,d,e,a,b,y，σ3=x,a,b,d,c,a,e,b,y。以活动a为例，对其分别应用Predset及Succset函数，可以得到：Predset(a,σ1)={x}∩{b,d,e,c}=∅，Predset(a,σ2)={x,d,e},Predset(a,σ3)={x}∩{b,d,c}=∅；Succset(a,σ1)={b,d,e,c}∩{b,y}={b}，Succset(a,σ2)={b,y}，Succset(a,σ3)={b,d,c}∩{e,b,y}={b}。

3 不完备事件日志下的系统变化挖掘方法

3.1 不完备事件日志下的基本变化操作

在变化操作(定义3)执行语义的基础上，下面以几组不完备事件日志及其变化后日志为例，从事件日志行为轮廓关系的角度出发，来探究系统可能发生的变化操作类型。

(1)若事件日志L={ABC}，则A≻B≻C，变化后事件日志为L′={AB}，分析导致日志L′中活动C无发生权的原因有两种可能：①日志L′为不完备日志，行为关系的变化未全部包含在内；②对日志L中的活动C执行了变化操作Delete，因此活动C未出现在日志L′中。

(2)若事件日志L={ABD,ACD}，则A≻B≻D,A≻C≻D，且B、C不同时出现在同一条迹中，L对应的变化后事件日志L′={ABED,ACED}，通过日志比对，在日志L′中活动E有发生权的原因同样包括两种可能：①日志L为不完备日志，活动E相关的行为关系丢失；②对日志L执行了变化操作Insert，插入了活动E导致变化日志L′的出现。

(3)若事件日志L={ABCD,ACBD}，则A≻B,B≻D,A≻C,C≻D,B≻C,C≻B,B‖C,C‖B，对应的变化后日志为L′={DBCA,DCBA}，同样地，比较两组日志，发生变化的原因包括两种情况：①日志L,L′为两组不完备日志，行为关系的不完整导致日志序列发生了变化；②日志L中活动A、D发生了位置变化，即执行了Move操作后获得了变化日志L′。

由分析可知，在不完备事件日志条件下，如果仅利用日志行为轮廓关系，无法推断具体的系统变化原因，因此需要进一步结合日志活动间的联合发生关系进行变化挖掘。

3.2 变化操作下任务间行为关系变化挖掘方法

对流程模型执行Delete,Insert,Move三种变化操作会引起活动间行为轮廓关系的变化，基于模型实施变化操作能够更直观地计算活动间行为关系的变化，因此针对流程模型研究活动间行为关系的变化相对简单。下面提出用于确定联合发生关系的相关概念及行为关系变化挖掘算法。

定义5[20]不变前继和不变后继。在日志L中，活动符号a的不变前继是指在a出现的任意一条迹σk中，总是发生在a之前的活动的集合，表示形式为：InvPred(a,L)=∩σkPredset(a,σk)；类似地，不变后继表示为InvSucc(a,L)=∩σkSuccset(a,σk)。

定义6[20]发生不变集。在日志L中，活动符号a的发生不变集是指总是随着活动a发生而发生的活动的集合，表示形式为Oi(a)=InvPred(a,L)∪InvSucc(a,L)∪{a}。

算法1行为关系变化挖掘算法(Behavior Relation Change Mining algorithm，BRCM)。

输入：原始不完备事件日志Lhis，系统实际日志Lact；

输出：日志中发生变化的行为关系集合Rch。

1.计算Lhis和Lact的行为轮廓关系Rhis和Ract；

2. ∀a∈σi,σi⊆Lhis:InvPred(a,Lhis)=∩σiPredset(a,σi),InvSucc(a,Lhis)=∩σiSuccset(a,σi), Oi(a)=InvPred(a,Lhis)∪InvSucc(a,Lhis)∪{a}；

3.日志Lhis中活动a相关的行为关系表示为Ra;

4.if ∀a∈σi∧σi⊆Lhis∧σi⊄Lact(i=1,2,3,…,n),a∈Lhis∧a∉Lact;

5.elseif Ract=Rhis-Ra，Ra⊄Ract∧Ra⊆Rhis

6.return Rch=Ra(→Lact,||Lact),且Lact是Lhis执行变化操作Delete(σi,a)得到的。

7.if ∀a∈σi∧σi⊆Lact∧σi⊄Lhis(i=1,2,3,…,n),a∈Lact∧a∉Lhis

8.elseif Ract=Rhis+Ra,Ra⊄Rhis∧Ra⊆Ract.

9.returnRch=Ra(→Lact,||Lact)，Lact是Lhis执行变化操作Insert(σi,a)得到的。

10.if ∀a,b∈σi∧σi⊆Lhis∧σi⊆Lact(i=1,2,3,…,n)，a∈Lhis∧Lact,b∈Lhis∧Lact

12.returnRch=Rhis-Ra,b(→Rhis)+Ra,b(||Ract)or Rch=Rhis-Ra,b(→Rhis)+Rb,a(→Ract)

Rch=Rhis-Ra,b(||Rhis)+Ra,b(→Ract)or Rch=Rhis-Ra,b(||Rhis)+Rb,a(→Ract)，且Lact是Lhis执行变化操作Move(σi,a,b)得到的。

13.算法结束。

算法1中，符号x⟹y表示关系x转变为y，如Ra,b(→Lhis)⟹Ra,b(||Lact)表示在Lhis中a,b的关系为→，而在Lact中a,b的关系转变为||。

下面利用具体的事件日志进行分析，选取一组不完备事件日志，日志中的相关迹信息如表1所示。事件日志Lhis包含7条事件轨迹，利用日志的行为轮廓关系计算日志的行为轮廓Rhis，建立行为轮廓关系表，如表2所示。

表1 源日志

表2 行为轮廓关系表Rhis

若业务系统的实际事件日志为Lact,其中的迹信息如表3所示。在事件日志Lact中，σ2=σ5,σ3=σ6,σ4=σ7，因此得到合并后的事件日志表4。根据日志行为轮廓关系计算如表4所示的实际系统日志对应的行为轮廓关系Ract，如表5所示。

表3 实际的事件日志

表4 合并后的事件日志

表5 行为轮廓关系表Ract

下面根据算法1来进行系统变化挖掘，根据Lhis中σi(i=1,2,…,7)包含的所有活动的Predset、Succset，得到活动的不变前继InvPred和不变后继InvSucc，以及所有活动的发生不变集Oi，计算结果如表6所示。

表6 活动的发生不变集

对于表4给出的实际系统事件日志，利用不完备日志联合发生关系以及日志行为轮廓关系，来探究日志发生变化的原因。

(1)由表6可知，活动F的发生不变集Oi(F)={A,C,D,E,F,I}，因此与活动F具有联合发生关系的活动为：A,C,D,E,I。已知日志Lhis行为轮廓关系为Rhis，系统实际日志行为轮廓关系为Ract。由表2可得，在日志Lhis中，活动A,C,D,E,I与活动F之间存在的行为关系表示为RhisF：A→F,C→F,D→F,F→E,F→I，且RhisF⊆Rhis,RhisF⊄Ract。因此，利用日志行为轮廓关系及日志间活动的联合发生关系，可以推断出变化的行为关系Rch=RhisF为日志Lact2中丢失的行为关系，实际系统日志Lact2发生变化的原因之一为变化操作Delete(σi,F)(i=5,6,7)的执行，即删除了活动F。

(2)由表6得活动C的发生不变集Oi(C)={A,C,D,E,G,I}，即活动C与活动A,D,E,G,I之间具有联合发生关系。在源日志行为轮廓关系Rhis中，活动C与活动A,D,E,G,I之间的行为关系表示为RhisC:A→C,C→D,C→E,C→G,C→I。而在实际系统日志Lact2对应的行为轮廓关系Ract中，活动C与活动A、D、E、G、I之间的行为关系变为RactC:A→C,D→C,E→C,G→C,C→I，行为关系的变化主要表现在严格序的改变：Rch:C→D⟹D→C,C→E⟹E→C,C→G⟹G→C。因此，对活动C执行Move操作是日志Lact2变化的另一原因。

不完备日志Lhis与系统实际日志Lact2分析比较过程中，其行为关系的变化可以表示为

进一步，由于变化操作DeleteF及MoveC的执行，可以得到行为关系发生变化的活动的集合，即变化集CS={A,C,D,E,G,I}。

以上探讨了Delete及Move两种日志变化原因下行为关系的变化挖掘，对于Insert导致的变迁间行为关系的变化亦可采用类似方法计算得出。比如，变化操作Delete是指对原始不完备日志中的活动进行删除获得变化后的事件日志，改变的行为关系需要以原始日志为例进行计算，被删除的活动在原始事件日志中相关的行为关系即为变化日志中活动间改变的行为关系。而变化操作Insert是指在源不完备日志的基础上任意增加单个活动获得变化后的事件日志，活动数量增多；在探究Insert执行下行为关系的变化时，需要以变化日志为研究对象进行计算，与新增加活动相关的行为关系在原始事件日志中是不存在的，因此，变化日志中增加的活动引起的行为关系的增加或改变即为Insert操作下行为关系的变化。由于变化操作Insert与Delete是一对相对的变化操作类型，行为关系变化挖掘步骤相似，不再对其执行引起的行为关系变化挖掘步骤进行详细阐述。

4 实验仿真与模拟

Inductive Miner是较为有效且方便的过程挖掘方法之一，因此利用ProM工具进行仿真模拟的大多数方法都使用Inductive Miner进行过程挖掘。本章利用ProM工具对真实的人工结构化控制流事件日志进行模型挖掘，如图1所示。

由于图1给出的Petri网模型相对复杂，对模型的完备事件日志进行研究工作量较大，因此选取部分模型子结构的执行序列即模型的部分事件日志为研究对象，来分析和验证本文所提方法的有效性。所选取的局部子模型如图2所示，图2是图1的一部分。为了表示清晰，图2给出含有隐变迁的部分视图，黑色方框表示隐变迁，其变迁标识统一用字母τ进行表示。

图3所示模型为真实的人工结构化控制流事件日志ProM仿真图的部分视图，通过CPN Tools在线仿真模拟工具，得到其运行的系统日志，在系统日志中隐变迁τ在日志中不记录，所得到的源系统事件日志Lhis如表7所示。日志Lhis中活动变迁(不包括隐变迁)对应的行为轮廓关系如表8所示。首先，计算事件日志Lact中的变迁活动(不包括隐变迁)的前继Predset和后继Succset，其次计算活动的不变前继InvPred和不变后继InvSucc，利用定义7中的公式计算其发生不变集，相关的计算结果如表9所示。实际系统日志Lact如表10所示，其对应的行为轮廓关系关系如表11所示。

表7 局部模型对应的事件日志L

表8 事件日志Lhis对应的行为轮廓关系表

表9 Lhis中活动的发生不变集

表10 系统实际日志Lact

表11 系统实际日志Lact对应的行为轮廓关系表

经过算法1的运行与分析，可得如下结论：

(1)与源系统事件日志Lhis相比较，实际系统事件日志Lact中活动a36没有出现在任何一条执行序列中，即活动a36无发生权，可以推测变化操作可能是对活动a36进行了删除。在表9中，活动a36的发生不变集为Oi(a36)={a36,a35,a37,a38,a16}，说明活动a35,a37,a38,a16与活动a36具有联合发生关系即活动a36发生必将导致活动a35,a37,a38,a16同时发生；活动a36出现在除活动a17,a20以外的所有活动的发生不变集中。同时，由行为轮廓关系表8得活动a36与活动a17，a20为交叉序关系，因此源日志中与活动a36相关的行为关系RLhis为：a35→a36，a37→a36，a38→a36，a16→a36，a12→a36，a18→a36，a19→a36，a36||a17，a36||a20。而活动a36未出现在日志Lact中，且RLhis为日志Lact丢失的行为关系。因此，可以判定变化操作Delete的执行导致了Lact中活动a36的丢失。

(2)日志变化的行为关系除了(1)中行为关系RLhis的丢失之外，由行为轮廓关系表8、表11可以简单地看出活动a16、a17、a20相关行为关系亦发生了变化。a16和a17由原来的严格序关系a16→a17，变为交叉序关系a16‖a17，a17和a20由原来的交叉序关系a17‖a20变为严格序关系a17→a20，从日志的执行序列中可推测活动行为关系的变化可能是变化操作Move的执行所引起。利用本文所提的法进一步验证：在日志Lhis,Lact中，活动a17与隐变迁τ3、τ4存在着不变的行为关系：τ3→a17→τττ。因此，活动a17未发生位置移动。活动a16的发生不变集为Oi(a16)={a16,a35,a37,a38,a17,a20,a36}，变化的行为关系表示为：a16→a17(表8)⟹a16||a17(表11)。活动a20变化的行为关系表示为：a17||a20(表8)⟹a17→a20(表11)，因此活动a16、a20行为关系变化的原因是对其执行了Move操作，即Move(σi,a16,τ3,τ4)，Move(σi,τ4,a20)。

结论(1)、(2)两种变化操作的执行导致部分活动间行为关系发生了变化，变化集CS={a35,a36,a37,a38,a16,a12,a18,a19,a17,a20}。为了验证方法的正确性，对变化后的真实的人工结构化控制流事件日志再次进行ProM过程挖掘，得出图3所示Petri网模型，与图1相比较，由于局部日志的变化导致图3模型发生了变化。为了更直观地进行观察，给出图3发生变化的局部模型(如图4a)，以及变化前的原始局部模型(如图4b)。

对比图4a和图4b的系统模型，能够清晰地看出，变化后模型与初始模型相比较活动a36被删除，a16,a20位置发生了移动。对于变迁活动之间行为关系的变化，仿真结果与本文所述方法计算结果一致，从而进一步验证了方法的正确性。

5 结果分析

本文基于不完备事件日志获取变化后的事件日志，并进一步利用日志行为轮廓关系及活动联合发生关系对变化所引起的行为关系的变化进行了探究计算，但本文的变化挖掘方法基于日志中所有活动都不考虑无标记变迁(隐变迁)的发生，若所分析的系统日志含有隐变迁，则变化挖掘研究会相对复杂。将图3中与活动a36处于排他关系的隐变迁用字母τi进行表示，即可获得变化后的模型，如图5所示。如果考虑隐变迁τi发生并对其进行标记，图5模型所对应的日志集可能出现的一条序列模式为l1=a35a19a38a16a20τia17，活动a36未出现在迹l1中，隐变迁τi的发生剥夺了活动a36的发生权，但是实际系统并未对活动a36执行变化操作Delete。由此可见，在考虑隐变迁发生的情况下，变化原因的判断相对复杂，需要进一步探究含隐变迁的不完备事件日志序列行为关系变化的计算方法。

6 结束语

事件日志中活动的变化将会导致模型中变迁活动行为关系的改变，因此在模型未知的情况下，如何通过比对源系统日志和实际系统日志来挖掘系统的变化是一个值得研究的问题。本文在现有研究基础上，利用不完备日志中变迁活动的联合发生关系来计算活动的发生不变集，并结合日志行为轮廓关系，探讨了日志的Insert、Delete、Move变化操作挖掘方法，并在ProM对所提出方法的正确性和有效性进行了分析验证。

未来的研究工作将从两个方面展开：一方面重点研究含隐变迁的不完备事件日志行为关系变化挖掘方法；另一方面是同时考虑多个活动执行不同的变化操作对系统带来的行为关系变化分析。