基于Petri网接口变迁的交互流程模型模块网挖掘方法

翟鹏珺，方贤文，刘祥伟

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

基于Petri网接口变迁的交互流程模型模块网挖掘方法

翟鹏珺，方贤文，刘祥伟

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

交互流程模型的模块分解是查找流程模型变化域的核心内容之一，已有的模块分解方法多是基于完整的流程模型，通过挖掘对比流程模型中所有活动的行为关系将流程模型分解为多个模块网。但是在基于单纯的事件日志分解交互流程模型方面，目前的模块分解方法存在一定的局限性。提出基于Petri网接口变迁的交互流程模型模块网挖掘方法，首先基于系统运行所记录的局部有效事件日志确定其中各活动间的前驱后继关系，并得到相应的活动前驱后继关系表。然后，基于前驱后继关系频繁的活动查找接口变迁，同时考虑无后继变迁的活动。其次，通过分析接口变迁的前集变迁查找交互流程模型中各个模块网的初始变迁，并由初始变迁开始，利用活动前驱后继关系表，逐个添加活动，以此挖掘交互流程模型的模块网。论文最后通过实例验证该优化方法的有效性。

Petri网；事件日志；接口变迁；模块分解；模块网

模块最初由Gallai提出［1］，常用于研究图表、2-结构、分类方面等。如今，随着模块应用的普遍性，许多研究着手将模块和流程模型相结合对交互流程模型进行分解。合理的模块分解不仅能清晰地分析交互流程模型的结构，还有利于分析行为对间的关系，从而快速有效地查找流程模型中的变化域或分析模型。

目前在模块分解方面，已经提出了一些研究。文献［2］提出基于微分Petri网的业务流程模块适配方法，指出修复变化域最容易想到的方法是模块替换，利用极小支持数来确定最佳适配模块，使其满足结构上的最稳定性。良构流程模型在拓扑学上与基于Petri网行为轮廓的弱序关系图结构相关。一种基于弱序关系图的模块分解方法在文献［3］中被提出，利用模块分解对源流程模型进行抽象，根据模块分解的特点构造其抽象模型，并说明模块分解树可以在线性时间内被构建。对业务流程模型进行模块分解，不仅能够将流程模型进行细化，还可以按需要进行分类。文献［4］结合模块分解的优势，基于模块行为轮廓分析模块间的行为关系，并以模块间的共用输出点为观测点，分析业务流程模型的变化域。文献［5］利用功能构架将功能模块分解，并基于通讯行为轮廓查找特征的模块日志，从而运用归纳挖掘算法［6］挖掘模块网。文献［7］通过绘制所有模块的所有事件的数据，可以很容易地可视化模块的类型随时间的变化模式。但上述的交互流程模块分解方法要求已知完整的流程模型，对于只知道系统运行所记录的事件日志的情况并不适用。针对这一缺陷本文提出了基于Petri网接口变迁挖掘交互流程模型模块网的模块分解方法，该方法克服了必须挖掘完整流程模型的缺陷，能够基于简单的事件日志有效挖掘交互流程模型的模块网。

1 动机例子

目前，储蓄卡、支付宝等支付方式在购物过程中被更多顾客采用。以某商场支付宝支付系统为例，考虑其系统运行所记录的事件日志，如表1所示。表1中所记录的事件日志并非系统运行的所有事件日志，且其中可能包含系统不能重放的事件日志，即无效事件日志。

模块分解在分析流程模型结构和查找流程模型变化域的过程中具有很重要的作用，有效的模块分解可以更快查找出模型中的变化域，从而很好的优化模型。但是对于只有事件日志的系统（如支付系统），已有的模块分解方法首先要基于事件日志挖掘出完整的交互流程模型，然后基于完整的模型进行模块分解，在一定程度上具有局限性。为了在不挖掘出完整的流程模型情况下合理分解流程模型，本文提出基于Petri网接口变迁的交互流程模型模块网的挖掘方法。

表1 支付系统的事件日志

2 基础知识

下面仅介绍与本文密切相关的概念，其它概念及术语参见文献［8］。

定义1 （Petri网）设一个Petri网N=(P,T,F)是一个三元组：

（1）P和T分别是有限的库所集和变迁集；

（2）P≠ϕ，T≠ϕ且P⋂T=ϕ；

（3）F=(P×T)⋃(T×P)表示PN的流关系，(P⋃T,F)是强连通图；

