方 歡，鄭雪文，王吳松

(安徽理工大學 數(shù)學與大數(shù)據(jù)學院，安徽 淮南 232001)

0 引言

隨著大數(shù)據(jù)技術的蓬勃發(fā)展，業(yè)務流程管理及優(yōu)化在企業(yè)的日常管理中發(fā)揮著越來越重要的作用，然而業(yè)務流程可能隨著時間的推移不斷地發(fā)生演變，以至于日志行為和模型行為之間存在差異，實際系統(tǒng)日志無法在模型中回放[1]。變化原因包括法規(guī)、政策、用戶需求和軟件維護等因素[2]。這些因素在影響業(yè)務流程發(fā)生變化的同時，也可能改變系統(tǒng)的業(yè)務能力和行為，因此高效、正確地檢測業(yè)務流程變化，并及時對業(yè)務系統(tǒng)模型進行修復具有較高的研究價值。

近年來涌現(xiàn)的基于完備日志的模型修復研究得到了諸多科研工作者的青睞。如文獻[3]研究了現(xiàn)有的一致性檢查器，將給定的過程模型與日志中的跡對齊?；诖?，將日志分解為不適合子跡的子日志。對于每個子日志，派生一個子過程，然后將其添加到原始模型適當?shù)奈恢?。文獻[4]提出將預定義的成本分配給修復動作(插入或跳過活動)的方法，使得對齊的計算量大大減少，同時得到最佳修復。文獻[5]提出一種用于過程模型修復的模塊化方法，可以使用不同的算法作為構建塊來實例化該方法。其主要思想是使用模型分解，找到不符合要求的片段，并用符合要求的片段替換，而不是完全重新發(fā)現(xiàn)。文獻[6]提出的方法可以在選擇結構中添加新的活動，它引入了一種新的偏差類型：選擇分支偏差，同時在流程模型和事件日志之間定義了擴展的對齊方式。若在選擇結構中找到該偏差，則可以將該偏差作為分支添加到原始模型中。文獻[7]提出一種新的基于Petri網(wǎng)的模型修復方法，該方法能使在原始模型中只能發(fā)生一次變遷，在修復后的模型中可以隨時發(fā)生。

以上研究方法大都基于Petri網(wǎng)的模型修復，然而，近兩年出現(xiàn)了一些基于邏輯Petri網(wǎng)(Labled Petri Nets，LPN)[8-13]的模型修復方法。例如，文獻[8]提出通過LPN的現(xiàn)有方法來分別修復包含順序結構和并發(fā)結構的過程模型。其主要思想是通過識別新活動找出事件日志中的跡與流程模型之間的偏差。然后可以分別構造新活動的前繼和后繼集，以及每組活動間的關系，最后構造邏輯關系函數(shù)。文獻[9]提出的模型修復方法首先定義了新活動和原始活動之間的兩種新關系，分別稱為邏輯并發(fā)關系和因果關系。然后，構造一個梯形矩陣，并獲得原始過程模型和事件日志之間的偏差。接下來，使用偏差矩陣記錄這些差異以修復模型。文獻[10]中的并發(fā)變遷對和選擇變遷對是基于過程樹構造的。通過遍歷最佳對齊，確定并發(fā)塊頭和尾之間的變遷，偏差用于判斷過程模型和事件日志中的活動是否具有并發(fā)變遷對或選擇變遷對，然后通過LPN修復該模型。文獻[11]提出了對于包含具有并發(fā)結構的一種模型修復方法。首先找到偏差的位置；然后，通過LPN添加從庫所到變遷或從變遷到庫所的有向?。蛔詈?，通過添加帶有邏輯函數(shù)的邏輯變遷來實現(xiàn)模型的修復。文獻[12]首先定義一個新的事件日志類型：選擇偏差子日志，然后，根據(jù)token的原理找到偏差位置重放。接下來，在選擇分支之間添加橋以修復模型。文獻[13]可以檢查模型是否與事件日志匹配。根據(jù)不同的結構和一致性檢查的結果獲得偏差位置。在不添加隱變遷和重復變遷的情況下，通過添加弧和邏輯變遷來修復模型，并保留原始結構。

