基于增强日志的过程挖掘算法

邵叱风，方贤文，盛梦君

(安徽理工大学数学与大数据学院，安徽 淮南 232001)

数据挖掘与过程挖掘之间既有区别又有共性。就目的而言，数据挖掘是从大量的数据中提取或挖掘出有用信息[1]，而过程挖掘是从表示流程执行工作流的数据中挖掘流程模型。故数据是数据挖掘以及过程挖掘的基础。从存储方式来看二者又是不同的，前者使用的数据常用数据库、数据仓库、万维网或其他信息存储库[2]存储信息，而后者使用的数据通常存储在捕获系统工作流的日志中。

在传统的过程挖掘研究中使用的日志称为事件日志，其用于从控制流角度记录和观察进程工作流。事件表示任务的执行。不同的挖掘算法使用不同的事件日志，文献[2]提出α算法，使用迹矩阵定义活动间的顺序操作符，从基本事件日志中发现结构化事件模型；文献[3]提出β算法为每个事件标记一个类型；文献[4]提出λ算法将后继任务添加到事件中。以上方法提出了不同的日志处理方案，生成不同算法所需的日志形式。

过程挖掘形式化定义用于从事件日志的一组实际执行中提取结构化流程的方法。过程挖掘至少在两个方面是有用的。首先，它可以被用作一个用来查明程序真实运作的工具；其次可用于增量分析，即将实际过程与一些预定义的过程进行比较。基于 ①多核和并行技术的发展导致数字世界的惊人增长[5]②随着数字世界的发展和组织进程的紧密结合，使得记录和分析更多的事件[6]成为可能，过程挖掘成为工作流技术的热点之一。文献[7]提出了遗传挖掘算法，该算法提出一种有效的因果矩阵结构来提高空间搜索的效率；文献[8]使用Rule-induction过程挖掘技术，提出RIPPER算法产生活动间的规则；文献[9]使用分治策略递归地构建过程模型，直到所有的迹都被处理为止，该方法称为归纳式挖掘算法；文献[10]提出一种由α-算法产生的启发式挖掘算法，该方法仅考虑了事件的顺序；文献[11]阐述了灵活启发式挖掘算法，它是一个灵活的控制流挖掘算法，提出的两个算法都能处理噪音和低频行为。针对过程挖掘方法有时不能获得完备事件日志的问题，文献[12]提出一种从不完备日志中发现块结构过程模型的方法，该方法利用对完备性不敏感的概率行为关系，给出了一个适用性更强的过程发现算法；文献[13]提出一种挖掘局部过程模型的方法，该方法通过生成过程树并依据5种评估标准选择局部过程模型，扩展生成新的过程树，以此迭代直到完成任务。但以上挖掘方法多以基本事件日志作为输入，且均不能挖掘出系统中的场景信息。

本文主要工作有：首先提出增强日志的相关定义，继而提出基于增强日志的挖掘算法(Process Mining-Enhanced Log，PM-EL)，通过颜色Petri网的加入用以表达具有场景信息的挖掘结果；使用UML转换结果模型说明其可扩展性；对比实验展示PM-EL算法在结构识别上的能力。以上工作就基于事件内部属性对模型做出优化[14]的工作提供了可切入点。

本文第1节介绍准备知识；第2节提出增强日志的概念以及基于增强日志的过程挖掘方法；第3节通过仿真实验验证所提方法的可行性及可扩展性；最后总结全文并展望未来。

1 准备知识

在本节中，将给出一些定义以及基本概念，用以辅助解释提出的方法。限于篇幅，有关 Petri网的概念及结构的定义在此不做赘述，具体内容可以参考文献[15]。

