社会经济的发展, 物联网、云计算等新兴技术革命的出现, 使得信息系统不仅仅是围绕处理业务数据为中心, 更多时候与它们所支持的运作流程越来越紧密^[1].同时, 业务流程的操作使得信息系统记录了数量众多的事件, 如何有效地从这些日志事件中提取有价值的信息, 是企业实现新型商务智能的一个重要基础.过程挖掘是业务过程自动化建模及分析的一个重要技术手段, 过程挖掘的应用场景主要有过程发现(process discovery)、符合性检查(process conformance)和模型增强(process enhancement)这3个方面^[1], 其中, 过程发现是过程挖掘最为重要的应用.目前, 已经有很多过程挖掘算法被提出:Alpha算法(α算法)^[2]、启发式挖掘算法^[3]、基于遗传算法挖掘^[4]、基于Markov链的挖掘算法^[5]、整数线性规划挖掘^[6]和基于区域的挖掘^[7]等.以上算法在挖掘方面各有特点, 但在挖掘并发模型的效率上, van der Aalst提出的Alpha算法还是具有很大优势的, 其中一个主要原因是该算法是基于局部完备性(local complete)日志, 而其他算法需要日志需满足全局完备性(global complete)才能得到较好的并发模型^{[8, 9]}.但对于存在大量并发及循环任务的模型, 要产生满足全局完备性的日志, 基本上是不可能的.

从满足局部完备性的日志文件中挖掘过程模型, 现有影响最大、应用最广的过程挖掘算法是经典的Alpha算法(α算法).经典的Alpha算法能够从日志中很好地挖掘出事件间的顺序关系、选择关系、长循环(长度大于2的循环)及并发关系, 但无法挖掘出短循环(长度为1的循环和长度2的循环).为此, 文献[10]将经典的α算法扩展为α⁺算法, 用于挖掘出1度循环和挖掘2度循环.但是文献[10]在挖掘2度循环时, 规定日志文件必须满足循环完备性(loop-complete), 即日志文件中必须出现“aba”和“bab”行为特征模式, 其中, a和b分别代表两个不同的任务, aba与bab都是任务在日志中的行为记录形式.对于不出现“aba”模式、但满足局部完备性的日志文件, 现有算法均不能很好地挖掘出2度循环.

为解决上述问题, 本文将经典α算法进行扩展, 提出了α^L+算法, 用于从满足局部完备性的日志中挖掘出2度循环.与文献[10]相比, α^L+算法并不规定日志文件中必须满足循环完备性.该算法的基本思想是:首先, 采用次序向量对原始日志进行抽象化简, 排除2度循环的变体结构(即循环里面包含子流程等), 然后从全局视角, 结合两种最简2度循环的结构特征——三角形2度循环和棱形2度循环, 用以区分三角形2度循环、棱形2度循环和并发结构; 其次, 针对并发分支上的两种干扰结构, 分别提出紧邻度和基于次序的回路抽象方法进行有效地解决; 最后, 对经典的Alpha算法进行扩展, 以挖掘出2度循环.

本文的主要贡献如下:

(1) 通过构造任务间的基本次序向量矩阵, 对原始日志进行抽象, 得到不包含2度循环变体结构的新日志文件;

(2) 从全局视角, 通过事件执行的次数以及任务间的位置, 识别出三角形2度循环、棱形2度循环和并发结构;

(3) 提出紧邻度和回路抽象的方法, 分别针对并发分支上两种结构存在识别混乱及识别错误的问题进行有效的解决, 降低干扰因素;

(4) 扩展经典的Alpha算法, 并将算法实现为ProM的插件, 通过实验说明了算法的有效性.

本文第1节是例子与问题分析, 通过实际例子来提出论文研究的主要内容.第2节是预备知识, 主要介绍本文涉及的相关基本概念和定义.第3节具体介绍整个2度循环挖掘的过程.第4节是对案例验证及结果分析.第5节是相关工作介绍.第6节是工作总结及下一步研究展望.

1 实例分析

图 1展示了网上购物过程中一部分简单的过程模型, 其中, 任务s表示“在线支付”, 任务a表示“输入验证码”, 任务b表示“重新发送”, 任务c表示“输入账号密码”, 任务d表示“错误提示”, 任务e表示“付款”.选择在线支付后, 用户执行的任务可以是先输入绑定的银行卡密码, 也可以先输入验证码, 所以二者没有先后顺序, 可以认为是并发执行的.在输入验证码的同时, 由于随机生成的验证码存在难以辨认的问题, 用户可以重复多次要求系统重新发送验证码.在输入账号密码时, 系统会随时提示账号不存在或密码不合理等.如图 1所示的过程模型中, 会产生两种不同的日志W₁=[〈s, c, d, c, a, e〉, 〈s, a, b, a, c, e〉, 〈s, a, b, c, a, d, c, e〉, 〈s, c, d, a, c, b, a, e〉, 〈s, a, c, d, b, a, c, b, d, c, a, e〉]和W₂=[〈s, c, a, e〉, 〈s, a, c, b, d, c, a, d, c, e〉, 〈s, a, b, c, d, a, c, d, b, a, c, e〉].这两个日志都满足了任务间的局部完备性要求, 唯一的不同是在日志W₁的前两条轨迹中分别存在“cdc”和“aba”模式, 而日志W₂中所有轨迹都没有出现该类型模式.针对日志W₁, 现有的α⁺算法是可以挖掘出正确的过程模型; 相反, 把日志W₂作为输入, 却得不到原模型.