以上大都是基于系統(tǒng)原始參考模型已知的情況，對模型的修復存在局限性問題。在實際應用場景中，系統(tǒng)原始參考模型也可能未知，或者實際模型與原始模型存在部分差異的情況，且得到的系統(tǒng)日志是不完備的。完備日志是指日志包含所有業(yè)務活動以及活動間所有可能的行為關系，而不滿足完備日志條件的日志稱之為不完備日志。因此，有必要在系統(tǒng)參考模型未知和基于不完備事件日志的情況下[14-16]對業(yè)務流程的變化進行檢測和模型修復。

本文的主要貢獻包括：①在系統(tǒng)參考模型未知的情況下，依據(jù)當前實際系統(tǒng)不完備日志，得到日志跡中每個活動的直接前繼和后繼；②基于原始不完備事件日志發(fā)現(xiàn)的模型與系統(tǒng)實際日志不同的行為輪廓關系集，提出了一種日志偏差域的識別方法；③通過日志跡中每個活動的直接前繼和后繼以及偏差域，提出一種實現(xiàn)模型修復的方法。

1 研究動機

隨著時間的演進，業(yè)務系統(tǒng)可能會引入一些變化操作，如活動的插入和刪除等，這些變化操作勢必會引起業(yè)務系統(tǒng)的行為發(fā)生變化[17]，除此之外，現(xiàn)實生活中存在許多不完備的事件日志業(yè)務系統(tǒng)。由于要實現(xiàn)業(yè)務系統(tǒng)的變化檢測及修復，需要了解系統(tǒng)的歷史日志信息和當前實際系統(tǒng)日志信息。為了簡化描述，記歷史日志為Lhis，當前系統(tǒng)日志為Lact。

下面以一個簡單的例子，從不完備日志的角度說明當前實際系統(tǒng)日志與系統(tǒng)模型不一致性的問題。利用具體的事件日志進行分析，選取一組日志，日志中的相關跡信息有：事件日志Lhis={,,,,,,}；事件日志Lact={,,,,,,}。日志Lhis和Lact均包含7條事件軌跡，Lact中的跡σ5、σ6同σ7分別與跡σ2、σ3和σ4相同。由日志Lhis在ProM中發(fā)現(xiàn)的系統(tǒng)模型如圖1所示。

將日志Lact在圖1的模型中回放可知，除了日志中的跡σ1與模型是一致的，其余的跡σ2到跡σ7都不能在模型中回放?？梢钥闯?，基于不完備事件日志的情況下，當前實際系統(tǒng)日志與業(yè)務系統(tǒng)模型之間也存在差異。因此，在不完備事件日志下對業(yè)務流程的變化檢測和模型修復問題的研究十分必要。

2 基本定義

定義1[18]跡，事件日志。設A為所有活動的集合。若σ∈A*，則記跡為σ。如果L∈B(A*)且L是跡σ上的多集，則記L為事件日志，S(σ)表示σ中所有活動的集合。

例如，A={a,b,c,d}是一個活動集，σ=是一條跡，則S(σ)={b,c,a,d}。

定義4[2]變化操作。L為一個事件日志，事件跡σ∈L，日志中的活動集合記為S，Delete和Insert分別指日志中活動的刪除變化操作和插入變化操作。其中，Delete和Insert具體操作如下：?ai∈S,σi∈L(i=1,2,…,n)，

(1)Delete：Delete(σi,ai)刪除操作是指把活動ai從跡σi中進行刪除。

(2)Insert：Insert(si,ai)是指把活動ak插入到跡si中的任意位置；Insert(σi,ak,a1,a2)指在跡σi中，把活動ak插入到a2和a3之間(其中ak為新增活動)。

定義5[2,20-21]跡處理運算符。設L為A上的日志，num為日志中跡的個數(shù)，a∈A，?σk=x1,x2,…,xn∧σk∈L∧a∈σk：

(1)τ(xi,σk)給出了σi中元素xi的活動名稱。

(2)Pos(a,σk)={p,q,r,…,s}，例如τ(xp,σk)=a,…,τ(xs,σk)=a。

(3)1-Pred(xi,σk)=τ(xi-1,σk),1-Succ(xi,σk)=τ(xi+1,σk),i是某一確切的數(shù)。

