基于擴(kuò)展足跡矩陣的一致性檢測

，

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

近年來，過程挖掘技術(shù)快速發(fā)展，很多企業(yè)已將過程挖掘功能添加到其產(chǎn)品中。過程挖掘主要包括三個方面：過程發(fā)現(xiàn)、一致性檢測和過程增強。過程發(fā)現(xiàn)是根據(jù)事件日志生成模型，并不使用任何先驗信息；一致性檢測是將一個已知的過程模型與這個模型的事件日志進(jìn)行對比；過程增強則是使用相關(guān)事件日志來擴(kuò)展或者改進(jìn)現(xiàn)有過程模型[1]。

在系統(tǒng)和實際過程中過程模型和事件日志經(jīng)常有不匹配的情況，造成這種情況的原因有多種。比如，系統(tǒng)不是為特定企業(yè)開發(fā)的、外部環(huán)境影響、業(yè)務(wù)過程變化迅速或者過程中不同利益相關(guān)人員之間的需求可能出現(xiàn)沖突等。一致性檢測的目標(biāo)是找到過程模型和事件日志之間的差異，確保系統(tǒng)和實際業(yè)務(wù)過程保持良好的合規(guī)性[2]。通過分析實際過程和診斷差異，可以從中獲得如何改進(jìn)模型的支持。

文獻(xiàn)[1]中針對一致性檢測提出了托肯重演、對比足跡等方法。托肯重演[1-2]是利用日志在模型上進(jìn)行重演，記錄所有丟失的和遺留的托肯來計算擬合度。對比足跡則是根據(jù)基于日志的次序關(guān)系[1]生成足跡，也就是表示因果依賴關(guān)系的矩陣來展示事件日志和過程模型的特征，然后通過對比得到它們之間的不同，但該方法沒有給出如何尋找偏差位置。基于α算法生成的次序關(guān)系也并不能涵蓋所有事件之間的依賴關(guān)系，因此在進(jìn)行一致性檢測的時候，不能準(zhǔn)確的找出所有偏差和識別偏差域。文獻(xiàn)[3]通過生成校準(zhǔn)[4-6]并添加基于日志動作位置的定義，進(jìn)行一致性檢測與后續(xù)的模型修正。然而這種方法只能得到大概的偏差位置，還需要進(jìn)一步精確。文獻(xiàn)[7]中提出校準(zhǔn)動作與過程模型的映射，通過校準(zhǔn)動作映射提供的信息正確識別出錯誤模型中的問題，也是要利用校準(zhǔn)進(jìn)行一致性檢測。文獻(xiàn)[8]提出了一種新型日志Token Log的符合性檢查方法，使用日志內(nèi)容檢查模型結(jié)構(gòu)正確性與使用模型結(jié)構(gòu)檢查日志內(nèi)容完整性標(biāo)準(zhǔn)，但是需要進(jìn)行雙向檢查。因此，本文利用矩陣[9]的概念提出一種基于擴(kuò)展足跡矩陣的一致性檢測方法，不需要利用校準(zhǔn)，而是擴(kuò)展活動間的依賴關(guān)系以得到日志和模型的擴(kuò)展足跡矩陣，進(jìn)而更精確地識別偏差位置。

1 基本概念

Petri網(wǎng)是一種用于系統(tǒng)分析與建模的工具，被廣泛應(yīng)用于多個領(lǐng)域，特別便于描述系統(tǒng)的順序、并發(fā)、沖突以及同步等關(guān)系[10]，既能描述系統(tǒng)的結(jié)構(gòu)，又能模擬系統(tǒng)的運行。本節(jié)簡要介紹Petri網(wǎng)的基本定義及基于日志的次序關(guān)系[1]相關(guān)概念。

定義1(跡，事件日志[11-12]) 設(shè)A是所有活動的集合，A?A。若活動序列σ∈A*，A*表示集合A上有限序列的集合，則稱σ是一條跡。若?L∈B(A*)是跡的一個多重集，稱L為一個事件日志。用&(σ)表示跡σ中所有活動構(gòu)成的集合。

定義2(前集，后集[11-13]) 設(shè)N= (P,T;F)為一個網(wǎng)。對于?x∈P∪T，令

·x={y|y∈P∪T∧(y,x)∈F}，

x·={y|y∈P∪T∧(x,y)∈F}，

稱·x為x的前集或輸入集，x·為x的后集或輸出集。

定義3(Petri網(wǎng)[11-13]) 一個四元組PN=(P,T;F,M)稱作Petri網(wǎng)，當(dāng)且僅當(dāng)

