詹 悦，王丽丽

随着计算机技术的快速发展，业务管理系统需要设计高效的模型以满足需求.但在实际操作过程中，当一个小的细节被以错误的方式运行时，或者外部的变化（例如新的立法或公司）强加在这个过程上，系统都将被迫偏离指定的流程模型.然而，考虑到系统重设计是昂贵并且耗时的，所以如何发现运行系统的实际模型与原设计模型之间的偏差并修复是目前工作的核心.过程挖掘技术［1］能够从当今信息系统记录事件的日志中提取有价值的信息，这些技术为发现、监控和改进各种应用领域的流程模型提供了新的手段.而变化挖掘是过程挖掘的一个重要分支，旨在发现实际模型或者运行日志变化片段，修复系统漏洞并完善模型构建.

已有的关于变化挖掘方面的文献比较匮乏，大多数是针对日志挖掘模型或者模型间的变化传播问题.一般地，适应性过程提供了关于过程变化的附加信息（例如单个过程实例的临时变化）可被用于管理系统组织.文献［2］介绍了自适应过程管理系统中挖掘变化日志的方法，通过过程挖掘汇总所有发生的变化过程.反过来，这可以作为各种过程改进措施的基础，例如触发过程重设计或更好地控制机制.系统的适应性导致了同一个流程模型可以产生多个结构存在差异的变体.一般地，对此类模型变体的配置与维护成本极高.文献［3］介绍了一个挖掘由配置变体而影响的参考模型，当原始参考模型不可知的情况下，利用过程变体的聚合技术构建一个完整的参考模型.文献［4］利用行为轮廓挖掘多个对应流程模型间的变化域，并利用变化传播原则改进模型以提高模型的可适应性.文献［5］根据模型结构保质性挖掘模型的动态变化，但较少考虑到活动的行为语义.文献［6］提出了一种基于嵌套深度的测试，探索变化模式的使用对认知复杂度的影响，有效地改进了基于挖掘变化模式的建模设计工具.文献［7］利用形态学片段提取事件日志中存在微量变化的可变片段，提高了过程片段的重用性和灵活性.文献［8］根据一致性准则对真实模型的动态变化作出分类比较；文献［9］在PAIS中提出了17个变化模式及6个变化支持特征，解决了特定变化系统框架的变化问题.以上的变化挖掘方法主要是针对变化的流程模型，或者先通过变化日志挖掘出实际模型，极少有直接作用于变化的事件日志.一个变化流程的诱导原因包括变化操作和因果关系，而这些变化将被记录在实际事件日志中，所以对事件日志中隐藏的变化挖掘显得尤为重要.

本文以行为包含［10］为基础，提出了基于完备日志的后继关系.通过比较日志中活动间后继关系与预先定义的模型间后继关系，分析活动所对应的实际模型是否行为包含与原模型检查一致性，并结合模型与日志的行为轮廓利用变化挖掘技术发现变化域［11］.

1 基本概念

定义 1［12］（流 程 模 型）一个六元组PM=(A,G,F,s,e,t)是一个流程模型，满足下列几条件：

A为有限的非空活动集；

①G={and,xor}为有限的网关集；

②N=A⋃B为有限节点集，当A⋂B=φ；

③F⊆N×N为流关系；

④ ·n={n′∈N|(n′,n)∈F}和为节点 n 的前集；n·={n′∈N|(n,n′)∈F}为节点 n 的后继；

⑤ ∀a∈A:|·a |≤1∧|a·|≤1；

⑥s∈A为唯一的开始活动，即·s=φ；

⑦e∈A为唯一的结束活动，即e·=φ；

变化挖掘的目的是提取出日志中活动行为关系与模型存在变化的片段，所以下面定义关于活动间关系的一些定义.

定义2［10］（k-后继关系）S=(N,Mi)为一个网系统，其中N=(P,T,F).k∈N.则对于一条

迹 σ∈Τ(N,Mi)可定义 k- 后继关系

定义3［10］（mink- 后继关系）对于迹 σ定义mink-后继关系：

同理对于系统S和日志L分别存在：

对于任意一个网系统为S=(N,Mi)，其中N=(P,T,F)中，都存在一个确定的后继界bs，使得所有的mink-后继系都满足k≤bs；同理对于完备日志L，也存在一个确定的后继界bL，使得所有的mink-后继关系都满足k≤bL.