在定義5中，函數(shù)1-Pred和函數(shù)1-Succ分別提供了活動xi的直接前繼和直接后繼；函數(shù)1-Predset是日志中發(fā)生在活動標識符a之前的最近活動集合的并集；相反，1-Succset是指發(fā)生在活動標識符a之后的最近活動集合的并集。

3 基于不完備事件日志的偏差域識別

為了有效地分析不完備日志，需要提取日志的主要信息。由定義2可知，研究的不完備日志行為輪廓關系僅為所有的嚴格序和交叉序關系。已知原始事件日志Lhis和系統(tǒng)實際日志Lact，由算法1可以得到其行為輪廓關系，Ract表示一組基于系統(tǒng)實際日志的行為輪廓關系，Rhis表示一組基于原始日志的行為輪廓關系。算法2提出了基于行為輪廓關系矩陣的日志間比較算法。在算法2中，可以并行執(zhí)行步驟5和步驟6以節(jié)省時間，從而得到Rhis和Ract。

算法1基于不完備日志的行為輪廓關系捕獲算法。

輸入：日志L;

輸出：基于不完備日志的行為輪廓關系集。

1.R=?,R→=?,R||=?

2.for each σ in L do

4.else if x?y and y?x then R||=R||∪(x,y) //(x,y)為交叉序關系

5.end for

6.R=R→∪R||

7.return R

定義6[18]日志偏差域。設A是日志中所有活動的集合Ract∪Rhis。對于?ai,aj∈A，如果Ract與Rhis之間存在不同的關系表示為無匹配關系。日志偏差域是由無匹配關系構成的極小域，記為(ai,aj)。

由定義6，日志偏差域是原始日志與系統(tǒng)實際日志之間的不匹配域[22]。由算法3調用算法2 ，可直接得到日志偏差域D。D不僅記錄不匹配的關系，還記錄活動。因此，可以很容易地獲得D中的活動信息。

算法2基于行為輪廓關系矩陣的原始日志與系統(tǒng)實際日志的比較算法。

輸入：原始日志行為輪廓關系集Rhis，系統(tǒng)實際日志行為輪廓關系集Ract;

輸出：Rhis和Ract之間的不同行為輪廓關系集。

1. Ahis表示Lhis中所有活動的集合，Aact表示Lact中所有活動的集合

2. D=?,A=? //D表示Rhis和Ract之間不同的行為輪廓關系集

3. A=Ahis∪Aact,n=|A| //n表示活動集A中所有活動的個數(shù)，A中元素是順序的

4. aact[n][n]={0},ahis[n][n]={0} //1(嚴格序關系)；2(交叉序關系)；0(其他)

5. for each element ∈Rhisdo ahis[i][j]=Rhis(ai,aj) //i,j=1,2,…,n

6. for each element ∈Ractdo aact[i][j]=Ract(ai,aj)

7. for (i=1;i≤n;i++) do

8. for (j=1;j≤n;j++) do

9. if aact[i][j]≠ahis[i][j] then

10.D=D∪{(aact[i][j],ahis[i][j])}

11.return D

算法3如下：

算法3基于不完備日志的偏差域識別算法。

輸入：Ract，Rhis；

輸出：基于不完備日志的偏差域(ai,aj)。

1. 調用算法2，得到D

2. for each element ∈D do return (ai,aj)

3. end for

4 基于不完備事件日志的模型修復

一些現(xiàn)有的一致性檢查技術已經(jīng)被用于修復過程模型，也有許多技術可以有效地發(fā)現(xiàn)日志行為差異[23]。本文研究了基于原始不完備事件日志挖掘的模型與系統(tǒng)實際日志的偏差域，提出一種模型修復的算法，使之重放系統(tǒng)實際日志。在進行具體修復過程前，利用算法4對基于不完備日志偏差域的變化活動進行捕獲，從而獲得個變化操作的變化活動集。

算法4基于不完備日志偏差域的變化活動的捕獲算法。

輸入：系統(tǒng)實際日志Lact，基于原始日志Lhis的Petri網(wǎng)N=(P,T,F);

輸出：各變化活動集Adel，Ains及Amov。

