基于邏輯Petri網(wǎng)的循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)過(guò)程模型修復(fù)方法

劉 偉,薄玉娟,杜玉越,孫紅偉

(山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,山東 青島 266590)

如今多數(shù)企業(yè)使用信息系統(tǒng)管理業(yè)務(wù)流程,而過(guò)程挖掘主要從信息系統(tǒng)中抽取信息[1]。過(guò)程挖掘可分為過(guò)程發(fā)現(xiàn)、一致性檢查和過(guò)程增強(qiáng)等階段[2]。過(guò)程發(fā)現(xiàn)通過(guò)算法從事件日志中挖掘模型;一致性檢查是將日志與模型進(jìn)行比對(duì)[3-4],若出現(xiàn)偏差說(shuō)明過(guò)程模型不能反映現(xiàn)實(shí),需要對(duì)過(guò)程模型進(jìn)行修復(fù);過(guò)程增強(qiáng)使用現(xiàn)有事件日志對(duì)原始模型進(jìn)行改進(jìn)或擴(kuò)展,以適應(yīng)更多事件日志。

現(xiàn)有模型修復(fù)方法主要使用校準(zhǔn)獲得偏差[5]。比如,最具代表性的Fahland方法[6]根據(jù)過(guò)程發(fā)現(xiàn)算法挖掘子過(guò)程,修復(fù)后的模型無(wú)限次重復(fù)子過(guò)程,然而這種子過(guò)程通常不允許重復(fù);Knapsack方法[7]通過(guò)設(shè)置模型移動(dòng)和日志移動(dòng)成本,比較多種不同方案得到最小總成本,獲得最佳模型修復(fù)方法,但該方法修復(fù)的模型包含不可見(jiàn)變遷。這兩種方法修復(fù)的過(guò)程模型雖然提高擬合度,但不能保證模型的簡(jiǎn)潔度,不能獲得很好的修復(fù)效果。文獻(xiàn)[8]基于Petri網(wǎng)的過(guò)程模型修復(fù)方法,針對(duì)循環(huán)結(jié)構(gòu)和選擇結(jié)構(gòu),提出模型偏差域識(shí)別方法, 該方法雖然保證了簡(jiǎn)潔度,但沒(méi)有考慮各結(jié)構(gòu)間的邏輯關(guān)系。為了解決該問(wèn)題,基于邏輯Petri網(wǎng),文獻(xiàn)[9]提出構(gòu)造自由循環(huán)結(jié)構(gòu)過(guò)程模型的修復(fù)方法,可根據(jù)事件日志識(shí)別有問(wèn)題的變遷構(gòu)造循環(huán)結(jié)構(gòu)。

現(xiàn)有模型修復(fù)方法很少考慮包含間接依賴關(guān)系的過(guò)程模型。如含循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)的過(guò)程模型,由兩個(gè)循環(huán)塊和一個(gè)選擇塊組成,第二個(gè)循環(huán)體的循環(huán)次數(shù)取決于第一個(gè)循環(huán)體的循環(huán)次數(shù)和執(zhí)行的選擇分支[10]。隨著業(yè)務(wù)流程愈加復(fù)雜,流程出現(xiàn)了各種特殊事件日志,如第一個(gè)循環(huán)塊沒(méi)有執(zhí)行完就執(zhí)行選擇塊,選擇分支混合執(zhí)行,間接依賴關(guān)系發(fā)生改變等。現(xiàn)有修復(fù)方法通過(guò)添加不可見(jiàn)變遷或自循環(huán)修復(fù)模型,但簡(jiǎn)潔度不高,修復(fù)結(jié)果不能滿足要求。因此,本研究針對(duì)循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu),提出一種基于邏輯Petri網(wǎng)的過(guò)程模型修復(fù)方法。首先,針對(duì)循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu),提出從事件日志中提取循環(huán)子日志和選擇子日志的算法,判斷模型中的循環(huán)結(jié)構(gòu)和選擇結(jié)構(gòu);其次,提出兩個(gè)定理用于發(fā)現(xiàn)事件日志和原始模型中關(guān)于循環(huán)和選擇結(jié)構(gòu)的偏差,找到偏差位置并提出修復(fù)算法進(jìn)行模型修復(fù);然后,引入關(guān)聯(lián)規(guī)則表達(dá)不同結(jié)構(gòu)間的間接依賴關(guān)系;最后,對(duì)建筑公司工程項(xiàng)目過(guò)程進(jìn)行模擬實(shí)驗(yàn),驗(yàn)證提出方法的合理性和可行性。

