基于邏輯Petri網的循環選擇驅動循環結構過程模型修復方法

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

(山東科技大學 計算機科學與工程學院,山東 青島 266590)

如今多數企業使用信息系統管理業務流程,而過程挖掘主要從信息系統中抽取信息[1]。過程挖掘可分為過程發現、一致性檢查和過程增強等階段[2]。過程發現通過算法從事件日志中挖掘模型;一致性檢查是將日志與模型進行比對[3-4],若出現偏差說明過程模型不能反映現實,需要對過程模型進行修復;過程增強使用現有事件日志對原始模型進行改進或擴展,以適應更多事件日志。

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

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

1 基本概念

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

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

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

定義3(Petri網)[12-14]PN=(P,T;F,M)為一個Petri網,當且僅當:

1)N=(P,T;F)為一個網,P為庫所集,T為變遷集;

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

3)M:P→N為一個標識。

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

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

1)PN=(P,T;F,M)為一個Petri網;

2)a:T→A∪{τ}是變遷到活動的映射函數,τ為不可見變遷;

3)mi=[pi]∈Mi是初始標識,mf=[po]∈Mf是終止標識。

圖1為一個基于Petri網的過程模型實例。

圖1 基于Petri網的過程模型實例

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

1)a∈A∪{τ}為一棵過程樹;

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

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

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

1)P是有限庫所集;

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

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

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

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

6)M:P→N為一個標識函數。

2 循環選擇及其驅動循環序列確定算法

本部分介紹循環選擇驅動循環結構,并劃分為循環結構和選擇結構分別進行分析。圖2為一個循環選擇驅動循環結構過程模型,使用關聯規則表示不同結構之間的間接依賴關系,比如關聯規則〈b,c〉2∧〈e,g〉1?〈j,k〉1表示循環活動b、c發生兩次后執行e、g選擇分支,則第二個循環塊執行一次循環。

圖2 循環選擇驅動循環結構過程模型

2.1 循環序列確定算法

對循環選擇驅動循環結構進行修復,首先要找到模型中所有循環結構。假設每個過程模型都有一個唯一的過程樹,過程樹中每個操作符代表模型的一個結構。例如在模型中有一個循環結構,則相應過程樹節點n=“”。為方便起見,Fi(n)表示n節點處第i個子樹的所有葉節點。

定義8(活動發生次數) σ∈L為日志中的一個跡,s∈σ為一個序列,對于任意活動a∈σ,num(a,σ)表示活動a在跡中出現的次數,num(s,σ)表示序列s在跡中出現的次數。

定義9(循環活動) σ∈L為日志中的跡,a∈σ為一個活動,若num(a,σ)>1,則a為循環活動。

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

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

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

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

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

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

Ls為所有循環序列集合。

定義12(循環開始活動和循環結束活動)SLA為循環活動集合,s∈SLA*為一個循環序列,循環開始活動為SLA_s,循環結束活動為SLA_e,其中:

算法 1 循環序列確定算法 輸入:事件日志 L 輸出:循環序列 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為循環序列確定算法。步驟1)初始化循環序列;步驟2)、3)遍歷日志和跡;步驟4)～5)表明若跡σi中的活動aj出現次數>1,則活動aj為循環活動;步驟6)～8)遍歷循環活動集合,添加循環活動到循環序列s中;步驟9)～12)表示若循環活動a,b為順序關系且活動b為s的第一個活動,把活動a添加到s中且在活動b之前;步驟13)～15)表示若循環活動a,b為順序關系且活動a為s的最后一個活動,則把活動b添加到s中且在活動a之后;步驟16)、17)把得到的循環序列s添加到循環序列集合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}。根據算法1,SLA=SLA-b={c,d,e},s=〈b〉,因為b>Lc,有s=s+c=〈b,c〉,SLA=SLA-c={d,e},同理得到s=〈b,c,d,e〉。

2.2 選擇序列確定算法

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

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

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

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

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

Lf為所有選擇序列集合。