1.G=Gd=Gk=Gm=?，Adel=Ains=Amov=?

2.調用算法1，得到基于日志的行為輪廓關系Ract和Rhis；調用算法2，得到D

3.for each element ∈D do //delete變化活動集Adel的捕獲

4.if all aact[i][d]=aact[d][j]=0 and ahis[i][d]≠0 and ahis[d][j] ≠0 then

5.Gd=(0,ahis[i][d])-(0,ahis[d][j]), G=D-Gd

6.調用算法3，得到活動對(ai,ad)，(ad,aj)，Adel=Adel∪{ad}，A=A-Adel

7.end for

8.for each element ∈G do//insert變化活動集Ains的捕獲

9.if all ahis[i][k]=ahis[k][j]=0 and aact[i][k]≠0 and aact[k][j]≠0 then

10.Gk=(aact[i][k],ahis[i][k])-(aact[k][j],ahis[k][j]), G=G-Gk

11.調用算法3，得到活動對(ai,ak)，(ak,aj)，Ains=Ains∪{ak}，A=A-Ains

12.end for

13.for each element ∈G do//move變化活動集Amov的捕獲

14.if all ahis[i][m]≠aact[i][m] and ahis[m][j]≠aact[m][j] then

15.調用算法3，得到活動對(ai,am)，(am,aj)，Amov=Amov∪{am}，A=A-Amov，Gm=G

16.end for

17.return Adel, Ains, Amov

大多數(shù)模型修復是基于對齊的方式。在對齊方法中，分為活動的跳過與移動。而在本文中，對于一個活動ad的刪除是通過添加一個對應的排他關系的隱變遷τd來實現(xiàn)系統(tǒng)實際日志的回放，刪除活動的修復方式具體如圖2所示，主要區(qū)別在于刪除活動的前繼和后繼的庫所數(shù)。對比Rhis和Ract，可以發(fā)現(xiàn)一個活動的刪除會導致系統(tǒng)實際日志中該活動與其他活動沒有相對應的關系，即Ract中該活動對應的行與列均為空，具體修復步驟見算法5。

算法5基于不完備日志偏差域的模型Delete操作修復算法。

輸入：delete日志偏差域Gd，delete變化活動集Adel，基于原始日志Lhis的Petri網(wǎng)N=(P,T,F)；

輸出：修復后的Petri網(wǎng)N1=(P1,T1,F1)。

1.for each ad∈Adeldo

2.Get(Pi,ad),(ad,Po)∈F，T1=T∪{τd},F1=F∪{(Pi,τd),(τd,Po)}

3.//其中Pi,Po為活動ad的前繼庫所集和后繼庫所集

4.//如果模型中已有隱變遷在該活動的跳過位置，則無需再添加跳過變遷

5.end for

6.return N1=(P1,T1,F1)

然而，在對由原始事件日志發(fā)現(xiàn)的模型中進行某一活動的刪除處理時，可能發(fā)現(xiàn)模型中存在與該活動具有排他關系的隱變遷。由于日志跡行為關系中無排他關系，該種情況下不在另外插入排他關系的隱變遷。一個活動ak的增添則有很多情況，如圖3所示。圖3a和圖3c是新增了具有嚴格序關系的活動，圖3b是新增了具有交叉序關系的活動，圖3d是新增了具有排他序關系的活動，插入操作具體的修復步驟見算法6。

算法6中，一個新活動的添加會使系統(tǒng)實際日志中出現(xiàn)與該活動相關的嚴格序和交叉序關系。其中第3～10行對圖3a和圖3c中X和X2類型結構進行了修復；第11～13行修復了圖3c中X1類型結構；第14～16行可對圖3c中X3類型結構進行修復；第17～21行對圖3b類型結構進行了修復；22～23行可對圖3d類型結構進行修復。

對于移動活動的修復大體采用先調用delete修復后insert修復以達到move修復的效果，例如圖4中前兩種類型，然而對于兩個活動間排他關系移動為交叉序關系的情況，正如圖4中類型的修復是通過添加一個循環(huán)隱變遷從而使得活動a1和a2之間存在交叉序行為。具體的move操作模型修復步驟如算法7。

算法6基于不完備日志偏差域的模型Insert操作修復算法。

