基于Petri网行为轮廓从事件日志中挖掘隐变迁的方法

王晓悦，方贤文，曹芮浩

(安徽理工大学理学院 安徽　淮南　232001)



基于Petri网行为轮廓从事件日志中挖掘隐变迁的方法

王晓悦，方贤文，曹芮浩

(安徽理工大学理学院 安徽淮南232001)

隐变迁是指一些存在于过程模型中，但没有出现在日志序列中的变迁。这样的变迁会大量存在于现实的模型中。从事件日志中寻找挖掘隐变迁的方法是过程挖掘技术的一个重要的难题。目前针对自由选择网有一些解决办法，但是对于复杂的过程模型有一定的局限性。本文提出了基于Petri网行为轮廓寻找隐变迁的方法。首先根据发生频率最高日志序列得出源模型，再根据剩余的日志序列一步步优化源模型从而找到隐变迁，最后通过评价指标来判定模型的合理性。

事件日志；行为轮廓；隐变迁；过程模型

在近几年，随着计算机的发展，各大企业都在寻找一种不但可以满足客户要求还可以通过提高业务水平节约成本的办法，换句话说就是用更短的时间生产更多的产品给客户提供更好的服务，从而提出了业务流程挖掘这项技术。但是挖掘业务流程模型的过程中往往会出现一些存在于过程模型中，但没有出现在日志序列中的变迁，同时这样的变迁又大量存在于现实的模型中。从事件日志中挖掘隐变迁可以很好的还原模型，提高操作的运转效率，既而达到高效率的生产及服务。

在日志中挖掘不可见变迁最开始是由W.M.P.van der Aalst等人提出来的，他分析了不可见任务产生的原因。在文献[1]中提出了Petri的相关概念。在文献[2-4]17中有提到不可见任务在哪几种情形下产生。在过程挖掘中常常会因为类似的原因出现一些存在于过程模型中，但没有出现在日志序列中的变迁。这样的变迁称之为隐变迁。然而从事件日志中挖掘隐变迁在流程挖掘中是一个巨大挑战。文献[5]163-176中提出了判定日志与模型一致性的分析方法，通过日志序列在模型中重放来计算其合理性和适当性。国外学者van der Aalst已经做了很多关于不可见任务挖掘的文章，文献[6]中给出了Petri网的相关知识。文献[7-8]讲述了有关流程挖掘的方法。文献[9]先介绍了行为轮廓的相关概念，之后Weidlich. M等人又提出因果行为轮廓的概念，因果行为轮廓是行为轮廓的一个补充及扩展在原来的三种关系基础上添加了共生关系。在文献[10]中基于流程挖掘提出了一种新颖的方法去解决异常的事件日志，这种方法能够形成一个与源模型相关的新的进程模型，最后基于新的进程模型重新执行事件日志。在文献[11]中把流程挖掘的技术运用到社会网络服务中检测异常行为的出现，使得社会网络服务系统更加完善。

在流程挖掘方面，文献[12]中给出了日志的相关概念。在文献[13]里给出了一个新的建模方法，此建模方法支持精确流程建模。文献[14]提出了一种与Web服务的相关的挖掘。文献[15]将流程挖掘技术运用到现实的结账过程中，结果会对其产生影响并取得进步。文献[16-17]说明了流程挖掘这项技术可以运用在医疗方面，介绍了基于过程挖掘这项技术来分析门诊的流程，并对其数据进行集成、探索和分析。提出了PALIA算法，把流程挖掘这项技术运用到卫生保健的设计和质量控制的流程。文献[18]在挖掘过程中分别从用户、时间的角度来对比方法的可用性。文献[19]将流程挖掘技术运用在现实教育中，通过对学生行为的分析来促进流程比较。

本文主要通过行为轮廓的关系来挖掘事件日志中的隐变迁。通过发生篇频率最高的且最长的日志序列得出源模型，再通过剩余的序列一步步优化。最后通过计算合理性及适当性得出所挖掘出模型的完备性。这种方法能够方便快捷的挖掘出日志中的隐变迁，从而使得模型更加完备。