1 基本概念

首先介紹一些基本概念,包括跡和事件日志、Petri網(wǎng)、過(guò)程模型、邏輯Petri網(wǎng)等。

定義1(跡和事件日志)[11]A是一個(gè)活動(dòng)集合,A*表示集合A上所有有限序列,B(A*)表示集合A上的多集集合,σ∈A*為一個(gè)跡,L∈B(A*)為一個(gè)事件日志。

定義2(前驅(qū)與后繼)[11]σ∈A*為一個(gè)跡,活動(dòng)a∈σ,且在σ中a的位置為i,#a是a的前驅(qū),在σ中的位置為i-1;a#是a的后繼,在σ中的位置為i+1。

定義3(Petri網(wǎng))[12-14]PN=(P,T;F,M)為一個(gè)Petri網(wǎng),當(dāng)且僅當(dāng):

1)N=(P,T;F)為一個(gè)網(wǎng),P為庫(kù)所集,T為變遷集;

2)F?(P×T)∪(T×P)表示有向連接弧集合;

3)M:P→N為一個(gè)標(biāo)識(shí)。

定義4(前集和后集)[14]PN=(P,T;F,M)為一個(gè)Petri網(wǎng),?x={y∈P∪T∧(y,x)∈F}為x的前集,x?={y∈P∪T∧(x,y)∈F}為x的后集。

定義5(過(guò)程模型)[15]Ns=(PN,a,Mi,Mf)為一個(gè)過(guò)程模型,其中:

1)PN=(P,T;F,M)為一個(gè)Petri網(wǎng);

2)a:T→A∪{τ}是變遷到活動(dòng)的映射函數(shù),τ為不可見(jiàn)變遷;

3)mi=[pi]∈Mi是初始標(biāo)識(shí),mf=[po]∈Mf是終止標(biāo)識(shí)。

圖1為一個(gè)基于Petri網(wǎng)的過(guò)程模型實(shí)例。

圖1 基于Petri網(wǎng)的過(guò)程模型實(shí)例

定義6(過(guò)程樹(shù))[16]A為活動(dòng)集合,⊕={→,×,∧,}為操作符集合,τ為不可見(jiàn)變遷,其中:

1)a∈A∪{τ}為一棵過(guò)程樹(shù);

2) 若PT1,PT2,…,PTn為n棵過(guò)程樹(shù),則⊕(PT1,PT2,…,PTn)也是一棵過(guò)程樹(shù),→表示順序關(guān)系,×表示選擇關(guān)系,∧表示并發(fā)關(guān)系,表示循環(huán)關(guān)系。

圖1過(guò)程模型可表示為過(guò)程樹(shù)PT1:→(a,(b,c),d,×(→(e,g),→(f,h)))。

定義7(邏輯Petri網(wǎng))[17]LPN=(P,T;F,I,O,M)為一個(gè)邏輯Petri網(wǎng),其中:

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

2)T=TI∪TO∪TD是有限變遷集,P∪T≠?,P∩T=?;若t∈TI∪TO,?t∩t?=?;其中,TI為邏輯輸入變遷集,TO為邏輯輸出變遷集,TD為經(jīng)典Petri網(wǎng)變遷集;

3)F?(P×T)∪(T×P)為有向連接弧集合;

4)I是從邏輯輸入變遷到邏輯輸入函數(shù)的映射,對(duì)?t∈TI,I(t)=fI(t);

5)O是從邏輯輸出變遷到邏輯輸出函數(shù)的映射,對(duì)?t∈TO,O(t)=fO(t);

6)M:P→N為一個(gè)標(biāo)識(shí)函數(shù)。

2 循環(huán)選擇及其驅(qū)動(dòng)循環(huán)序列確定算法

