基于引發(fā)序列的流程模型修正

王 路 杜玉越 祁宏達(dá)

(山東科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 山東青島 266590) (wanglu253@126.com)

隨著大數(shù)據(jù)[1-2]時(shí)代的到來(lái)，業(yè)務(wù)過(guò)程管理(business process management, BPM)必將得到進(jìn)一步的改善.近年來(lái)，企業(yè)信息系統(tǒng)(enterprise infor-mation systems, EIS)通過(guò)集成提高了企業(yè)業(yè)務(wù)流程的功能[3]，產(chǎn)生了大量的事件日志(event logs)，并且這些日志被記錄并存儲(chǔ)在了系統(tǒng)中[4].流程挖掘(process mining)可以從記錄的這些數(shù)據(jù)中提取出與流程相關(guān)的信息并發(fā)現(xiàn)流程模型(process model)[5-6].

事件日志通常作為流程挖掘的輸入數(shù)據(jù)，是流程模型在執(zhí)行過(guò)程中產(chǎn)生的事件序列集合.日志中的每一個(gè)事件對(duì)應(yīng)于一個(gè)活動(dòng)，并與一個(gè)特定的實(shí)例相關(guān).事件日志記錄的實(shí)例中的一條事件序列稱為一條跡(trace).除了活動(dòng)，事件日志同樣包含其他信息，比如初始資源(initial resources)、事件的時(shí)間戳(timestamp)等.現(xiàn)有的流程挖掘技術(shù)有流程發(fā)現(xiàn)(process discovery)、合規(guī)性檢查(conformance checking)、流程改進(jìn)(process enhancement)[4-7].流程發(fā)現(xiàn)是通過(guò)挖掘日志中流程的主要步驟來(lái)創(chuàng)建 流程模型.合規(guī)性檢查是將流程模型的行為與事件日志中記錄的行為進(jìn)行對(duì)比，從而找到建模的行為與記錄的行為之間的共性和差異.流程改進(jìn)是根據(jù)事件日志對(duì)流程模型進(jìn)行改進(jìn)或擴(kuò)展.通過(guò)這3種流程挖掘技術(shù)可以進(jìn)行瓶頸分析與延遲預(yù)測(cè)等.

目前，存在很多從控制流角度描述流程模型的形式化語(yǔ)言，比如業(yè)務(wù)流程建模標(biāo)記法(business process modeling notation, BPMN)[8]、因果網(wǎng)(causal nets)[4]、事件驅(qū)動(dòng)流程鏈(event-driven process chains, EPCs)[9]、Petri網(wǎng)[10]等.Petri網(wǎng)[10]能夠作為分布式系統(tǒng)建模和分析的工具，并且具有嚴(yán)格的數(shù)學(xué)定義以及強(qiáng)大的圖形表達(dá)能力.Petri網(wǎng)不僅能夠描述流程的靜態(tài)結(jié)構(gòu)，還可以模擬流程運(yùn)行過(guò)程中的動(dòng)態(tài)行為.對(duì)于具有并行、并發(fā)、異步、分布和不確定性等性質(zhì)的信息系統(tǒng)，可以利用Petri網(wǎng)對(duì)其進(jìn)行有效地描述和分析[11-15]，因此，本文用Petri網(wǎng)來(lái)描述流程模型.

如果現(xiàn)在有流程模型不能夠重演(replay)對(duì)應(yīng)的實(shí)例，原則上要用流程發(fā)現(xiàn)來(lái)得到一個(gè)新的流程模型.但是，重新發(fā)現(xiàn)的模型通常與原模型沒有相似度并且丟棄了原模型的優(yōu)勢(shì)，特別是在原模型通過(guò)手工創(chuàng)建的情況下，丟失掉的優(yōu)勢(shì)顯得由為重要.對(duì)于不能重演實(shí)例的流程模型，一個(gè)比較好的方法是對(duì)原模型進(jìn)行修正，從而使模型可以重演(大多數(shù))事件日志并且盡可能保留原模型的優(yōu)勢(shì).本文介紹了一種新的流程挖掘技術(shù)——模型修正.該技術(shù)將流程模型N與日志L中的異?；顒?dòng)作為輸入.如果模型N符合日志L，就沒有必要修正N.但是如果N中的部分模型不能重演L中的某些活動(dòng)，那么就需要對(duì)該部分模型進(jìn)行修正.與流程發(fā)現(xiàn)不同，模型修正可以將流程模型中能夠重演事件日志的部分保留下來(lái).得到的修正模型N′ 可以看作是原模型N及事件日志L的一個(gè)協(xié)同(synergy)部分.模型修正技術(shù)保證了修正模型與原模型的相似度.

1 相關(guān)工作

本文提出的模型修正技術(shù)主要與2個(gè)方面的研究方向相關(guān)：模型合規(guī)性檢查與模型發(fā)現(xiàn).

如果模型可以重演事件日志中的活動(dòng)行為，則該模型的擬合度比較好，如果模型可以重演日志中的所有跡，則該模型的擬合度為1.0[4]. 如今已經(jīng)提出了很多合規(guī)性檢查的方法.基于托肯(token)的重演[16]就是檢測(cè)事件日志與Petri網(wǎng)之間一致性的方法.將日志中的每條跡分別在模型上進(jìn)行重演，根據(jù)跡中的活動(dòng)順序，網(wǎng)中的變遷可以被依次引發(fā).在流程執(zhí)行的過(guò)程中可以計(jì)算產(chǎn)生(produced)、消耗(consumed)、丟失(missing)和剩余(remaining)的token，然后通過(guò)這些token的數(shù)目計(jì)算日志與模型之間的擬合度.Petkovic等人以BPMN的描述形式提出了流程與日志合規(guī)性檢查的框架[17].

當(dāng)已有的模型與流程的執(zhí)行過(guò)程不一致時(shí)，可以通過(guò)流程發(fā)現(xiàn)(process discovery)技術(shù)得到一個(gè)新的流程模型.根據(jù)活動(dòng)的次序關(guān)系發(fā)現(xiàn)流程模型的技術(shù)有Alpha算法[18]及其衍生算法[19-20]，這種技術(shù)可以保證模型的同構(gòu)-再發(fā)現(xiàn)(isomorphic-rediscover)能力[21]，但是不能保證模型的擬合性與健壯性.基于語(yǔ)義(semantics-based)的發(fā)現(xiàn)技術(shù)有基于語(yǔ)言的區(qū)域挖掘(language-based region miner)[22-23]、基于狀態(tài)的區(qū)域挖掘(state-based region miner)[24]和ILP挖掘(integer linear programming)[25]，這種發(fā)現(xiàn)技術(shù)可以保證模型的擬合性，但是不能保證模型的健壯性與再發(fā)現(xiàn)能力.