针对W₁和W₂, 使用经典α算法挖掘出来的模型如图 2(a)所示, 与图 1所示的过程模型不同.为此, Aalst等人对原有算法进行扩展, 提出了α⁺算法:要求日志必须满足循环完备性.即在满足局部完备性的前提下, 日志中必须存在模式“aba”和“cdc”, 以便区分2度循环和并发关系.针对W₁, 使用α⁺挖掘出的过程模型如图 2(b)所示, 与图 1所示过程模型相同.但对于W₂, 使用α⁺挖掘出的过程模型依旧不符合原模型(如图 2(a)所示).究其原因在于, W₂虽满足局部完备性, 但不存在“aba”和“cdc”.因此, α⁺无法从满足局部完备性、但不出现上述紧邻模式的日志文件中挖出2度循环.

对于上述问题, 本文认为日志轨迹中不存在紧邻模式“aba”的本质原因是:由于其他并发分支上的活动执行, 打断了原有的紧邻模式.然而通过对大量实验的观察发现, 虽然局部不能形成“aba”模式, 但是全局日志行为与原有的结构是密切相关的.展开讲, 对于任意两个任务a和b, 如果是顺序关系, 则所有日志轨迹中的行为一定是任务a执行后, 任务b才能执行, 表现在轨迹中为紧邻执行(反之亦然); 如果是选择关系, 则所有日志中二者的前集任务执行完后, 只能执行其中一个任务(a或b); 如日志轨迹中存在a紧邻b执行, b也紧邻a执行, 则表明二者没有任何因果关系, 即为并发关系; 对于2度循环结构, 局部虽然满足并发关系的行为记录, 但从全局视角观察发现, 其还有独特的行为记录.比如, 图 1中的模型产生每条轨迹中, a记录的次数一定比任务b的多(前提是排除了1度循环), 并且b要发生必须得a先发生.这就是2度循环所体现的其中一个事件特征.基于此观察, 本文将对α算法进行扩展, 提出一种α^L+算法, 从满足局部完备性的日志, 挖掘出2度循环.

需要说明的是, 无论是“aba”还是“cdc”, 都是指两个不同任务在日志文件中紧邻出现的模式, 同日志W₁中以〈a, b, a〉和〈c, d, c〉表示是一样的.为了表示方便及简单, 后面统称“aba”模式.

2 预备知识 2.1 Petri网

Petri网凭借其形式化基础、直观的图形化表示及分析技术, 在业务过程管理领域常常被用于建模和分析业务过程.因此, 给出文中涉及的相关概念定义, 如无特殊说明均直接引用, 更多内容参见文献[11].

定义 2.1(Petri网)^[11]. Petri网是一个四元组N=(P, T; F, M), 其中,

1) P∪T≠Ø, 习惯称P为库所集, T为变迁集;

2) P∩T=Ø;

3) F⊆(P×T)∪(T×P), 称F为流关系;

4) 映射M:P→{0, 1, 2, 3, ...}称为Petri网的一个标识.通常用M₀表示Petri网的初始标识.

通常, 在Petri网的图形化表示中, 库所使用圆圈表示, 变迁使用方框表示, 流关系使用有向线段表示, 托肯使用实心小黑点表示.设N=(P, T; F, M)是一个Petri网, 若x∈P∪T, ^·x={y|(y, x)∈F∧y∈P∪T}, 则称^·x为x的前集; 若x∈P∪T, x^·={y|(x, y)∈F∧y∈P∪T}, 则称x^·为x的后集.

定义 2.2(可达标识集)^[11].设N=(P, T; F, M₀)是一个Petri网, N的可达标识集R(M₀)满足下面两个条件的最小集合.

1) M₀∈R(M₀);