輸入：insert日志偏差域Gk，活動集Ains，Ains對應的1-pred和1-succ集以及Petri網(wǎng)N1=(P1,T1,F1);

輸出：修復后的Petri網(wǎng)N2=(P2,T2,F2)。

1. for each ak∈Gkdo

2.調用算法3，得到其對應的活動對(ai,ak)，(ak,aj)

3. for each ax∈1-pred(ak) and ay∈1-succ(ak) do//ax為新增活動ak直接前繼中的元素

4. if Ract(ax,ak)=1 and Ract(ak,ay)=1 then Get(ax,px),(py,ay)∈F

5. //px,py為網(wǎng)N中對應的庫所

6. if px=pythen T2=T1∪{ak},F2=F1∪{(px,ak),(ak,px)}

7. else if |1-pred(ak)|≥2 and each ax1,ax2∈1-pred(ak),Ract(ax1,ax2)=2

8. then Get(ax1,px1),(px1,τxo),(τxo,pk)∈F1,T2=T1∪{ak},F2=F1∪{(pk,ak),(ak,pk)}

9. else if |1-succ(ak)|≥2 and each ay1,ay2∈1-succ(ak),Ract(ay1,ay2)=2

10. then Get(py1,ay1),(τyi,py1),(pk,τyi)∈F1,T2=T1∪{ak},F2=F1∪{(pk,ak),(ak,pk)}

11. for each ax1,ax2∈1-pred(ak) do//ax1,ax2為新增活動ak直接前繼中的元素

12. if Ract(ax1,ak)=2 and Ract(ax2,ak)=1 and Ract(ax1,ax2)=2

13. then Get(ax2,px2)∈F1,T2=T1∪{ak},F2=F1∪{(px2,ak),(ak,px2)}

14. for each ay1,ay2∈1-succ(ak) do//ay1,ay2為新增活動ak直接后繼中的元素

15. if Ract(ak,ay1)=2 and Ract(ak,ay2)=1 and Ract(ay1,ay2)=2

16. then Get(py2,ay2)∈F1,T2=T1∪{ak},F2=F1∪{(py2,ak),(ak,py2)}

17. for each ax1,ax2∈1-pred(ak) and each ay1,ay2∈1-succ(ak) do//同上意義

18. if Ract(ax1,ak)=Ract(ak,ay1)=2 and Ract(ax2,ak)=Ract(ak,ay2)=Ract(ax1,ax2)=Ract(ay1,ay2)=2

19. then Get(px1,ax1)，(τi,px1)，(ay1,py1)，(py1,τo)∈F1,T2=T1∪{ak},P2=P1∪{pi,po},

20. F2=F1∪{(ti,pi),(pi,τnew),(pi,ak),(τnew,po),(ak,po),(po,to)}

21. //其中ti,to可能為可見變遷，也可能為隱變遷

22. if ?ac∈A,Ract(ac,ak)=0 and ?ax∈1-pred(ak),Ract(ax,ac1)=1 and ?ay∈1-succ(ak),Ract(ac2,ay)=1

23. then Get(pi,ac1),(ac2,po)∈F1,T2=T1∪{ak},F2=F1∪{(pi,ak),(ak,po)}

24. end for

25. return N2=(P2,T2,F2)

算法7基于不完備日志偏差域的模型move操作修復算法。

輸入：move日志偏差域Gm，活動集Amov，Amov對應的1-pred和1-succ集以及Petri網(wǎng)N2=(P2,T2,F2);

輸出：修復后的Petri網(wǎng)N′=(P′,T′,F′)。

1. Az=?

2.for each am∈Gmdo Az=1-pred(am)∩1-succ(am)

3.if Az≠?

4.for each az∈Azdo

5.if Rhis(am,az)=0 and Ract(am,az)=2

6. then Get(pi,am),(am,po)∈F2,T′=T2∪{τm},F′=F2∪{(po,τm),(τm,pi)},Gm=Gm-am-az

7. else調用算法5，調用算法6，Gm=Gm-am

8. else調用算法5，調用算法6，Gm=Gm-am

9. return N′=(P′,T′,F′)

5 業(yè)務系統(tǒng)模型修復案例分析