2 基礎(chǔ)知識(shí)

本節(jié)中簡(jiǎn)單地回顧了多重集與Petri網(wǎng)的定義，并介紹了事件日志與流程模型的概念.在本文中，表示一個(gè)自然數(shù)集合，S是一個(gè)有限集合.

定義1.S上的多重集Z是一個(gè)映射Z：S→.B(S)表示集合S上的所有多重集.

多重集Z=[a3,b,c2]表示集合S上的1個(gè)多重集，其中a,b,c∈S，Z(a)=3,Z(b)=1,Z(c)=2.Z1,Z2∈B(S)是2個(gè)多重集.2個(gè)多重集的和是Z3=Z1⊕Z2，其中Z3∈B(S)，對(duì)于所有的a∈S：Z3(a)=Z1(a)+Z2(a).2個(gè)多重集的差是Z4=Z1-Z2，對(duì)于所有的a∈S：Z4(a)=max{0,Z1(a)-Z2(a)}.如果?a∈S，Z1(a)≤Z2(a)，則Z1≤Z2.比如：[b,c]≤[a3,b,c2]，但[b2][a3,b,c2].

定義2.S*表示集合S上所有有限序列的集合，ε表示一個(gè)空序列.序列σ=〈σ[1],σ[2],…,σ[n]〉，其中σ[i]表示序列的第i個(gè)元素，〈σ[i],σ[i+1]〉表示2個(gè)相鄰接的元素，|σ|=n表示序列σ的長(zhǎng)度.對(duì)于?a∈S，σ(a)表示a在σ中出現(xiàn)的次數(shù).σsub表示σ的子序列，σ(σsub)表示子序列σsub在σ中出現(xiàn)的次數(shù).

定義3.Z是集合S上的一個(gè)多重集，Q?S是集合S的一個(gè)子集，σ∈S*.σ|Q表示σ在Q上的投影，Z|Q表示Z在Q上的投影.

比如：如果σ=aabc，Q={a,b}，Z=[a3,b,c2].則σ|Q=aab，Z|Q=[a3,b].

定義4.v=(a1,a2,…,an)∈S×…×S是集合S上的一個(gè)向量.πi(v)表示v的第i個(gè)元素，其中1≤i≤n.

比如v=(a,b)∈S×S，則π1(l)=a，π2(l)=b.可以將該定義擴(kuò)展到序列中，比如σ∈(S×S)*，πi(σ)=〈πi(σ[1]),πi(σ[2]),…,πi(σ[|σ|])〉，i=1,2.

定義5[9].N=(P,T;F)為一個(gè)網(wǎng)，其中：

1)P是庫(kù)所有限集合；

2)T是一個(gè)變遷有限集合，并且P∪T≠?，P∩T=?；

3)F?(P×T)∪(T×P)是一個(gè)流關(guān)系集合.

定義6[9]. 設(shè)N=(P,T;F)為一個(gè)網(wǎng).對(duì)于x∈S∪T，記：

?x={y|y∈S∪T∧(y,x)∈F}，

x?={y|y∈S∪T∧(x,y)∈F}，

順序、并行、選擇和循環(huán)結(jié)構(gòu)是工作流和流程模型的4種基本結(jié)構(gòu)，如圖1所示.流程所有的執(zhí)行過(guò)程都可以由這4種結(jié)構(gòu)組合而成.

Fig. 1 Four basic structures of Petri nets圖1 工作流的4種基本結(jié)構(gòu)

定義7[28].A表示一個(gè)活動(dòng)集，Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型，其中：

2)α:T→Aτ是變遷到活動(dòng)的映射函數(shù)；

3)α-1:Aτ→T是α的逆函數(shù),是活動(dòng)到變遷的映射函數(shù)；

4)mi是初始標(biāo)識(shí)，mf是終止標(biāo)識(shí).

除非特別指出，只有可見變遷可以標(biāo)記為活動(dòng).假設(shè)τ?A表示所有的不可見變遷.為方便起見，Aτ=A∪{τ} 表示A與{τ}的并集.

定義8[4].A表示一個(gè)活動(dòng)集，Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型，每一個(gè)變遷t∈T對(duì)應(yīng)于流程執(zhí)行中的一個(gè)活動(dòng).模型Ns的一條活動(dòng)序列l(wèi)∈A*，或空序列是活動(dòng)的一條有限序列，即跡.L∈B(A*)是一個(gè)事件日志，即跡的一個(gè)多重集.ξ表示一個(gè)空事件日志.

由于不同的實(shí)例可能有相同的跡，因此一個(gè)事件日志是一個(gè)跡的多重集.如果不關(guān)心跡的發(fā)生頻數(shù)，可以將一個(gè)日志看成一個(gè)跡的集合，即L={l1,l2,…,ln}.在定義8中，一個(gè)事件是指一個(gè)活動(dòng).通常，事件日志還記錄了事件的其他信息，比如時(shí)間戳、資源和附加數(shù)據(jù)元素等.

Fig. 2 An example of an engineering drawing process Nd圖2 工程圖設(shè)計(jì)流程N(yùn)d

圖2給出了汽車制造廠的工程圖設(shè)計(jì)流程.在這個(gè)模型中，A={Submit,Design,…,Archive}，α(t1)=Submit，α-1(Insulation Proof)=t4.l=〈Submit,Design,Electrician Proof,Check Inventory,Evaluate,Archive〉是該模型的一條跡，對(duì)應(yīng)的引發(fā)序列是σ=〈t1,t2,t4,t5,t6,t7〉.對(duì)于l和σ，有α(σ)=l，α-1(l)=σ.

如果一條跡缺少活動(dòng)或者存在不同于模型的活動(dòng)，則該跡不能被流程模型正確地重演.為了確定活動(dòng)序列是否被完整地記錄在事件日志中，給出了引發(fā)序列的概念.

定義9[26-27].Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型，則Ns的一條引發(fā)序列及其后集可遞歸定義為：

1) 空序列ε是一條引發(fā)序列，且ε*={bstart}；

如果σ是模型Ns的一條引發(fā)序列且σ?={bend}，則稱序列σ符合流程模型，記為σNs.如果σ不符合Ns，則記為σ/Ns.

定義10[5].A表示一個(gè)活動(dòng)集，跡l∈A*是一個(gè)活動(dòng)序列.&(l)是一個(gè)多重集，包含跡l的所有活動(dòng).

比如，如果l′=〈a,b,h,i,k,s,m,o,m,o,t,p,r〉，那么&(l′)={a,b,h,i,k,s,m2,o2,t,p,r}.