本部分介紹循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu),并劃分為循環(huán)結(jié)構(gòu)和選擇結(jié)構(gòu)分別進(jìn)行分析。圖2為一個(gè)循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)過(guò)程模型,使用關(guān)聯(lián)規(guī)則表示不同結(jié)構(gòu)之間的間接依賴關(guān)系,比如關(guān)聯(lián)規(guī)則〈b,c〉2∧〈e,g〉1?〈j,k〉1表示循環(huán)活動(dòng)b、c發(fā)生兩次后執(zhí)行e、g選擇分支,則第二個(gè)循環(huán)塊執(zhí)行一次循環(huán)。

圖2 循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)過(guò)程模型

2.1 循環(huán)序列確定算法

對(duì)循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)進(jìn)行修復(fù),首先要找到模型中所有循環(huán)結(jié)構(gòu)。假設(shè)每個(gè)過(guò)程模型都有一個(gè)唯一的過(guò)程樹(shù),過(guò)程樹(shù)中每個(gè)操作符代表模型的一個(gè)結(jié)構(gòu)。例如在模型中有一個(gè)循環(huán)結(jié)構(gòu),則相應(yīng)過(guò)程樹(shù)節(jié)點(diǎn)n=“”。為方便起見(jiàn),Fi(n)表示n節(jié)點(diǎn)處第i個(gè)子樹(shù)的所有葉節(jié)點(diǎn)。

定義8(活動(dòng)發(fā)生次數(shù)) σ∈L為日志中的一個(gè)跡,s∈σ為一個(gè)序列,對(duì)于任意活動(dòng)a∈σ,num(a,σ)表示活動(dòng)a在跡中出現(xiàn)的次數(shù),num(s,σ)表示序列s在跡中出現(xiàn)的次數(shù)。

定義9(循環(huán)活動(dòng)) σ∈L為日志中的跡,a∈σ為一個(gè)活動(dòng),若num(a,σ)>1,則a為循環(huán)活動(dòng)。

循環(huán)活動(dòng)集合SLA={a∈σ|?σ∈L∧num(a,σ)>1}。

定義10(活動(dòng)集)A為活動(dòng)集合,對(duì)任意序列s∈A*,κ(s)為序列s中的活動(dòng)集。

定義11(循環(huán)序列)SLA為循環(huán)活動(dòng)集合,s=〈s[1],s[2],…,s[i],…,s[n]〉∈SLA*為一個(gè)循環(huán)序列,其中s[i]∈SLA,i∈{1,2,…,n-1}。以|s|表示序列s的長(zhǎng)度。若:

1)κ(s)=1,s為自循環(huán)序列;

2)κ(s)=2,且s[1]>Ls[2],s為短循環(huán)序列,|s|=2;

3)κ(s)>2,且s[i]>Ls[i+1],|s|-2>i>0,s為長(zhǎng)循環(huán)序列。

Ls為所有循環(huán)序列集合。

定義12(循環(huán)開(kāi)始活動(dòng)和循環(huán)結(jié)束活動(dòng))SLA為循環(huán)活動(dòng)集合,s∈SLA*為一個(gè)循環(huán)序列,循環(huán)開(kāi)始活動(dòng)為SLA_s,循環(huán)結(jié)束活動(dòng)為SLA_e,其中:

算法 1 循環(huán)序列確定算法 輸入:事件日志 L 輸出:循環(huán)序列 Ls 1) SLA←?;s←?; 2) For (i = 1,σi∈L,i++; | L | ) do 3) For (j = 1,aj∈σ;j++; | σ| ) do 4) if (num(aj,σi) >1) then 5) SLA = SLA∪aj 6) For (k = 1,ak∈SLA ;k++; | SLA | ) do 7) SLA←SLA -ak 8) s←s+ak 9) For (?a,b∈SLA )do 10) if (a>L b and b = s[1]) then 11) s←a+s 12) SLA←SLA -a 13) if (a>L b and a = s[ | s| ]) then 14) s←s+b 15) SLA←SLA -b 16) Ls←Ls∪s 17) return Ls

1)SLA_s=(ai∈SLA|ai=si[1]);

2)SLA_e=(ai∈SLA|ai=si[n]),i∈{1,2,…,m}。