5.1 基于日志偏差域的修復算法的時間復雜度分析

在本文提出的7個算法中，算法1的時間復雜度為O(|σ|)，其中σ指事件日志L中所有的跡數(shù)量；算法2的時間復雜度為O(|T|2)，|T|相當于活動集A中所有活動的個數(shù)；算法3、算法4和算法5的時間復雜度均為O(n)；算法6和算法7的時間復雜度為O(n·max(|1-pred(a)|,|1-succ(a)|))，其中：|1-pred(a)|表示活動a的直接前繼的個數(shù)，|1-succ(a)|表示活動a的直接后繼的個數(shù)。

5.2 醫(yī)療實驗案例分析

5.2.1 實驗模型和數(shù)據(jù)

實驗中使用的數(shù)據(jù)來自青島一家醫(yī)院。以醫(yī)院的胸外科手術為例，利用Prom工具中的演繹挖掘機(Inductive Miner，IM)挖掘原始系統(tǒng)的不完備事件日志，可以得到一個模型，如圖5所示。首先，患者在醫(yī)院掛號有兩種方式：互聯(lián)網(wǎng)預訂；先詢問咨詢臺，其次準備排隊掛號，排到時工作人員會問及其之前的醫(yī)療診斷，同時需確定是專家還是普通門診，然后支付掛號費，然后患者會收到一個號碼并等待叫號。當患者需要門診檢查時，可能會檢查胸部CT，并進行心電圖檢查，常規(guī)，紅細胞沉降率(Erythrocyte Sedimentation Rate,ESR)或血氣分析同時進行。最后醫(yī)生會根據(jù)結果診斷檢查并開始治療。

實際過程中可能存在某些情況。例如，對于某些大城市在掛號后會根據(jù)放號的范圍在就診前進行排隊；或當病人做一個門診檢查，需要創(chuàng)建一個新的檢查，如胃鏡；或病人需要血液常規(guī)檢查后同時進行ESR和血氣分析；或對病人進行一個生物全套檢查。

隨著實際醫(yī)療過程的變化，系統(tǒng)實際的事件日志出現(xiàn)的如上新事件的添加和舊事件的刪除或移動，使得原始事件日志挖掘出的模型不能重放其對應的變遷。為了解決因insert、delete和move變化操作引起的行為不一致問題，從醫(yī)院系統(tǒng)獲得8個事件日志(L1～L8)，上述所有更改都記錄在這些日志中。在手動刪除嚴重偏離原始模型的事件日志后，日志中包含的跡從200到900不等，實驗數(shù)據(jù)集中的跡、事件、活動的數(shù)量和跡的長度范圍如表1所示。

表1 實驗中日志的詳細信息

5.2.2 三種修復方法的模型修復實驗

圖5是根據(jù)表1中日志L1-L8得到的演繹挖掘模型，而圖6是根據(jù)表1中日志L1-new-L8-new得到的演繹挖掘模型，可以看出圖5和圖6存在結構上的差異。

本節(jié)利用Fahland方法，Goldratt方法以及本文方法來修復圖5中的模型，如圖7、圖8和圖9所示。由于表1中日志L1-new包含最全面的跡，因此將L1-new作為模型修復的實驗數(shù)據(jù)。

圖7中Fahland修復模型的方法是基于給定事件日志和原始模型之間的最佳對齊方式獲得偏差。根據(jù)日志中的移動以最佳對齊方式收集子日志；然后挖掘相應的子過程并將其以自循環(huán)的形式添加到原始模型中。對于事件日志中屬于不同選擇分支的活動，該方法可以根據(jù)對齊方式查找偏差；然后添加不可見變遷和子過程以修復原始模型。然而在圖7中可直觀地發(fā)現(xiàn)Fahland模型修復方法不能重放活動blood gas analysis和ESR之間的交叉序關系。

圖8中Goldratt修復模型的方法根據(jù)某些約束向模型中添加了一個單獨的變遷作為自循環(huán)或不可見變遷。對于包含不同選擇分支上活動的事件日志，此方法在原始模型中插入不可見變遷和自循環(huán)以重放以上事件日志。