1)N= (P,T;F)為一個網(wǎng)；

2) 映射M:P→{0,1,2,…}為網(wǎng)N的一個標(biāo)識(marking)。

定義4(變遷發(fā)生規(guī)則) 一個四元組PN= (P,T;F,M)是一個標(biāo)識Petri網(wǎng)，具有下列變遷發(fā)生規(guī)則：

1) 變遷t∈T在標(biāo)識M有發(fā)生權(quán)或稱為使能的(enabled)，當(dāng)且僅當(dāng)對?p∈P：p∈·t：M(s) ≥ 1，記作M[t>。

2) 若M[t>，則在標(biāo)識M下發(fā)生變遷t后得到一個新的標(biāo)識M′，記作M[t>M′，且對?p∈P，

從M可達(dá)的一切標(biāo)識的集合記為R(M)，約定M∈R(M)。

定義5(基于日志的次序關(guān)系[1]) 使用L表示一個基于A的事件日志，即L∈B(A*)。令a，b∈A，那么：

1)a>Lb當(dāng)且僅當(dāng)存在一個軌跡σ=,i∈{1,…,n-1}使得σ∈L,ti=a并且ti+1=b;

2)a→Lb當(dāng)且僅當(dāng)a>Lb并且b≯La;

3)a#Lb當(dāng)且僅當(dāng)a≯Lb并且b≯La;

4)a‖Lb當(dāng)且僅當(dāng)a>Lb并且b>La。

2 擴(kuò)展足跡矩陣

過程模型可以通過事件日志挖掘出來，并越來越傾向于對真實生活中自然語言的處理和挖掘[14-15]。給定事件日志和過程模型，則可以根據(jù)兩者之間的擴(kuò)展足跡來對比它們之間的差異。文獻(xiàn)[1]基于α算法提出的基于日志的次序關(guān)系，雖然可以將基本的活動間的關(guān)系表示出來，但是對于不是直接跟隨關(guān)系或者不是直接因果關(guān)系的活動無法表示兩者之間深層次的關(guān)系，這就導(dǎo)致事件日志和過程模型在進(jìn)行一致性檢測的時候很容易將活動之間的關(guān)系漏掉，以至于檢測出的事件日志和過程模型之間的偏差位置并不精確。因此，本節(jié)針對此問題進(jìn)行了改進(jìn)，提出了基于日志的擴(kuò)展次序關(guān)系以及擴(kuò)展足跡矩陣的相關(guān)定義，擴(kuò)展后可以將事件日志中活動之間的關(guān)系更完備的表達(dá)出來。在定義6中，擴(kuò)展了間接因果關(guān)系和并行關(guān)系。下面首先給出基于日志的擴(kuò)展次序關(guān)系。

定義6(基于日志的擴(kuò)展次序關(guān)系) 設(shè)L表示一個基于A的事件日志，即L∈B(A*)。σ∈L是日志中的一條跡，a，b∈&(σ)，那么：

1) 直接跟隨關(guān)系>：a>b當(dāng)且僅當(dāng)存在一個軌跡，σ=，i∈{1,…,n-1}使得σ∈L，ti=a并且ti+1=b；

2) 直接因果關(guān)系→：a→b當(dāng)且僅當(dāng)任意a,b∈&(σ)，a>b并且b≯a;

3) 間接因果關(guān)系→i：a→ib當(dāng)且僅當(dāng)存在a,t1,…,tn,b∈&(σ)，a≯b且b≯a，有a→t1→…→tn→b;

4) 并行關(guān)系‖：a‖b當(dāng)且僅當(dāng)存在σ1,σ2∈L，a，b∈A，對于a，b∈&(σ1)：a>b或者a>…>b，并且對于a，b∈&(σ2)：b>a或者b>…>a。

5) 排他關(guān)系：a#b當(dāng)且僅當(dāng)任意a,b∈&(σ)，a≯b并且b≯a。