算法1為循環(huán)序列確定算法。步驟1)初始化循環(huán)序列;步驟2)、3)遍歷日志和跡;步驟4)～5)表明若跡σi中的活動(dòng)aj出現(xiàn)次數(shù)>1,則活動(dòng)aj為循環(huán)活動(dòng);步驟6)～8)遍歷循環(huán)活動(dòng)集合,添加循環(huán)活動(dòng)到循環(huán)序列s中;步驟9)～12)表示若循環(huán)活動(dòng)a,b為順序關(guān)系且活動(dòng)b為s的第一個(gè)活動(dòng),把活動(dòng)a添加到s中且在活動(dòng)b之前;步驟13)～15)表示若循環(huán)活動(dòng)a,b為順序關(guān)系且活動(dòng)a為s的最后一個(gè)活動(dòng),則把活動(dòng)b添加到s中且在活動(dòng)a之后;步驟16)、17)把得到的循環(huán)序列s添加到循環(huán)序列集合Ls中并返回Ls。

例1L={〈a,b,c,g〉,〈a,b,c,d,e,g〉,〈a,b,c,d,e,b,c,d,e,g〉}。num(b,σ3)=2,num(c,σ3)=2,num(d,σ3)=2,num(e,σ3)=2,所以SLA={b,c,d,e}。根據(jù)算法1,SLA=SLA-b={c,d,e},s=〈b〉,因?yàn)閎>Lc,有s=s+c=〈b,c〉,SLA=SLA-c={d,e},同理得到s=〈b,c,d,e〉。

2.2 選擇序列確定算法

提取出事件日志中的循環(huán)序列后,下一步確定事件日志中的選擇序列。

定義13(選擇活動(dòng)) σ1,σ2∈L為日志中的兩個(gè)跡,a∈σ為跡中的一個(gè)活動(dòng),若a∈σ1,a?σ2且a?SLA,則a為選擇活動(dòng)。選擇活動(dòng)集合SCA={a∈A|?σ1,σ2∈L∧a∈σ1∧a?2∧a?SLA}。

定義14(選擇序列)SCA為選擇活動(dòng)集合,f∈SCA*為一個(gè)選擇序列,其中?f[i]∈SCA,若:

1)κ(f)=1,f為只包含一個(gè)活動(dòng)的選擇序列;

2)κ(f)≥2,且f[i] >Lf[i+1],i∈{1,2,…,n-1},f為長(zhǎng)度為n的選擇序列;

Lf為所有選擇序列集合。

定義15(選擇開(kāi)始活動(dòng)和選擇結(jié)束活動(dòng))SCA為選擇活動(dòng)集合,f∈SCA*為一個(gè)選擇序列,選擇開(kāi)始活動(dòng)為SCA_s,選擇結(jié)束活動(dòng)為SCA_e,其中:

1)SCA_s=(ai∈SCA|ai=fi[1]);

2)SCA_e=(ai∈SCA|ai=fi[n]),i∈{1,2,…,m}.

定義16(選擇分支)Ns=(PN,a,Mi,Mf)為一個(gè)過(guò)程模型,PT為對(duì)應(yīng)過(guò)程樹(shù),CB=(t1,t2,…,tn)是一個(gè)選擇分支元組,其中:

1) ?n=“×”∈PT;

2)tk∈Fi(n),1≤k≤m,1≤i≤n。

選擇分支集合SCB={(t1,t2,…,tn)|tk∈Fi(n),1≤k≤m,1≤i≤n,?n=“×”∈PT}。

算法2為選擇序列確定算法。步驟1)初始化選擇序列f,選擇活動(dòng)集合SCA;步驟2)遍歷日志;步驟3)～4)表明若活動(dòng)a屬于L,但不屬于跡σi,則a為選擇活動(dòng);步驟5)～9)遍歷SCA,若活動(dòng)a,b為順序關(guān)系且a不屬于SCA,b是選擇活動(dòng),則添加b到f;步驟10)～12)表示若活動(dòng)a,b為順序關(guān)系且a屬于SCA,b不是選擇活動(dòng),則添加a到f;步驟13)～14)把f添加到選擇序列集合Lf中并返回Lf。