定義11.A表示一個(gè)活動(dòng)集，L∈B(A*)是一個(gè)事件日志，e∈A是L有一個(gè)活動(dòng)，

◆e={a|?l∈L∧a∈A∧〈a,e〉∈l}，

e◆={a|?l∈L∧a∈A∧〈e,a〉∈l}，

稱◆e為e的前活動(dòng)集，e◆是e的后活動(dòng)集.

3 模型修正

本節(jié)主要基于引發(fā)序列給出一種模型修正的方法.通常，可以通過(guò)對(duì)流程模型進(jìn)行移除活動(dòng)與增加活動(dòng)的方式對(duì)流程模型進(jìn)行修正.移除活動(dòng)是將活動(dòng)從流程模型中移除，增加活動(dòng)是在合適的位置對(duì)流程模型增加活動(dòng).模型修正的目標(biāo)是使修正的流程模型可以重演其(大多數(shù))事件日志.

定義12.Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型，L是Ns的一個(gè)事件日志.如果?l∈L:lNs，則稱Ns可以執(zhí)行中L的每一個(gè)實(shí)例，即Ns可以重演L.如果?l∈L:l/Ns，則稱Ns不能夠重演L.

如果模型Ns不能夠重演其對(duì)應(yīng)的事件日志L，

3.1 移除活動(dòng)

當(dāng)序列σt在實(shí)際情況下可以發(fā)生，但對(duì)于模型來(lái)說(shuō)，?tσ?時(shí)，則需要在模型中將σ與t之間的變遷移除.如果模型中描述活動(dòng)從來(lái)沒有記錄在事件日志中時(shí)，則需要將該活動(dòng)從模型中刪除，如果模型中描述有活動(dòng)被記錄但是只有記錄在部分事件日志中時(shí)，則需要在模型執(zhí)行的過(guò)程中跳過(guò)該活動(dòng).模型中的活動(dòng)可以通過(guò)2種方式移除：跳過(guò)變遷、刪除變遷.

定義13.A表示一個(gè)活動(dòng)集，Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型.l=lke是Ns的一條跡，且α-1(l)=α-1(lke)=α-1(lk)α-1(e)=σkti(1≤i≤|T|).如果?ti則是在σk和ti之間至少跳過(guò)一個(gè)變遷的間隔(gap).

間隔表明跡lke可以在實(shí)際情況下執(zhí)行，但是lke不符合流程模型的描述規(guī)則.換句話說(shuō)，在實(shí)際運(yùn)行過(guò)程中，lk與e之間跳過(guò)了一些活動(dòng).

定義14.A表示一個(gè)活動(dòng)集，Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型，L∈B(A*)是Ns的一個(gè)事件日志.如果?ti∈T(1≤i≤|T|)，α(ti)=e，但L中從來(lái)沒有記錄e，則稱活動(dòng)e是一個(gè)刪除的活動(dòng).

定義14指出，Ns描述了活動(dòng)e，但是在流程實(shí)際運(yùn)行過(guò)程中，e從來(lái)沒有發(fā)生過(guò)，那么需要在Ns中刪除活動(dòng)e.

證明.

對(duì)于ti∈T，如果?tj∈T，?(?tj)=?(?ti)，則ti在并行結(jié)構(gòu)中.

證畢.

給定流程模型Ns和需要從Ns移除的活動(dòng)e，算法1給出了將e移出Ns的方法.

算法1. 從模型Ns中移除活動(dòng)e.

FunctionRemoveActivity(Ns,e)

②T是變遷集合,T=transitions set;

③i=1;

④ while (i≤|T|) do

⑤ if (α(ti)=e)

⑥ break;

⑦ end if

⑧i++;

⑨ end while

⑩ if (ti是可跳過(guò)變遷)

在算法1中，首先判斷e是可跳過(guò)的活動(dòng)，還是刪除的活動(dòng).當(dāng)e是可跳過(guò)的活動(dòng)時(shí)，可以加入不可見變遷τ.在流程執(zhí)行的過(guò)程中，可以在e與τ之間進(jìn)行選擇.如果e是刪除的活動(dòng)時(shí)，需要確定包含e的結(jié)構(gòu).如果e在順序結(jié)構(gòu)中，需要加入從?(α-1(e))到((α-1(e))?)?的弧，刪除變遷α-1(e)及庫(kù)所(α-1(e))?，同時(shí)要?jiǎng)h除連接α-1(e)與(α-1(e))?的弧.對(duì)于e在選擇結(jié)構(gòu)或并行結(jié)構(gòu)中，可以類似的處理.需要?jiǎng)h掉連接α-1(e)的弧與庫(kù)所.根據(jù)算法1可以將一個(gè)活動(dòng)從Ns中移除.如果有連續(xù)的活動(dòng)需要在Ns中移除時(shí)，可以根據(jù)算法1將對(duì)應(yīng)這些連續(xù)活動(dòng)的一個(gè)子模型從Ns移除.函數(shù)DetermineStructure(Ns,e)可以用來(lái)確定包含e的結(jié)構(gòu)，在算法2給出了該函數(shù)的實(shí)現(xiàn)方法.

算法2. 確定活動(dòng)e所在的結(jié)構(gòu).

FunctionDetermineStructure(Ns,e)

①T是變遷集合,T=transitions set;

②S=null;

③i=1;

④ while (i≤|T|) do

⑤ if (α(ti)=e)

⑥j=1;