定義15(選擇開始活動和選擇結束活動)SCA為選擇活動集合,f∈SCA*為一個選擇序列,選擇開始活動為SCA_s,選擇結束活動為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)為一個過程模型,PT為對應過程樹,CB=(t1,t2,…,tn)是一個選擇分支元組,其中:

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,選擇活動集合SCA;步驟2)遍歷日志;步驟3)～4)表明若活動a屬于L,但不屬于跡σi,則a為選擇活動;步驟5)～9)遍歷SCA,若活動a,b為順序關系且a不屬于SCA,b是選擇活動,則添加b到f;步驟10)～12)表示若活動a,b為順序關系且a屬于SCA,b不是選擇活動,則添加a到f;步驟13)～14)把f添加到選擇序列集合Lf中并返回Lf。

例2事件日志L={σ1,σ2}={〈a,b,d,f〉,〈a,c,e,f〉},選擇活動集合SCA={b,c,d,e}。對于σ1,有a>Lb且b∈SCA,a?SCA。根據算法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 循環選擇驅動循環序列確定算法

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

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

3 循環選擇驅動循環結構過程模型修復方法

對于循環選擇驅動循環結構,不同循環次數和選擇分支執行會影響第二個循環塊的執行。在實際過程中,可能會發生循環結構沒有執行完就執行選擇結構、選擇塊的選擇分支交叉執行等情況。此時跡中沒有包含完整循環活動,或跡中選擇活動來自不同的選擇分支。本節給出含循環選擇驅動循環結構過程模型修復算法,在確定過程模型中的偏差位置后,對循環選擇驅動循環結構進行修復。

3.1 偏差位置確定算法

本研究將循環選擇驅動循環結構分為不同結構分別確定偏差位置。步驟為:①判斷循環結構是否存在偏差。若某循環結構不存在循環前進路徑[1]、循環活動出現次數不同且出現次數大于1,則確定循環結構存在偏差;②判斷選擇結構是否存在偏差。若某跡中選擇活動來自不同的選擇分支,說明選擇結構存在偏差;③通過關聯規則判定原過程模型的間接依賴關系是否正確,若存在錯誤,則利用關聯規則進行改進。

定理1若a∈SLA是一個沒有循環前進路徑的循環結構中的循環活動,且存在某個跡有num(a,σ)>num(a#,σ)>1,則偏差位置在循環結構且a為偏差變遷。

證明：循環活動a有num(a,σ)>1,即在某跡中出現次數大于1,說明循環體執行了多次,同時num(a, σ)>num(a#,σ),a的出現次數大于a的后繼變遷出現次數,說明a執行完后沒有執行a#,循環體沒有執行完,確定循環結構存在偏差。

定理2a、b∈SCA為兩個選擇活動,且a、b屬于不同的選擇分支,若存在某個跡同時含有a、b兩個選擇活動,則選擇結構含有偏差,偏差變遷為a、b。

算法 4 偏差變遷確定算法 輸入:事件日志,循環活動 SLA ,選擇活動 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為兩個選擇活動,且a、b選擇分支不同,說明a和b不能同時出現在一個跡中,因為選擇結構的每次執行只會執行一個選擇分支,若存在某個跡同時含有a、b兩個選擇活動,說明a、b所屬的選擇分支同時混合執行,確定選擇結構含有偏差。

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

3.2 循環選擇驅動循環結構過程模型修復方法

算法5為循環選擇驅動循環結構過程模型修復算法。步驟1)初始化LPN′;步驟2)根據算法4找到偏差變遷Dtl,Dtc;步驟3)～9)表明若存在循環偏差變遷Dtk,遍歷Dtl,確定偏差位置DP=(ti,po),其中ti=Dtk,po=?Dtk;步驟10)～16)表明若存在選擇偏差變遷Dti和Dtj,同時Dti不是選擇結束活動,Dtj不是選擇開始活動,確定偏差位置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〉}。在過程模型NS2中,循環活動為{b,c,j,k},選擇活動為{e,f,g,h}。對于跡σ2,包含活動b和c的循環塊中b的發生次數比c的發生次數多并且兩個活動發生了多次,說明循環結構發生偏差。根據算法4確定偏差變遷為b,b的前集庫所為p2,根據算法5確定偏差位置DP=(b,p2)。添加一條從偏差變遷b到前集庫所p2的弧,修改b為邏輯輸出變遷,O(b)=p2?p3。跡σ2中的選擇活動來自兩個不同的選擇分支,根據算法4確定偏差變遷為e和h,e的后集庫所為p5,h的前集庫所為p6。因為h為選擇結束活動,根據算法5確定偏差位置DP=(e,p6), 添加一條從偏差變遷e到前集庫所p6的弧,修改e為邏輯輸出變遷,O(e)=p5?p6,得到圖3。Fahland方法添加了一個重復變遷,兩個不可見變遷和六條弧重放L1中的跡,如圖4。相對于只添加了兩條弧的圖3,Fahland方法比較復雜,并且不能表示過程模型不同結構間的間接依賴關系。