例2事件日志L={σ1,σ2}={〈a,b,d,f〉,〈a,c,e,f〉},選擇活動(dòng)集合SCA={b,c,d,e}。對(duì)于σ1,有a>Lb且b∈SCA,a?SCA。根據(jù)算法2,f=〈b〉,SCA={c,d,e},d>Lf且d∈SCA,f?SCA,選擇序列f=〈b,d〉,SCA={c,e}。同理可得選擇序列集合Lf={〈b,d〉,〈c,e〉}。

算法 2 選擇序列確定算法 輸入:事件日志 輸出:選擇序列 Lf 1) SCA ← ?,f ← ?; 2) For (i = 1,σi ∈ L;i + +; L ) do 3) if a ∈ L ∧ a ?σi then 4) SCA ←SCA ∪ a 5) For (i = 0;i < | SCA | ;i + +) do 6) For ?a,b ∈ A do 7) if (a > L b ∧ a ?SCA ∧ b ∈SCA ) then 8) f ← f + b 9) SCA ←SCA - b 10) if (a > L b ∧ a ∈SCA ∧ b ?SCA ) then 11) f ← f + a 12) SCA ←SCA - a 13) Lf ←Lf ∪ f 14) return Lf

2.3 循環(huán)選擇驅(qū)動(dòng)循環(huán)序列確定算法

定義17(切分子跡) σ=〈r1,s,r2,…,rn〉∈L為日志上的一個(gè)跡,del(s,σ)={〈r1〉,〈r2,…,rn〉}。

算法3為循環(huán)選擇驅(qū)動(dòng)循環(huán)序列確定算法。步驟1)初始化關(guān)聯(lián)對(duì)集合A?s,循環(huán)選擇驅(qū)動(dòng)循環(huán)序列Llc→l;步驟2)、3)遍歷事件日志和循環(huán)序列集合;步驟4)～7)表明若有循環(huán)序列sj屬于σi,活動(dòng)a屬于sj,且a是循環(huán)結(jié)束活動(dòng),記錄a出現(xiàn)次數(shù),同時(shí)切分子跡σi為λ1;步驟8)遍歷選擇序列集合;步驟9)～12)表明若有選擇序列fk屬于λ1[2],活動(dòng)b屬于fk,且b是選擇開(kāi)始活動(dòng),記錄b出現(xiàn)次數(shù),同時(shí)切分子跡λ1[2]為λ2;步驟13)遍歷循環(huán)序列集合;步驟14)～16)表明若有循環(huán)序列sm屬于λ2[2],活動(dòng)c屬于sm,且c是循環(huán)結(jié)束活動(dòng),記錄c出現(xiàn)次數(shù);步驟17)、18)得到A?s;步驟19)、20)得到并返回Llc→l。

3 循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)過(guò)程模型修復(fù)方法

對(duì)于循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu),不同循環(huán)次數(shù)和選擇分支執(zhí)行會(huì)影響第二個(gè)循環(huán)塊的執(zhí)行。在實(shí)際過(guò)程中,可能會(huì)發(fā)生循環(huán)結(jié)構(gòu)沒(méi)有執(zhí)行完就執(zhí)行選擇結(jié)構(gòu)、選擇塊的選擇分支交叉執(zhí)行等情況。此時(shí)跡中沒(méi)有包含完整循環(huán)活動(dòng),或跡中選擇活動(dòng)來(lái)自不同的選擇分支。本節(jié)給出含循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)過(guò)程模型修復(fù)算法,在確定過(guò)程模型中的偏差位置后,對(duì)循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)進(jìn)行修復(fù)。

3.1 偏差位置確定算法

本研究將循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)分為不同結(jié)構(gòu)分別確定偏差位置。步驟為:①判斷循環(huán)結(jié)構(gòu)是否存在偏差。若某循環(huán)結(jié)構(gòu)不存在循環(huán)前進(jìn)路徑[1]、循環(huán)活動(dòng)出現(xiàn)次數(shù)不同且出現(xiàn)次數(shù)大于1,則確定循環(huán)結(jié)構(gòu)存在偏差;②判斷選擇結(jié)構(gòu)是否存在偏差。若某跡中選擇活動(dòng)來(lái)自不同的選擇分支,說(shuō)明選擇結(jié)構(gòu)存在偏差;③通過(guò)關(guān)聯(lián)規(guī)則判定原過(guò)程模型的間接依賴關(guān)系是否正確,若存在錯(cuò)誤,則利用關(guān)聯(lián)規(guī)則進(jìn)行改進(jìn)。