>L關(guān)系包含了日志L中所有緊鄰的活動對，是關(guān)于日志L中所有跡的完備的直接跟隨關(guān)系。例如日志L= [，，]，在軌跡中b緊跟在a之后，所以有a>b。→L關(guān)系包含了日志L中全部具有直接因果關(guān)系的活動對。例如，在日志L中b直接跟隨于a，但a不直接跟隨于b，所以有a→b。→i L關(guān)系包含了日志L中全部具有間接因果關(guān)系的活動對。例如，在日志L中a…d，但a不直接跟隨于d，所以有a→id。由于原次序關(guān)系并沒有深層次的挖掘活動間的關(guān)系，造成在進(jìn)行一致性檢測的時候很多偏差識別不出來。所以本文在添加間接因果關(guān)系之后，可以根據(jù)日志和模型間直接和間接因果關(guān)系的變化推導(dǎo)出偏差位置，比如一個新活動的增加勢必會使原本模型中的直接因果關(guān)系變成間接因果關(guān)系。‖L表示日志L中所有具有并發(fā)關(guān)系的活動對。例如，在日志L中，跡和中有b>c且c>b,即b和c互相存在直接跟隨關(guān)系的情況，所以有b‖c。在并行關(guān)系中并非只有a>b并且b>a的情況，還可能存在兩者之間不是直接跟隨關(guān)系，而是并不存在因果依賴關(guān)系但是必定都在同一條跡中發(fā)生的情況，所以這種定義方式并不嚴(yán)謹(jǐn)。因此，本文根據(jù)存在并行關(guān)系的兩個活動的所有可能情況作了擴(kuò)展。#L表示日志L中所有具有排他關(guān)系的活動對的集合。例如，在日志L的所有跡中，b，e都不能同時發(fā)生，所以有b#e。

對于?a，b∈A，有且只有一種確定的關(guān)系。在日志L中，一定有a→b，a→ib，a‖b或者a#b。也就是說，任一活動對一定滿足這4種關(guān)系中的一種，且任意兩個活動之間的依賴關(guān)系都是確定的。因此可以用一個擴(kuò)展足跡矩陣來描述日志的足跡[1]，即表示活動間依賴關(guān)系的矩陣。下面給出基于日志的擴(kuò)展足跡矩陣和基于模型的擴(kuò)展足跡矩陣的相關(guān)定義。

定義7(基于日志的擴(kuò)展足跡矩陣) 設(shè)L是一個基于A的事件日志，即L∈B(A*)。LEFM=L[n][n]是一個基于日志的擴(kuò)展足跡矩陣，n=|A|。|A|表示集合A中所有元素的個數(shù)。對于li，lj∈A，i∈{1,…,n-1}，j∈{i+1,…,n}，L[i][j]表示活動li，lj之間基于日志的擴(kuò)展次序關(guān)系。

定義8(基于模型的擴(kuò)展足跡矩陣) 設(shè)PN= (P,T;F,M)是一個Petri網(wǎng)。MEFM=M[n][n]是一個基于模型的擴(kuò)展足跡矩陣。對于mi，mj∈T，i∈{1,…,n-1}，j∈{i+1,…,n}，M[i][j]表示mi，mj之間基于模型PN重演記錄的執(zhí)行序列的擴(kuò)展次序關(guān)系。

例1圖1展示了一個用Petri網(wǎng)表示的過程模型N1，這個模型描述了一家航空公司處理索賠申請的過程。該過程從處理一個申請開始，為了方便，用標(biāo)簽為a(register request)的變遷表示。當(dāng)申請很復(fù)雜或可疑時，執(zhí)行變遷b(examine thoroughly)，當(dāng)申請比較簡單時，只需要執(zhí)行非正式的檢查c(examine casually)即可。這兩個變遷是選擇關(guān)系，即一方執(zhí)行都不會再執(zhí)行另一方。變遷d(check ticket)代表一項查看顧客是否由自個提出申請的行政檢查，變遷e(decide)代表著可能做出的決策。最后支付所申請的賠償g(pay compensation)或者拒絕賠償h(reject request)，或者需要更多的檢查將會發(fā)生變遷f(reinitiate request)。對于變遷f發(fā)生的情況，整個過程將會重新回到選擇結(jié)構(gòu)(b，c)的位置繼續(xù)執(zhí)行。實際中整個過程可能會發(fā)生多次迭代，會在支付或者拒絕賠償后結(jié)束。

圖1 一個描述索賠申請?zhí)幚磉^程的Petri網(wǎng)N1

例2過程模型N1如圖1所示，日志L= {, , , , , }，日志L從實際流程中得到。下面列出基于日志的擴(kuò)展次序關(guān)系，并得出基于日志的擴(kuò)展足跡矩陣和基于模型的擴(kuò)展足跡矩陣。

日志L的6條跡中包含的所有的擴(kuò)展次序關(guān)系如下所示：

1) 直接跟隨關(guān)系>：

>σ1= {(a,c), (c,d), (d,e), (e,h)};

>σ2= {(a,b), (b,d), (d,e), (e,h)};

>σ3= {(a,d), (d,c), (c,e), (e,g)};

>σ4= {(a,d), (d,b), (b,e), (e,h)};

>σ5= {(a,c), (c,d), (d,e), (e,f), (f,b), (b,d), (d,e), (e,h)};