2) 若M∈R(M₀), 且存在t∈T使得M[t〉M', 则M'∈R(M₀).

定义2.3(死锁)^[11].设N=(P, T; F, M₀)是一个Petri网, 存在标识M, ∀t∈T, 在M下均没有发生权, 则称标识M为死锁.

定义2.4(安全性)^[11].设N=(P, T; F, M₀)是一个Petri网, ∀p∈P, 若存在正整数B=1, 使得∀M∈R(M₀):M(p)≤B, 则称N是安全的.

本文讨论的内容都是在满足合理性的结构化Petri网的基础上, 即满足:(1) Petri网模型只有一个入口库所i, 一个出口库所o; (2) Petri网模型是安全的, 从入口标识到出口标识是可达的, 且中间不残留托肯; (3)不存在死变迁.此外, α⁺算法已经很好地解决了1度循环(自循环).所以, 本文讨论的过程模型假设不存在自循环.

2.2 事件日志

过程发现的本质就是在分析信息系统记录的日志文件基础上构造过程模型.事件日志记录了事件发生的多方面信息, 但在过程挖掘的理论方面, 最关心的问题是能否从事件执行的先后顺序中发掘整个系统事件的控制流模型.下面给出本文涉及相关概念的定义, 更多内容参见文献[8, 9].

定义 2.5(事件轨迹和事件日志)^[9].假设T为所有任务集合, σ∈T^*是一条事件轨迹, W⊆Ƥ(T^*)是一个事件日志.

即日志是轨迹的集合, 每条轨迹由有限个任务按照执行次序排列而成(也可以说由多个事件组成).如图 1中, s=〈s, c, a, e〉为一条轨迹, W₂=[〈s, c, a, e〉, 〈s, a, c, b, d, c, a, d, c, e〉, 〈s, a, b, c, d, a, c, d, b, a, c, e〉]为其满足局部完备性的一个事件日志.为了方便起见, 文中皆省略了案例属性及轨迹的发生次数.

定义 2.6(基本次序关系)^[10].令T为任务集合, W⊆Ƥ(T^*)是一个事件日志.对于∀a, b∈T:

●  a > _Wb当且仅当存在一条轨迹σ=“t₁t₂t₃…t_n-1t_n” and i∈{1, …, n-1}, 同时满足σ∈W and t_i=a∧t_i+1=b;

●  a→_Wb当且仅当a > _Wb and b≯_Wa;

●  a#_Wb当且仅当a≯_Wb and b≯_Wa;

●  a||_Wb当且仅当a > _Wb and b > _Wa.

定义2.7(全局完备性的事件日志)^[9].令T为有限的任务集合, N是基于T的过程模型, W是基于T的事件日志.W是全局完备的当且仅当所有出现在日志中的轨迹与过程模型N执行产生的所有可能关于T的序列都是等价的.

定义2.8(局部完备性的事件日志)^[8]. T代表有限的任务集合, 令W⊆Ƥ(T^*)代表事件日志, 则W满足局部完备性的条件是:(1)假设σ是模型N产生的任意一条执行轨迹, 则满足 > _σ ⊂ > _W; (2)对于∀t∈T, 必存在一条轨迹σ∈W且t∈σ.

根据定义2.7和定义2.8可知, 全局完备性的日志要求是过程模型中所有可能执行的序列轨迹都要存在.这对于并发任务就是一个排列组合问题.

3 挖掘2度循环过程

本节将讨论从不含有“aba”模式的日志中, 如何挖掘出2度循环.该挖掘过程包括4步, 如图 3所示.

●  第1步, 日志抽象.对原始日志进行抽象, 排除2度循环变体结构带来的结构干扰.

●  第2步, 挖掘两种2度循环.根据不同结构体现出来的事件记录形式不同, 挖掘出2度循环.

●  第3步, 排除并发分支上的同类型循环引起的干扰.采用紧邻度排除并发分支上同类型2度循环的干扰, 采用回路抽象排除并发分支上同类型的长循环结构引起的干扰.

●  第4步, 扩展Alpha算法.在经典Alpha算法中事件间的次序关系中扩展2度循环关系, 同时扩展原有算法步骤, 挖掘出最终过程模型.

3.1 日志抽象

日志循环是为了排除2度循环的变体.如图 4所示, 图 4(a)和图 4(b)这两种类型Petri网结构都是本文认为最简2度循环.然而, Petri网结构在满足合理性的前提还是具备很多种变型, 如图 4(c)和图 4(d)所示的两种2度循环的变体结构与图 4(a)和图 4(b)分别对应.这些变体结构种类繁多, 比如将任务n细化为一个子网.限于篇幅, 本文只考虑图 4(c)和图 4(d)中这两种结构, 其他结构解决方式都是类似的.

定义3.1(三角形2度循环, 用Δ表示).令N=(P, T; F, M₀)为一个基本Petri网模型, 任务a, b是N中的两个变迁, a, b∈T.a, b构成三角形2度循环aΔb当且仅当:(1) ^·a=b^·, a^·=^·b且a≠b and ^·a∩a^·=Ø; (2)假设M₁∈R(M₀), 使得M₁[a > M₂, 且不存在M₁[s > M₂, 其中, σ有穷点火序列, 则仅存在M₂[b > M₁, 若M₂非最终标识且存在M₂[x > M₃, 其中, x∈T, a≠x≠b(如图 4(a)所示).

定义3.2(棱形2度循环, 用◇表示).令N=(P, T; F, M₀)为一个基本Petri网模型, 任务a, b是N中的两个变迁, a, b∈T.a, b构成棱形2度循环a◇b当且仅当:(1) ^·a=b^·, a^·=^·b且a≠b and ^·a∩a^·=Ø; (2)假设M₁∈R(M₀), 使得M₁[a > M₂, 且不存在M₁[s > M₂, 其中, σ有穷点火序列, 则仅存在M₂[b > M₁, 若M₁非最终标识且存在M₁[x > M₃, 其中, x∈T, a≠x≠b(如图 4(b)所示).

定义3.1和定义3.2分别从静态结构和动态执行标识来描述了两种最简2度循环.从静态结构来看, 任务a和任务b都形成了简单的回路关系, 因此采用Petri网的前后集来定义.从动态执行的角度, 运用Petri网的点火标识来体现两者的执行差异.根据2度循环的定义, 可以判定能够组成其变体结构的任务只有选择关系.

定理1.对于任意一个任务n, 且存在2度循环aΔb, 若要构成nΔb, 则a与n一定是选择关系a#n.

证明:采用反证法.假设现有两个任务a, b构成了最简的2度循环结构aΔb, 其中, N=(P, T; F, M₀)为一个基本Petri网模型, 任务a, b是N中的两个变迁, a, b∈T.现存在任务n∈T, n与b构成一个新的2度循环结构nΔb:如图 4(a)所示, 由于aΔb, 则满足^·a=b^·, a^·=^·b.现如果nΔb且a与n不是选择关系, 则a与n则为顺序关系、并发关系中的一种.假设a与n为顺序关系, 则很容易推出^·a≠n^·或者a^·≠^·n.又因为^·a=b^·, a^·=^·b, 所以^·n≠b^·或者n^·≠^·b.这与nΔb的定义是互相矛盾的.因此, 假设不成立.同理可证明, 并发关系也是不成立的.证毕.

以上定理1的证明对2度循环结构◇的变体也是适用的, 并且同理得:若aΔn, 则n#b.因此, 综上所得, 2度循环结构Δ和◇的变体结构中, 只能出现选择关系.根据定义2.6可以发现, 选择关系的任务与其他任务的基本次序是相等的.为此, 算法1给出了日志抽象的过程, 其主要思路是:根据最初日志记录, 建立每个任务之间的相互次序向量, 然后将次序向量相等的任务抽象为一个新的任务.

算法1.VariantAbstracting(W) return W⁺.

输入:满足局部完备性的日志W.

输出:不存在2度循环变体结构的日志W⁺.

BEGIN

1.定义二维矩阵order[n][n]={0, 0, …, 0}, 定义动态链表list;   //其中, n代表w中任务集合个数

2.根据定义2.6计算出W中基本次序关系order;   //0代表选择#, 1代表顺序→, 2代表并发||

3.将order中每一行值转为一个一维向量v_i, 整个二维矩阵形成V=[v₁, v₂, …, v_n];

4.循环对比V中任意两个向量:

  4.1. IF (v_i.equals(v_i+1) & & order[i][i+1]==0 & & v_i.contians(2))

    4.1.1.variantList.add(t_i, t_i+1);  //v_i即任务t_i的次序向量

5. WHILE (j小于variantList的长度)  //将多个相等向量的任务放在一个集合

  5.1.若variantList.get(j)与variantList.get(j+1)存在交集, 合并两个集合;

6.将list中每个集合中的任务抽象为新的任务, 修改日志W为W⁺;

END

任务的次序向量代表当前任务与其他任务之间的基本次序关系.同时, 两个任务若为选择关系(如图 4(c)中的任务a与n), 则体现在日志轨迹中是可以相互替换, 所以构造出二者的次序向量是相等的.算法1中的第4步就是基于此思想, 将选择关系找出来; 然后, 第5步将多个互为选择关系的任务放在一起; 第6步是将这些任务抽象为一个新的任务, 同时修改原有日志文件.

3.2 挖掘2度循环结构

挖掘2度循环结构是指从没有“aba”模式的的日志文件中发现三角形2度循环和棱形2度循环, 其基本思想是:对于结构化的Petri网而言, 其结构特征可以准确地反映行为, 例如, 任务的串行结构可以反映任务间的顺序行为等.因此, Petri网中任务间具有串行结构、选择结构和并发结构在日志轨迹中表现出的事件间的前后位置和事件出现次数也不同.本文把事件在日志轨迹中所体现出来的前后位置和出现次数视为事件特征.首先, 给出事件在轨迹中位置和次数的定义.

定义3.3(事件位置).令σ∈T^*为日志W中一条轨迹, T为任务集合.对于∀a∈T, L(a)={k_i|k为正整数且0≤k_i < σ.sizeand, 1≤i < σ.size}表示为事件a在当前轨迹σ中出现的位置的集合, 其中, ∀k_i∈L(a), k_i代表a在轨迹中第i次出现的位置.如σ=〈s, a, b, a, c, e〉, 则L(a)={1, 3}.

定义3.4(事件次数).令σ∈T^*为日志W中一条轨迹, T为任务集合.对于∀a∈T, Sum(a)表示为事件a在当前轨迹σ中的出现次数, 其中, Sum(a)=N, N为自然数.

轨迹中的事件位置和事件次数是任务行为的记录, 反映了Petri网中任务之间的结构特征.这种特征本文称之为事件特征, 并给出Petri网基本结构体现出来的不同事件特征对比, 见表 1.

由表 1可知, 不同结构反应在日志轨迹中的事件特征也是不同的.顺序结构、选择结构的事件特征实质上就是定义2.6所表示的紧邻关系, 因此可以用经典Alpha算法找到.但是并发结构、三角形2度循环和棱形2度循环这3种结构仅依靠事件特征中第1个条件(实质是紧邻关系)是无法区分, 必须结合后两个条件.因此, 本文给出了算法2用于挖掘三角形2度循环.

算法2.MiningLoop(W⁺) return triangleList.

输入:满足局部完备性的日志W⁺.

输出:挖掘三角形2度循环.

BEGIN

1.令iterator为迭代变量, Q为日志W⁺的轨迹集合;

2. WHILE (iterator小于Q.size())

  2.1.计算每条轨迹中出现的任务t_i的位置L(t_i)和次数Sum(t_i);

3.若order[i][j]为2, 则mayloop.add(t_i, t_j);   //满足事件特征第1个条件

4. WHILE (iterator小于mayloop.size())

  4.1. WHILE (iterator小于Q.size)

    4.1.1.判定〈t_i, t_j〉是否满足的事件特征2、特征3的条件;

  4.2.若所有轨迹Q都满足, 则动态链表添加三角形2度循环任务对triangleList.add(t_i, t_j);

END

挖掘棱形2度循环的算法基本和算法2步骤一样, 仅是将步骤4.1.1中的判定条件改为棱形2度循环的事件特征第2个条件即可, 其挖掘结果放入动态链表prismList中, 所以这里不给出其挖掘算法内容.

3.3 排除干扰

本节主要讨论算法2在挖掘2度循环时存在的两个干扰问题:识别混乱和识别错误, 见表 2.

●  问题1:识别混乱.

本质在于并发分支上存在同类型2度循环结构, 导致两个2度循环的事件特征在日志中交织在一起, 形成识别混乱.针对识别混乱问题, 启发于文献[12]采用了相关性计算公式ECC(a, b)从全局的轨迹角度计算了两个事件类相关程度的思想, 本文提出紧邻度的概念用于解决并发结构中多个同类型2度循环间的相互干扰问题.

定义3.5(紧邻度).令W是关于任务T的一个局部完备性日志, {s₁, σ₂, …, σ_n}是W中轨迹的集合, 任务a, b∈T, a, b的紧邻度表示为Follow Degree(a, b), 简称FD(a, b).其中, FD(a, b)的计算公式如下:

$ FD(a,b) = \sum\limits_{k = 1}^n {\sum\limits_{r = 1}^m {{\beta ^{t - 1}}} } , $

其中, 变量m是在每条轨迹中b出现的次数; n是轨迹的数量; t是任务b与任务a的距离; b是稀释因子, 默认β=0.5.

紧邻度的核心思想是, 正确的2度循环在全局日志中其紧邻程度比假的2度循环强(假的2度循环指二者应该为并发关系).算法3给出了具体的计算过程:采用算法3中步骤1.1的紧邻度计算W₃的结果是{FD(a, b)= 2.5, FD(c, b)=1.75, FD(c, d)=2.5}, 再结合步骤2和步骤3, 最终确定2度循环的正确结果是TloopList={〈a, b〉, 〈c, d〉}.注意, 算法3换做棱形循环结构也可以解决, 输出集合为PloopList.

算法3.DivideLoop(triangleList) return TloopList.

输入:满足结构特征的任务对.

输出:最后确定的循环对.

BEGIN

1. WHILE (iterator小于triangleList的长度)

  1.1.FD(a, b);   //定义3.5

2.循环比较triangleList每个集合, 若{a, b}∈triangleList, 且所有跟b构成循环结构中FD(a, b)最大, 则TloopList.add(a, b);

3.确认TloopList中集合间不存在交集, 返回最终结果;

END

●  问题2:识别错误.

本质是并发分支上存在长循环, 导致了不同长循环之间的两个任务可以产生任意的事件特征(除了入口任务外, 即t₁和t₄).针对识别错误问题, 本文提出在日志层面, 通过定义2.6建立基本次序, 然后通过次序向量来找到任务的回路(特指长循环结构), 将整个回路抽象为一个新任务, 再基于事件特征挖掘及紧邻度判定.需要说明的是, 之所以没有放在第3.1节是为了避免内容混乱, 保证章节内容的紧凑性.

定理2.构成并发的长循环结构, 一定能抽象为不存在长循环的简单并发结构.

如图 5所示, 首先说明的是, 图 5(b)中的4种情况都会导致Petri网模型不合理, 证明可参见文献[2].所以, 证明过程是为了阐述图 5(a)在日志层面可以化简为图 5(c)的模型.

证明:为了证明定理2, 需要考虑两方面.

1) 长循环并发结构中, 一定存在两个任务是真并发关系, 不是2度循环;

2) 从该任务出发, 基于次序向量, 有限次数寻找后继, 一定能找到长循环结构.

●  首先证明1).

由于模型对应的日志满足局部完备性, 所以图 5(a)中一定存在t₀ > t₁, t₀ > t₄, t₁ > t₄, t₄ > t₁.又由于Petri网的点火规则, 日志中一定存在轨迹为σ₁=〈t₀, t₁, t₄, …, t₇〉, σ₂=〈t₀, t₄, t₁, …, t₇〉.任务t₄和t₁虽然可以任意次数出现, 且满足并发关系, 但是在轨迹中为了保证t₀的局部完备性, 一定会出现t₁的前面没有t₄, t₄的前面也可以没有t₁.这就破坏了二者形成2度循的事件特征.因此, 两者为真并发, 不会挖出二者满足2度循环.

●  接着证明2).

令并发分支上存在长循环, 分两种情况:长循环包含任务t₁和不包含t₁的.

●  对于第1种情况, 现从任务t₁出发, 运用广度优先搜索在每个任务的次序向量中找其后继任务, 由于日志是满足局部完备性的, 所以肯定能找到从t₁为出发点又回到t₁的循环路径.

●  第3种情况是长循环不包含t₁, 但是证明过程类似, 依然从t₁出发, 总是能找到某个任务通过自身的后继完后找到, 又回到本身.所以, 基于次序向量通过有限次寻找后继, 一定能将长循环任务抽象.

综上可得, 并发分支上的长循环结构, 一定能够通过满足局部完备性的日志找到, 并抽象.证毕.      □

算法4.CircuitAbstracting(W) return W⁺.

输入:满足局部完备性的日志W.

输出:不存在并发分支上的长循环结构的日志W⁺.

BEGIN

1.定义二维矩阵order[n][n]={0, 0, …, 0}, 定义动态链表list;

2.根据定义2.6计算出W中基本次序关系order;

3.将order中每一行值转为一个一维向量v_i, 整个二维矩阵形成V=[v₁, v₂, …, v_n];

4.循环对比V中任意两个向量v_i和v_j

  4.1. IF(order[i][j]==2 & & v_i与v_j存在共同前继)

    4.1.1.采用广度优先搜索分别从v_i与v_j出发, 寻找当前任务的后继, 建立动态链表;

    4.1.2.如果动态链表形成回路, 则回路中所有任务添加到circuitList中, 并记下入口出口;

5. WHILE (index小于circuitList的长度)

  5.1.将circuitList.get(index)中的任务全部替换为一个新的任务, 修改日志;

END

算法4中, 为了保持内容完整性, 前3步与算法1是一致的.核心步骤为第4步, 其中满足并发关系且存在共同前继的两个任务肯定是真并发.再采用广度循环搜索算法, 寻找当前任务的后继(在次序向量中表现为含有1所对应的列), 一旦形成回路的链表, 就表明存在长循环结构, 并抽象.

3.4 扩展Alpha算法

扩展Alpha算法是在前面分析的基础上重新定义基本次序, 进而扩展经典的Alpha算法内容, 使其能从不具备“aba”模式的日志中挖掘出含有2度循环的过程模型.

定义3.6(挖掘循环的次序关系).令N=(P, T, F; M₀)为合理的WF-net, W为N的局部完备事件日志, 对于∀a, b∈T,

●  aΔ_Wb当且仅当〈a, b〉∈TloopList,

●  a◇_Wb当且仅当〈a, b〉∈PloopList,

●  a > _Wb当且仅当存在一条轨迹σ=“t₁t₂…t_n-1t_n” and i∈{1, …, n-1}, 同时满足σ∈W and t_i=a, t_i+1=b,

●  a→_Wb当且仅当a > _Wb and (b≯_Wa or aΔ_Wb or a◇_Wb),

●  a#_Wb当且仅当a≯_Wb and b≯_Wa,

●  a||_Wb当且仅当a > _Wb and b > _Wa and ¬(aΔ_Wb) and ¬(a◇_Wb).

定义3.6主要增加了三角形2度循环和棱形2度循环两种次序, 再结合紧邻关系 > _W, 用于定义顺序关系→_W和并发关系||_W.

定义3.7(α^L+算法).令W表示基于任务T的一个局部完备日志, 那么α^L+(W)的定义如下:

(1) T_w={t∈T|∃σ∈w:t∈σ};

(2) T_I={t∈T|∃σ∈w:t=first(σ)};

(3) T_O={t∈T|∃σ∈w:t=last(σ)};

(4) X_W={(A, B)|A⊆T_w⊆A≠Ø∧|B⊆T_w∧B≠Ø∧∀a∈A, ∀b∈B, a→_Wb∧∀a₁, a₂∈A, a₁ #_Wa₂⊆∀b₁, b₂∈B, b₁ #_W b₂};

(5) Y_W={(A, B)∈X_W|∀(A', B')∈X_WA⊆A'∧B⊆B'⇒(A, B)=(A', B')};

(6) For each (A, B)∈Y_W do:

  (a) For each a∈A do:

    If (a is avariant task) then restoring the original tasks;

  (b) For each b∈B do:

    If (b is avariant task) then restoring the original tasks;

(7) P_W={P_{(A, B)}|(A, B)∈Y_W}∪{I_w, O_w};

(8) F_W={(a, P_{(A, B)})|(A, B)∈Y_W⊆a∈A}∪{(P_{(A, B)}, b)|(A, B)∈Y_W⊆b∈B}∪{(I_w, t)|t∈T_I}∪{(t, O_w)|t∈T_o};

(9) α^L+(W)={P_W, T_w, F_W};

算法α^L+的定义内容主要体现在扩展了第6步:由于针对原始日志中的2度循环变体结构进行了抽象, 则在算法第5步消除冗余关系后, 紧接着第6步是将抽象出来的新任务删除掉, 还原原始的多个选择任务.然后再添加任务之间的库所和流关系, 得到最终模型.注意, 长循环的抽象在这里没有扩展进来.原因在执行α^L+算法前, 对输入的日志W就已经做了还原处理.这里为了保证与原有Alpha算法的对比性, 所以没有体现出来.

3.5 更多讨论

本文提出在不具备“aba”模式的局部完备性日志中挖掘2度循环结构, 是现有挖掘算法的一个扩展补充.但是, 该算法目前还无法解决结构极其复杂、非结构化的2度循环问题.下面重点讨论3个问题.

(1) 过程模型限定问题:为什么要限定挖掘的过程模型是合理的结构化Petri网?

首先, 合理的Petri网模型是现有过程管理的基础, 一个不合理的过程模型一定存在错误, 则其产生的日志轨迹也失去了实际意义; 其次, 结构化的Petri网其行为记录(日志文件)能充分反映原有模型的结构特征, 而非结构化Petri网, 其行为记录无法准确刻画任务间的结构.如图 6所示, 该模型产生的日志W=[〈a, b〉, 〈a, c, d, b〉, 〈e, d, c, f〉, 〈e, f〉], 日志中既不出现模式“aba”, 又满足了局部完备性.当前, 挖掘算法都无法准确挖掘到该模型中的c与d构成的2度循环, 究其原因是, 非结构化的模型产生的日志无法刻画任务间的真正关系.现有方法是在模型层面将非结构化的模型转化为结构化的模型^{[13, 14]}.此外, 文献[14]明确指出了何为结构化模型:一个过程模型是结构化的, 则对于任意一个具有多条输出弧的节点(分叉点), 都存在唯一一个具有多条输入弧的节点(汇聚点)与之对应, 反之亦然; 同时, 由分叉和汇聚点之间的节点和边构成的模型片段称之为一个单入单出的过程组件; 如果, 整个过程模型能分解为一个个过程组件, 则该过程模型是结构化的, 否则, 为非结构化的.

(2) 2度循环结构复杂变体问题:本文仅讨论由单个任务组成的2度循环变体结构, 对于子网组合的变体如何解决?

本文提供了基于次序向量的方法来解决2度循环结构的变体, 如图 4(c)所示.如果将图 4(c)中的任务a和任务n分别替换为两个子网, 按照本文的方式, 也可以通过抽象来完成, 只是需要更多的约束条件来保证抽象的选择关系的准确性.但是如果子网里面还有2度循环, 相当于2度循环里面有子网, 子网里面又有2循环, 这就极其复杂, 就当前的解决方式, 还不能较好地解决, 需要进一步进行讨论.实际当中, 能够做到两层不同结构相互嵌套, 模型已经很复杂了, 极少出现出现3层及以上不同结构相互嵌套.以上嵌套结构, 特指循环以及更加复杂的子网嵌套, 对于简单的结构嵌套, 基本不影响本文算法.

(3) 回路抽象问题:针对识别错误问题, 本文采用了回路抽象方法, 能够准确抽象吗?效果又如何呢?

定理2已证明, 从日志中一定能够长循环找到, 并抽象为一个新的任务.现有一些研究也充分体现了这一思想, 如团队成员已在文献[15]中准确地找出了单触发序列中的循环结构, 并成功地划分日志轨迹以达到更好的拟合度.文献[16]采用了增量式的挖掘方式来解决循环结构问题, 本质上也是将长循环抽象为一个任务.而本文中所采用的抽象方式是基于次序向量来寻找, 与已有的工作相比, 该算法效率更优.唯一不足的是, 如果处于并发分支上的两个长循环里面又嵌套2度循环, 该抽象会导致挖掘内部2度循环无法被挖掘出来.当然, 现有的抽象方法也都会碰到这个难题, 而且这种嵌套已经形成了上述问题2中讨论的3层嵌套结构, 存在的概率极小.针对该问题, 本文暂时不作讨论, 将在后续工作中展开研究.

4 案例测试及算法评估

本节主要从两个方面来验证上述理论内容:(1)通过人工案例来测试α^L+算法的有效性; (2)通过人工案例及实际案例相结合方式来对现有循环挖掘算法进行测试对比, 体现本文算法的优势.

4.1 案例测试

算法α^L+内容已经成功地实现了插件, 并集成到开源平台ProM中^[17].文献[17]实现插件的步骤包括:

1) 配置需要运行的环境.如安装eclipse集成环境及配置java运行的环境(此部分内容读者可在网上轻松获取到相关资料).

2) 下载ProM的开源代码.首先要求读者安装一个版本控制器, 如TortoiseSVN; 其次, 创造一个新的文件夹“new file”, 打开文件后, 右键, 选择“SVN Checkout”.在URL of repository中输入下载源码的地址: https://svn.win.tue.nl/repos/prom/Framework/trunk/.点击“OK”下载就行.

3) 将源码导入至eclipse环境中, 所有的插件代码在项目中的“src-Plugins”文件下面添加即可.

4) 运行ProM工具.网址https://svn.win.tue.nl/trac/prom/wiki/setup/RunningProM很详细地说明了如何选择哪个类进行运行.需要说明的是, 如果是第1次运行ProM工具, 请确保计算机连着网络, 耐心等待它自动安装完所需插件.

为了验证算法的有效性, 首先通过一个较为复杂的人工案例来进行测试.图 7为人工案例模型, 表 3为该模型产生的日志文件.

如表 3所示, 该日志内容运用现有循环挖掘算法得不到图 7中的原模型, 根本原因在于所有轨迹中都不存在“aba”模式.

针对日志W₅, 采用本文算法却可以完整地挖掘出原模型.图 8所示为α^L+算法的插件选择界面, 图 9为α^L+算法对W₅挖掘的最终结果(与原模型一致).此外, 从过程挖掘官网(http://www.promtools.org/prom5/downloads/Process%20Log%20examples.zip)中下载的8个实例, 算法都能挖掘出原有的过程模型.这也表明了算法在扩展经典Alpha算法后, 不仅没有破坏原有算法挖掘顺序、选择和并发结构的能力, 反而增强了挖掘2度循环的能力, 对原有算法是一种很好的扩展.

4.2 算法评估

算法的评估内容包括3个方面.

a) 从时间复杂度上分析扩展后α^L+算法, 其时间复杂度还是多项式时间.

b) 结合实际例子分析, 通过多种循环挖掘算法对比测试, 表明本文算法针对现实日志能够更好地挖掘出2度循环.

c) 在上述两者的基础上, 深入探讨α^L+算法的核心内容, 为下一步工作奠定基础.