1　研究动机

在本文的介绍中，已经提到了挖掘隐变迁的重要性，并且介绍了挖掘隐变迁的算法。在实际生活中，不乏存在不可见任务的业务流程日志。本节中利用一个简单的例子来证明隐变迁的存在性及挖掘隐变迁的重要性。下面给出了一个操作记录的日志序列L：{ABCEDFGHJ， ABEDFGHJ， ABJ， ABCEGHJ，ABEGHJ，ABCDEFGHJ，ABDEFGHJ，ABDCEFGHJ，ABDFCEGHJ，ABCEGDFHJ，ABCEDGFHJ，ABCDEGFHJ，ABDCEGFHJ}

α算法挖掘出来的模型如图1、图2所示。

图1　挖掘的模型图

图2　挖掘的模型图

分析图1与图2可知，这两个模型的合理性与行为适当性的值偏低。在运转的过程中会出现死锁的情况。而且它们产生的日志轨迹并不符合过程挖掘的准则。在过程挖掘中所得到的模型必须完全覆盖所有的日志轨迹。在本文的第四部分就介绍了基于行为轮廓挖掘日志中的隐变迁的合理性。

2　基本知识

这部分介绍了petri网的相关概念。

定义1[6]324(流程模型)设P=(A，ai，a0，C，F，T)为一个六元组的流程模型，

-A为一个非空的活动变迁节点集，C为控制流节点集，A和C不相交；

-ai∈A为一个最初的活动变迁，a0∈A为一个最终的活动变迁；

-F⊆((A{a0})∪C)×((A{ai})∪C)为流关系；

-T∶C|→{and，or，xor}流程模型控制流的类型。

定义2[6]325(弱序关系(流程模型))设P=(A，ai，a0，C，F，T)是一个六元组的流程模型，εp为它的执行序列集。≻P⊆(A×A)包含所有的变迁对(x，y)，如果εp存在一条执行序列σ=n1，…，nm，并且存在j∈{1，…，m-1}，j

流程模型中弱序关系是以变迁对为基础的，在弱序关系的基础上又定义了变迁集合的三种关系即严格序关系、排他序关系和交叉序关系。这三种关系称为行为轮廓。

定义3[6]325(行为轮廓(流程模型))设P=(A，ai，a0，C，F，T)为一个六元组的流程模型，变迁对(x，y)∈(A×A)至多存在下面三种关系的一种：

-严格序关系→p，当且仅当x≻py，y≻/px.

-排他序关系+p，当且仅当x≻/py，y≻/px

-交叉序关系‖p，当且仅当x≻py，y≻px.

这三种关系的集合BP={→P，+P，‖P}组成了行为轮廓。

此外，如果变迁对(x，y)满足严格序关系，即x→y，那么变迁对(y，x)满足逆严格序关系，即y→-1x。

下面介绍了关于日志的行为轮廓的相关概念。与流程模型行为轮廓的定义方式类似，日志的行为轮廓是定义在日志弱序关系的基础上的。

定义4[6]327(弱序关系(日志))设LP=n1，…，nm是流程模型P=(A，ai，a0，C，F，T)中的一条日志。弱序关系≻L⊆(AL×AL)包含了所有的变迁对(x，y)，如果存在两个下标指数j，k∈{1，…，m-1}使得j

定义5[6]327(行为轮廓(日志))设LP=n1，…，nm为流程模型P=(A，ai，a0，C，F，T)中的一条日志，变迁对(x，y)∈(AL×AL)至多存在下面两种关系的一种：

-严格序关系→L，当且仅当x≻Ly，y≻/Lx.

-交叉序关系‖L，当且仅当x≻Ly，y≻Lx.

这两种关系的集合BPL={→L，‖L}称之为日志中的行为轮廓。

注：一条日志中的两个活动变迁是不存在排他序关系的。

3　基于行为轮廓挖掘事件日志中的隐变迁