定理1若a∈SLA是一個(gè)沒(méi)有循環(huán)前進(jìn)路徑的循環(huán)結(jié)構(gòu)中的循環(huán)活動(dòng),且存在某個(gè)跡有num(a,σ)>num(a#,σ)>1,則偏差位置在循環(huán)結(jié)構(gòu)且a為偏差變遷。

證明：循環(huán)活動(dòng)a有num(a,σ)>1,即在某跡中出現(xiàn)次數(shù)大于1,說(shuō)明循環(huán)體執(zhí)行了多次,同時(shí)num(a, σ)>num(a#,σ),a的出現(xiàn)次數(shù)大于a的后繼變遷出現(xiàn)次數(shù),說(shuō)明a執(zhí)行完后沒(méi)有執(zhí)行a#,循環(huán)體沒(méi)有執(zhí)行完,確定循環(huán)結(jié)構(gòu)存在偏差。

定理2a、b∈SCA為兩個(gè)選擇活動(dòng),且a、b屬于不同的選擇分支,若存在某個(gè)跡同時(shí)含有a、b兩個(gè)選擇活動(dòng),則選擇結(jié)構(gòu)含有偏差,偏差變遷為a、b。

算法 4 偏差變遷確定算法 輸入:事件日志,循環(huán)活動(dòng) SLA ,選擇活動(dòng) SC A ; 輸出:偏差變遷 Dt l,Dt c . 1) Dt l,Dt c ← ? 2) For (i = 1,σi ∈ L;i + +;i ≤| L | ) do 3) if (a,a # ∈SLA ∧ num(a,σ) > num(a # ,σ) > 1) then 4) Dt l ← a 5) if (b,c ∈SCA ∧ b ∈SCBi ∧ c ∈SCBj) then 6) Dt c ← b,c 7) return Dt l,Dt c

證明：a、b∈SCA為兩個(gè)選擇活動(dòng),且a、b選擇分支不同,說(shuō)明a和b不能同時(shí)出現(xiàn)在一個(gè)跡中,因?yàn)檫x擇結(jié)構(gòu)的每次執(zhí)行只會(huì)執(zhí)行一個(gè)選擇分支,若存在某個(gè)跡同時(shí)含有a、b兩個(gè)選擇活動(dòng),說(shuō)明a、b所屬的選擇分支同時(shí)混合執(zhí)行,確定選擇結(jié)構(gòu)含有偏差。

算法4為偏差變遷確定算法。步驟1)初始化偏差變遷Dtl、Dtc;步驟2)遍歷日志;步驟3)～4)表明若活動(dòng)a,a#屬于循環(huán)活動(dòng)SLA,并且a在跡中出現(xiàn)次數(shù)大于a#在跡中出現(xiàn)次數(shù)大于1,則a為循環(huán)偏差變遷;步驟5)～6)表明若活動(dòng)b、c屬于選擇活動(dòng)SCA,b和c屬于不同選擇分支,則b、c為選擇偏差變遷;步驟7)返回偏差變遷。

3.2 循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)過(guò)程模型修復(fù)方法

算法5為循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)過(guò)程模型修復(fù)算法。步驟1)初始化LPN′;步驟2)根據(jù)算法4找到偏差變遷Dtl,Dtc;步驟3)～9)表明若存在循環(huán)偏差變遷Dtk,遍歷Dtl,確定偏差位置DP=(ti,po),其中ti=Dtk,po=?Dtk;步驟10)～16)表明若存在選擇偏差變遷Dti和Dtj,同時(shí)Dti不是選擇結(jié)束活動(dòng),Dtj不是選擇開(kāi)始活動(dòng),確定偏差位置DP=(ti,po),其中ti=Dti,po=?Dtj;步驟17)返回LPN′。

