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

邵叱风 方贤文 盛梦君

摘要：过程挖掘的目的是通过分析系统中的日志以发现、构建和优化系统业务流程.，现有的过程挖掘算法大多采用从控制流角度记录和观察进程工作流的系统日志，且日志在使用前需进行大量预处理工作将其转换为算法可识别的事件日志，不仅仅增加了挖掘难度，最终挖掘所获过程模型所含属性单一，很难准确描述实际流程的运作。为减少预处理工作，增强过程挖掘算法挖掘能力，基于系统事件执行详情，通过可利用属性的提取，提出了增强日志的概念，并基于增强日志开发出一种新的过程挖掘算法。此方法利用增强日志中的附加属性，识别事件结构，通过有色Petri网的加入，挖掘出具有场景信息的过程模型。最后通过一个具体的挖掘实例进一步说明了该方法的可行性及结果的可扩展性。

关键词：过程挖掘;事件日志;过程模型;增强日志;有色Petri网

中图分类号：TP391.9

文献标志码：A

文章编号：1672-1098（ 2020）04-0025-08

作者简介：邵叱风（1995-），男，安徽合肥人，在读硕士，研究方向：Petri网、过程挖掘及模型修复。

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

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

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

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

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

1 准备知识

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

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

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

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

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

2.1 增强日志

27. Add Transition To CPN（ 'PAR， New CPN）;

28. Add Place To CPN（ New Place， NewCPN）;//加入前置变迁‘par'

29. else

30. Add Place To CPN（ New Place， NewCPN）;

31. End If

32. End If

33. End If

34. End If

35.End Foreach

36. End Foreach

37. retum New CPN

3 仿真实验

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

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

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

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

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

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

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

4 结论

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

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

参考文献：

[1] F CORUNESCU. Data Mining： Concepts， Models andTechniques[M].Blue Publishing House， ClujNapoca，2011：30-35.

[2] W VAN DER AALST，T WEUTERS，L MARUSTER.Workflow mining： discovering process models from e.vent logs [J]. IEEE Trans. Knowl. Data Eng. 16（ 2004）：1 128-1 142，

[3] L WEN，J WANC，W VAN DER AALST，et al.A novel ap-proach for process mining based on event types[C]//J.Intellig. Inform. Syst.32 （2009）： 163-190.

[4] D WANG，J CE，H HU， et al.Discovering processmodels from event multiset[J]. Exp. Syst. Appl. 39 （2012）：11 970-11 978.

[5] J COOK，A L WOLF. Discovering models of softwareprocesses from event- based data[M].ACM Transac.Softw. Eng. Methodol. （TOSEM）7（1998） 215-249.

[6] K G COMAN，A M ODLYZKO. Intemet growth： isthere a Moore's law for data traffic？ [J]. Handbook ofMassive Data Sets， Kluwer， 2001：47-93.

[7] BROUCKE S K L M V，VANTHIENEN J.BAESENSB. Declarative process discovery with evolutionary com-puting[ C]// 2014 IEEE Congress on Evolutionary Computation （ CEC）. IEEE， 2014 ：2 412-2 419.

[8]MARUSTER L， WEIJTERS A， VAN DER AALST W M P， et al. A rule-based approach for process discovery[J]. Data Mining & Knowledge Discovery， 2015， 13（1） ： 67-87.

[9]LEEMANS S J J， FAHLAND D， VAN DER AALST W MP. Scalable process discovery and conformance chec-king [J]. Software & Systems Modeling， 2018， 17（2） ： 1-33.

[10] WEIJTERS A， VAN DER AALST W M P， DE ME-DEIROS A K A. Process mining with the heuristicsminer- algorithm [ J ] . Technische Universiteit Eind-hoven， Tech. Rep. WP， 2006， 166： 1-34.

[11] WEUTERS A T， RIBEIRO J J. Flexible heuristicsminer（ FHM） [ C ]//Proceedings of IEEE Conferenceon Computational Intelligence and Data Mining.Washington， D. C. ， USA： IEEE， 2011 ：310-317.

[12]LEEMANS S J J， FAHLAND D， VAN DER AALST WMP. Discovering block-structured process models frommcomplete event logs [ C ]//Proceedings of Intemation-al Conference on Applications and Theory of Petri Netsand Concurrency. Berlin， Germany： Springer-Verlag，2014 ：91-110.

[13] TAX N， SIDOROVA N， HAAKMA R， et al. Mininglocal process models[ J] . Joumal of Innovation in Dig-ital Ecosystems ， 2016 ，3 （ 2） ： 183 -196.

[14] 邵叱風，基于流程挖掘的并行优化算法 [ J] .赤峰学院学报（自然科学版） ， 2019. 35（ 10） ： 66-70.

[15 ]方贤文. Petri网行为理论及其应用 [ M ] .上海 ：上海交通大学出版社 ，2017 ：39-40.

[16]VAN DER AALST W MP. Process mining： discovery， conformance and enhancement of business processes [M ]. Springer Publishing Company， Incorporated，2011 ：56-89.

[17] ZHANG L， ZEICLER B P， LAILI Y. Introduction to Model Engineering for Simulation [ M ] . Model Engi-neering for Simulation， 2019 ： 43-56.

[18] CHUANYI LI， JIDONC GE， UGUO HUANC， et al.Process mining with token carried data[ J] . InformationSciences， 2016 ： 34-48.