>σ6= {(a,b), (b,d), (d,e), (e,f), (f,d), (d,b), (b,e), (e,g)};

>L= {(a,b),(a,c),(a,d),(b,d),(b,e),(c,d),(c,e),(e,h),(e,g),(e,f),(f,b),(f,d)}

2) 直接因果關(guān)系→：

→L= {(a,b), (a,c), (a,d), (b,e), (c,e), (d,e), (e,g), (e,f), (e,h), (f,b), (f,d)};

3) 間接因果關(guān)系→i：

→i L= {(a,e), (a,g), (a,h), (a,f), (b,g), (b,h), (c,f), (c,g), (c,h), (d,g), (d,h), (f,g), (f,g)};

4) 排他關(guān)系#：

#L= {(b,c), (g,h)};

5) 并行關(guān)系‖：

‖L= {(b,d), (c,d)}

由此得到基于日志L的擴(kuò)展足跡矩陣如下：

abcdefgh

重演模型N1記錄執(zhí)行序列，產(chǎn)生的基于模型的擴(kuò)展足跡矩陣如下：

abcdefgh

通過得到的日志L的擴(kuò)展足跡矩陣和模型N1的擴(kuò)展足跡矩陣可以看出，事件日志中有些活動的依賴關(guān)系相比過程模型有了改變，下一節(jié)將通過對比兩者之間的變化識別出事件日志和過程模型之間的偏差位置。

3 一致性檢測

第2節(jié)中已經(jīng)得到了基于日志的擴(kuò)展足跡矩陣和基于模型的擴(kuò)展足跡矩陣，本節(jié)通過對比兩種擴(kuò)展足跡矩陣，并在此基礎(chǔ)上定義對比擴(kuò)展足跡矩陣的概念，通過求得的對比擴(kuò)展足跡矩陣，可以識別出事件日志和過程模型之間精確的偏差位置。

3.1 對比擴(kuò)展足跡矩陣

定義9(對比擴(kuò)展足跡矩陣) 設(shè)L是一個基于A的事件日志，即L∈B(A*)，PN= (P,T;F,M)是一個Petri網(wǎng)。LEFM=L[n][n]是一個基于日志的擴(kuò)展足跡矩陣，n=|A|。MEFM=M[n][n]是一個基于模型的擴(kuò)展足跡矩陣。CEFM=C[n][n]是一個對比擴(kuò)展足跡矩陣。對于li，lj∈A，i∈{1,…,n-1}，j∈{i+1,…,n}，C[i][j]表示擴(kuò)展足跡矩陣LEFM與MEFM中不一致的元素，C[i][j]=L[i][j]-M[i][j]。即活動li，lj之間在日志中并且不在模型中的依賴關(guān)系。

定義9中，對比擴(kuò)展足跡矩陣中保留了兩個擴(kuò)展足跡矩陣中不一致的元素，即模型中存在偏差的部分。下面給出對比擴(kuò)展足跡矩陣的算法。

算法1(對比擴(kuò)展足跡矩陣算法)

設(shè)LEFM=L[n][n]是一個基于日志的擴(kuò)展足跡矩陣，MEFM=M[n][n]是一個基于模型的擴(kuò)展足跡矩陣，CEFM=C[n][n]是一個對比擴(kuò)展足跡矩陣。

輸入：LEFM，MEFM

輸出：對比擴(kuò)展足跡矩陣CEFM

①L[i][j]表示日志的擴(kuò)展足跡矩陣LEFM中的元素，M[i][j]表示模型的擴(kuò)展足跡矩陣MEFM中的元素，C[i][j]用來存儲不一致元素，初始設(shè)為空。

② 根據(jù)定義9，逐步遍歷L[n][n]和M[n][n]，若L[i][j]=M[i][j]，跳過；

③ 若L[i][j]≠M[i][j]，更新矩陣CEFM，C[n][n]←C[n][n]∪{L[i][j]}；//將L[i][j]保存到矩陣CEFM中；

④ RETURNCEFM

例3過程模型N1如圖1所示，日志L= {, , , , , }，日志L從實際流程中得到。由例2，得出對比擴(kuò)展足跡矩陣。

abcdefgh

3.2 定位偏差位置