⑦ while (j≤|T|) do {

⑨k=j+1;

⑩ while (k≤|T|) do {

對(duì)于圖3的非正確模型N1，假設(shè)事件日志中包含2條跡：l2=〈B,C,D,E,F,I〉和l3=〈B,C,E,D,F,G,I〉.對(duì)于l2=〈B,C,D,E,F,I〉，〈B,C,D,E,F〉是引發(fā)序列，且〈B,C,D,E,F〉?={b6}，對(duì)于活動(dòng)I，?I={b8}〈B,C,D,E,F〉?.因此，〈B,C,D,E,F〉與I之間存在間隔.對(duì)于l3=〈B,C,E,D,F,G,I〉，〈B,C,E,D,F,G〉是引發(fā)序列，且〈B,C,E,D,F,G〉?={b7}，?I={b8}〈B,C,E,D,F,G〉?.〈B,C,E,D,F,G〉?與I之間跳過(guò)了活動(dòng)K.

活動(dòng)G記錄在l3中，但是沒有記錄在l2中，如果要修正N1，需要在模型中跳過(guò)活動(dòng)G.如果要跳過(guò)G，可以添加不可見變遷τ，?τ=?G且τ?=G?.同時(shí)要添加從b6到τ及從τ到b8的弧.活動(dòng)K即沒有記錄在l2中也沒有記錄在l3中，因此需要在N1中刪除K.從N1可以看出，K是在順序結(jié)構(gòu)中.要?jiǎng)h除K，需要加入從G到b8的弧，且刪除庫(kù)所b7，刪除從b7到K及從K到b8的弧.N1的修正模型如圖4所示.

Fig. 3 An incorrect process model N1圖3 非正確模型N1

Fig. 4 The repaired model of N1圖4 流程模型N1的修正模型

3.2 添加活動(dòng)

通過(guò)在流程模型中插入額外的活動(dòng)來(lái)添加活動(dòng).但是，在插入活動(dòng)e時(shí)，需要在模型中確定e的插入位置(定義為loc(e)).e并不會(huì)在每一條跡中都發(fā)生，因此，需要確定e和◆e∪e◆之間的關(guān)系.如果插入的位置以及關(guān)系類型都已確定，則可以通過(guò)添加活動(dòng)對(duì)模型進(jìn)行修正.

通常有2個(gè)插入額外活動(dòng)的位置，1個(gè)是◆e之后的最后一個(gè)活動(dòng)，另一個(gè)是e◆之前的第1個(gè)活動(dòng)，現(xiàn)在還沒有辦法確定這2個(gè)位置中的哪一個(gè).因此，這2個(gè)位置都需要檢查，然后評(píng)價(jià)模型的質(zhì)量，選擇使模型質(zhì)量高的位置.

定義15.A表示一個(gè)活動(dòng)集，L∈B(A*)是Ns的一個(gè)事件日志，Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型.l=lkelm是Ns的一條跡，如果ti∈T(1≤i≤|T|):α(ti)=e.則稱活動(dòng)e是一個(gè)額外的活動(dòng).

定義15表明跡l可以在實(shí)際情況下執(zhí)行，但是有些活動(dòng)在實(shí)際執(zhí)行的過(guò)程中發(fā)生了，沒有在Ns中描述，因此，需要將這些額外的活動(dòng)添加到模型中.

定理2.A表示一個(gè)活動(dòng)集，Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型.L是關(guān)于Ns的一個(gè)事件日志，e對(duì)于Ns是一個(gè)額外活動(dòng).當(dāng)在Ns中插入e時(shí)，可以通過(guò)◆e和e◆確定loc(e).

證畢.

定理2表明在流程模型中，loc(e)可以由◆e和e◆確定.由定理2可以確定e與模型中其他活動(dòng)的關(guān)系.

給定流程模型Ns和模型Ns的額外活動(dòng)e，算法3給出了將e插入Ns的方法.

算法3. 在模型Ns中添加活動(dòng)e.

FunctionAddActivity(Ns,e)

②T是變遷集合,T=transitions set;

③t|T|+1是額外活動(dòng), 即α(t|T|+1)=e;

④α(tk)∈◆e;

⑤α(tm)∈e◆;

⑥ if (DetermineActivitiesRelationship(e,

α(tm))=sequential)

⑧ 添加庫(kù)所t|T|+1?使?tm=t|T|+1?;

⑩ end if

α(tm))=choice)

α(tm))=parallel)

{?t|T|+1,?tm};

算法4. 確定活動(dòng)a與b的關(guān)系.

FunctionDetermineActivitiesStructure(a,b)

①A是活動(dòng)集合,A=activities set;

②L是一個(gè)事件日志,L∈B(A*);

③R=null;

④ if (a∈A且b∈A)

⑤ for (i=0;i≤|L|;i++)

⑥ if (a∈&(li))

⑦ if (b∈&(li))

⑧ if (a與b的順序是〈a,b〉)

⑨j=i+1;

⑩ while (j≤|L|)

在算法4中，當(dāng)a和b記錄在一條跡中時(shí)，那么它們應(yīng)該在順序結(jié)構(gòu)中或并行結(jié)構(gòu)中.如果在每條跡中，它們的順序總是〈a,b〉，則它們?cè)陧樞蚪Y(jié)構(gòu)中.如果在一些跡中，它們的順序是〈a,b〉，在其他跡中，它們的順序是〈b,a〉，則a與b在并行結(jié)構(gòu)中.如果a包含在一條跡中，但b不能被記錄在該跡中.類似地，如果b包含在一條跡中，但a不能被記錄在該跡中.則a與b在選擇結(jié)構(gòu)中.算法4需要遍歷日志L中的所有跡，在算法4中包含2層循環(huán).|L| 表示日志L中跡的數(shù)目.因此，算法4的復(fù)雜度是O(|L|2).

對(duì)于圖5的非正確模型N2，假設(shè)事件日志中包含2條跡：l4=〈B,C,D,E,F,G,I〉和l5=〈B,C,E,D,F,G,J〉.對(duì)于l4=〈B,C,D,E,F,G,I〉，在變遷集T中不存在ti和tj(1≤i,j≤|T|)，有α(ti)=D和α(tj)=I.因此，D和I是額外活動(dòng)，需要插入到N2中.同樣，對(duì)于l5=〈B,C,E,D,F,G,J〉，D是一個(gè)額外活動(dòng).

Fig. 5 An incorrect process model N2圖5 非正確模型N2

Fig. 6 The repaired model of N2圖6 流程模型N2的修正模型

在l4=〈B,C,D,E,F,G,I〉與l5=〈B,C,E,D,F,G,J〉中，◆D∩D◆={E}.因此，D與E在一個(gè)并行結(jié)構(gòu)中，并且并行結(jié)構(gòu)可以正確的重演這2條跡.由N2可以看出，E是在一個(gè)順序結(jié)構(gòu)中.因此，需要構(gòu)建一個(gè)包含D與E的并行結(jié)構(gòu)，將該并行結(jié)構(gòu)插入到N2中.

l4=〈B,C,D,E,F,G,I〉包含I但不包含J.l5=〈B,C,E,D,F,G,J〉包含J但不包含I.這意味著跡中只能包含這2個(gè)活動(dòng)中的1個(gè).因此，只有包含I與J的選擇結(jié)構(gòu)可以正確的重演這2條跡.N2的修正模型如圖6所示：

3.3 改變子流程

通過(guò)在模型中添加活動(dòng)或刪除活動(dòng)可以改變模型的行為，但通過(guò)改變模型的子流程同樣可以改變模型的行為.如果跡中的一些活動(dòng)關(guān)系不能被模型中相應(yīng)的子流程描述，則需要在模型用可以描述活動(dòng)關(guān)系流程將相應(yīng)的子流程替換.換句話說(shuō)，如果跡中存在異常活動(dòng)，則需要改變模型中的子流程.下面給出了替換模型子流程的方法.

如果跡中存在異?；顒?dòng)e，則必定存在包含e的子日志La.模型中對(duì)應(yīng)于La的子流程N(yùn)a不能重演

