基于块结构的过程模型隐变迁挖掘方法*

李 增,方贤文

(安徽理工大学)

0 引言

在广泛的过程挖掘领域中，一个令人感兴趣的领域是流程发现，它从事件日志中挖掘出流程模型,但在挖掘业务流程模型的过程中发现一种有趣的情况，一些活动没有在事件日志中发现，而在许多IT系统的业务流程模型中存在，这种活动被称为隐变迁.从事件日志中挖掘隐变迁可以还原更符合实际情况的流程模型，提高模型的运转效率，从而业务流程模型更加完善.

过程挖掘的目标之一是研究频繁行为，以便在过程挖掘的不同任务(发现、监控和增强)中关注过程中更常见的部分.文献[1-5]提出了几种算法来发现涵盖最常见行为的流程模型，并直接在日志中搜索频繁的结构.在发现流程模型的过程中，文献[6-7]也使用了对不常见情况(偏差或异常痕迹)的搜索，去除它们以降低模型的复杂性，同时不大幅降低适合度.文献[8]提出了一种WoMine-i算法用于从过程模型中检索不频繁的行为模式，实验表明，可找到所有类型的模式，提取无法用最先进的技术挖掘的信息.文献[9]提出一种活动过滤方法的新技术，比基于频率的方法过滤异常活动更有效.文献[10] 提出基于规则的合并方法和规则建议算法，用于流程日志的合并，并在Prom中实现.文献[11]根据区域理论寻找非平凡区域,建立了一个具有隐式变迁的分片子模型, 将子模型与初始模型相结合，挖掘出具有隐变迁的目标模型.

目前已有研究主要针对事件日志中活动之间的依赖关系进行隐变迁的挖掘，很少关注模型的结构，算法执行效率比较低.该文通过行为轮廓块结构来挖掘日志中的隐变迁.在进行流程挖掘之前,预先定义一个合理的截断系数,再通过序列编码过滤对事件日志进行处理.事件日志经过截断系数过滤划分为平凡序列和非平凡序列，并利用α+算法挖掘出初始模型.利用块结构对初始模型进行层次分解.将非平凡子序列与模型分解的块结构进行匹配，找出模型结构中可能存在的隐变迁.最后利用拟合度和精确度对疑似隐变迁进行进一步的检验, 过滤掉异常的变迁,从而挖掘出含有隐变迁的目标优化模型.通过该方法所得到的业务流程模型更加精确、完善, 提高了业务流程模型的利用效率.

该文第1节介绍了基本概念；第2节提出基于块结构的隐变迁挖掘方法；第3节给出了相应的案例分析，并通过相关度量值进行检验该方法的可行性；最后总结全文并展望未来.

1 基本概念

定义1[12]：(工作流Petri网 WF-PN) 一个Petri网N=(S,T;F,i,o)称为WF-PN, 当且仅当满足条件:

(1) 该Petri网有唯一的开始库所i:′i=∅；

(2) 该Petri网有唯一的终止库所o:o′=∅；

(3) 该Petri网上的每一个节点都属于i到o的一条路径上, 即Petri网N是强连通的.

定义2[12](行为轮廓)设(N，M0)是一个网，初始标识为M0.对任给的变迁对(ti,tj)，弱序关系 >⊆(T×T)，满足下面关系

(1)若t1>t2且t2>/t1，则称严格序关系，记作t1→t2；

(2)若t1>/t2且t2>/t1，则称排他关系，记作t1+t2；

(3)若t1>t2且t2>t1，则称交叉序关系，记作t1‖t2.

定义3[13](块结构)设Petri网

N=(S,T;F)为一个WF-PN，

N′=(S′,T′;F′)为N的一个子网.

(1)若N′为一个顺序块,记为SB，当且仅当

|S′|>1∧∀ti1,ti2∈T′⟹ti1→ti2∨ti1→ti2

(2)若N′为一个并发块，记为CB，当且仅当 ∀t∈T′⟹∃t′∈T′,t‖t′.

(3)若N′为一个选择块，记为ChB，当且仅当∀t∈T′⟹∃t′∈T′,t+t′.

定义4 (隐变迁)设T′是Petri网业务流程模型中的变迁集，L′是记录日志事件集.

λ:T′→L′ 是标记映射，变迁t′为隐变迁,当且仅当t′∉dom(λ),即t′不属于λ的定义域内.

定义5[12](事件日志)T是任务集,σ∈T*是一个执行迹,L∈P(T*) 是一个事件日志.P(T*)是T*的幂集,L⊆T*.

定义6[14]日志对模型的拟合度f(M,L)计算如下，其中：k为给定日志中的不同轨迹数，n日志迹中所含实例的数目,m丢失令牌的数量,r剩余令牌的数量,c使用令牌的数量.

定义7[15](行为精确度和查全率) 设σ是一个事件日志的迹,L(σ)为迹σ在一个事件日志中所发生的次数,Nr和Nm分别表示Petri网的参考模型和挖掘模型,Cr和Cm分别表示Nr和Nm的因果关系,行为精确度和查全率的计算式分别为