在本文的介绍中已经提到，在过程挖掘中寻找隐变迁的重要性。文献[2]15中也已经给出了寻找不可见任务的算法，本文的这一部分将运用行为轮廓的的关系定性分析日志序列，从而寻找隐变迁，最终达到还原模型的目的，此方法可以直观，简单且不失准确性的还原模型。下面首先给出了隐变迁的形式化定义，再给出基于Petri网行为轮廓挖掘隐变迁的一个算法。

首先根据日志序列在模型中的重放来评价模型的合理性程度，下面根据[5]163-176中合理性的判断标准。

式中：k为给定日志中的不同轨迹数，n为日志轨迹中所含的数目，m为日志轨迹中缺少的标识数，r为日志轨迹中遗留的标识数，c为日志轨迹中消耗的标识数，p为日志轨迹中产生的标识数。

最后，在f→1的情况下再考虑行为适当性aB(指的是所观察到的行为在此模型中的精确程度)。

式中：k为给定日志中的不同轨迹数，n为日志轨迹中所含的数目，x表示日志轨迹重放时就绪变迁的平均数目。m表示模型中可见任务的个数。

定义6[12]21(日志的弱行为轮廓)设L为一条日志，对任意两个变迁P，Q∈L，则P与Q之间的至多存在下面三种关系的一种：

1) 如果满足Ν(P，Q)≠0∧Ν(P，Q)=0，则称为严格序关系→L，记作P→LQ；

2) 如果满足Ν(P，Q)≠0∧Ν(P，Q)≠0，则称为交叉序关系‖L，记作P‖LQ；

3) 如果满足Ν(P，Q)=0∧Ν(P，Q)=0，则称为排他序关系+L，记作P+LQ。

我们称集合BL={→L，‖L，+L}为日志L的弱行为轮廓。

其中，对任意两个变迁P和Q，N(P，Q)=n，n表示以PQ形式在所有执行日志中出现的次数。下面给出一组日志序列{ACDE，ABDE，ADBE，ADCE}，根据定义6可以画出日志活动关系如表1所示。

表1　活动关系表

定义7(标记函数[2]75)T′是进程模型的变迁集合，L′是对应的日子序列集合，标记函数l∈T′→L′是一个偏序标记函数，它把每一个变迁和日志序列相关联。

定义8(隐变迁)T′是进程模型的变迁集合，l代表来自T′的标记函数的定义域，变迁t∈T′被称为隐变迁当且仅当t∉dom(l)，即t不在l的定义域范围内。

下面给出隐变迁常出现的几种类型：

1) 给出完备日志W1={ABC，BAC}，由行为轮廓弱关系定义得知A‖LB，A→LC，B→LC，得出图3。

图3　不可见任务类型一

2) 给出完备日志W2={ABC，AC}，由行为轮廓弱关系定义得知A→LB，A→LC，B→LC，得出图4。

图4　不可见任务类型二

3) 给出完备日志W3={ABC，ABBBC}，由行为轮廓弱关系定义得知A→LB，A→LC，B→LC，得出图5。

图5　不可见任务类型三

4) 给出完备日志W4={ABCD，ACBD，ACD}，由行为轮廓弱关系定义得知A→LB，A→LC，A→LD，B‖LC，C→LD，得出图6。

图6　不可见任务类型四

算法1：行为轮廓挖掘隐变迁

输入：执行日志序列

输出：Petri网模型

步骤1：在记录产生的日志序列中找出发生频率最高的且最长的日志序列(一般情况下最长的日志序列中发生作用的隐变迁最少)。

步骤2：根据日志序列得出模型简图(初始模型λ0)。根据最长的日志序列建立日志活动关系表，根据日志活动关系表可以画出Petri网模型简图，此时不考虑评价指标。

步骤3：将已确定的具有严格序关系的变迁相连形成的链，把它们视为整体，剔除冗余的日志序列(冗余的日志序列指的是在严格序关系的变迁中夹有与其存在并列关系的变迁)。找出缺省的变迁，可以确定与缺省变迁并列存在隐变迁。

