基于Petri网的业务流程低频行为挖掘与优化分析

郝惠晶，方贤文，方 娜，许 健

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

0 引言

在实际应用中，从信息系统中提取的事件日志不可避免地包含低频行为，这些低频行为由于发生频数较低往往被作为无序事件、记录错误、异常行为或者噪音而被删除。然而,有些低频行为虽然出现频率较低，但是对流程管理也很重要，不能直接过滤，例如，飞机的逃逸系统、保险公司的欺诈性索赔，由此可见，低频行为的挖掘具有重要意义。

目前，针对低频行为的挖掘已经成为学者专家研究的热门课题，并有了一定的研究成果。文献[1]提出一个从日志中移除低频行为的自动技术，该技术自动识别所有的行为并移除低频行为。文献[2]中提出了区分噪音与流程的规则行为的噪音过滤方法。文献[3-4]提出在过程发现中处理包含噪音的事件日志是一个重大挑战。文献[5]提出一种利用数据属性来区分低频路径和随机噪声的启发式挖掘算法(Data-aware Heuristic Miner, DHM)。文献[6]提出了增广因果网，它能用于一致性检测，也能在有噪音和真实日志的复杂和低结构化过程中得到例证。文献[7]提出一种新的基于频率的流程挖掘方法来过滤噪音。文献[8]提出一种Inductive Miner-infrequent技术，该技术选择切操作来拆分日志，并过滤低频行为，且该技术已在ProM中实施。文献[9]提出WoMine-i算法，是一种在已经发现的过程模型中不仅能搜索不常见的行为模式，还能发现具有最常见控制结构模式的算法，该结构允许执行的子进程能够发现少于预期的或不常见的错误行为。文献[10]提出一种最大模式挖掘(Maximal Pattern Mining, MPM)的新技术，用于从事件日志中发现过程模型，该技术在召回、精度、F-测量、运行效率等方面表现良好，并进而基于频率提出了噪音过滤的方法。

本文以模块间的通讯行为轮廓为基础，通过预处理事件日志挖掘初始流程模型，用带切关系的直接流图与初始模型进行匹配，发现低频行为。考虑事件日志间的行为属性，基于日志与模型的行为紧密度区分有效低频日志和噪音日志，过滤噪音。并通过不同模块间的通讯特征挖出模块网和特征网，将模块网和特征网进行交互通讯，得到一个优化的业务流程通讯模型。

1 基本概念

定义1[11]通讯行为轮廓。设L⊆T*是事件日志，L⊆T×T是相应的通讯后继关系。通讯行为轮廓是一个3元数组(→C,‖C,+C)Com，它由以下关系组成：

(1)严格通讯关系A→CB，当且仅当ALB，BLA；

(2)交叉通讯关系A‖CB，当且仅当ALB，BLA；

(3)排它通讯关系A+CB，当且仅当ALB，BLA；

(4)逆严格通讯关系A←CB，当且仅当ALB，BLA。

定义2[12]流程树切(日志)。设Li(i=1,2,…,n)为流程模型CP=(S,T,F,c)对应的事件日志，S(T)为关于变迁T的迹，L∈S(T)，c∈S∪T，若变迁∀x,y∈c:((x,y∉F+)∧(y,x∉F+))，其中F+为流关系F的传递闭包，则c为流程树切，对于任意一个活动(x,y)∈Li×Li，存在日志序列δ=t1t2…tn，其中i,j∈{1,2,…,n}，i

(1)x≻y，当且仅当∃δ∈L⟹ti=x，tj=y；

(2)x→y，当且仅当x≻y,yx；

(3)xy，当且仅当xy,yx；

(4)x‖y，当且仅当x≻y,y≻x；

(5)xy，当且仅当∀δ∈L,∀x,y∈T⟹(x∈δ,y∉δ)∨(y∈δ,x∉δ)。