定义 4［13］（基 于 日 志 的 弱 序 关 系）Lp=n1,...,nm为过程模型PM=(A,G,F,s,e,t)的一组日志.则弱序关系为≻L⊆(AL×AL)，当对于所有的活动对(x,y)，存在两个下标 j,k∈{1,...,m-1}且 j＜k≤m满足nj=x,nk=y.

定义 5［13］（基于日志的行为轮廓）L={l1,l2,...,ln}为过程模型 PM=(A,G,F,s,e,t)的一组日志，li(1≤i≤n)为日志中的一条迹.一组活动对(x,y)∈(AL×AL)至多满足一下关系之一，集合 BL={→L′||L′×L}为日志 L 的行为轮廓.

①如果x≻Ly且y⊁Lx，则为严格序关系→L；

②如果x≻Ly且y≻Lx，则为交叉序关系||L；

③如果x与y不在同一条有重复活动的迹中出现，则为排他序关系×L.

此外，当且仅当满足y→Lx的活动对(x,y)为逆严格序关系，记为x→-1Ly.

2 基于行为包含的日志变化挖掘方法

系统开发之前都需要需求分析，即设计一个完整的预定义模型.如何测试实际开发的系统是否符合要求，必须对系统的结构进行分析.由于运行系统的内部架构是不可视的，已有的方法是通过系统产生的大量事件日志重构模型，再与原设计模型一致性比较，如图1所示.但重构模型并不能保证其质量，此过程可能产生不一致的二次变化问题.

图1 系统评估

为了有效提高系统测试结果，本文提出了基于行为包含的日志变化挖掘方法，直接对事件日志进行分析（图1中加粗箭头），主要包括日志和模型后继关系的计算，行为包含的具体诱导规则，以及如何利用行为包含与行为轮廓关系对完备日志进行变化挖掘.

2.1 计算日志的行为包含

通过直接分析处理实际系统运行产生的事件日志，可以挖掘出系统对应仿真模型的变化片段.如果该日志所有活动的行为关系都包含于预定义模型中，则说明实际系统符合设计规范与要求，否则存在变化.下文给出计算日志的活动行为是否包含于预定义模型的具体方法.

定义 6［10］（行 为 包含）已知 网 系统 为S=(N,Mi)，其中N=(P,T,F)；实际日志为L.如果所有属于日志L的投影迹σˉL∈Τˉ(L)，存在一条迹σ∈Τ(N,Mi)且满足σˉL∈σ，则L抽象迹包含于S，即日志L行为包含于网系统S，记为L⊆S.

定义 7［10］（后 继 包含）已知 网 系统 为S=(N,Mi)，其中N=(P,T,F)；实际日志为L.分别为他们的后继关系.如果，则系统S后继包含L记为L⊆S.

后续包含仅仅需要比较日志与预定义模型的所有后继关系，如果后继关系已知，则可在日志活动个数的二次时间内计算出结果，这种方法对比直接计算抽象迹包含更加高效.因此，如果某日志并不被包含于此后继关系中，则该日志对应的实际模型存在变化，可以进一步研究其变化域或异常情况.

推论1：对于完备日志L和合理的自由选择网S，后继关系是抽象迹包含的充分必要条件，证明过程参照文献［10］推论2和推论3.

2.2 基于日志行为轮廓的基本结构

根据上文提出的后继包含关系，可以判断日志活动行为是否包含于预定义模型，对于不满足行为包含的活动集合，利用基于日志的行为轮廓方法挖掘其对应的变化片段.

要想准确挖掘出变化活动对应的模型片段，必须明确基于日志行为轮廓的基本结构，一些常见的结构如下，活动下标代表满足该结构的活动至少在迹中发生的次数.

①如果日志L={...xy...}，即x→Ly，则对应的基本结构如图2a；

② 如 果 日 志L={...xy...；...yx...}，即x1||Ly1，则对应的基本结构如图2b；

③如果日志L={...xyx...}，即x2||Ly1，则对应的基本结构如果2c；

④如果日志L={...x...;...y...}，即x×Ly，则对应的基本结构如图2d.

图2 基本结构

2.3 变化片段的挖掘方法

对于给定的一组事件日志，根据活动间的行为包含关系可判断日志对应的模型是否存在变化.通过后继包含关系找到其存在变化的活动集合，然后结合日志的行为轮廓挖掘这些变化活动对应的局部模型片段.具体的算法如下.

基于行为包含的变化挖掘算法：

输入：完备日志L，预定义模型S.

输出：日志L对应的变化片段FCT.

步骤1：初始化，设潜在的变化活动组CT=φ.