1) 讨论算法的时间复杂度

由于现有的文献[2, 10]已经很好说明了Alpha算法可以很好地在多项式时间内容挖掘出过程模型, 本文是在此基础上进行了扩展, 所以只给出扩展部分算法的时间复杂度分析.令W为满足局部完备性的日志, 其中轨迹数量为t, 总任务数量为n, 日志事件总数量为m, 则日志抽象中两个主要步骤建立基本次序矩阵和循环比较次序向量, 其时间复杂分别为O(m)和O(n²); 事件特征挖掘中由于两种类型循环可以并行执行, 所以仅考虑其中三角形2度循环结构的时间复杂度为O((n/2)×m); 并发分支结构干扰中采用紧邻度来解决的识别混乱问题时间复杂度为O((m/2)×t); 基于次序向量, 采用广度优先搜索算法进行长循环抽象及还原, 时间复杂度为O(n); 扩展经典的Alpha算法中, 还原变体结构的时间复杂度为O(n).由于α^L+算法是顺序执行上面步骤内容, 所以整体复杂度为O(m+n²+(n+t)×m/2+n).更为重要的一点是:相对人工建模的业务过程时间(几周~月), 采用过程挖掘算法从日志中得到的模型时间(几分钟~几十分钟)可以忽略不计.如图 9的W₅日志在个人PC上的挖掘时间为1ms, 而针对较为复杂的实际日志(Log of Volvo IT incident management system, 包含7 554条轨迹, 65 533个事件, 来源http://data.4tu.nl/repository/uuid:500573e6-accc-4b0c-9576-aa5468b10cee)在个人PC上的挖掘时间也只有十几分钟.因此, 时间一般不是挖掘算法的瓶颈问题.

2) 讨论现有循环挖掘算法与本文算法的对比