定義16.A表示一個(gè)活動(dòng)集，Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型.l=lsljlkelmlnlu是Ns的一條跡，且α-1(l)=α-1(lsljlkelmlnlu)=α-1(ls)α-1(lj)α-1(lk)α-1(e)α-1(lm)α-1(ln)α-1(lu)=σsσjσktiσmσnσu(1≤i≤|T|).如果?ti?或者???σn，則稱e(α(ti)=e)是一個(gè)異?；顒?dòng).

給定流程模型Ns和異?；顒?dòng)e，算法5給出了改變子流程的方法.

算法5. 改變Ns中包含e的子流程.

FunctionChangeBehavior(Ns,e)

②Na=null;

③T是變遷集合,T=transitions set;

④la=DetermineSubtrace(e);

⑤La=DetermineSublog(la);

⑨σa=α-1(la);

⑩ for (i=0;i≤|T|;i++)

算法6. 確定Ns不能重演的子跡.

FunctionDetermineSubtrace(e)

①A是活動(dòng)集合，A=activities set;

②L是一個(gè)事件日志,L∈B(A*);

③t=α-1(e);

④la=e;

⑤ for (i=0;i≤|L|;i++)

⑥σi=α-1(li);

⑦ if (t∈&(σi))

⑧j=σi(t);

⑨k=σi(t);

⑩ if (α(?(?t))?◆la)

算法6首先判斷◆e中的活動(dòng)是否與?(?t)(t=α-1(e))相同，將不同的活動(dòng)添加到la中.然后迭代的判斷◆la中的活動(dòng)，將所有不同的活動(dòng)添加到la中.◆e中的活動(dòng)查找完之后，對(duì)e◆中的活動(dòng)進(jìn)行相同的操作.在每一次的循環(huán)中需要對(duì)日志L中的所有跡進(jìn)行遍歷，需要遍歷每條跡中的所有活動(dòng).|l|表示L中最長(zhǎng)跡的長(zhǎng)度，因此，算法6的復(fù)雜度是O(|L|×|l|).

算法7. 確定需要重新發(fā)現(xiàn)的子日志.

FunctionDetermineSublog(la)

①A是活動(dòng)集合，A=activities set;

②L是一個(gè)事件日志,L∈B(A*);

③La={la};

④ for (i=0;i≤|L|;i++)

⑥ for (j=0;j≤|li|;j++)

⑦ if (li[j]∈&(la))

⑨ end if

⑩ end for

Fig. 7 An incorrect process model N3圖7 非正確模型N3

Fig. 8 The repaired model of N3圖8 流程模型N3的修正模型

3.4 修正循環(huán)結(jié)構(gòu)

在修正有循環(huán)結(jié)構(gòu)的模型時(shí)，需要確定跡中重復(fù)的子跡，在模型中找到可以描述該子跡的子模型，在跡中確定“redo”活動(dòng)，通過(guò)在模型中添加“redo”活動(dòng)，使模型可以重演重復(fù)的子跡[28].因此，在修正模型時(shí)需要在模型中確定循環(huán)體，并在模型添加“redo”活動(dòng).

定義17.A表示一個(gè)活動(dòng)集，Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型.l=lslbe…lblu是Ns的一條跡.lbe是一條循環(huán)子跡，且l(lb)-l(e)=1.如果Ns可以重演lb，但ti∈T(1≤i≤|T|):α(ti)=e，則稱lb為循環(huán)體，e為“redo”活動(dòng).

定義17表明跡l可以在實(shí)際情況下執(zhí)行，但是Ns中不存在“redo”活動(dòng)e，因此只能重演第1次出現(xiàn)的子跡lb，其他重復(fù)的子跡lb不能重演.為了修正Ns可以重演其他的lb，需要在模型中添加活動(dòng)e.

定理3.A表示一個(gè)活動(dòng)集，Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型.L是關(guān)于Ns的一個(gè)事件日志，e對(duì)于Ns是一個(gè)額外活動(dòng)，且?l∈L:l(e)>1.那么可以通過(guò)e確定跡中的重復(fù)子跡.

證明.e是Ns的一個(gè)額外活動(dòng)，且?l∈L:l(e)>1.對(duì)于l(e)>1，那么在l中e至少迭代了2次.那么在這第1次e與第2次e之間存在一條子跡lb，且l(lb)-l(e)=1.因此e是“redo”活動(dòng)，lb是重復(fù)子跡.

證畢.

給定流程模型Ns和“redo”活動(dòng)e，算法8給出了發(fā)現(xiàn)和添加循環(huán)結(jié)構(gòu)的方法.

Fig. 9 An incorrect process model N4圖9 非正確模型N4

算法8. 在模型Ns發(fā)現(xiàn)并添加循環(huán)結(jié)構(gòu).

FunctionAddLoops(Ns,e)

②Nb=null;

③T是變遷集合,T=transitions set;

④t|T|+1是額外活動(dòng), 即α(t|T|+1)=e;

⑤lb=DetermineLoopbody(e);

⑥σb=α-1(lb);

⑦ for (i=0;i≤|T|;i++)

⑧ if (ti∈&(σb))

⑩ end if

在算法8中，e是1個(gè)“redo”活動(dòng).函數(shù)Determine-Loopbody(e)確定了重復(fù)子跡lb.根據(jù)lb中的活動(dòng)，可以找到對(duì)應(yīng)該于lb的子模型Na.在Ns中添加活動(dòng)e之后，Ns可以重演其他迭代的lb.在本文中，假設(shè)循環(huán)體可以正確重演第1次迭代的lb，然后用算法8修正有循環(huán)結(jié)構(gòu)的模型.如果循環(huán)體不能重演lb，就用前面提到的方法對(duì)循環(huán)體進(jìn)行修正.有些情況下，跡中只包含重復(fù)子跡，沒有“redo”活動(dòng)，那么在修正模型時(shí)需要加入不可見變遷作為“redo”活動(dòng).函數(shù)DetermineLoopbody(e)可以確定重復(fù)子跡lb，在算法9中給出了其實(shí)現(xiàn)方法.

算法9. 確定重復(fù)子跡.

FunctionDetermineLoopbody(e)

①A是活動(dòng)集合，A=activities set;

②L是一個(gè)事件日志,L∈B(A*);

③lb=ε;

④ for (i=0;i≤|L|;i++)

⑤ if (e∈&(li))

⑥ for (j=0;j≤|li|;j++)

⑦ if (li(li[j])>1且li[j]?&(lb))

⑧l(xiāng)b=lbli[j];

⑨ end if

⑩ end for