步骤2：找出L与S中满足对应关系的活动组T={t1,t2,...,tn}.

步骤3：根据定义7的后继关系，遍历日志的所有迹，建立具有对应关系的活动对间的mink-后继关系表ti≥Lktj(1≤i,j≤n)，记长度为Length.

步骤4：遍历模型，建立活动对之间的mink-后继关系表.

步骤5：比较一组日志活动与模型活动关系，当前Length=Length-1.

步骤6：如果日志所有的活动对均满足后继包含关系，则日志包含于模型即L⊆S，即FCT=φ.

步骤7：将不满足后继包含关系的日志活动组并入潜在变化活动组即CT⋃(ti,tj)，如果Length≠0，则返回步骤5.

步骤8：根据日志行为轮廓BL={→L,||L,×L}，计算CT的行为轮廓关系BLCT.

步骤9：根据BLCT的基本结构构建BLCT的模块结构，即为日志对应的变化片段FCT.

Case 1：x→Ly，则为顺序结构；

Case 2：x||Ly，则为并发结构；

Case 3：x2||Ly，则为循环结构；

Case 4：x×Ly，则为选择结构.

算法的核心思想就是判断日志与预定义模型间的后继包含关系.特别地，当事件日志单条迹中存在重复活动（或者模型存在循环结构），k-后继关系的k取值可无限增大.所以在实际应用时，给定一个后继界b，分别计算满足k≤b下的所有日志与模型活动后继关系，有利于降低因循环结构而带来的计算复杂度.

3 实例分析

近年来网上购物十分火爆，但在实行过程中容易受到黑客或者木马程序的攻击，造成系统紊乱，商家和买家利益也因此受损.找出系统存在的变化区域或者异常点是解决系统故障的重要途径，利用上述的方法可以明显提高查找效率.图3给出了系统预定义的模型包含以下活动（用大写字母表示）.表1为收集的该系统事件日志.

图3 预定义模型

表1 事件日志L

表2 日志L的min1-后继关系

表3 预定义模型S的min1-后继关系

首先根据后继关系的定义，遍历预定义模型S和日志L，计算出对应的mink-后继关系，分别如表2、表3所示.从表中可以发现，活动对(D,E)、(D,E)、(G,I)、(I,L)、(K,I)、(L,K)及(L,M)（表中阴影部分）均满足min1-后继关系≥L1，但不属于≥S1.根据行为包含关系定义，不满足后继包含的活动均存在变化或异常，所以可将包含{D,E}的变化活动集合记为CT1，包含{G,I,K,L,M}的变化活动集记为CT2.

然后，提取这些存在变化的活动并根据基于日志的弱序关系计算它们之间的行为轮廓关系.由于在日志中，D≻LE∧E≻LD，可知D||LE形成CT1的行为轮廓关系BLCT1；

G≻LI∧I⊁LG，可知G→LI，同理可得I→LL、K→LI、L→LK、L→LM形成CT2的行为轮廓关系BCT2.

最后，基于日志行为轮廓的基本结构，构建变化活动集CT1与CT2的模块结构，记为变化片段FCT1与FCT2.由于存在变化的活动对(D,E)属于交叉关系，且在无重复活动中仅发生一次，则对应结构片段如图4a所示，后者(G,I)为严格序则对应结构为顺序块，由于I→LL→LK→LI，则存在循环结构如图4b所示.

图4 日志L的变化片段

通过上述方法挖掘出的变化片段，与预定义模型的对应片段（图3的虚线框所示）可以发现在该网上购物系统中出现的异常情况，（D）在线支付与（E）到付只能选择一种，而日志中隐含的为两种支付方式都采用的异常状况.其次是商家由于缺货等原因选择（G）拒绝接单，而系统可能自动跳转到其他仿冒商家继续发货（I），导致买家所购商品存在仿冒、质量等问题.所以接下来对系统的修复问题只需针对支付系统与商家处理订单及发货的局部系统，大大地提高了系统变化检测的效率.

4 结束语

针对系统内部出现的不可视变化问题，提出了基于日志行为包含的概念并结合行为轮廓挖掘其变化域的方法，然后通过日志对应的基本结构构建变化域的具体变化结构［14］.与现有通过日志挖掘出实际模型再与预定义模型比较的方法，有效避免了重构模型而引起的二次变化问题的产生，也为系统修复与优化提供更可靠的基础.但由于实际系统运行产生的日志质量问题，针对不完备日志的行为包含变化挖掘技术与一致性分析，将在以后的工作中解决.