基于区域事件日志的过程挖掘方法研究

石弯弯，刘祥伟，王丽丽

（安徽理工大学 数学与大数据学院，淮南 232001）

基于区域事件日志的过程挖掘方法研究

石弯弯，刘祥伟，王丽丽

（安徽理工大学 数学与大数据学院，淮南 232001）

过程挖掘是从事件日志中运用挖掘方法得到过程模型。已有的挖掘方法在处理大量事件日志上还存在一定的局限性，提出一种基于区域日志过程挖掘方法，首先根据事件日志间任务的可达性分为不同区域，在此基础上将不同区域日志转化为间接继承矩阵再对应Petri网，建立区域过程模型；然后，将各个区域进行融合，得到完整的过程模型。最后，通过分析建模实例验证算法的可行性。

过程挖掘；Petri网；可达性

近年来，随着信息技术的发展，过程挖掘的应用越来越广泛。过程挖掘的目的是从事件日志中提取模型，发现真实的过程并对其进行监控、改进。各种过程发现算法已经被提出并且被采用，文献［1］中基于局部事件的挖掘算法，通过给每个事件分配一个非空的域集定位事件；文献［2］中描述了从不完备事件日志中发现流程模型结构,分析不完备日志对过程发现的影响，引入概率行为，利用这些关系处理不完备日志，给出基于这些概率关系的算法,用于重新发现流程模型；文献［3］中启发式的算法在构建过程模型时考虑到了任务的频率；文献［4］中在考虑间接继承的基础上把事件日志任务的可达性用矩阵表示,根据矩阵值把总体事件日志分离成子日志，不断迭代，自动发现流程块结构；文献［5］中基于局部日志的过程发现把Petri网分为不同区域，再对不同区域分析；文献［6］中基于语言的域挖掘算法，算法中域理论从行为的演变方面来构建Petri网；文献［7］中采用了不同的方法，把过程挖掘问题分解成了较小的多个问题，从而提高了过程挖掘效率；文献［8］介绍了从事件日志中挖掘出块结构的过程模型方法；此外在文献［9］中提出对于过程发现模型，一般使用4个标准进行判断：适合性、简洁性、精确性、一般性，避免过程模型的过度拟合或低度拟合。

本文采取的方法：（1）将事件日志任务的可达性分为不同区域；（2）各个区域中将事件日志中任务的可达性转化为间接继承矩阵，得到子过程模型；（3）子过程模型作为一个块结构，将各个块结构再次转化为间接继承矩阵；（4）将得到的间接继承矩阵转化为Petri图得到最终过程模型。

1 基本概念

1.1 Petri网基本概念

定义［10］1 满足下列条件的三元组N=(P,T,F)称作一个网：

1.2 行为轮廓的定义

在迹语义的基础上，行为轮廓描述了一个网系统的行为特征和变迁的潜在并发的顺序。它的定义是在弱序概念的基础上，给出了变迁对之间的依赖关系。

定义［11］2 （弱序）设是一个网，初始标识为M0，一对变迁是弱序，记作ta≻tb，当且仅当存在一个发生序列σ=t1,...,tn使得并且有a=i,b=i，1≤i＜j≤n。

（4）若t1≻t2且t2≻t1，则称交叉序关系，记作t1×t2；

2 基于区域日志的挖掘方法

2.1 基于区域的事件日志

由于现在的过程模型越来越复杂，而且许多网系统可以被分为不同区域，因此可以将图1过程模型化，根据任务的相关性分为5个区域，r1和r5为公共区域，r2，r3，r4区域互不交互，因此在分析过程模型时，可以针对不同区域进行分类讨论。本文讨论根据事件日志任务的可达性，将事件日志分为不同模块，针对不同模块进行挖掘，提高过程挖掘效率。

图1 区域Petri网模型

2.2 将日志转换成间接继承矩阵值

要求的事件日志转化成间接继承矩阵，首先要引用以下定义：

定义4：（间接继承运算符）在工作流中定义间接继承基础命令关系如下：工作流例如令ab∈T定义为：

（1）a≫wb仅当存在且例如（间接继承）

（2）a→→wb当且仅当a≫wb且b≫wa（因果关系）

（3）awb当且仅当（无直接关系和间接关系）

定义5：（间接继承矩阵）定义L为n个事件组成的日志，且表示日志中的一组事件间接继承用矩阵是二进制矩阵(0,1)当

（1）若Mi,j=1时，则Ai→LAj；即事件日志任务存在因果关系；

（2）否则Mi,j=0时，则Ai→LAj；即事件日志任务无直接和间接关系。

基于日志行为轮廓中的各种结构利用继承矩阵表示日志的可达性如下： /

（1）顺序模式

在Petri网中A，B，C D顺序模式如图2所示。

图2 顺序模式Petri网图

表1 顺序模式对应的继承矩阵

（2）选择模式

选择模式相互排斥，在Petri网中如图3所示。

图3 选择模式Petri图

表2 选择模式对应的继承矩阵

如上表2的值表示了B，C之间没有继承关系，且对A，D的作用值是相等的。

（3）循环模式

在Petri图中事件日志任务B、C循环发生，如图4所示，对应的继承矩阵如表3所示。

图4 循环模式Petri图

表3 循环模式对应的继承矩阵

B C D 0 0 0 1 1 0 1 1 0 1 1 0

（4）平行模式

在Petri网中事件日志任务B，C同时发生,如图5所示，对应的继承矩阵值如表4所示。

图5 平行模式Petri图

表4 平行模式对应的继承矩阵

基于上述对模型中事件日志任务的可达性对模型进行划分区域及Petri网与继承矩阵的转换，提出了基于区域事件日志算法，算法步骤如下：

算法：基于区域事件日志的挖掘算法

