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

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

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

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

目前，存在很多從控制流角度描述流程模型的形式化語言，比如業(yè)務(wù)流程建模標(biāo)記法(business process modeling notation, BPMN)[8]、因果網(wǎng)(causal nets)[4]、事件驅(qū)動流程鏈(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)，還可以模擬流程運行過程中的動態(tài)行為.對于具有并行、并發(fā)、異步、分布和不確定性等性質(zhì)的信息系統(tǒng)，可以利用Petri網(wǎng)對其進(jìn)行有效地描述和分析[11-15]，因此，本文用Petri網(wǎng)來描述流程模型.

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

1 相關(guān)工作

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

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

當(dāng)已有的模型與流程的執(zhí)行過程不一致時，可以通過流程發(fā)現(xiàn)(process discovery)技術(shù)得到一個新的流程模型.根據(jù)活動的次序關(guān)系發(fā)現(xiàn)流程模型的技術(shù)有Alpha算法[18]及其衍生算法[19-20]，這種技術(shù)可以保證模型的同構(gòu)-再發(fā)現(xiàn)(isomorphic-rediscover)能力[21]，但是不能保證模型的擬合性與健壯性.基于語義(semantics-based)的發(fā)現(xiàn)技術(shù)有基于語言的區(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ǔ)知識

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

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

多重集Z=[a3,b,c2]表示集合S上的1個多重集，其中a,b,c∈S，Z(a)=3,Z(b)=1,Z(c)=2.Z1,Z2∈B(S)是2個多重集.2個多重集的和是Z3=Z1⊕Z2，其中Z3∈B(S)，對于所有的a∈S：Z3(a)=Z1(a)+Z2(a).2個多重集的差是Z4=Z1-Z2，對于所有的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上所有有限序列的集合，ε表示一個空序列.序列σ=〈σ[1],σ[2],…,σ[n]〉，其中σ[i]表示序列的第i個元素，〈σ[i],σ[i+1]〉表示2個相鄰接的元素，|σ|=n表示序列σ的長度.對于?a∈S，σ(a)表示a在σ中出現(xiàn)的次數(shù).σsub表示σ的子序列，σ(σsub)表示子序列σsub在σ中出現(xiàn)的次數(shù).

定義3.Z是集合S上的一個多重集，Q?S是集合S的一個子集，σ∈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上的一個向量.πi(v)表示v的第i個元素，其中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)為一個網(wǎng)，其中：

1)P是庫所有限集合；

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

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

定義6[9]. 設(shè)N=(P,T;F)為一個網(wǎng).對于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í)行過程都可以由這4種結(jié)構(gòu)組合而成.

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

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

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

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

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

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

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

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

Fig. 2 An example of an engineering drawing process Nd圖2 工程圖設(shè)計流程Nd

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

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

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

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

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

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

比如，如果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表示一個活動集，L∈B(A*)是一個事件日志，e∈A是L有一個活動，

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

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

稱◆e為e的前活動集，e◆是e的后活動集.

3 模型修正

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

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

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

3.1 移除活動

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

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

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

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

定義14指出，Ns描述了活動e，但是在流程實際運行過程中，e從來沒有發(fā)生過，那么需要在Ns中刪除活動e.

證明.

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

證畢.

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

算法1. 從模型Ns中移除活動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是可跳過變遷)

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

算法2. 確定活動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 {

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

活動G記錄在l3中，但是沒有記錄在l2中，如果要修正N1，需要在模型中跳過活動G.如果要跳過G，可以添加不可見變遷τ，?τ=?G且τ?=G?.同時要添加從b6到τ及從τ到b8的弧.活動K即沒有記錄在l2中也沒有記錄在l3中，因此需要在N1中刪除K.從N1可以看出，K是在順序結(jié)構(gòu)中.要刪除K，需要加入從G到b8的弧，且刪除庫所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 添加活動

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

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

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

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

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

證畢.

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

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

算法3. 在模型Ns中添加活動e.

FunctionAddActivity(Ns,e)

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

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

④α(tk)∈◆e;

⑤α(tm)∈e◆;

⑥ if (DetermineActivitiesRelationship(e,

α(tm))=sequential)

⑧ 添加庫所t|T|+1?使?tm=t|T|+1?;

⑩ end if

α(tm))=choice)

α(tm))=parallel)

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

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

FunctionDetermineActivitiesStructure(a,b)

①A是活動集合,A=activities set;