定义8[15](结构精确度和查全率) 设Nr和Nm分别表示Petri网的参考模型和挖掘模型,Cr和Cm分别表示Nr和Nm的因果关系,结构精确度和查全率的计算公式分别为:

2 基于行为轮廓挖掘隐变迁的方法

在结构良好的流程中，模型支持的行为被设计就期望被执行，而执行频率较低的模型子结构可能会暗示流程中的一条路径，为了增加其频率，必须加强该路径；相反地，可以重新构造分配的资源以优化流程.恰好隐变迁的挖掘能很好地还原某些低频日志代表的意义，提高日志在模型中拟合度，完善系统模型，有利于业务流程管理的高效生产与服务.因此从事件日志中挖掘隐变迁是一个值得研究的课题.

该文通过Petri网块结构的理论来挖掘事件日志中的隐变迁.首先对系统生成的海量流程日志进行清洗，过滤掉异常日志，利用序列编码过滤图将日志划分为平凡序列和非平凡子序列.对于高频日志利用α+算法挖掘出初始模型M0，利用行为轮廓块结构对初始模型M0进行层次分解.将非平凡子序列与模型分解的模块进行匹配，找出可疑模块，查找出可能含有隐变迁的位置，插入隐变迁，形成含有隐变迁的子模块，融合子模块将其构建为目标模型M1，最后通过拟合度、行为精确度、查全率和结构精确度、查全率等指标对模型M1进行评价，删除错误的隐变迁，保留对模型有改善的含有隐变迁的目标模型.

算法1 从事件日志中找出符合流程模型的低频序列

BEGIN(算法开始)

输入:事件日志序列L,合理的截断系数cc，阈值tf

输出:初始模型M0和符合流程模型的低频日志

步骤1 对日志序列进行预处理，直接过滤掉不完整的日志序列(明显为异常序列)，

eg.{{A},{A,B}}.

步骤2 针对预处理后的序列，先计算其前缀闭包集，然后作出序列的编码过滤图 .

步骤3 以广度的方式遍历图，保留顶点出弧的权值最大的分支，设最大权值为a，若该顶点其它出弧的权值小于a·cc，截断该分支.

步骤4 步骤3的结果把日志序列划分为平凡序列和非平凡序列，对于平凡序列，在Prom软件运用α+算法挖掘得到其初始模型M0.

步骤5 某些非平凡子序列对模型是有效的，而构建的初始模型M0并未考虑,因此模型是不完善的，为了提高模型准确度，将这些非平凡序列重放到模型M0中.

步骤6 将步骤4得到的非平凡序列重放到初始模型M0中,根据拟合度计算公式

计算各序列的拟合度.

步骤7 若拟合度f≤tf，则把此非平凡序列视为噪音序列，从日志中删除；若拟合度f≥tf，则保留此非平凡序列，视为有效的序列.重复步骤6.

步骤8 输出流程模型有效的非平凡子序列.

END(算法结束)

算法1中，通过计算将事件日志L分为平凡序列、非平凡序列以及异常序列，基于平凡序列建立初始模型M0，然后分析低频序列中的有效序列，继续完善模型.通过计算拟合度来判断某序列是否有效，低于设定的阈值，将视为噪声序列，反之即为有效.当找到所有的低频有效序列后，如何去修改并完善模型就是需要考虑的问题.该文需要借助有效的非平凡子序列和块结构完善目标模型，再从模型的行为和结构的精确度、查全率指标上进行检验，若满足所设的阈值则保留，否则重新配置，若该隐变迁对模型还是没有改善，则视为冗余删除.算法2给出了基于块结构的隐变迁挖掘方法.

算法2 基于行为轮廓的隐变迁挖掘方法

BEGIN(算法开始)

输入:算法1初始模型M0及有效的非平凡子序列

输出:含有隐变迁的Petri网目标模型

步骤1 分析初始模型M0中各变迁之间的行为轮廓关系.

步骤2 依据定义3利用块结构对初始模型M0进行层次分解，依次得到模块m0,m1,…,mn.

步骤3 将算法1得到的有效非平凡子序列与模型的各模块进行对齐，找出可疑位置 ，对模块进行分析并添加可疑变迁.

步骤4 将步骤3构建的子模块融合到初始模型中，添加适当流弧，因为算法1已经对非平凡子序列的拟合度进行了计算,因此当前需要计算模型精确度和查全率.

步骤5 根据步骤4得到目标模型M1.根据定义7, 计算目标模型M1的行为精确度BP(L,Cr,Cm)和行为查全率BR(L,Cr,Cm),若BP≥δ& &BR≥δ，则挖掘到的模型在行为上是符合要求的，若BP<δ‖BR<δ，则模型不符合要求,需要进行过滤操作.

步骤6 步骤5完成后,依据定义8,算模型的结构精确度SP(Nr,Nm)和结构查全率SR(Nr,Nm) ,若SP≥δ& &SR≥δ,则所挖掘到的模型在结构上符合要求,否则不符合结构要求,将其过滤掉.