例3L1={σ1,σ2,σ3,σ4}={〈a,b,c,d,e,g,j,l〉, 〈a,b,c,b,c,b,d,e,h,i,j,k,j,k,j,k,j,l〉, 〈a,b,c,b,c,d,e,g,i,j,k,j,l〉〈a,b,c,b,c,b,c,d,f,h,i,j,k,j,k,j,l〉}。在過(guò)程模型NS2中,循環(huán)活動(dòng)為{b,c,j,k},選擇活動(dòng)為{e,f,g,h}。對(duì)于跡σ2,包含活動(dòng)b和c的循環(huán)塊中b的發(fā)生次數(shù)比c的發(fā)生次數(shù)多并且兩個(gè)活動(dòng)發(fā)生了多次,說(shuō)明循環(huán)結(jié)構(gòu)發(fā)生偏差。根據(jù)算法4確定偏差變遷為b,b的前集庫(kù)所為p2,根據(jù)算法5確定偏差位置DP=(b,p2)。添加一條從偏差變遷b到前集庫(kù)所p2的弧,修改b為邏輯輸出變遷,O(b)=p2?p3。跡σ2中的選擇活動(dòng)來(lái)自兩個(gè)不同的選擇分支,根據(jù)算法4確定偏差變遷為e和h,e的后集庫(kù)所為p5,h的前集庫(kù)所為p6。因?yàn)閔為選擇結(jié)束活動(dòng),根據(jù)算法5確定偏差位置DP=(e,p6), 添加一條從偏差變遷e到前集庫(kù)所p6的弧,修改e為邏輯輸出變遷,O(e)=p5?p6,得到圖3。Fahland方法添加了一個(gè)重復(fù)變遷,兩個(gè)不可見(jiàn)變遷和六條弧重放L1中的跡,如圖4。相對(duì)于只添加了兩條弧的圖3,Fahland方法比較復(fù)雜,并且不能表示過(guò)程模型不同結(jié)構(gòu)間的間接依賴關(guān)系。

圖3 基于邏輯Petri網(wǎng)的過(guò)程模型修復(fù)方法修復(fù)的模型

4 模擬實(shí)驗(yàn)

本研究選用Fahland方法進(jìn)行對(duì)比實(shí)驗(yàn),評(píng)估提出方法的正確性和有效性?；谶壿婸etri網(wǎng)的模型修復(fù)采用手工模擬方式,Fahland方法已在過(guò)程挖掘工具Prom6.6(http://www.promtools.org/prom6/)中實(shí)現(xiàn)。

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

以建筑公司工程項(xiàng)目實(shí)施過(guò)程為例,如圖5所示。建筑公司首先投標(biāo),中標(biāo)后監(jiān)理單位對(duì)施工方案進(jìn)行專業(yè)評(píng)審,如果評(píng)審不通過(guò)需要對(duì)施工方案進(jìn)行修改,重新確定施工方案。確定方案后需要準(zhǔn)備施工材料,建筑公司有兩種方案選擇材料公司:競(jìng)爭(zhēng)性談判或者招標(biāo),談判可直接確定材料公司并確定材料,招標(biāo)則要實(shí)地考察材料后才能確定材料。確定施工材料后要對(duì)材料送檢后施工,施工時(shí)要定期質(zhì)檢,最后完成工程項(xiàng)目。通過(guò)算法3可以發(fā)現(xiàn)日志中存在間接依賴關(guān)系,比如在修改方案、確定方案發(fā)生一次后,選擇競(jìng)爭(zhēng)性談判確定材料公司可以使施工質(zhì)檢階段執(zhí)行3次等,故可以確定此模型為含循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)過(guò)程模型。

圖5 建筑公司工程項(xiàng)目實(shí)施過(guò)程模型