例4過程模型N1如圖1所示，日志L= {, , , , , }，日志L從實際流程中得到。通過例2、例3求得對比擴(kuò)展足跡矩陣，可以很清晰地看到：日志中變遷b(examine thoroughly)和c(examine casually)構(gòu)成的選擇結(jié)構(gòu)跟變遷d(check ticket)應(yīng)該是并行關(guān)系，但原模型中卻顯示的是因果關(guān)系。日志中b(examine thoroughly)，c(examine casually)，d(check ticket)與e(decide)是直接跟隨關(guān)系，而在原模型中錯誤的將b(examine thoroughly)，c(examine casually)與e(decide)表示成間接跟隨關(guān)系。因為b，c，d三個變遷結(jié)構(gòu)的改變，在日志中存在循環(huán)時，f(reinitiate request)與d(check ticket)的關(guān)系在模型中是間接因果關(guān)系，日志中是直接因果關(guān)系，說明實際返回變遷f與并行結(jié)構(gòu){(b,c)，d}是直接因果關(guān)系，之間存在兩條流關(guān)系直接相連。除此之外，日志和模型之間直接因果關(guān)系和間接因果關(guān)系的變化對于添加新活動的情況也能很好的識別出來。利用這些信息可以很準(zhǔn)確的對模型進(jìn)行修正。

圖2 圖1中的N1的偏差位置

4 結(jié)束語

一致性檢測是過程挖掘研究的重要內(nèi)容，本文提出了一種基于擴(kuò)展足跡矩陣的一致性檢測方法。具體工作是對已有的基于日志的次序關(guān)系進(jìn)行擴(kuò)展，得到基于日志的擴(kuò)展次序關(guān)系，進(jìn)而得到兩種擴(kuò)展足跡矩陣。最后對比兩個擴(kuò)展足跡矩陣之間的差異得到精確的偏差位置。本文所提出的方法不需要利用校準(zhǔn)，并且能夠更精確地識別偏差位置，尤其能夠更好地識別模型存在結(jié)構(gòu)錯誤的情況。下一步的工作是基于以上工作對模型中的偏差位置進(jìn)行修正，得到正確的過程模型。

[1]VAN DER AALST W M P.Process mining:Discovery,conformance and enhancement of business process[M].Berlin，Heidelberg：Springer,2011:64-162.

[2]VAN DER AALST W M P,ADRIANSYAH A,VAN DONGEN B.Replaying history on process models for conformance checking and performance analysis[J].WIREs Data Mining and Knowledge Discovery,2012,2(2):182-192.

[3]FAHLAND D,VAN DER AALST W M P.Model Repair：Aligningprocess models to reality[J].Information Systems,2015,47(1):220-243.

[4]WANG L,DU Y X,LIU W.Aligning observed and modeled behavior based on workflow decomposition[J].Enterprise Information Systems,2017,11(8):1207-1227.

[5]ADRIANSYAH A.Aligning observed and modeled behavior[D].Eindhoven:Technische Universiteit Eindhoven,2014:122-149.

[6]ADRIANSYAHA,MUNOZ-GAMA J,CARMONA J,et al.Alignment based precision checking[C]//Business Process Management Workshops.Berlin,Heidelberg:Springer,2013:137-149.

[7]王路,杜玉越.一種基于校準(zhǔn)的模型問題域識別方法[J].山東科技大學(xué)學(xué)報(自然科學(xué)版),2015,34(1):42-46.

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 (Natural Science),2015,34(1):42-46.

[8]李傳藝,葛季棟,胡海洋,等.一種基于Token Log的符合性檢查方法[J].軟件學(xué)報,2015,26(3):509-532.

LI Chuanyi,GE Jidong,HU Haiyang,et al.Method for conformance checking based on Token Log[J].Journal of Software,2015,26(3):509-532.

[9]SUN Y N,DU Y Y,LI M Z.A repair of workflow models based on mirroring matrices[J].International Journal of Parallel Programming,2016,45(4):1-20.

[10]蔣昌俊.Petri網(wǎng)的行為理論及應(yīng)用[M].北京:高等教育出版社,2003:19-26.

[11]SUN S,AKHIL K,JOHN Y.Merging workflows:A new perspective on connecting business processes[J].Decision Support Systems,2006,42(2):844-858.

[12]查海平,王建民,聞立杰.一種 Petri 網(wǎng)模型完備日志生成算法[J].系統(tǒng)仿真學(xué)報,2007,19(A01):271-274.

ZHA Haiping,WANG Jianmin,WEN Lijie.An algorithm of complete log generation for Petri net models[J].Journal of System Simulation,2007,19(A01):271-274.

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

[14]AALST W V D.Process mining:Overview and opportunities[J].ACM Transactions on Management Information Systems,2012,3(2):1-17.

[15]AALST W V D,DONGEN B F V.Discovering Petri nets from event logs[J].Transactions on Petri Nets and Other Models of Concurrency,2013,7:372-422.