一个Petri网N=(P,T,F)，给定一个节点，则有n的前集的后集另外，一个流程模型Petri网PN和一个初始标识M0，就确定了一个标识网，变迁t在标识M0下可以发生（M0[t＞），如果称M1为从M0可达的，若存在t∈T，使得M0[t＞M1。

定义2（标签Petri网）一个网BN=(N,l)是标签Petri网，其中N=(P,T,F)是一个Petri网。标签函数l∈T→UA，UA是活动名称集［10］。

一个标签Petri网BN=(N,l)定义了一个Petri网中各个节点和流关系的有向图，N中每个可见变迁t∈dom(l)都有一个活动标签标签Petri网是Petri网的一个特殊子集，可以被用来构建流程模型。在一个标签Petri网BN中，用i来表示初始标识，用f来表示终止标识。

定义3（事件日志）A是一个有限的活动集。迹可以被描述为活动的一个有限序列，即σ∈A∗。一个事件日志L是迹的一个多重集，即L∈Μ(A∗)［11］。

定义4（模块网）N=(P,T,F,l)是一个标签Petri网：

（4）空集ϕ和网N中的所有活动集TA所对应的模块网，是网N的平凡模块网，其他均为非平凡模块网［3］。

3 基于Petri网接口变迁逐步挖掘交互流程模型的模块网

已有的交互流程模型模块分解方法主要基于完整的流程模型，本部分基于Petri网接口变迁提出交互流程模型模块网的挖掘算法。该算法主要是基于有效的事件日志，确定各个事件活动的前驱后继关系，结合活动前驱后继关系分析查找接口变迁和初始变迁。然后，由初始变迁开始逐个添加后继活动，以此挖掘交互流程模型的模块网。挖掘出的模块网不一定为合理的流程模型，为检验其有效性给出完全流程模型的定义。

定义5（完全流程模型）模型N=(P,T,F,l)是一个带标签的流程模型，M:P→{0,1…}是流程模型中的一个标识，χ是标识集合，N是一个完全流程模型，当且仅当对任意的，总存在σj使得

定义7（前驱后继关系）模型N=(P,T,F,L)是一个带标签的流程模型，对任意的变迁t∈T存在一个或多个前驱变迁和后继变迁。前驱变迁，且前驱变迁有直接的流关系到变迁t后继变迁，且变迁t有直接的流关系到后继变迁

算法1：挖掘交互流程模型的模块网

输入：事件日志Li

步骤1：确保输入事件日志Li为有效的日志。即对每个事件日志，在系统中都可以被有效重放。删除无效的事件日志，保留有效事件日志。转步骤2；

步骤2：基于步骤1所保留的有效事件日志中各个活动事件的前驱后继关系，绘制相应的活动前驱后继关系表。转步骤3；

步骤3：查找活动前驱后继关系表中活动关系紧密的部分，在图表中对该部分活动进行标记。转步骤4；

步骤4：对步骤3的标记部分进行分析，确定接口变迁。图表中被标记部分中的活动ej（j≥1），若其无后继活动，则记录该活动为接口变迁。转步骤5；

步骤5：考虑活动前驱后继关系表中无后继活动的活动ej。若其至多5个连续前驱活动中，至少存在一个活动e，使得在不发生ej的情况下仍有合理的发生序列σj，则该活动ej无后继活动是由于token数不够。且该活动ej与接口变迁相连，为接口变迁的前驱活动e←j。否则，该活动为结束变迁te。转步骤6；

步骤6：确定初始变迁ts。接口变迁前集变迁中，后继变迁最多的变迁以及总是发生在某些前集变迁之前的活动为模块网的初始变迁。转步骤7；

步骤7：由初始变迁开始，通过活动前驱后继关系表，逐个添加活动，直至无后继活动或结束变迁。转步骤8；

图1 算法流程图

4 实例分析

本部分以支付宝支付系统（动机例子）的事件日志为例来分别说明本文基于Petri网接口变迁挖掘交互流程模型模块网的方法的可行性。

分析表1中14个事件日志，对于有效日志中每个活动得到其前驱活动和后继活动。如案例1中活动A无前驱活动，其后继活动为B；活动D的前驱活动和后继活动分别为C和I；活动J无后继活动，其前驱活动为I。根据每个活动的前驱后继关系绘制活动前驱后继关系表，表中纵向表示各个活动的前驱关系，横向则表示各个活动的后继关系。从表2中很容易可以标记出前驱后继关系紧密的活动，如表2中方框所标记的活动。对于表2中左上角的方框，其中包含了4个活动A、B、C、D的前驱后继关系。可以看出活动D无后继活动，所以活动D为接口变迁，同理可知活动N和Q也是接口变迁。

表2 活动前驱后继关系表

另外，由表2可以观察到活动H、J和R均无后继活动。由于活动H和J的前驱活动G和I存在其他后继活动L和K，且由案例7、8、11等可知模型中存在不包含活动H和J的发生序列使得活动L和K有效发生，所以活动H和J无后继活动是因为不满足Petri网变迁发生规则，即其前集库所中的token数不够。但是，对于活动R的连续5个前驱活动Q、P、L、O、K，均没有不包含活动R的合理发生序列，所以判定活动R为结束变迁。

考虑接口变迁D的前集变迁A、B和C，由表2可知活动A的发生总在活动B发生之前，且活动C的后继活动数最多（3个），由此判定活动A和活动C为初始变迁（同理可得活动M为初始变迁）。根据活动的前驱后继关系，由初始活动A，C和M开始，逐个添加活动无后继活动J、H或结束变迁R。由于活动J、H前集库所中的token数不够，其后继活动为接口变迁D。综上所述，支付系统的三个模块网如图2所示。

图2 支付系统模块网

5 结语

目前，交互流程模型模块分解是查找流程模型变化域的重要任务之一。基于完整交互流程模型模块分解的方法要求必须已知系统的完整流程模型，这类模块分解方法在只得知系统运行所记录的事件日志的情况下具有一定的局限性。为了在不挖掘完整流程模型的前提下合理分解交互流程模型，本文提出了基于Petri网接口变迁的交互流程模型模块网挖掘方法。该方法避免了挖掘过程中存在的一些不必要的工作，在一定程度上减少了挖掘过程的工作量。而且，基于事件日志中各个活动的前驱后继关系查找接口变迁，提高了本文挖掘算法的精准度。

未来关于交互流程模型模块网的挖掘，进一步的研究主要是针对存在交叉序结构的流程模型以及对挖掘出的模块网进行一致性检测评估。

［1］Gallai T.Transitiv orientierbare graphen［J］.Acta Mathematica Hungarica，1967，18（1-2）：25-66.

［2］方贤文，陶小燕，刘祥伟.基于微分 Petri网的业务流程模块适配方法［J］. 电子学报，2017，45（4）：777-781.

［3］Sergey Smirnov，Matthias Weidlich，Jan Mendling.Business process model abstraction based on synthesis from well-structured behavioral profiles［J］.International Journal of Cooperative Information Systems，2012，21（01）：55-83.

［4］Fang X，Liu L，Liu X.Analyzing method of change region in BPM based on module of Petri net［J］.Information Technology Journal，2013，12（8）：1655-1659.

［5］van der Werf J M，Kaats E.Discovery of functional architectures from event logs［C］//PNSE@Petri Nets，2015：227-243.

［6］Leemans S J J，Fahl and D，van der Aalst W M P.Discovering p tit e=quot;pagenum er_eboo models from event logs-a constructive approach［C］.International Conference on Application and Theory ofPetri Nets and Concurrency，Springer Berlin Heidelberg，2013：311-329.

［7］Buijs J，van der Aalst W M P.Enabling interactive process analysis with process mining and visual analytics［J］.BIOSTEC，2017（2017）：573-578.

［8］吴哲辉.Petri网理论［M］.北京：机械工业出版社，2006：6-22.

［9］Smirnov S，Weidlich M，Mendling J.Business process model abstraction based on behavioral profiles［C］.International Conference，Heidelberg：Springer Berlin Heidelberg，2010（6470）：1-16.

［10］Aalst W M P V D，Kalenkova A，Rubin V，et al.Process discovery using localized events［M］.Application and Theory of Petri Nets and Concurrency，2015：287-308.

［11］Kalenkova A A，Lomazova I A.Discovery of cancellation regions within process mining techniques［M］.IOS Press，2014.

［12］Zha H，Wang J，Wen L，et al.A workflow net similarity measure based on transition adjacency relations［J］.Computers in Industry，2010，61（5）：463-471.

The Module Net of Interaction Process Model Mining Method Based on Interface Transitions of Petri Net

ZHAI Pengjun，FANG Xianwen，LIU Xiangwei
（School of Mathematics and Big Data，Anhui University of Science and Technology，Huainan 232001）

Module decomposition of the interaction process model is one of the core contents of search change region of process model.The existing module decomposition methods are mostly based on a complete process model，the process model is decomposed into multiple module nets by mining and comparing the behavior relation of all activities in the process model.However，there are some limitations in the current module decomposition method of decomposing interaction process model just based on the event log.This paper puts forward a mining method of module net of interaction process model based on the interface transition of Petri net.Firstly，determine the predecessor and successor relation of the activities that from the local effective event logs which are recorded by the system running，and obtain the corresponding table of predecessor and successor relation of activities.Then，search the interface transition based on the activities with frequent precursor successor relation，and consider the activities without successor transition.Secondly，determine the initial transition in each module net of the interaction process model by analyzing the pre-set of the interface transition，and add activity one by one that start from the initial transition using the table of precursor successor relation of activities to mining the module net of interaction process model.Finally，an example is given to prove the effectiveness of the mining method.

Petri net；event log；interface transition；module decomposition；module net

TP391.9

A

1672-9870（2017）05-0132-04

2017-06-05

国家自然科学基金项目（61572035，61402011，61272153）；安徽省自然科学基金（1508085MF111）；安徽省高校自然科学基金重点项目（KJ2014A067）；安徽理工大学研究生创新基金（2017CX2048）；安徽省优秀青年基金项目（ZY290）

翟鹏珺（1991-），女，硕士研究生，E-mail：877191453@qq.com