在算法9中，需要確定活動(dòng)e是否在li.如果e存在于li中，則可以通過(guò)li(li[j])確定重復(fù)的活動(dòng).其中l(wèi)i[j]表示li中的第j個(gè)活動(dòng)，li(li[j])表示在li中l(wèi)i[j]的發(fā)生次數(shù).li(li[j])>1表示li[j]是重復(fù)活動(dòng)，li[j]應(yīng)該在重復(fù)子跡lb.|l|表示日志L中最長(zhǎng)跡的長(zhǎng)度，在每次循環(huán)中需要遍歷L中的每一條跡，對(duì)于跡li需要遍歷跡中的每一個(gè)活動(dòng)，因此，算法9的復(fù)雜度是O(|L|×|l|).

對(duì)于圖9的非正確模型N4，假設(shè)事件日志中包含2條跡：l7=〈A,B,C,D,E,G,B,D,C,E,G,B,C,D,E,F,I〉和l8=〈A,B,D,C,E,G,B,C,D,E,H〉.

〈B,C,D,E,G〉或〈B,D,C,E,G〉是2條跡中的重復(fù)子跡.N4不能描述活動(dòng)G，且l7(〈B,D,C,E〉)>1，l8(〈B,D,C,E〉)>1.因此，G是“redo”活動(dòng)，〈B,D,C,E〉是循環(huán)體.N4可以正確重演〈B,D,C,E〉，在N4中添加活動(dòng)G且?G={b6}，G?={b1}.N4的修正模型如圖10所示:

Fig. 10 The repaired model of N4圖10 流程模型N4的修正模型

3.5 完整修正

如果流程模型Ns可以重演日志L，則不需要對(duì)模型進(jìn)行修正.如果Ns不能重演L，則需要根據(jù)L對(duì)Ns修正.對(duì)于L中的跡，需要判斷能否在模型重演，如果不能重演，則要找出跡與模型之間的偏差，然后根據(jù)偏差的類型，對(duì)模型進(jìn)行相應(yīng)的修正.根據(jù)日志L,算法10給出了對(duì)模型Ns的修正方法.

算法10. 根據(jù)日志L對(duì)模型Ns修正.

FunctionModelRepair(Ns,L)

② for (i=0;i≤|T|;i++)

④ break;

⑤ else

⑦ for (j=0;j<|DE|;j++)

⑧ if (dj是移除的活動(dòng))

⑩ end if

定理4.Ns=(P,T;F,α,α-1,mi,mf)是一個(gè)流程模型，L是關(guān)于Ns的一個(gè)事件日志.根據(jù)日志L，

證畢.

4 仿真實(shí)驗(yàn)

對(duì)本文提出的模型修正方法進(jìn)行了手工模擬，對(duì)重新發(fā)現(xiàn)的挖掘方法與增加子流程的修正方法在ProM 6(process mining toolkit)上進(jìn)行了驗(yàn)證.運(yùn)行ProM的計(jì)算機(jī)需要是64位的Win7系統(tǒng)，3.20 GHz的處理器及1 GB的Java虛擬內(nèi)存.在本節(jié)，給出了模型修正方法的實(shí)驗(yàn)評(píng)價(jià).

4.1 實(shí)驗(yàn)數(shù)據(jù)

在這部分，根據(jù)青島某三甲醫(yī)院信息系統(tǒng)的流程模型與事件日志給出了2個(gè)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明了本文方法的正確性與實(shí)用性.醫(yī)院信息系統(tǒng)的住院流程模型如圖11所示.但是由于每個(gè)醫(yī)生和病人在執(zhí)行流程時(shí)，根據(jù)不同的需求會(huì)有不同的處理方式.因此，在醫(yī)院觀察到的實(shí)際流程會(huì)與參考模型(reference model)存在偏差.

Fig. 11 A process model of hospitalization in a hospital圖11 醫(yī)院的住院流程模型

從醫(yī)院信息系統(tǒng)中提取了5個(gè)未加工的日志(L1～L5).從這些日志中，通過(guò)刪除明顯不擬合參考模型的案例得到了5個(gè)過(guò)濾的日志(L1f～L5f)，比如，刪除缺少開始活動(dòng)或不完整的日志.表1顯示了這10個(gè)日志的一些屬性，會(huì)在接下來(lái)的內(nèi)容討論.在這個(gè)表中列出了跡的數(shù)目、最小和最大長(zhǎng)度，利用過(guò)濾的日志(L1f～L5f)進(jìn)行手工修正時(shí)添加的變遷和庫(kù)所的數(shù)目以及移除的變遷數(shù)目.

Table 1 10 Logs from Hospital to a Reference Model and the Properties of Manual Repaired Models

4.2 手工修正

為了獲得指導(dǎo)模型修正的最優(yōu)標(biāo)準(zhǔn)，我們得到了專家用手工修正的參考模型.根據(jù)日志L1f手工修正的模型如圖12所示，對(duì)參考模型進(jìn)行改變：添加了4個(gè)活動(dòng)、跳過(guò)了1個(gè)活動(dòng)、刪除了2個(gè)活動(dòng)、模型的修正部分由虛線圓標(biāo)出.參考模型中有64個(gè)庫(kù)所、68個(gè)變遷、149條弧，表1給出了根據(jù)每個(gè)過(guò)濾日志通過(guò)手工修正得到的模型與參考模型之間的差別.根據(jù)日志L5f修正，對(duì)模型的改變最大，因?yàn)樾枰砑幼恿鞒?，跳過(guò)一些變遷并刪除一些變遷.根據(jù)L1f和L2f的修正，對(duì)移除活動(dòng)的改變比較少.根據(jù)L4f的修正，添加的活動(dòng)與移除的活動(dòng)相等.

Fig. 12 Manually repaired model for log L1f圖12 根據(jù)日志L1f手工修正的流程模型

4.3 實(shí)驗(yàn)對(duì)比

對(duì)于給定的日志與流程模型，第3節(jié)給出了模型修正的方法，使修正的流程模型符合給定的事件日志.函數(shù)RemoveActivity(Ns,e)可以識(shí)別跳過(guò)的活動(dòng)與刪除的活動(dòng)，并將這些活動(dòng)從流程模型中移除.函數(shù)AddActivity(Ns,e)可以識(shí)別額外的活動(dòng)，并將這些活動(dòng)添加到流程模型中.函數(shù)Change-Behavior(Ns,e)可以識(shí)別不能被模型描述的子日志，并用重新發(fā)現(xiàn)的子流程替換模型中的相應(yīng)部分.函數(shù)AddLoops(Ns,e)可以識(shí)別日志中的“redo”活動(dòng)，并在模型中添加循環(huán)結(jié)構(gòu).函數(shù)ModelRepair(Ns,L)，可以根據(jù)日志L，對(duì)模型Ns進(jìn)行整體修正.