步骤4：剩余日志序列中用发生频率最高的且最长的来优化模型λ0中的控制流，从而得到模型λ1。根据执行日志来计算模型的合理性f，根据合理性来判断日志的重放效果。

步骤6：所有日志重放完毕，模型λ1即为所挖掘的模型。

注：1)如果日志序列中的起始变迁或者终止变迁出现不一致，则考虑起始变迁或者终止变迁是隐变迁的情况。

2)如果出现{ABC，ABBC}此类日志序列，则考虑此自交叉变迁与隐变迁构成循环结构的情况。

4　案例说明

在本节中，利用一个简单的实例来说明上述挖掘隐变迁方法的可行性。表2是各个日志的轨迹和实例数(即频数)。

表2　执行日志列表

下面给出了一个操作作记录的日志序列L：

{ABCEDFGHJ，ABEDFGHJ，ABJ，ABCEGHJ，ABEGHJ，ABCDEFGHJ，ABDEFGHJ，ABDCEFGHJ，ABDFCEGHJ，ABCEGDFHJ，ABCEDGFHJ，ABCDEGFHJ，ABDCEGFHJ}

1) 首先根据几个最长的序列且发生频率较高的可以画出如图7所示的简图。

图7源模型M0

2) 再把具有具有并列关系的严格序(集)分为一个模块，如图8所示。

图8　模块图M1

3) 剔除冗余的日志序列{ABCDEFGHJ， ABDCEFGHJ，ABDFCEGHJ}及{ABDEFGHJ， ABDFEGHJ}并由缺省的C可以判断出与C并列的存在一个隐变迁，如图9所示。

图9　源模型优化一M2

4) 由缺省D、F的这个模块的序列{ABCEGHJ}可以判断出与D、F并列的存在一个隐变迁，如图10所示。

图10　源模型优化二M3

5) 由剩余的序列{ABJ，ABEGHJ}优化得出图11。

图11　源模型优化三M4

表3　一致性评价表

5　结束语

本文提出了基于行为轮廓寻找挖掘事件日志中隐变迁的方法。首先介绍了进程模型与日志的相关概念。然后讲述了日志与模型间的一致性判别方法。在其之后，引出了本文的核心部分，即基于行为轮廓挖掘事件日志中的隐变迁。首先根据最长的日志序列集得出源模型，再根据剩余日志中最长的序列一步步优化源模型从而找到隐变迁，最后通过与源模型进行比较得出挖掘出带有隐变迁模型的合理性及适当性。

本文基于Petri网行为轮廓提出了从事件日志中挖掘隐变迁的方法，但是在实际的流程挖掘中还存在其它异常变迁，比如block变迁。所以在未来的工作中，应该对更多的异常变迁加以分析，使得流程挖掘技术能够更加完善。

[1]WU ZHEHUI.Petri net Introduction[M].BeiJing:Press of machinery industry,2006：5-80.

[2]WEN LIJIE.Study on process mining algorithm based on WF net[D].BeiJing: Tsinghua University.2007.

[3]W M P VAN DER AALST, B F VAN DONGEN, J HERBST, et al. Workflow Mining: A Survey of Issues and Approaches[J]. Data and Knowledge Engineering, 2003,47(2):237-267.

[4]W M P VAN DER AALST, A J M M WEIJTERS.Process Mining:A Research Agenda[J]. Computers in Industry,2004,53(3):231-244.

[5]ROZINAT A, W M P VAN DER AALST . Conformance Testing: Measuring the Fit and Appropriateness of Event Logs and Process Models [J].Computer Science,2005,3812 LNCS:163-176.

[6]MATTHIAS W, ARTEM POLYVYANYY, NIRMIT DESAI, et al. Process Compliance Measurement based on Behavioural Profiles [J]. Computers in industry, 2004, 53(3):321-343.

[7]W M P VAN DER AALST .Process Mining:Discovery, Conformance and Enhancement of Business Processes[M]. 1st Edition. Berlin: Springer, 2011: 352-374.