本文修復模型的方法是基于不完備日志的變化檢測方法，利用活動的比較矩陣對事件日志的Insert、Delete和Move變化操作進行描述，從而發(fā)現(xiàn)原始事件日志同系統(tǒng)實際日志的偏差域，根據(jù)日志偏差域對原始事件日志發(fā)現(xiàn)的模型進行修復。實驗中原始事件日志和實際事件日志數(shù)據(jù)中所有活動的簡記符號如表2所示。

通過調用算法1、算法2、算法3和算法4得到的實驗中原始事件日志和實際日志的偏差域如下所示：

(1)刪除活動相關的日志偏差域：(A,H),(B,H),(C,H),(D,H),(E,H),(F,H),(G,H),(H,I),(H,J),(H,K),(H,L),(H,M),(H,N),(H,O),(H,P),(H,Q),(H,R),(H,S)。

(2)新增活動相關的日志偏差域：(A,K),(B,K),(D,K),(E,K),(F,K),(G,K),(H,K),(I,K),(J,K),(L,K),(M,K),(N,K),(O,K),(P,K),(Q,K),(K,L),(K,M),(K,N),(K,O),(K,P),(K,Q),(K,R),(K,S),(A,M),(B,M),(D,M),(E,M),(F,M),(G,M),(H,M),(I,M),(J,M),(K,M),(L,M),(M,K),(M,L),(M,N),(M,O),(M,P),(M,Q),(M,R),(M,S)。

表2 日志中活動名稱簡記表

(3)新增活動相關的日志偏差域：(C,D),(C,E),(C,F),(C,G),(C,H),(A,C),(D,C),(E,C),(F,C),(G,C),(O,P),(P,O)。其中行為關系發(fā)生變化的活動的集合即變化集為CS={A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S}。

由定義5可知實驗數(shù)據(jù)中實際事件日志活動的直接前繼和直接后繼如表3所示。

表3 實際日志中各活動的直接前繼和直接后繼

經(jīng)過算法4、算法5、算法6和算法7的運行與分析，可得如下結論：

(1)Delete變化操作的修復：根據(jù)上述被刪除活動的日志偏差域，可知實驗案例中H為刪除的活動。由于圖5中沒有隱變遷能使其跳過，因此需添加一個隱變遷使實際日志跡能在原始事件日志挖掘出的模型中重放，可從圖9中的delete操作修復1觀察到修復結果。

(2)Insert變化操作的修復：根據(jù)表3及新增活動的日志偏差域，可知實驗案例中K，M為新增活動。由于活動K的直接前繼和直接后繼分別為{J,M,N,O,P,Q,L}和{M,N,R,P,Q,O,L}，算法6中的17～21行代碼對其進行修復，并知K同活動M,N,O,P,Q,L均為交叉序關系。但滿足算法6中第18行代碼條件的僅活動L和Q，19～20代碼的運行可對其進行修復，在圖9中的insert操作修復1可觀察到修復結果，對應圖3b的情況。

表3中活動M的直接前繼和直接后繼分別為{J,L,K}和{K,L,N,Q}，算法6中的14～16行代碼對其進行修復。在實際事件日志中，由于活動M的直接后繼中活動L和K同M均為交叉序關系，活動N和Q同M均為嚴格序關系，又因為活動L和K為交叉序關系，因此可以根據(jù)活動L或活動K執(zhí)行第16行代碼對圖5中的模型進行修復，圖9中的insert操作修復2觀察到修復結果，對應于圖2c中X3的情況。

(3)Move變化操作的修復：根據(jù)表3及移動活動的日志偏差域，可知實驗案例中C,O和P為移動的活動。活動C的直接前繼和直接后繼分別為{B,D,E,F}和{I}，由于活動C的直接前繼和直接后繼交集為空，算法7中的第9行代碼的執(zhí)行可對其進行修復，在圖9中的move操作修復1觀察到修復結果。

表3中活動O的直接前繼和直接后繼分別為{J,L,M,N,Q,P}和{L,M,R,Q,P,K}。由于活動O的直接前繼和直接后繼交集非空，而且活動O和P在原始事件日志中Rhis(O,P)=0，在實際日志中的行為關系為交叉序關系Ract(O,P)=2，因此算法6中第7行代碼對其進行修復，在活動O和P的前繼庫所和后繼庫所間添加一個可循環(huán)的隱變遷，以此使其之間的交叉序關系得以重放，可從圖9中的move操作修復2觀察到修復結果。仿真結果與本文所述方法計算結果一致，進一步驗證了方法的正確性。