步骤7 经步骤6，所保留的变迁为最终满足要求的变迁-隐变迁，模型为含有隐变迁的最终模型.最后输出优化的含有隐变迁Petri网模型.

END(算法结束)

3 案例分析

为了验证算法的可行性，借助银行保险索赔流程实例, 来挖掘出保险索赔Petri网流程模型中的隐变迁活动.记录的执行日志分别用下列大写字母表示：A：开始申请索赔；B：申请低额索赔；C：申请高额索赔；D：政策审查；E：低额索赔成功；F：高额索赔成功；G：专家审核；H：检查事宜；I：结束索赔.具体事件日志见表1.

对表1的事件日志集进行初步分析，可以判断日志集发生次数极低且无初始活动A,可以认为是申请人异常操作造成的异常日志序列，直接去日志中删去.

图1 日志L′的序列编码过滤图

根据序列编码过滤的结果,在PROM软件中使用α*算法挖掘到初始模型M0,如图2所示.

图2 初始模型M0

图3 初始模型M0的块结构化简图

低频序列中不排除对模型有用的序列，即低频有效序列.对于序列编码过滤的异常序列L5,L6,L7,L9,L10，依次重放到初始模型M0中，根据定义6，计算其拟合度.先计算L5=< ACHDFI >,L6=,m1=r1=m2=r2=m3=r3=m4=r4=0；m5=r5=m6=r6=1；c1=p1=c4=p4=6；c5=p5=c6=p6=8；所以fL5=fL6=0.9935>λ;重复计算可求fL7=0.9937;fL9=0.3354;fL10=0.2683.对各日志序列的拟合度分析，L5,L6,L7的拟合度极高，可考虑进行下一步操作，试着通过算法二挖掘模型的隐变迁，L9,L10对模型的拟合度较低，小于设定的阈值，视为噪声序列.

根据定义3利用块结构对初始模型M0抽象化简，例如：活动A作为一个单独的顺序块，然后考虑活动B和C.BC之间的行为轮廓关系为B+C，符合选择快Chb的定义，所以将其化简为一个选择块.依次分析其它活动，得到结果如图3所示，其中A、I、G和H为顺序块，B与C、E与F为选择块.D与G、H为并发块.

a.子模块1

b．子模块2图4 含有隐变迁的子模块

最后将子模块1和2合并到初始模型M0中,并对初始模型进行补充和完善，最终得到图5所示的含有隐变迁的目标模型 .在完善后的目标模型M1中,分析所挖掘到的隐变迁J和K,可以知道变迁所表示的意义分别是：当申请者为SVIP时，可直接跳过专家审核G，进入政策审查；当申请者在申请索赔过程中可能由于材料不足导致政策审查H失败时，应当允许返回开始审查C阶段，补充材料继续索赔.实践证明通过完善模型可以让顾客的利益得到保障，提高系统模型的运行效率.

图5 含有隐变迁的目标模型M1

根据定义7、8提出的概念以及算法2中的步骤6,计算初始模型M0和目标模型M1的行为精确度、查全率和结构精确度、查全率(该文中的精确度δ取值为0.85).

通过计算得出BP(L,Cr,Cm)=0.9112>0.85&&BR(L,Cr,Cm)=1>0.85, 说明在行为精确度和查全率上所构建的目标模型M1都比初始模型M0好，再通过算法2中的步骤7对初始模型M0和目标模型M1的结构精确度和结构查全率进行比较.

通过计算得出SP(Nr,Nm)=0.85 &&SR(Nr,Nm)=1>0.85, 可知目标模型M1在结构精确度和结构查全率上都比初始模型M0好, 因此含有隐变迁J和K的模型M1即为所得到的最终目标模型.

通过算法1、算法2挖掘的隐变迁使所构建模型更加完善、稳定，模型效率也得到了提高，而且不管是行为精确度、查全率还是结构精确度、查全率，目标模型M1都得到了提升.所以含有隐变迁的目标模型M1更符合时间日志的要求.

4 结束语

该文在现有研究的基础上, 提出基于块结构从事件日志中挖掘隐变迁的方法.首先利用序列编码过滤将事件日志中分为序列平凡序列和非平凡序列，对平凡序列利用α+算法挖掘出初始模型，再利用块结构进行层次分解.通过拟合度删除不符合业务流程的事件日志，保留余下有效的低频日志，然后通过这些有效的非平凡子序列对模型进行进一步的补充和优化，构建含有隐变迁的子模块，最后将子模块融合到初始模型中并完善.通过行为精确度和结构精确度指标，发现构建的模型在优化指标上有很大的提高，最后结合实例验证了该方法的可行性.

基于块结构对隐变迁挖掘时，并没有将模型的复杂性考虑在内, 这是因为在复杂模型的系统中，设计一个合理的块结构对模型进行层次分解还是比较困难的，复杂模型中子模块的融合也仍需进一步研究.在未来的研究工作中, 需要对复杂流程模型进行挖掘，也可配置其它异常变迁，如：阻塞变迁，使过程挖掘技术能更加完善.