定义1[16](颜色petri网)一个简单的(带有k种颜色的)颜色Petri网是一个五元组Σ=(S,T;F,W,M)其中(S,T;F)是一个网，W∶F→{0,1,2,…}k,M∶S→{0, 1, 2,…}k对t∈T，如果s∈·t→M(S)≥W(s,t)，那么变迁t在标识M有发生权(M[t>)，在标识M下发生变迁t,产生一个新的标识M′(M[t>M′)，

定义2[17](UML2.0序列图)序列图是常用的且偏向于捕获对象间行为的图。它通常可以与正在开发的系统的逻辑视图中的用例相关联。高级序列图(High-level Sequence Diagrams，HLSD)是一个序列图，它引用一组基本序列图(Basic Sequence Diagram，BSD)，并使用一组交互操作符组合它们。主要的操作符是:弱顺序(SEQ)、选择(ALT)、 循环(LOOP)和并行(PAR)。

在Petri网的许多现有变种中，CPN被用于以序列图的形式表示的组合和集成场景。库所表示BSD，变迁表示操作符，如ALT、LOOP、SEQ和PAR。颜色用于区分库所。图1显示了HLSD如何映射到CPN。T3表示条件为C1的操作符LOOP。操作符PAR和SEQ也可以映射，如图2所示。可见对于HLSD，可以相互转换生成一个可表示主要的UML序列图操作符的CPN。

图1 序列图将操作符LOOP和ALT映射到CPN

图2 序列图将操作符PAR和SEQ映射到CPN

2 基于增强日志的过程挖掘方法

过程挖掘起源于系统日志的使用，定义和统一系统日志是过程挖掘的关键步骤。过程挖掘1995年由J.E.Cook提出至今，技术方面取得了长足的发展，且取得了诸多较完善的研究成果，但多以行为间控制流结构挖掘过程模型；不同类型的事件日志(其中可能包含略微不同的信息)被不同的挖掘算法所使用，但大多数仅从控制流角度记录和观察工作流。

2.1 增强日志

在软件系统运行时会产生大量的日志，常用来作为挖掘算法输入的事件日志往往只记录了执行的事件。在此对文献[18]中的日志数据格式进行扩展，针对事件执行信息中一些可利用的属性，提出增强日志的概念。

定义3(增强日志)若Traces是任务集,且满足如下两个条件，则称ω∈Traces*是一条事件轨迹,W⊆Traces*为一个增强日志。

(1)Trace是一个四元组Trace= (线程号；发送方，消息，接收方),其中:发送方是调用对象，形如threadNumber: package:class:object，消息是接收方对象的调用方法，形如mathodName ( param1, param2,…);接收方是被调用对象，形如package:class:object。

(2)方法调用之间的等价性:方法调用如A1=(sender1;message1;receiver1)和A2 =(sender2;message2;receiver2)是等价调用，当且仅当：两个对象隶属同一实体类(可创建相同属性值对象)，并在同一线程中以相同的参数值创建，那么等价。信息对象message1与message2涉及相同的方法且具有相同的签名。

其中有4个函数操作TLineNumb(Trace)=线程号，TSend(Trace)=发送方，TMsg(Trace)=消息，TReceive(Trace)=接收方。其中的线程号可用来分析事件执行的内部联系，其他三个属性可用来生成场景化信息。

2.2 过程挖掘算法PM-EL

现有的过程挖掘算法从事件日志中挖掘任务之间的因果依赖关系和并行关系，发现过程模型中所有库所的前后任务，然后重建整个过程模型。文章在此提出了一种新的算法PM-EL。在这一部分，我们首先介绍了算法的定义和数据结构。然后详细介绍了该算法的伪代码及运行过程。

在增强日志中，因果依赖、并发及选择关系定义如下。

定义4(因果依赖)：设Traces={t1,t2,…,tn}是WF-netPN= (P,T,F)的变迁集.∀a,b∈T，变迁之间的因果关系记为′→w′,a→wb,当且仅当:

(1)TLineNumb(a)=TLineNumb(b),

(2)TReceive(a)=TSend(b)。

定义5(并发关系)：设Traces={t1,t2,…,tn}是WF-netPN= (P,T,F)的变迁集.∀a,b∈T，变迁之间并发关系记为‘||w’,a||wb当且仅当： ∃c∈Traces

(1)(c→a,c→b)∨(a→c,b→c)

(2)TLineNumb(a)≠TLineNumb(b),

(3)(TSend(a)=TSend(b)=TReceive(c))∨

(TReceive(a)=TReceive(b)=TSend(c))。

定义6(选择关系)：设Traces = {t1,t2,…,tn}是WF-netPN= (P,T,F)的变迁集. ∀a,b∈T，变迁之间选择关系记为‘+’,a+b当且仅当：∃c∈Traces

(1)(c→a,c→b)∨(a→c,b→c)

(2)TLineNumb(a)=TLineNumb(b),

(3)(TSend(a)=TSend(b)=TReceive(c))∨

(TReceive(a)=TReceive(b)=TSend(c))。

对于相同用例(场景)的CPN被迭代合并,以获得用例的集CPNs，其颜色用于区分不同输入场景。算法PM-EL描述了这一步操作。它可以输入多个执行序列,并且增量的生成一个可表示系统行为的CPNs。首先，算法逐行扫描执行序列，如果是新执行序列，则分析每一个执行迹，创建一个新库所。其中表示执行迹的所有库所都具有相同的颜色，这些颜色帮助我们区分场景，变迁表示场景的执行。算法还可以创建变迁，它通过分析前面的执行迹和当前的执行迹，为每个库所关联相应的变迁(UML操作符)。该算法主要通过执行迹内部属性来进行结构化模型的提取。如用线程的ID来区分线程，如果这些执行迹属于同一线程,则可以通过在不同的序列中对以前的迹和当前的迹进行简单的比较，然后识别操作符”SEQ”和”ALT”。通过分析线程号信息识别主线程及其子线程来检测操作符”PAR”。如果执行迹已经存在并且属于相同的执行序列(相同的场景)，那么与当前线对应的变迁将被标记为临时循环。如果一个变迁已经被标记为一个临时循环，就会更改变迁的关联操作符为“LOOP”。PM-EL算法如下所示。

算法PM-EL

1.Data:Trace trace set；

2.Result：CPN cpn；

3.Place NewPlace；

4.Color New_Color;

5.CPN New_CPN；

6.For each trace T in trace set New_Color=createNewCPNColor();//为每一条执行序列创建一个CPN颜色

7.For each activity a in T New_Place =creatPlace WithColor(a,New Color);

8.If(isCPNImpty())/若是CPN为空，直接添加库所到CPN中

9.Add_Place_To_CPN( New Place);

10.else If(is Not New(a))// New Placea不是新的

11.If(is ln Same Trace(a))/已经存在并且属于相同的执行序列即相同的场景

12.If(is Loop Marked( New CPN))

13.change_pervious_Transition(LOOP,New_CPN)；//修改变迁关联‘LOOP’

14.else

15.mark pervious_Transition(LOOP,New CPN)；

16.EndIf

17.else

18.If(is The Same thread())//属于在同一线程中

19.If(previous place have Transition( New CPV))//库所前已有变迁

20.Change_Transition_To_CPN('ALT,New CPN)；//修改变迁类型为’ALT’

21.Add_Place_To_CPN( New Place,New CPN);

22.else Add_Place_To_CPN( New Place,New CPN);

23.Add_Transition_To_CPN('SEQ,New_CPN)；

24.End If

25.else

26.If(is previous Main ThreadID())/如果前一个线程ID为主线程

27.Add Transition To CPN('PAR,New CPN);

28.Add Place To CPN( New Place,New CPN);//加入前置变迁‘par'

29.else

30.Add Place To CPN( New Place,New CPN);

31.End If

32.End If

33.End If

34.End If

35.End Foreach

36.End Foreach

37.return New CPN

3 仿真实验

在本节中，我们选择了一个信息查看程序示例。使用应用程序对多场景登录以及信息查看进行操作并产生日志。信息查看程序检测登录类型如果是普通用户登录，使用系统的登录线程(场景1)；员工登录增加两个部分，校验工号以及工种，每部分都是由不同的线程来解决(场景2)；管理员账号登录，需要对登录IP地址进行检测(场景3)；普通用户登陆后查看信息(场景4)；员工登录后查看信息(场景5)；管理员登陆后查看信息并对信息进行过滤(场景6)。不同用户登陆后查看信息是不同的。经过以上操作获得系统日志文件，这个文件包含系统当前运行时被检测类的对象的所有创建和销毁事件。对象请求的方法调用和返回事件也同时被记录。依据执行的父ID对日志进行聚类并记录执行次数，表1中数据字典对日志中的方法名及对象名进行相应替换，生成的最终增强日志如表2所示。

表1 事件坐标对应方法或对象

表2 增强日志详情

文章在此利用Java编程实现了算法，其算法复杂度为O(m*n),图形化界面如图3所示，功能包括txt、rtf格式日志导入及算法结果保存，CPN结果以节点形式输出。

图3 算法的实现插件(PMEL)及挖掘结果展示

图4形象的表达了算法的执行步骤，且每条执行序列均对应不同场景进行了遍历迭代，故日志的每一条执行序列与模型中的可达路径都是一一对应的。

通过定义4、5、6的描述可知L3、L8、L4,L10、L12、L14为选择关系，L6、L7为并发关系。在PM-EL算法结果中这些结构均被识别且通过颜色区别不同场景；

通过CPNtool4.0.1对PM-EL所获结构模型进行仿真实验(见图5)，此CPN模型为可运行的。另外通过定义2及图1、图2表述的映射规则，可将此CPN模型转化为UML模型，可更加直观展示系统的运行，并验证此方法结果的可扩展性。

图4 过程挖掘算法PM-EL执行示例图

图5 使用cpn tools 4.0.1对结果模型进行模拟可行

在此将日志导入Prom平台中，并利用Alpha Miner及IDHM(interactive Data-aware Heuristic Miner)进行挖掘，以突出PM-EL算法在不完备日志基础上对模型结构的识别能力。

图6 Alpha Miner挖掘结果

图7 IDHM挖掘结果(Frequency为0.1，Dependency为0.9，Binding为0.1，Conditions为0.5)

三个算法实验结果均有完整回路(即循环结构)，现就结果中选择结构和并发结构数量进行对比，如表3所示。

表3 选择、并发结构数量对比

4 结论

文章通过分析数据挖掘与过程挖掘的异同，说明日志的重要性，然后提出增强日志的概念。将系统日志中除事件执行外的一些可利用信息加入事件日志，基于增强日志提出过程挖掘算法PM-EL，依赖事件执行的附加属性识别结构关系。依据定义4、5、6，结果过程模型也是符合源增强日志的。通过UML序列图的转换说明了算法结果的可扩展性。即从增强日志中挖掘出附带场景信息的过程模型。

通过PM-EL算法所提取的过程模型可以为后续的模型修复及优化工作提供支持。在此文章的研究基础之上，未来可以利用增强日志提升模型修复精度，将模型优化细分为多场景有针对性的优化。