首先给出过程模型中具有2度循环的挖掘准确率对比柱状图(图 10所示), 充分展示了本文算法相对原有算法的优势; 其次, 将现有2度循环挖掘的算法集成为一种, 统称为集成算法, 再与本文算法进行对比(图 11所示), 表明本文算法依然具有优势.

图 10中, 横坐标轴代表的是过程模型中任务的数量, 并且长循环及2度循环的数量占任务数量的10%;纵轴代表不同算法对应过程模型随机产生的局部完备性日志挖掘出循环的准确率.每种类型的模型, 随机产生200个日志文件, 然后依次采用现有算法进行挖掘.增量式挖掘算法针对2度循环挖掘能力最弱, 基本上只能解决长循环结构, 对于部分没有处于并发分支上的2度循环也能处理; Alpha+挖掘算法强制规定了日志轨迹必须同时存在“aba”与“bab”模式来满足循环完备性, 以此挖掘2度循环, 而模型复杂度增加会导致同时出现的概率大幅度下降; 启发式是目前较为认可的方式来挖掘2度循环, 即通过“aba”或“bab”出现的频率, 设定一个阀值, 满足阀值要求即可.其思想核心也是因为2度循环结构体现在日志中的事件特征是“aba”模式; 本文算法α^L+在此基础上更进一步, 考虑了事件特征不仅体现在紧邻模式上, 更表现为事件间的位置及次数.正常分析, 本文算法应该是随着模型规模增长, 其准确率与其他算法会逐渐拉开差距, 但是在规模为100个任务时, 本文算法与启发算法基本上是一样的准确率.其主要原因是, 紧邻度还不能完全保证百分百地排除识别混乱的问题; 其次, 模型产生的日志不含有“aba”模式的概率虽然是随着模型复杂度增加而降低, 但并不是完全成正比关系.不过, 从整体上分析, 本文算法相对现有算法还是能够较好地解决2度循环挖掘问题.