其中：x≻y表示活动对间的弱序关系，x→y表示活动对间的因果关系，xy表示活动对间无关系，x‖y表示活动对间平行交叉关系，xy表示活动对间的互斥关系。

事件日志L：[a,b,c,a,b,e,f50,(a,b,f,e)100,d,e,f100,d,f,e100]，将日志L划分为一些子日志：L1=[a,b,c,a,b50,a,b100,d200]，L2=[e,f150,f,e200]，L3=[a,b,c,a,b50,a,b100]。

图1中虚线为切，图1a日志L1是关于弱序流程树切图；图1b日志L2是关于互斥流程树切图；图1c日志L3是关于交叉流程树切图；图1d日志L4是关于循环流程树切图。

定义4[14]日志距离向量。设一条事件日志T={t1,t2,…,tn}，其中∀(t1,t2)∈T，∀(pi,pi+1)∈ti的日志行为值为VT(pi,pi+1)，且VT(pi,pi+1)=1。日志的行为距离向量为：X={VT(p1,p2),VT(p2,p3),…,VT(pi,pi+1),…,VT(pj,pm)}={l1,l2,…li,…,lm}。类似地，可以定义模型的行为值为VM(pi,pi+1)=k。模型的行为距离向量定义为：X={VM(p1,p2),VM(p2,p3),…,VM(pi,pi+1),…,VM(pj,pm)}={k1,k2,…ki,…,km}。

其中：m表示变迁个数，且0

定义5[11]特征网。设L⊆T*是一个事件日志，A,F∈T是特征。设(→C,‖C,+C)Com相应的通讯行为轮廓，特征网ΝF满足以下条件：

(2)I={pA-F|A→F}；

(3)O={pF-A|F→A}；

2 基于Petri网的业务流程低频行为挖掘与优化分析

一般情况下，从信息系统中获取的事件日志往往包含低频行为，这些行为通常被认为是噪音而被直接删除，而发现的业务流程模型因此会失去一些有用的规则行为。本文主要介绍了基于Petri网的业务流程低频行为挖掘与优化分析的方法，并提出了相关的算法，通过基于带切关系的直接流图及行为紧密度对低频行为进行挖掘与优化，并通过分析模块间的通讯特征，更好地优化业务流程模型，从而更好地应用于实际生活。

2.1 基于Petri网的业务流程低频行为的挖掘方法

在过程挖掘中，已有研究大多集中在发现频繁行为，少有涉及低频行为，且很少从行为关系角度考虑低频行为。许多算法的提出基本是以事件日志记录业务过程的完整行为为基础，进而挖掘业务流程模型。但是事件日志中往往存在异常或者偏差，即噪音，噪音的存在会影响业务流程的结构。运用流程树切的行为关系匹配初始模型挖掘低频行为，基于日志与模型的行为距离向量计算日志与模型的行为紧密度，根据紧密度阈值区分低频行为和噪音，从而对低频行为进行挖掘与优化。下面首先给出行为紧密度的定义。

定义6[12]行为紧密度。给出事件日志T和流程模型M，则日志T与模型M的行为紧密度

其中，m表示日志中的活动行为关系数，ki为模型中与日志对应变迁的最小行为距离，li为日志行为距离。

算法1基于Petri网的业务流程低频行为挖掘方法。

输入：事件日志L={τ1,τ2,…,τn}，紧密度阈值θ；

输出：低频行为。

步骤1预处理给定的事件日志L={τ1,τ2,…,τn}，分析各个变迁对ti,tj之间的行为轮廓关系，按照实例数大小从大到小排列事件日志，找到频数发生较高的日志序列，建立初始的Petri网流程模型M0，转步骤2。

步骤2根据定义2，对给定的事件日志用流程树切进行划分，将事件日志中活动对的关系用带切关系的直接流图表示出来，将直接流图的序列关系与初始流程模型M0的序列关系进行匹配，找出所有无匹配项的直接流图的序列关系，即为该事件日志中所包含的低频行为，转步骤3。