圖3 基于邏輯Petri網的過程模型修復方法修復的模型

4 模擬實驗

本研究選用Fahland方法進行對比實驗,評估提出方法的正確性和有效性?；谶壿婸etri網的模型修復采用手工模擬方式,Fahland方法已在過程挖掘工具Prom6.6(http://www.promtools.org/prom6/)中實現。

4.1 實驗數據與模型

以建筑公司工程項目實施過程為例,如圖5所示。建筑公司首先投標,中標后監理單位對施工方案進行專業評審,如果評審不通過需要對施工方案進行修改,重新確定施工方案。確定方案后需要準備施工材料,建筑公司有兩種方案選擇材料公司:競爭性談判或者招標,談判可直接確定材料公司并確定材料,招標則要實地考察材料后才能確定材料。確定施工材料后要對材料送檢后施工,施工時要定期質檢,最后完成工程項目。通過算法3可以發現日志中存在間接依賴關系,比如在修改方案、確定方案發生一次后,選擇競爭性談判確定材料公司可以使施工質檢階段執行3次等,故可以確定此模型為含循環選擇驅動循環結構過程模型。

圖5 建筑公司工程項目實施過程模型

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

表1 事件日志信息

4.2 模型修復實驗

通過與Fahland方法對比,驗證本研究方法的合理性和正確性。圖6為利用Fahland方法修復后的模型,比圖5增加了1個重復變遷、2個不可見變遷和6條流關系?；谶壿婸etri網的修復方法如圖7所示,比圖5增加了2條弧和2個邏輯函數,同時根據關聯規則添加了新的間接依賴關系。

圖6 基于Fahland方法修復的模型

圖7 基于邏輯Petri網的過程模型修復方法修復的模型

4.3 模型分析

本節從擬合度、精確度、簡潔度三方面對兩種修復方法得到的模型進行分析。擬合度用于確保事件日志中行為的發生,模型的擬合度越高,說明模型重復事件日志的能力越強,模型的質量越好;精確度是指過程模型不會發生除事件日志外其他行為的能力,模型的精確度越高,模型生成外部事件日志的跡就越少,模型的質量也越好;簡潔度是用簡單的模型重演日志中所有跡的能力,簡潔度太低會影響模型的可讀性。邏輯Petri網模型擬合度、精確度的計算方法見文獻[18]。

不同日志情況下,兩種方法修復的模型擬合度、精確度分別如圖8、圖9所示。相較于Fahland方法,本研究方法修復后模型的擬合度、精確度更高,修復效果更好。Fahland 方法在修復過程模型時增加了自循環,導致過程模型產生許多事件日志之外的跡,使得修復后的模型擬合度、精確度降低。本研究基于邏輯Petri網,針對循環選擇驅動循環結構,提出修復方法,在修復循環選擇驅動循環結構的同時可以表達結構間的間接依賴關系,提高了修復后模型的擬合度和精確度。

圖8 擬合度變化曲線

圖9 精確度變化曲線

從修復模型的庫所、變遷、流關系上對兩種方法進行簡潔度對比,結果如表2所示,可以看出,本研究方法得到的模型簡潔度更高。與Fahland方法相比,本研究方法提高了模型的簡潔度,同時也表示了不同結構之間的間接依賴關系。

表2 模型簡潔度比較

5 結論

本研究針對循環選擇驅動循環結構過程模型提出一種新的模型修復方法,將循環選擇驅動循環結構分成三部分分別進行修復。由于不同結構確定偏差的方式不同,提出兩個定理判斷各個結構是否存在偏差。在使用確定偏差變遷算法得到循環偏差變遷和選擇偏差變遷后,在不添加不可見變遷和重復變遷的情況下,使用提出的修復算法進行模型修復。實驗表明,本研究方法不僅能夠保持原始結構,而且能夠正確描述各結構之間的間接依賴關系。下一步將研究更加復雜的組合結構,進行模型修復并研究之間的間接依賴關系。