根據(jù)提取的5個(gè)過(guò)濾日志，手工模擬本文提出的修正方法，對(duì)參考模型進(jìn)行了修正.對(duì)于每個(gè)過(guò)濾日志，通過(guò)ProM 6上的Repair Model[29]插件完成了增加子流程方法對(duì)參考模型的修正，利用ProM 6中Alpha Miner[18]插件得到了重新挖掘的流程模型.為了評(píng)價(jià)論文中提出的模型修正技術(shù)，我們進(jìn)行實(shí)驗(yàn)對(duì)比.

4.3.1 模型相似度

由定義11可知，修正的模型要與參考模型盡可能相似.圖編輯相似度(graph edit similarity)[30]大致地表明了參考模型與修正/重新發(fā)現(xiàn)模型(repaired/rediscovered model)之間的差異部分，即1.0表示模型完全相同.為了證明基于引發(fā)序列修正的流程模型(process model repair via alignment)的有效性，根據(jù)文獻(xiàn)[30]中的圖編輯相似度公式，手工計(jì)算了參考模型與基于引發(fā)序列修正的模型之間的相似度、手工修正的模型與參考模型之間的相似度、增加子流程修正的模型(add sub-processes repaired model)[29]與參考模型之間的相似度以及Alpha算法[18]發(fā)現(xiàn)模型與參考模型之間的相似度，其結(jié)果如圖13所示：

Fig. 13 Similarity on different repair methods圖13 對(duì)于每個(gè)日志不同修正模型之間的相似度

由圖13可知，手工修正模型、基于引發(fā)序列的修正模型、增加子流程的修正模型都與參考模型非常相似，因?yàn)槠湎嗨贫戎祷驹?.9以上.手工修正的模型較基于校對(duì)序列修正的模型相似于參考模型，比如對(duì)于日志L2f來(lái)說(shuō)，基于引發(fā)序列修正模型與參考模型的相似度是0.952 4，手工修正模型與參考模型的相似度是0.958 7.在有些情況下，基于引發(fā)序列修正的模型比增加子流程修正的模型更相似于參考模型，比如對(duì)于日志L3f來(lái)說(shuō)，基于引發(fā)序列修正模型與參考模型的相似度是0.924 7，增加子模型修正模型與參考模型的相似度是0.880 9.但有些情況下，增加子流程修正的模型比基于引發(fā)序列修正的模型更相似于參考模型，比如對(duì)于日志L4f來(lái)說(shuō)，增加子模型修正模型與參考模型的相似度是0.946 0，基于引發(fā)序列修正模型與參考模型的相似度是0.922 3.這是由于有些情況下，基于引發(fā)序列的修正方法會(huì)改變參考模型的子流程，而增加子流程的修正方法會(huì)在參考模型中加入一個(gè)結(jié)構(gòu)比較復(fù)雜的子流程.通過(guò)Alpha算法重新挖掘得到的模型與參考模型之間的相似度比較差，其相似度基本都小于0.9，這是因?yàn)楦鶕?jù)日志重新挖掘得到的模型可能會(huì)改變參考模型的結(jié)構(gòu).

4.3.2 跡的完全重演率

模型修正的目的是使修正的流程模型可以重演(大多數(shù))相應(yīng)的事件日志.跡的完全重演率指的是模型可以完全重演的跡所占日志中跡的百分比.通過(guò)跡的完全重演率可以證明修正方法的正確性，即100%意味著模型可以完全重演日志中的所有跡.為了檢測(cè)基于引發(fā)序列模型修正的正確性，通過(guò)ProM中的Replay a Log on Petri Net for All Optimal Alignment插件，計(jì)算日志L1f～L5f在參考模型，增加子流程修正模型與Alpha算法發(fā)現(xiàn)模型上的所有最優(yōu)校準(zhǔn)，并統(tǒng)計(jì)了日志在各模型上重演得到的最優(yōu)校準(zhǔn)(即校準(zhǔn)序列中只有同步動(dòng)作，沒有日志動(dòng)作或模型動(dòng)作)的條數(shù)，以此作為日志可以在模型完全重演跡的條數(shù).對(duì)于基于引發(fā)序列修正模型，通過(guò)模擬跡在模型上的重演，統(tǒng)計(jì)了日志在模型上完全重演跡的條數(shù).修正或重新發(fā)現(xiàn)模型上跡的完全重演率如圖14所示：

Fig. 14 Replayed trace percentages of different repair methods for logs圖14 對(duì)于每個(gè)日志不同修正模型上跡的完全重演率

從跡的重演率上可以看出，手工修正模型可以完全重演過(guò)濾的5個(gè)日志中的所有跡，因?yàn)檑E的重演率都是100%.基于引發(fā)序列修正的模型基本可以完全重演日志中80%以上的跡.而參考模型的跡重演率基本都在80%以下，由此可以證明本文所提修正方法的正確性.而通過(guò)Alpha算法挖掘發(fā)現(xiàn)模型的跡重演率不穩(wěn)定，比如對(duì)于L2f來(lái)說(shuō)，跡的重演率是85.95%；而對(duì)L3f來(lái)說(shuō)，其結(jié)果是31.53%，這是由于重新挖掘的模型不一定能夠解決現(xiàn)有模型存在的問題.而增加子流程修正模型的跡重演百分率都比較低，這是由于增加子流程的修正方法不能修正模型中的選擇分支結(jié)構(gòu)，而參考模型中存在多個(gè)選擇分支.根據(jù)日志L1f～L5f，通過(guò)增加子流程修正的模型都將參考模型中的一條正確分支上所有活動(dòng)修正為不可見變遷，這導(dǎo)致在求模型與日志的所有最優(yōu)準(zhǔn)時(shí)，將日志中的相應(yīng)活動(dòng)當(dāng)作了日志動(dòng)作.日志與模型最優(yōu)校準(zhǔn)的條數(shù)會(huì)相應(yīng)減少，導(dǎo)致修正模型的跡重演率嚴(yán)重降低.

5 總 結(jié)

本文給出了一種流程模型的修正方法.在模型修正的過(guò)程中，主要考慮模型的擬合度.對(duì)于日志中從來(lái)沒記錄的活動(dòng)，給出了將這些活動(dòng)移除流程模型的方法.對(duì)于流程模型沒有描述的活動(dòng)，給出了在模型的合適位置添加子流程的方法.對(duì)于跡中活動(dòng)關(guān)系與模型中相應(yīng)的子流程描述不一致的，給出了改變模型子流程的方法.該模型修正方法目的是使得到的修正模型可以重演(大多數(shù))相應(yīng)的事件日志，并盡可能地與參考模型相似.最后通過(guò)相似度與跡的完全重演率證明了所提方法的有效性與正確性.