3) 进一步讨论本文算法的内容

本文α^L+算法可以从含有或不含有“aba”模式的日志轨迹中挖掘出2度循环, 但是还是不能做到百分之百的准确率.为此, 针对现有的实验数据, 逐步执行算法的每部分内容, 分析当前算法每部分的贡献度及不足.贡献度是为了刻画α^L+算法在挖掘2度循环过程中, 每部分核心内容对挖掘出最终2度循环的重要性.贡献度的计算为

$ CT = \frac{{SW'}}{{SW}}. $

借鉴文献[18]用并行度来衡量挖掘后模型的效率问题, 本文使用贡献度来衡量算法核心内容的重要性.其中, CT为贡献度, 分子SW'表示算法核心内容单独或者与其他内容联合执行, 能够挖掘出来2度循环的日志数量.而分母SW表示所有内容联合起来, 挖掘出2度循环的日志的数量.

如图 11(a)所示, 随着模型规模的增加, 事件特征内容呈递减下降, 而其他3部分内容呈缓慢递增上升.其反映了本文算法是以事件特征为核心, 其他内容为辅的挖掘方法.在模型规模较少时, 紧靠事件特征基本上就可以挖掘出2度循环; 但随着模型的复杂度增加, 变体结构、嵌套结构的出现, 需要对日志进行预处理, 才能保证日志轨迹也能很好地体现出2度循环的事件特征.图 11(b)针对300规模模型产生的数据, 具体给出了算法中不同内容的贡献度柱状图:除了3层以上的嵌套结构不进行探索以外, 目前主要核心内容的不足体现在紧邻度.虽然紧邻度能够较好地解决识别混乱问题, 但是其核心依据是真正2度循环的任务间紧邻度要比其他假的2度循环结的任务强.这种解决方式只是根据实际实验判断而形成的, 存在一定的小概率事件.即存在识别混乱问题, 依靠紧邻度还是不能解决.此外, 多重嵌套结构也会造成变体抽象和回路抽象出现错误, 从而导致挖掘的2度循环缺失.这部分内容已经在上述讨论中给出, 这里不再赘述.综上所述, 后续研究要具体针对这些不足进行深入探讨.

5 相关工作

过程挖掘已经成为现代组织用于管理复杂运作流程的一种重要手段, 其中, 准确地挖掘出过程模型是该领域极其重要的研究内容.现有的算法在挖掘模型中的顺序关系、选择关系、并发关系及长循环关系中都获得了较好的进展.最大的难题是如何从日志文件中挖掘出长度为2的短循环结构.该内容的讨论及研究也从未停止过, 表 4给出了在挖掘循环结构上取得一定成果的文献内容(按时间降序).

表 4展示了循环结构挖掘的一些代表性成果, 其中, 短循环特指本文研究的2度循环结构, 方式为模式代表其挖掘循环的内容用到了本文前面所提及的“aba”模式.从表 4可以得出, 现有的挖掘算法能够很好地解决长循环的挖掘问题^{[16, 21, 23]}.相比之下, 短循环的结构挖掘是一个亟待解决的问题.为此, 文献[10, 19, 20]分别提出了启发式因子、遗传+启发、扩展α算法及定义循环完备等方式来解决2度循环的挖掘难题.上述解决2度循环挖掘问题的本质在于采用了“aba”模式, 但现实情况是, 当日志满足局部完备性时, 其日志轨迹中可以不出现“aba”模式.因此, 本文在前人的工作基础上提出了α^L+算法, 用于解决从满足局部完备性且不含“aba”模式的日志轨迹中挖掘出2度循环.

当前, 业务过程随着经济发展而变得相当庞大复杂, 要想保证信息系统记录的日志能够完全反映任务间的关系(全局完备性), 几乎是不可能的.已有较多的研究工作者提出了在更弱的完备性日志中挖掘出过程模型, 如, 文献[24, 25]分别提出了因果完备性(causally complete)和弱完备性(weakly complete), 但此类挖掘算法往往不能得到完整的模型(如并发结构和循环结构不能准确挖掘).因此, 本文算法的优势在于不仅放宽日志的约束条件, 又能保证准确地挖掘出完整的过程模型.

6 结束语

现有的过程挖掘算法在挖掘2度循环时, 规定了日志中必须存在“aba”模式.但是, 满足局部完备性的日志文件可以不存在该模式.为此, 本文扩展了Alpha算法, 从不具备“aba”模式的日志中挖掘出2度循环结构.本文开始给出了最简2度循环结构的定义, 并通过次序向量对原始日志进行抽象, 排除2度循环的变体结构; 然后, 通过全局视角, 采用事件特征来挖掘两种不同的2度循环结构及并发结构; 接着, 针对并发分支上同类型循环结构带来的识别混乱和识别错误问题, 提出了紧邻度和回路抽象的概念, 较好地解决了以上问题; 最后, 借鉴前人工作的基础, 提出了扩展算法α^L+用于从不具备“aba”模式的日志中挖掘包含2度循环结构的完整过程模型.此外, 运用人工案例及实际案例验证了α^L+算法的可实现性, 并通过实验的对比, 探讨了目前算法的一些局限性.因此, 后续研究也将在本文的基础上, 对算法的不足进行更进一步的研究分析.另外, 如何在不满足局部完备性的日志中挖掘出合理模型, 以进一步提高算法在实际应用中的鲁棒性, 也是未来工作的一个重点.