步骤4根据定义6，求出日志与模型行为紧密度的值，根据给定的紧密度阈值θ，如果紧密度值ξ(Ti,M)≥θ，则该低频日志为有效低频日志，如果ξ(Ti,M)<θ，则该日志为噪音日志，转步骤5。

步骤5过滤噪音日志，过滤掉该流程树切的运算符和切口选择，即过滤直接流图和最终跟随图的低频序列，算法结束。

2.2 基于通讯行为轮廓的低频行为的优化分析

由上述研究可知，挖掘发现的非频繁的行为并不都是异常行为，有的可能是对系统有用的有效低频，为了提高系统或企业的运行效率，应将有效低频保留下来。但已有关于低频行为的研究主要是基于完整的流程模型，对通过不同模块间通讯特征挖掘低频行为的研究还很少。本节提出一个新的低频行为的优化算法，具体算法如下。

算法2基于通讯行为轮廓的低频行为挖掘与优化。

输入：事件日志L={τ1,τ2,…,τn}，紧密度阈值θ;

输出：优化的业务流程模型。

步骤1根据算法1建立的初始Petri网流程模型M0，预处理其给定的事件日志L={τ1,τ2,…,τn}，n=1,2,3,…，转步骤2。

步骤2将预处理后的事件日志L′={τ1,τ2,…,τm}(m

步骤3根据处理后的事件日志及通讯行为轮廓关系，将系统分解为不同的模块，构建相应的模块网M1,M2,…，转步骤4。

步骤5将步骤4和步骤5挖掘得到的模块网M1,M2,…和特征网MF进行进行融合，进而得到优化的业务流程模型，算法结束。

3 实例分析及仿真实验

3.1 实例分析

为验证上述算法的可行性，以网络订购火车票为例，用户首先需要注册并登录官网，登陆成功以后进入车票预订界面，依次选择乘车区间及日期，然后选择车次进行车票预订、付款、改签或者退票等流程。下面给出一些基于网络购票系统所记录的事件日志(如表1)。其中：t11表示注册，t12表示登录，t13表示选择乘车区间，t14表示选择乘车日期，t15表示选择车次，t16表示余票查询，t17表示车票预订，t18表示付款，t19表示订票成功，t1，10表示改签，t1，11表示取票，t1，12表示退票。t21表示登录成功，t22表示登录失败，t23表示余票信息，t24表示余票充足，t25表示余票不足，t26表示返回车次选择，t27表示重新登录，t28表示付款信息，t29表示付款成功，t2，10表示待付款，t2，11表示付款时间超过30 min，t2，12表示交易关闭，t2，13表示付款时间在30 min以内。

表1 网络购票系统的事件日志

对表1给定的事件日志用流程树切进行划分，通过与图2的初始流程模型进行匹配，可发现日志L9：t11t12t22t12t2,1214，L10：t11t12t21t13t14t15t16t23t1745，L11：t21t16t23t25t1，12t2,1226，L12：t24t17t18t28t2,1251，L13：t13t14t21t15t16t23t24t1,127与初始模型不匹配，而初始模型由频数相对较高的日志构建，因此视这些事件日志为低频日志。然后，判断低频日志是有效低频日志还是噪音日志，利用定义4计算低频日志与模型的行为紧密度，日志L9的行为距离向量为X1=(1,1,1,1)，与初始模型M0对应变迁的最小行为距离向量为日志L9与初始模型M0的行为紧密度为同理，日志L10与初始模型M0的行为紧密度为σ2≈0.959 4，日志L11与初始模型M0的行为紧密度为σ3≈0.650 8，日志L12与初始模型M0的行为紧密度为σ4≈0.866，日志L13与初始模型M0的行为紧密度为σ5≈0.699 9。引入行为紧密度阈值为0.8，当日志与模型的行为紧密度大于阈值时，说明低频日志符合模型的行为关系，视为有效低频日志，应当保留；当小于阈值时，说明低频日志与模型的行为关系不符，视为噪音日志，应当过滤。

由上述行为紧密度值与阈值比较的结果可知，事件日志L9，L11和L13的行为紧密度小于阈值，视为噪音日志，其中L9：t11t12t22t12t2,1214划分为一些子日志，分别为：[t11t12t22t121 034，t12t2,1214]，其中流弧t12t2,12是低频的，观察流程树切的直接流图，用启发式过滤的方法过滤流弧t12t2,12，因此含有流弧t12t2,12的事件日志也应当过滤。同理，L11和L13通过过滤直接流图的低频序列，进而过滤含有此低频序列的事件日志，而事件日志L10和L12为有效低频日志，需保留在事件轨迹集中。

通过优化事件轨迹集，根据日志之间的变迁对的关系，分析各个活动事件之间的行为关系，建立通讯行为轮廓表，如表2所示。基于域的方法与优化事件轨迹集挖掘出两个模块网，如图3所示，不同模块之间存在交互行为，且事件之间的特征不仅能接受信息,还能传递信息，重构事件之间的内部行为，找出相应的特征网，如图4所示。分析可知，模块网可反映模块内部行为，特征网可反映不同模块之间的特征交互，故将模块网与特征网融合可得到优化的业务流程模型，如图5所示。

表2 通讯行为轮廓关系

续表2

3.2 仿真分析

为验证本文所提基于Petri网的业务流程低频行为的挖掘与优化算法的有效性，将本文提出的基于Petri网的业务流程低频行为挖掘与优化的新方法与文献[8]提出的方法进行比较分析，对模型的一致性度(见文献[15])和精确度(见文献[16])进行比较。一致性度是指事件日志与业务流程行为相匹配的程度，而一个模型精确度高说明流程模型中无过多的行为。关于一致性度、精确度和运行时间的具体实验结果如图6a～图6c所示。

分析图6a可知，两种算法的一致性度比较接近，且都接近1，说明本文的过滤算法和文献[8]中基于切操作的过滤算法挖掘出的流程模型与日志行为之间具有很好的匹配度，但本文的过滤算法相较于文献[8]的算法一致性度要高一些，说明本文的挖掘算法可基于事件日志挖掘出更有效的流程模型，且受日志的数量影响较小。

分析图6b可知，本文的过滤方法相较于文献[8]的过滤方法，精确度明显要高，说明本文只过滤对系统造成影响的噪音序列；而文献[8]的过滤方法将所有低频行为和噪音全部过滤，因此过滤了很多活动，导致精确度明显较低。

分析图6c可知，两种方法在挖掘流程模型的过程中，系统运行时间随事件日志数量的增长而快速增加，且相同日志数下本文的过滤方法所需运行时间相较于文献[8]的运行时间较长，但两者整体运行时间相差不大，且对于挖掘流程模型没有影响。

由以上分析可知，本文提出的方法在一致性度和精确度方面相较于以前的方法提高了很多，虽然运行时间稍微比之前方法较长，但本文的过滤方法只过滤掉噪音，保留了对系统有用的低频行为，达到了优化系统的目的。

4 结束语

本文在已有研究的基础上，给出了基于Petri网的业务流程低频行为挖掘与优化的方法。首先基于流程树切的基本流图与初始模型进行匹配，不仅能区分频繁行为和低频行为，通过行为紧密度的知识还能区分有效低频与噪音序列，从而过滤噪音日志，优化事件轨迹集；然后分析了事件对之间的行为关系，建立了模块网和特征网，从而解决了不同模块间低频行为的挖掘问题，融合了模块网和特征网，可以得到一个优化的业务流程模型，从而提升了企业或组织的运行效率。

本文所提方法是从行为关系的角度区分有效低频行为和噪音行为，未来还要将行为属性和数据属性相结合来区分低频行为，从而更好地过滤噪音，优化系统。