未來(lái)工作是如何修正存在循環(huán)結(jié)構(gòu)的流程模型，并在模型修正的過(guò)程中參考模型的其他符合性標(biāo)準(zhǔn)，比如泛化度與精確度等.

[1] Manyika J, Chui M, Brown B. Big data: The next frontier for innovation, competition and productivity[EB/OL]. (2011-07-01)[2015-05-20]. http://www.mckinsey.com/insights/business-technology/big_data_the_next_frontier_for_innovation

[2] Li Guojie. The scientific value of big data research[J]. Communications of the CCF, 2012, 8(9): 8-15 (in Chinese)(李國(guó)杰. 大數(shù)據(jù)研究的科學(xué)價(jià)值[J]. 中國(guó)計(jì)算機(jī)學(xué)會(huì)通訊, 2012, 8(9): 8-15)

[3] Olson D L, Kesharwani S. Enterprise Information Systems: Contemporary Trends and Issues[M]. River Edge, NJ: World Scientific, 2009: 13-16

[4] van der Aalst W M P. Process Mining: Discovery, Conformance and Enhancement of Business Processes[M]. Berlin: Springer, 2011: 1-10

[5] Wang Lu, Du Yuyue, Liu Wei. Aligning observed and modelled behaviour based on workflow decomposition[J]. Enterprise Information Systems, 2017, 11(8): 1207-1227

[6] Wang Lu, Du Yuyue. An alignment-based identifying method of the problem areas within process models[J]. Journal of Shandong University of Science and Technology: Nature Science, 2015, 34(1): 42-46,53 (in Chinese)(王路, 杜玉越. 一種基于校準(zhǔn)的模型問題域識(shí)別方法[J]. 山東科技大學(xué)學(xué)報(bào):自然科學(xué)版, 2015, 34(1): 42-46,53)

[7] Du Yuyue, Sun Yanan, Liu Wei. Petri nets based recognition of model deviation domains and model repair[J]. Journal of Computer Research and Development, 2016, 53(8): 1766-1780 (in Chinese)(杜玉越, 孫亞男, 劉偉. 基于Petri網(wǎng)的模型偏差域識(shí)別與模型修正[J]. 計(jì)算機(jī)研究與發(fā)展, 2016, 53(8): 1766-1780)

[8] Rodrguez A, Fernndez-Medina E, Piattini M A. BPMN extension for the modeling of security requirements in business processes[J]. IEICE Trans on Information and Systems, 2007, 90(4): 745-752

[9] van der Aalst W M P. Formalization and verification of event-driven process chains[J]. Information and Software Technology, 1999, 41(10): 639-650

[10] Murata T. Petri nets: Properties, analysis and applications[J]. Proceedings of the IEEE, 1989, 77(4): 541-580

[11] Du Yuyue, Qi Liang, Zhou Mengchu. A vector matching method for analyzing logic Petri nets[J]. Enterprise Information Systems, 2011, 5(4): 449-468

[12] Du Yuyue, Qi Liang, Zhou Mengchu. Analysis and application of logical Petri nets to e-commerce systems[J]. IEEE Trans on Systems, Man, and Cybernetics: Systems, 2014, 44(4): 468-481

[13] Du Yuyue, Jiang Changjun, Zhou Mengchu. A Petri net-based model for verification of obligations and accountability in cooperative systems[J]. IEEE Trans on Systems, Man, and Cybernetics, Part A: Systems and Humans, 2009, 39(2): 299-308

[14] Du Yuyue, Jiang Changjun, Zhou Mengchu, et al. Modeling and monitoring of e-commerce workflows[J]. Information Sciences, 2009, 179(7): 995-1006

[15] Du Yuyue, Wang Lu, Qi Man. Constructing service clusters based on service space[J]. International Journal of Parallel Programming, 2017, 45(4): 982-1000

[16] Rozinat A, van der Aalst W M P. Conformance checking of processes based on monitoring real behavior[J]. Information Systems, 2008, 33(1): 64-95

[17] Petkovic M, Prandi D, Zannone N. Purpose control: Did you process the data for the intended purpose?[C] //Proc of the 8th VLDB Int Conf on Secure Data Management. Berlin: Springer, 2011: 145-168

[18] van der Aalst W M P, Weijters A J M M, Maruster L. Workflow mining: Discovering process models from event logs[J]. IEEE Trans on Knowledge and Data Engineering, 2004, 16(9): 1128-1142

[19] Wen Lijie, van der Aalst W M P, Wang Jianmin, et al. Mining process models with non-free-choice constructs[J]. Data Mining & Knowledge Discovery, 2007, 15(2): 145-180

[20] Wen Lijie, Wang Jianmin, Sun Jiaguang. Invisible tasks from event logs[G] //Advances in Data and Web Management. Berlin: Springer, 2007: 358-365

[21] Badouel E. On the α-reconstructibility of workflow nets[G] //Application and Theory of Petri Nets. Berlin: Springer, 2012: 128-147

[22] Bergenthum R, Desel J, Lorenz R, et al. Process mining based on regions of languagesn[C] //Proc of the 5th Int Conf on Business Process Management. Berlin: Springer, 2007: 375-383

[23] Bergenthum R, Desel J, Mauser S, et al. Synthesis of Petri nets from term based representations of infinite partial languages[J]. Fundamenta Informaticae, 2009, 95(1): 187-217

[24] Cortadella J, Kishinevsky M, Lavagno L, et al. Deriving Petri nets from finite transition systems[J]. IEEE Trans on Computers, 1998, 47(8): 859-882

[25] van der Werf J M E M, Dongen B F V, Hurkens C A J, et al. Process discovery using integer linear programming[J]. Fundamenta Informaticae, 2008, 94(3): 368-387

[26] Wang Jianmin, Song Shaoxu, Zhu Xiaochen, et al. Efficient recovery of missing events[J]. Proceedings of the VLDB Endowment, 2013, 6(10): 841-852

[27] Wang Jianmin, Song Shaoxu, Lin Xuemin, et al. Cleaning structured event logs: A graph repair approach[C] //Proc of the 31st IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2015: 30-41

[28] van der Aalst W M P. The application of Petri nets to workflow management[J]. The Journal of Circuits, Systems and Computers, 1998, 8(1): 21-66

[29] Fahland D, van der Aalst W M P. Model repair-aligning process models to reality[J]. Information Systems, 2015, 47(1): 220-243

[30] Dijkman R M, Dumas M, Garcabauelos L. Graph matching algorithms for business process model similarity search[C] //Proc of the 7th Int Conf on Business Process Management. Berlin: Springer, 2009: 835-842