②L是一個事件日志,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記錄在一條跡中時，那么它們應(yīng)該在順序結(jié)構(gòu)中或并行結(jié)構(gòu)中.如果在每條跡中，它們的順序總是〈a,b〉，則它們在順序結(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).

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

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在一個并行結(jié)構(gòu)中，并且并行結(jié)構(gòu)可以正確的重演這2條跡.由N2可以看出，E是在一個順序結(jié)構(gòu)中.因此，需要構(gòu)建一個包含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個活動中的1個.因此，只有包含I與J的選擇結(jié)構(gòu)可以正確的重演這2條跡.N2的修正模型如圖6所示：

3.3 改變子流程

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

如果跡中存在異?；顒觘，則必定存在包含e的子日志La.模型中對應(yīng)于La的子流程Na不能重演

定義16.A表示一個活動集，Ns=(P,T;F,α,α-1,mi,mf)是一個流程模型.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)是一個異?；顒?

給定流程模型Ns和異?；顒觘，算法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是活動集合，A=activities set;

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

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

FunctionDetermineSublog(la)

①A是活動集合，A=activities set;

②L是一個事件日志,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)的模型時，需要確定跡中重復(fù)的子跡，在模型中找到可以描述該子跡的子模型，在跡中確定“redo”活動，通過在模型中添加“redo”活動，使模型可以重演重復(fù)的子跡[28].因此，在修正模型時需要在模型中確定循環(huán)體，并在模型添加“redo”活動.

定義17.A表示一個活動集，Ns=(P,T;F,α,α-1,mi,mf)是一個流程模型.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”活動.

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

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

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

證畢.

給定流程模型Ns和“redo”活動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是額外活動, 即α(t|T|+1)=e;

⑤lb=DetermineLoopbody(e);

⑥σb=α-1(lb);

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

⑧ if (ti∈&(σb))

⑩ end if

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

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

FunctionDetermineLoopbody(e)

①A是活動集合，A=activities set;

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

對于圖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不能描述活動G，且l7(〈B,D,C,E〉)>1，l8(〈B,D,C,E〉)>1.因此，G是“redo”活動，〈B,D,C,E〉是循環(huán)體.N4可以正確重演〈B,D,C,E〉，在N4中添加活動G且?G={b6}，G?={b1}.N4的修正模型如圖10所示:

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

3.5 完整修正

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

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

FunctionModelRepair(Ns,L)

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

④ break;

⑤ else

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

⑧ if (dj是移除的活動)

⑩ end if

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

證畢.

4 仿真實驗

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

4.1 實驗數(shù)據(jù)

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

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

從醫(yī)院信息系統(tǒng)中提取了5個未加工的日志(L1～L5).從這些日志中，通過刪除明顯不擬合參考模型的案例得到了5個過濾的日志(L1f～L5f)，比如，刪除缺少開始活動或不完整的日志.表1顯示了這10個日志的一些屬性，會在接下來的內(nèi)容討論.在這個表中列出了跡的數(shù)目、最小和最大長度，利用過濾的日志(L1f～L5f)進(jìn)行手工修正時添加的變遷和庫所的數(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所示，對參考模型進(jìn)行改變：添加了4個活動、跳過了1個活動、刪除了2個活動、模型的修正部分由虛線圓標(biāo)出.參考模型中有64個庫所、68個變遷、149條弧，表1給出了根據(jù)每個過濾日志通過手工修正得到的模型與參考模型之間的差別.根據(jù)日志L5f修正，對模型的改變最大，因為需要添加子流程，跳過一些變遷并刪除一些變遷.根據(jù)L1f和L2f的修正，對移除活動的改變比較少.根據(jù)L4f的修正，添加的活動與移除的活動相等.

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

4.3 實驗對比

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

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

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]中的圖編輯相似度公式，手工計算了參考模型與基于引發(fā)序列修正的模型之間的相似度、手工修正的模型與參考模型之間的相似度、增加子流程修正的模型(add sub-processes repaired model)[29]與參考模型之間的相似度以及Alpha算法[18]發(fā)現(xiàn)模型與參考模型之間的相似度，其結(jié)果如圖13所示：

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

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

4.3.2 跡的完全重演率

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

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

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

5 總 結(jié)

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

未來工作是如何修正存在循環(huán)結(jié)構(gòu)的流程模型，并在模型修正的過程中參考模型的其他符合性標(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)(李國杰. 大數(shù)據(jù)研究的科學(xué)價值[J]. 中國計算機(jī)學(xué)會通訊, 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)的模型問題域識別方法[J]. 山東科技大學(xué)學(xué)報:自然科學(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)的模型偏差域識別與模型修正[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