[8]W M P VAN DER AALST. Work-flow mining: Discovering process models from event logs [J]. Knowledge and Data Engineering ,2004, 16(9): 1 128-1 142.

[9]MATTHIAS W, JAN M. Perceived consistency between process models [J]. Information Systems, 2012, 37(2): 80-98.

[10]YANG ZHANMIN , ZHANG LIQUN , HU YUAN. A Method to Tackle Abnormal Event Logs Based on Process Mining[C]//2nd International Conference on Software Engineering, Knowledge Engineering and Information Engineering , 2014:34-38.

[11]MAHDI SAHLABADI,RAVIE CHANDREN MUNIYANDI ，ZARINA SHUKUR.Detecting Abnormal Behavior In Social Net Work Websites By Using A Process Mining Technique[J].Journal of Computer Science ,2014,10 (3): 393-402.

[12]WU JUNZHI.Researches on Mining Methods of Business Process Based on Behavioral Profiles of Petri Net[D]. HuaiNan:Anhui University of Science and Technology,2014.

[13]王广立. 基于日志的流程挖掘算法研究[D].山东：山东大学，2008.

[14]ANDRZEJ STROINSKI, DARIUSZ DWORNIKOWSKI, JERZY BRZEZIN SKI. Resource Mining: Applying Process Mining to Resource-Oriented[J]. Systems Business Information Systems, Lecture Notes in Business Information Processing, 2014, 176: 217-228.[15]JAKUB STOLFA,MARTIN KOPKA,SVATOPLUK STOLFA,et al. An Application of Process Mining to Invoice Verification Process in SAP[J]. Advances in Intelligent Systems and Computing, 2014, 237: 61-74.

[16]MINSU CHO, MINSEOK SONG, SOOYOUNG YOO. A Systematic Methodology for Outpatient Process Analysis Based on Process Mining[J]. Lecture Notes in Business Information Processing 2014, 181: 31-42.

[17]CARLOS FERNANDEZ-LLATAS,BERNARDO VALDIVIESO,VICENTE TRAVER,et al. Using Process Mining for Automatic Support of Clinical Pathways Design[M]. Methods in Molecular Biology,2015,1 246:79-88.[18]JAKUB STOLFA, SVATOPLUK STOLFA, KATE INA SLANINOVA, JAN MARTINOVI, et al. An Impact of the User and Time Parameters to Sequence Alignment Methods for Process Mining[M]. Computer Information Systems and Industrial Management,2014,8 838: 580-591.

[19]W M P VAN DER AALST, SHENGNAN GUO, PIERRE GORISSEN. Comparative Process Mining in Education: An Approach Based on Process Cubes[J]. Lecture Notes in Business Information Processing, 2015, 203: 110-134.

(责任编辑：李丽，范君)

A Mining Method of the Hide Transitions From the Event Logs Based on theBehavioral Profiles of Petri Net

WANG Xiao-yue，FANG Xian-wen，CAO Rui-hao

(School of Science, Anhui University of Science and Technology, Huainan, Anhui 232001,China)

The hide transitions exist in the process models, but can not be found in the log sequence. Such transitions exist in the realistic models. It is one of the important difficulties to find the methods about mining the hide transitions from the event logs. There are some solutions to the free choice nets, but they have some limitations due to the complex process models. The method to find hide transitions based on the behavioral profiles of Petri net is proposed in the paper. First of all, according to the highest frequency of occurrence log sequence the source model is obtained, and then, according to the remaining log sequence step by step optimization model, the hidden transitions are required. Finally, the fitness of the model by means of evaluation index is judged.

Event log； Behavioral profiles； Hide transition； Process model

2015-09-22

国家自然科学基金资助项目(61572035，61272153，61402011)；安徽省自然科学基金资助项目(1508085MF111)；安徽省高校自然科学基金资助项目(KJ2014A067，KJ2016A208)

王晓悦(1990-)，女，安徽寿县人，在读硕士，研究方向：Petri网和过程挖掘。

TP391.9

A

1672-1098(2016)03-0013-07