實(shí)際過(guò)程可能會(huì)出現(xiàn)一些情況:對(duì)施工方案進(jìn)行修改,修改完成后不需要再進(jìn)行評(píng)審、經(jīng)過(guò)競(jìng)爭(zhēng)性談判選擇的材料公司依舊需要實(shí)地考察等。此時(shí)原始模型不能滿足這些情況,需要修復(fù)模型。從某建筑公司系統(tǒng)中獲取10組事件日志L1～L10,如表1所示(可以通過(guò)鏈接https://www.aliyundrive.com/s/BWaeSsq1zQv獲取)。本研究基于這10組事件日志進(jìn)行模型修復(fù)。

表1 事件日志信息

4.2 模型修復(fù)實(shí)驗(yàn)

通過(guò)與Fahland方法對(duì)比,驗(yàn)證本研究方法的合理性和正確性。圖6為利用Fahland方法修復(fù)后的模型,比圖5增加了1個(gè)重復(fù)變遷、2個(gè)不可見(jiàn)變遷和6條流關(guān)系?；谶壿婸etri網(wǎng)的修復(fù)方法如圖7所示,比圖5增加了2條弧和2個(gè)邏輯函數(shù),同時(shí)根據(jù)關(guān)聯(lián)規(guī)則添加了新的間接依賴關(guān)系。

圖6 基于Fahland方法修復(fù)的模型

圖7 基于邏輯Petri網(wǎng)的過(guò)程模型修復(fù)方法修復(fù)的模型

4.3 模型分析

本節(jié)從擬合度、精確度、簡(jiǎn)潔度三方面對(duì)兩種修復(fù)方法得到的模型進(jìn)行分析。擬合度用于確保事件日志中行為的發(fā)生,模型的擬合度越高,說(shuō)明模型重復(fù)事件日志的能力越強(qiáng),模型的質(zhì)量越好;精確度是指過(guò)程模型不會(huì)發(fā)生除事件日志外其他行為的能力,模型的精確度越高,模型生成外部事件日志的跡就越少,模型的質(zhì)量也越好;簡(jiǎn)潔度是用簡(jiǎn)單的模型重演日志中所有跡的能力,簡(jiǎn)潔度太低會(huì)影響模型的可讀性。邏輯Petri網(wǎng)模型擬合度、精確度的計(jì)算方法見(jiàn)文獻(xiàn)[18]。

不同日志情況下,兩種方法修復(fù)的模型擬合度、精確度分別如圖8、圖9所示。相較于Fahland方法,本研究方法修復(fù)后模型的擬合度、精確度更高,修復(fù)效果更好。Fahland 方法在修復(fù)過(guò)程模型時(shí)增加了自循環(huán),導(dǎo)致過(guò)程模型產(chǎn)生許多事件日志之外的跡,使得修復(fù)后的模型擬合度、精確度降低。本研究基于邏輯Petri網(wǎng),針對(duì)循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu),提出修復(fù)方法,在修復(fù)循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)的同時(shí)可以表達(dá)結(jié)構(gòu)間的間接依賴關(guān)系,提高了修復(fù)后模型的擬合度和精確度。

圖8 擬合度變化曲線

圖9 精確度變化曲線

從修復(fù)模型的庫(kù)所、變遷、流關(guān)系上對(duì)兩種方法進(jìn)行簡(jiǎn)潔度對(duì)比,結(jié)果如表2所示,可以看出,本研究方法得到的模型簡(jiǎn)潔度更高。與Fahland方法相比,本研究方法提高了模型的簡(jiǎn)潔度,同時(shí)也表示了不同結(jié)構(gòu)之間的間接依賴關(guān)系。

表2 模型簡(jiǎn)潔度比較

5 結(jié)論

本研究針對(duì)循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)過(guò)程模型提出一種新的模型修復(fù)方法,將循環(huán)選擇驅(qū)動(dòng)循環(huán)結(jié)構(gòu)分成三部分分別進(jìn)行修復(fù)。由于不同結(jié)構(gòu)確定偏差的方式不同,提出兩個(gè)定理判斷各個(gè)結(jié)構(gòu)是否存在偏差。在使用確定偏差變遷算法得到循環(huán)偏差變遷和選擇偏差變遷后,在不添加不可見(jiàn)變遷和重復(fù)變遷的情況下,使用提出的修復(fù)算法進(jìn)行模型修復(fù)。實(shí)驗(yàn)表明,本研究方法不僅能夠保持原始結(jié)構(gòu),而且能夠正確描述各結(jié)構(gòu)之間的間接依賴關(guān)系。下一步將研究更加復(fù)雜的組合結(jié)構(gòu),進(jìn)行模型修復(fù)并研究之間的間接依賴關(guān)系。