输入：事件日志；

输出：过程模型；

（1）根据事件日志任务因果关系将事件日志分为不同区域ri(i=1,2,3...n)；

（2）将各区域事件日志任务因果关系转化为间接继承矩阵，分别计算出行和列值的总和；

（3）选择任务组（两个或更多个）具有最高的行中的值的总和；

（4）为选定的任务，运用逻辑算子的相似性；

（5）选定的任务是在一个块结构，试图发现事件日志任务所属模式；

（6）创建一个子Petri网Ni=(1,2,3...n)框架；

（7）重复未选中的任务执行所有步骤直至所有任务都被选中；

（8）重组Petri网流程框架，得到最终模型N。

3 实例分析

为了验证基于区域事件日志的挖掘算法，给定一组事件日志，其中事件日志包含6种情形，任务包括A，B，C，D，E，F，G，H，I；根据事件任务的可达性将6种情形分为2个区域，其中事件任务A，B，C为r1区域；事件任务D，E，F，G，H，I为r2区域；r1和r2区域间的事件任务相互独立，事件任务D为公共区域；如图6所示。

图6 对应的区域事件日志

将图6中各区域的事件日志用继承矩阵表示。

（1）根据日志r1区域用矩阵表示如表5所示。

表5 间接继承矩阵

图7 r1区域过程模型

则得出B，C是循环关系且A，BC，D是继承关系（2）根据日志r2区域用矩阵表示，如表6 所示。

表6 间接继承矩阵

由表6得E,F是平行关系且对D，G，H，I，影响值相同，分析得出E，F为平行关系，则E,F归为一类，继续用矩阵表达在日志中D，EF，G，H，I的关系。

表7 间接继承矩阵（减少）

由表7得出G，H为选择关系，且对D，EF，I的影响值相同。

表8 间接继承矩阵（减少）

由表8得出EF，GH为选择关系，且对D，EF，GH，I的影响值相同，由此分析得出E，F为平行关系，G，H为选择关系，则EF，G，H为选择关系，用Petri网图表示，如图8所示。

图8 r2区域过程模型

（3）合并r1和r2区域

表9 间接继承矩阵

由表9矩阵值得出ABC，DEFHHI为继承关系，由此得出日志的过程模型Petri图如图9所示。

图9 融合区域的过程模型

4 结论

基于Petri网及行为轮廓的研究，通过对事件日志任务的可达性分析，对事件日志划分区域，再转化为间接继承矩阵，最终得到过程模型。对事件日志分区域能大大减少计算量，避免过程模型的过度拟合性。

本文虽然在过程挖掘上减少了计算量，但是需要保证事件日志区域划分的正确性，针对过程挖掘还有许多问题有待解决，例如通过挖掘方法得到的过程模型是否与事件日志相一致，需要在以后的工作中继续研究。

［1］AalstWVD,Weijters T，Maruster L.Workflow mining：discovering process model from event logs［J］.IEEE Transactions on Knowledge and Data Engineering，2004，16（16）；1128-1142.

［2］Leemans S J J，Fahland D，Aalst W M P V D.Discovering block-structured process models from incomplete event logs［M］.Application and Theory of Petri Nets andConcurrency.Sprin-erInternationalPublishing，2014：91-110.

［3］Carmona J，Cortadella J，Kishinevsky M.A Regionbased algorithm for discovering Petri Nets from event logs［J］.Springer Belin Heidelberg，2008（5240）：358-373.

［4］Boushaba S，Kabbaj.MI，BakkouryZ.Process discovery：automated approach for block discovery［C］.International Conference on Evaluation of Novel Approaches To Software Engineering.IEEE，2014：1-8.

［5］Aalst WMPVD，KalenkovaA，Rubin.V，et al.Process discovery using localized events［M］.Application and Theory of Petri Nets and Concurrency，Springer International Publishing，2015：287-308.

［6］Leemans SJJ，Fahland D，Aalst WMPVD.Discovering block-structured process models from event logs-a constructive approach［C］.International Conference on Application and Theory of Petri Nets and Concurrency，2013，23（5）：311-329.

［7］A.K.Alves de Medeiros.Genetic process mining PhD thesis［J］.The Nethherlands，2006，21（3）：105-107.

［8］Aalst W M P V D.A general divide and conquer approach for process mining［C］.Computer Science and Information Systems.IEEE，2013.

［9］Werf J，Kaats E.Discovery of functional architectures from event logs［C］.International Workshop on Petri Nets and Software Engineering，2015：227-243.

［10］吴哲辉.Petri网导论［M］.北京：机械工业出版社，2006：15-78.

［11］Weidlich M，Mendling J，Weske M.Efficient consistency measurement based on behavioral profiles of process models［J］.Software Engineering IEEE Transactions on，2011，37（3）：410-429.

Research on Process Mining Based on Region Event Log

SHI Wanwan，LIU Xiangwei，WANG Lili
（College of Mathematics and Big Data，Anhui University of Science and Technology，Huainan 232001）

The mine model of process is gained by mining method from event log.With the limiting from exsiting mining method，it is difficult to dealing with a large number of event logs.In this paper，a mining algorithm based on regin log is proposed.Firstly，according to the accessibility of task between different event logs，the different regio logs are transformed into indirect inheritant martrix.The complete model can be got by mixing them together.Finally，the effectiveness of our model is verified through analysis.

process mining；petri net；accessibility

TP391.9

A

1672-9870（2017）04-0120-05

2017-03-28

国家自然科学基金（61402011，61572035）；安徽省自然科学基金（1508085MF111）；安徽省高校自然科学基金重点项目（KJ2014A067）

石弯弯（1993-），女，硕士研究生，E-mail：1091258607@qq.com