5.2.3 模型評估

以表1中的8個事件日志L1-new～L8-new為例，將本文方法與Fahland和Goldratt兩種模型修復方法從適合度、精確度和簡單性3個方面進行比較。根據(jù)文獻[24]中提供的公式來計算事件日志和修復模型之間的適合度和精確度。

圖10顯示了3種模型修復方法的適合度和精確度的比較結果。 適合度是評估過程模型質量的最重要指標。 如果模型可以重放事件日志中的活動，則該模型具有良好的適合度。 即如果一個模型可以重放事件日志中的所有跡，則該模型的適合度為1。由圖10a可以看出，在不同數(shù)量的事件日志下，本文方法的適合度較高，其次為Fahland和Goldratt模型修復方法。

精確度是指在過程模型中不允許發(fā)生事件日志中無法觀察到的活動。從圖10b可以看出，隨著事件日志中跟蹤數(shù)量的增加，精度值不會發(fā)生太大變化。 在不同數(shù)量的事件日志中，由于重復變遷或自環(huán)可能會降低修復模型的精確度，本文方法具有比其他兩種方法更高的精確度。

簡單性意味著修復的模型應盡可能簡單。為了比較這3種模型修復方法的簡單性，統(tǒng)計了各修復模型中的主要標準：添加的庫所數(shù)、變遷數(shù)|T+τ|、弧數(shù)和重復變遷數(shù)，如表4所示。Fahland方法添加的庫所數(shù)、變遷數(shù)|T+τ|、弧數(shù)和重復變遷數(shù)分別為1,9，19和3；Goldratt方法添加的庫所數(shù)、變遷數(shù)|T+τ|、弧數(shù)和重復變遷數(shù)分別為0,14，28和10；本文方法添加的庫所數(shù)、變遷數(shù)|T+τ|、弧數(shù)和重復變遷數(shù)分別為2,8,18和2；因此本文模型修復方法的簡單性更好些。由上述分析可知，本文方法在適合度、精確度和簡單性這3個方面具有較好的結果，由此可以證明本文方法的有效性和正確性。

表4 四種模型簡單性表

5.3 結果分析

本文通過日志偏差域、實際系統(tǒng)日志的直接前繼和后繼來進行模型的修復，最后使得原始事件日志和系統(tǒng)實際日志均能在修復后的模型中回放可行跡。然而，本文是基于日志中所有活動都不考慮隱變遷的發(fā)生情況進行變化檢測分析。因為對于與某活動具有排他關系的隱變遷可能會導致該活動的發(fā)生權被剝奪，但并沒有執(zhí)行刪除該活動的變化操作。所以，本文方法修復的模型也存在不能重放的跡，如實驗中活動blood routine的跳過在圖9中無法執(zhí)行，但相比Fahland和Goldratt模型修復方法還是具有較好的適合度，精確度和簡單性。同時當某系統(tǒng)的原始事件日志缺失時，還可利用本文方法修復的模型同修復前的模型進行對比，以尋找到原始事件日志的大多數(shù)可行跡。

6 結束語

事件日志中活動的變化將導致模型中變遷行為關系的改變，大多數(shù)研究人員的前提都是基于完備日志進行原始模型的修復，然而如何基于不完備日志進行變化檢測和模型修復同樣是一個有價值的研究課題。本文在現(xiàn)有研究基礎上，利用不完備日志中變遷活動的偏差域以及系統(tǒng)實際日志中活動的直接前繼和后繼來確定變化的活動和變化后活動的位置，根據(jù)變化的活動及其變化后活動的位置實現(xiàn)模型的修復，并通過Prom工具對所提出方法的正確性和有效性進行了分析驗證。

在今后的工作中，重點研究更為高效的不完備日志變化檢測技術與模型修復方法，以及基于不完備日志的局部活動集所對應的模型修復問題，而不再是單個活動的變化。同時，基于不完備日志模型的相似度問題也有待解決。