基于可預測適合度的選擇性模型修復

張力雯 方賢文 邵叱風 王麗麗,3

1(淮南師范學院機械與電氣工程學院 安徽淮南 232038) 2(安徽理工大學數學與大數據學院 安徽淮南 232001) 3(嵌入式系統與服務計算教育部重點實驗室(同濟大學) 上海 201804)

過程挖掘技術是從信息系統所記錄的事件日志中提取知識發現過程模型，并通過提供技術和工具對其實現性能上的改善.過程挖掘技術主要從3個方面對業務流程進行分析：過程發現、服從性校驗、過程完善，其中服從性校驗與過程完善之間有著密切的聯系[1-3].模型修復是過程完善的一種，其旨在使事件日志能夠回放于過程模型，且修復后的模型與初始模型盡可能相似.通常使用一致性校驗的4個度量標準來對模型修復方法的性能進行評估，即適合度(fitness)、精度(precision)、簡化度、泛化度[4].適合度是指事件日志在過程模型上的回放程度，而精度則描述了回放形式的準確程度[5].能夠回放的活動不一定被準確回放，而準確回放的活動一定可以被回放.簡化度決定了修復后模型的結構復雜性[6].泛化度表示修復后模型與初始模型之間的相似性，也就是說過程模型被限制為事件日志中可觀測行為的程度.如果僅根據事件日志的可觀測行為修復過程模型，則泛化度將受到影響；否則，過度泛化會降低精度造成欠擬合的情況[7].模型修復主要處理使得事件日志無法在過程模型上正常回放偏差活動，因此適合度和精度是評估其性能最為重要的2個指標[8-9].

模型修復通過一致性校驗的方式檢測事件日志回放于過程模型時產生的偏差，并基于這些偏差信息對過程模型進行修復[10-11].一致性校驗主要包括跡對齊與行為關系匹配2種方法，且最優對齊是跡對齊中最優的一種檢測方式[12-13].行為關系匹配用于發現對應活動之間不同的行為關系，也就是產生偏差的非擬合行為[14].最優對齊能夠檢測出事件日志與過程模型之間發生次數最少的偏差，并確定其具體發生位置.通過層層排除的方法構建最優對齊，并根據偏差的不同單位成本進一步分析其最優性，從而獲得任意業務流程的最小偏差成本[15].模型修復通常基于偏差信息執行相應的操作，其中主要包括2種類型的偏差[16]：1)事件日志產生的可觀測偏差,該偏差的修復形式同時影響適合度與精度；2)過程模型產生的偏差，其會阻礙事件日志正常地回放，這種偏差的修復形式僅對適合度有影響.就平衡適合度與精度而言，需要考慮第1類偏差的修復問題，現存技術主要對這類偏差采用2種修復形式：1)以自循環的方式將可觀測偏差插入過程模型；2)構建偏差與隱變遷的沖突子結構，并將其添加于過程模型的合適位置.前者無法準確回放非迭代的可觀測偏差，而后者不能回放迭代的可觀測偏差，因此適合度與精度始終無法得到很好的平衡[17].由于循環路徑的重復性，因而使得一些相同的偏差不斷地發生.現存方法通常沒有單獨對循環部分的修復問題進行分析，而是采用與非循環部分一致的修復方法.因此，當事件日志與過程模型之間存在循環路徑產生的偏差時，很容易在改善適合度的同時導致精度成倍地下降.理想的修復性能是在合理程度上保證適合度的同時盡可能提高精度，且不增加修復活動的數量(擁有相同標簽和位置的所有偏差被視為一個修復活動).值得注意的是，為了準確計算適和度與精度，每一個需要被修復的偏差活動都被看作一個獨立的單位成本進行核算(其中包括偏差的迭代發生)[18].

圖1使用業務流程模型與標注(business process model and notation, BPMN)描述了一個投保流程的模型M.M在信息系統中會不斷變化，并被記錄為一個事件日志L={(a1,…,an)1,(a1,…,an)2,…,(a1,…,an)m}.其中，(a1,…,an)1,…,(a1,…,an)m表示從初始活動a1到終止活動an之間所有活動組成的m條跡，L則為m條跡的集合.圖1設定L={(ABEIIIJK),(ABFJIIIK),(ACDGGGHIJK),(ADCGHIJK)}，統一使用A到K之間的字母表示L中所有活動的對應標簽.通過最優對齊可搜索到L與M之間非循環部分存在的3種偏差：1)L中的非迭代可觀測偏差{D,G,I,J}；2)M上能夠捕獲且使得L無法正常回放的偏差{D}；3)L中的迭代可觀測偏差{I2,G2}(偏差右上角的數字表示事件日志中偏差自身迭代發生的次數).將偏差活動的單位成本設置為1，可計算出L與M之間的適合度和精度分別為fitness=1-Devcost/(|L|+|ML|)≈0.67，precision=1(Devcost為偏差成本，|L|+|ML|為日志與模型在對齊過程中所有元素的個數).初始模型上沒有自循環路徑產生的迭代活動時，核算精度需要將日志預處理為與模型完全擬合的子日志，因而在這種情況下精度始終為1[19].上述第2類偏差均來自于M，因此其修復形式不影響精度.通過在此類偏差元素的原有位置添加隱變遷進行修復，可以使這部分的適合度得到完整提升.上述第1類和第3類偏差均來自于L，以自循環方式將其插入M進行修復，則第1類偏差無法被準確回放.修復后L與M之間的適合度為1，但精度卻下降了0.32.將L中的偏差元素與隱變遷組建為一個沖突子結構，并添加到過程模型上的合適位置，該方法無法回放第3類偏差.修復后L與M之間的精度為1，但適合度卻只有0.88.這種情況下，要么以大幅度犧牲精度為代價來保證適合度最終為1，要么精度為1但適合度則不夠合理.

Fig. 1 Life insurance application process and deviations based on information system圖1 人生保險申請過程和基于信息系統產生的偏差

本文針對如何同時兼顧適合度與精度對模型的修復問題主要進行了2方面的改進：1)根據迭代可觀測偏差的總成本預測使用配置方法進行整體優化后的適合度，并當其滿足給定閾值范圍時確定對所有可觀測偏差進行配置優化.2)當預測適合度不滿足閾值時，利用行為關系的匹配性發現事件日志與過程模型之間存在的變體，并通過檢測每個變體中是否包含迭代可觀測偏差來執行合適的操作.由于低頻過濾不在本文的研究范圍之內，因此本文默認事件日志是已經過濾后的有效事件序列集.

1 相關工作

本文所提出的方法主要涉及模型修復與配置優化2種技術[20-21].模型修復的目標是使事件日志能夠在修復后的過程模型上回放，并盡可能地維護原始模型的特有行為.采用偽布爾約束來處理多目標問題，該方法以最小代價實現了模型的最大回放[22].與自動操作相比，手動修復可以盡可能地避免過程模型中不必要的冗余行為[23].上述偽布爾約束方法和手動修復方法在合理提高適合度的同時盡可能降低修復成本，但其忽視了一致性度量中的其他重要標準，即精度.將定義的擴展對齊添加到過程模型的可達標記中，計算模型中的偏差并對其進行修復[24].通過Petri網和各選擇結構之間的轉換關系確定模型的修復位置[25].上述2種方法綜合考慮了各種度量標準的改進，但僅適用于選擇結構的網系統.將多個經典問題的解決方案用來搜索事件日志與過程模型之間所需的修復活動,旨在以最小的代價處理最多的偏差[26].這種方法需要犧牲大量精度來換取適合度的提升.基于4個度量標準分析過程模型的修復方法，并將滿足并發關系的可觀測偏差子結構以自循環方式插入到過程模型上，其在一定程度上改善了修復后的精度，但仍然無法對非迭代插入偏差進行準確修復.在保證適合度為1的前提下根據當前變體的實際情況選擇執行不同的操作，其往往由于過分追求適合度而導致精度仍然可能存在不合理的現象[27].

配置優化在給定約束條件下發現一個業務流程中具有共性的參考模型，并將其與變化模型之間產生的變量進行兼容[28-29].這種技術通過在控制流中添加/移除可配置活動的選擇子結構來實現優化[30-31].基于事件日志所記錄的真實行為構建可配置片段，并通過對其進行優化獲得一個具有共性和個性行為的過程模型[32].配置優化技術構建日志中可觀測偏差與隱變遷的沖突子結構，并通過將其添加到過程模型的合適位置實現修復[33].使用這種方法不能回放日志中自循環路徑產生的迭代可觀測偏差，因而無法保證修復后的適合度在合理范圍內.本文首先對整體配置后的適合度進行預測，并根據閾值條件選擇是否對初始模型執行整體配置.當不能進行整體配置時，需要發現事件日志與過程模型之間的變體，并根據每個變體中是否包含迭代可觀測偏差選擇執行不同的操作.循環部分的修復要根據循環中產生偏差的不同情況來執行，從而最大程度地兼顧適合度與精度.

2 準備工作

定義1.事件日志.將元組L=(κ,q,e,?,,∠)記為事件日志，其中包含事件日志L的元組中包含所有可能出現的符號標注.κ為日志中的一條跡，q為多重跡的統一案例號.由于事件日志中可能存在不同的多重發生跡，因此其中所有案例號都屬于一個案例集q*，即?q=q*.e為日志中的事件元素，記作?ei∈L.?為事件日志中所有事件的標簽集，且將每個事件指定為其對應的標簽，為相鄰事件之間的流關系，記作∠?E×E.

定義2.標簽工作流網系統.將元組N*=(P,T,F,Z,λ,δ,D,pini,pfinal)定義為標簽工作流網系統.P，T，F分別表示網系統N*上的庫所、變遷以它們之間的流關系，F?(PF)∪(FP).Z為網系統N*中所有變遷的標簽集，且λ將每個變遷指定到對應的標簽，為網系統上從初始結點到終止結點之間的一條完整序列，d為每條序列δ的案例號，記作δd.由于網系統N*中可能存在不同的序列，因此其中所有發生序列都屬于一個序列集即與pfinal∈P分別為工作流網的初始庫所與終止庫所，當且僅當|pini|=|pfinal|=1時網系統N*為工作流網.

定義4.擬合模式與非擬合變體.非擬合變體是指引起事件日志與過程模型之間部分偏差的對應子模式[34].在最優對齊中劃分由不同行為變化所產生的偏差，并根據每個行為變化中的活動在所有對齊中的行為關系確定變體類型.

例如，L={(ABCDEFGHK),(ACBDEFGHK)}被回放于過程模型上，該過程模型的發生序列集為δ*={(ABCDEIJK),(ABCEDJIK),(ABCDEIJK),(ABEDJIK)}.圖2中找出3組偏差(B,C)，(F,G,H)，(I,J)分別屬于并發/因果、插入因果行為包含及跳過因果行為包含的變體，記作v(C,D)L+∧N*，v(F,G,H)L?，v(I,J)N*?.值得注意的是，事件日志或網系統N*中單個出現的偏差可被看作一個獨立的變體，記作vL‖N*((ei)‖λ(ti)).圖2中B=(D,E)和Bfit(a)=(A,K)表示事件日志與過程模型之間擬合的行為模式，其中B=(D,E)為擬合的因果行為模式，而Bfit(a)=(A,K)則是單個活動的擬合行為模式.

Fig. 2 Search for variants based on optimal alignment圖2 基于最優對齊搜索變體

Fig. 3 Examples of repair operation and configuration operation圖3 修復操作與配置操作的實例

定義6.修復操作與配置操作.修復操作利用最優對齊檢測偏差的完整信息，并采用自循環插入日志中的偏差或隱變遷跳過模型中的偏差對網N*進行修復.根據偏差的不同結構類型，可將修復操作分為2種：1)單個活動的修復操作RO=sl_Esert(ei)或者RO=Skipλ(tj)；2)子結構的修復操作RO?=sl_E((e1),…,(ei))或者RO?=Skip(λ(t1),…,λ(tj)).圖3(a)中描述了修復操作的實例.配置優化通常是對業務流程之間所有不匹配的行為進行優化，而本文則只考慮回放過程中非擬合行為變體所產生的差異.圖3(b)所示的配置操作是在模型上添加日志中不可回放的行為或者通過隱變遷隱藏模型中阻礙日志回放的行為，并將配置操作執行的所有行為稱作可配置行為[35].根據可配置行為的不同結構類型將配置操作分為2種：1)單個活動的配置操作是CO=Add((ei))=((ei),τ)×或者CO=Hide(λ(tj))=(τ,λ(tj))×;2)子結構的配置操作CO?=NAdd((e1),…,(ei)),+,×=(((e1),…,(ei)),τ)×或者CO?=NHide(λ(t1),…,λ(tj)),+,×=(τ,(λ(t1),…,λ(tj)))×.

3 操作確定及故障診斷

事件日志與過程模型在實際運行中可能會存在一些不被期望的非一致行為，其中模型修復主要對日志回放于模型所產生的非擬合行為進行處理.本節根據可預測適合度是否在給定合理范圍內來確定不同的修復方案，并分別從2種角度對一個變體中的故障進行檢測與分析.

3.1 確定不同情況下的修復方式

為了盡可能兼顧事件日志與修復后模型之間的適合度與精度，可設定適合度的合理范圍，并在此范圍內最大化提升精度.使用配置操作對初始模型進行整體修復后的新模型不包含迭代活動，且任意事件日志與該模型之間的精度值始終為1.然而，這種情況下所有迭代插入偏差不能被回放，以至于適合度可能會受到不同程度的影響.因此，當使用配置操作整體修復后的可預測適合度值低于合理范圍時，需要發現事件日志與過程模型之間的變體，并根據每個變體的具體情況選擇執行配置操作和修復操作[36].

可預測適合度是指使用配置操作對初始模型進行整體修復后的適合度，其中所有迭代插入偏差無法被修復.根據迭代插入偏差總成本核算可預測適合度的公式為per_fitness=1-IDevcost/(|L|+|ML|)，其中IDevcost為迭代插入偏差的成本函數.當pre_fitness≥0.9時，使用配置操作對初始模型進行整體修復(給定閾值被設置為0.9，且0.9

Fig. 4 The alternative principle for different operations圖4 不同操作的選擇原理

Fig. 5 Three optimal alignments圖5 3組最優對齊

3.2 檢測偏差

修復操作依賴于最優對齊檢測到的偏差元素來優化過程模型，其中迭代插入偏差是一種特殊的偏差類型，即只有當日志記錄的單個偏差元素經過自循環路徑時才會發生[37].設定事件日志L回放于初始網系統N*={(ABCDG),(AEFG)}時產生了圖5中的3組最優對齊.

根據圖5中的3組對齊可獲得一個變體v(C,D)L+∧N*，并且還有6個完全由自循環路徑產生的迭代插入偏差，即ξop1中的IEsert(B)2，IEsert(C)1，IEsert(D)1和ξop2中的IEsert(B)1，IEsert(D)1，IEsert(C)1.由于它們在正常路徑下不能發生，因此即使只發生1次也會被看作迭代插入偏差處理.ξop2中的插入偏差IEEsert(D)2既產生于并發/因果的變體也產生于自循環路徑，且ξop3中的非迭代插入偏差Esert(D)包含于ξop2中的迭代偏差IEEsert(D)2.值得注意的是，ξop2中有來自于變體v(C,D)L+∧N*的插入偏差，其可與IEsert(D)1合并在一起，并記作IEEsert(D)2(根據定義5可知，IEEsert(D)2中D的迭代次數為1).

3.3 識別可配置行為

配置是一種將參考模型與定制模型之間不匹配行為相互兼容的優化技術.在發現可配置行為的過程中，將事件日志看作是不含有迭代插入偏差的一個參考過程模型，而給定過程模型則是一個變化模型[38].為了能夠更好地兼顧適合度與精度，在一定條件下需要基于可配置行為在初始模型上執行配置操作，從而完成模型修復的功能.

Fig. 6 Execution program and effect of real-time repair圖6 實時修復的執行方案及效果

設定事件日志與過程模型之間的變體分別為{vL(ad),v(ag,ah)L×∧N*+,v(ai,aj)L?+}，其中vL(ad)為僅日志中可觀測到的單個活動變體，因而被看作一個可配置活動Add(ad).v(ag,ah)L×∧N*+可展開為(agHide(ah))‖(Hide(ag)ah)，其中選擇發生的可配置活動之間滿足沖突行為關系，將它們構建為可配置的沖突子結構NHide(ag,ah)×.v(ai,aj)L?+展開為(Add(ai)Add(aj))‖(Add(aj)Add(ai))，其中直接跟隨的可配置活動之間滿足并發行為關系，將它們構建為可配置的并發子結構NAdd(ai,aj)+.配置操作根據定義6描述的方式在初始模型上對可配置活動或子結構進行修復.值得注意的是，當可預測適合度在合理范圍時，無需發現事件日志與過程模型之間的變體，而是直接使用配置操作對初始模型進行整體修復.在這種情況下，將最優對齊檢測出的迭代插入偏差移除，并使其余偏差轉換為相對應的可配置行為.

4 基于可預測適合度的選擇性修復

適合度與精度是衡量業務流程一致性的2個重要依據，因此關于事件日志對過程模型進行修復時需要同時兼顧適合度與精度.修復操作與配置操作在修復中分別對適合度和精度進行優先考慮，使用其中一種操作對初始模型進行整體修復，往往會造成回放性能的改善過于局限.綜上所述，為了能夠合理地權衡適合度與精度，需要在修復初始模型時根據具體情況選擇不同的操作.

4.1 非循環部分的選擇性模型修復

事件日志與過程模型之間的可預測適合度在閾值范圍之內時，需采用配置操作對過程模型進行整體修復.當可預測適合度不在閾值范圍內時，則根據每個變體中是否包含迭代插入偏差選擇修復操作或配置操作.本節介紹各種非循環部分產生變體的修復方式，也就是修復操作與配置操作的選擇性執行.一個包含迭代插入偏差的變體中也可能存在非迭代插入偏差，因此需要執行修復操作.修復操作能夠使這種變體中的所有插入偏差回放于過程模型上，但其中非迭代插入偏差不能被準確回放.另一方面，在不包含迭代插入偏差的變體中執行配置操作，可以使其中所有插入偏差被準確回放.圖6首先判定可預測適合度不在合理范圍內，并給定事件日志與過程模型之間存在的3個變體v(ai,ai+1)L∧N*×，v(ai+2,ai+3)L×∧N*+，v(ai+4,ai+5)L?.v(ai,ai+1)L∧N*×中包含插入偏差但沒有迭代插入偏差，使用配置操作可完整提升該變體的適合度和精度.v(ai+2,ai+3)L×∧N*+中不包含插入偏差，因此使用修復操作或配置操作都能夠完整提升它的適合度，且精度不受影響.v(ai+4,ai+5)L?中包含迭代插入偏差，使用修復操作可完整提升其適合度，但精度會由于非迭代插入偏差無法被準確回放而受到影響[39].

如圖7所示，L與N*之間的變體分別為v(C,D)L+∧N*，v(E,F)L+∧N*×，v(H,I)L?+，它們可選擇的修復方式分為2種：1)彎虛線表示當前變體中含有迭代插入偏差時所做的修復操作；2)直虛線描述了當前變體中不包含迭代插入偏差時所做的配置操作(空心箭頭連接的隱變遷表示修復操作與配置操作的共有部分).值得注意的是，當pre_fitness≥0.9時使用直虛線描述的配置操作對過程模型進行整體修復.

Fig. 7 Repair instance of the acyclic part based on an optional operation圖7 基于可選操作的非循環部分的修復實例

根據3.1節的方法檢測出變體v(C,D)L+∧N*和v(E,F)L+∧N*×中含有迭代插入偏差，因此選擇執行修復操作.由于變體v(H,I)L?+中沒有迭代插入偏差，則選擇執行配置操作.v(C,D)L+∧N*和v(E,F)L+∧N*×中包含的偏差分別為(IEEsert(D)3(21),Skip(D)1(21))和(IEEsert(F)3(9),Esert(E)1(2))，其中IEEsert(D)3(21)中3表示迭代次數，21表示跡發生的多重次數，該偏差元素的成本為3×21.v(H,I)L?+中包含的偏差為(Esert(H)1(7+21+9+2),Esert(I)1(7+21+9+2)).在v(C,D)L+∧N*和v(E,F)L+∧N*×上執行修復操作后能夠修復的偏差成本為84和29，而準確修復的插入偏差成本則為42和18，也就是說非迭代插入偏差Esert(D)1(21)，Esert(F)1(9)，Esert(E)1(2)無法被準確修復，且跳過偏差Skip(D)1(21)的修復不影響精度，因而不被計入需要準確修復的偏差中.在v(H,I)L?+上執行配置操作后能夠修復的偏差成本為78，而能夠準確修復的插入偏差成本也為78.綜上所述，根據不同情況選擇執行2種操作后的適合度與精度分別為fitness=1-和0.91.由于并發行為中活動發生順序的隨機性會使配置回放圖表的結構較為復雜，因此當vL+∧N*和vL+∧N*×中的活動個數大于2時，可分別根據圖8和圖9中描述的方式尋找配置操作CO，并確定其具體位置.圖8和圖9中使用矩形方框來標注vL+∧N*和vL+∧N*×所對應的配置操作CO.

Fig. 8 Search for configuration operation in concurrency/causality variant圖8 搜索并發/因果變體中的配置操作

Fig. 9 Search for configuration operation in concurrency/conflict variant圖9 搜索并發/沖突變體中的配置操作

非循環部分的變體主要由非一致的行為輪廓關系和行為包含產生，算法1描述了非循環部分產生變體的配置操作與修復操作.

算法1.非循環部分產生變體的選擇性修復.

輸入：網系統N*、事件日志L、所有偏差之和∑d、迭代插入偏差的成本判定函數ψ、選擇任意一個或幾個元素的函數σ、配置操作cO(cO∈CO)、修復操作rO(rO∈RO)；

輸出：配置操作集CO、修復操作集RO.

①CO←?，RO←?;

② for eachei∈Ldo

③ for eachtj∈Tdo

④ for eachak∈Zdo

⑤ ifpre_fitness=1-IDevcost/(|L|+

|ML|)≥0.9 then

⑥CO(∑d);

⑦ else

((a1,a2)‖((a1,a2,…,an),

(an+1,an+2,…,an+m))) then

⑨ ifψ(IDevcost)=0 then

⑩cO1←(Add(a2)∪Hide(a2))

‖(NSkip∪sl-Esert(an+1,an+2,…,an+m)∪sl_Esert(σ(a1,a2,…,an+m)));

vL×∧N*+(a1,a2) then

(Hide(a1)∪Hide(a2));

Nsl_Esert((a1,…,an),(an+1,…,an+m))×)

‖rO2cO2;

(Hide(a1)∪Hide(a2)));

rO3cO3;

τ)×τ)/(τ(τ,

(NHide(a1,a2)‖+‖×,τ)×τ));

rO4cO4;

算法1中，將空集賦予配置操作與修復操作的集合CO，RO(行①).首先判定可預測適合度是否在合理范圍內，如果在合理范圍內則統一使用配置操作修復所有偏差(行⑤～⑦).當可預測適合度不在合理范圍內時，根據以下不同變體中是否包含迭代插入偏差選擇合適的操作：1)構建并發和因果行為關系產生變體的配置操作(行⑧～)或修復操作(行)；2)構建并發和沖突行為關系產生變體的配置操作(行～)或修復操作(行)；3)構建因果和沖突行為關系產生變體的配置操作(行～)或修復操作(行)；4)構建3種行為包含產生變體的配置操作(行～)或修復操作(行).由于迭代插入偏差的發生是隨機的，因此所有自循環插入偏差的情況都被關聯于修復操作集中，即RO(V(L+∧N*),(L+∧N*×),(L∧N*×),(L?,+,×))←χ.不包含插入偏差變體的修復操作與配置操作可互換，即RO(V(L×∧N*+),(L×∧N*),(N*?,+,×))←CO(V(L×∧N*+),(L×∧N*),(N*?,+,×)).最后，返回可能在因果、并發、沖突、行為包含引起變體中執行的所有配置操作集CO與修復操作集RO.

4.2 循環部分的模型修復

循環部分的修復首先需要識別其所發生的位置，由于長度為1或者2的短循環可通過?+算法來識別[40]，因此這里僅對包含3個及以上活動的循環進行分析.設定pstart…lreturn…pend為一條循環路徑，其中pstart和pend分別表示循環路徑上的起始庫所與結束庫所，lreturn表示返回路徑上的行為模式.loopbody=(pf(entry)…pstart,pstart…lreturn…pend)表示一個完整的循環體，也就是循環中所包含的所有活動以及它們之間的行為關系，其中pf(entry)…pstart為非循環部分.判定一個循環體結構的存在需要滿足2點：1)循環體輸入庫所pentry的因果后置庫所pf(entry)與結束庫所lend是一致的，即pf(entry)=pend；2)pf(entry)的執行配置尺寸小于pend，記作pf(entry)=pend∧C(pf(entry))

Fig. 10 Path partitioning of the cyclic part圖10 循環部分的路徑劃分

通過一個不等式來描述返回路徑上的活動：

循環部分可能出現的變體有3種：1)只有事件日志中含有循環路徑；2)非循環部分存在變體(這個問題在4.1節進行討論)；3)返回路徑上存在變體.

修復循環部分需要根據以上3種情況產生的變體執行操作，本節在不考慮非循環部分的情況下對其中2種進行分析：

2) 事件日志與過程模型中都含有循環路徑，但在返回路徑lreturn上的行為不一致.例如，圖11(b)所描述的網系統N*中的循環路徑是lend…lf(entry)=D/C…B/C，而事件日志L中的循環路徑則為lend…lreturn…lf(entry)=D/C…E(A)…B/C，由此產生變體vL(E(A)).圖11(b)中使用彎虛線描述了vL(E(A))中含有迭代插入偏差時對網系統N*所做的修復操作，其位置為loc(Esert(E))∪loc(τ)=p6∪(p6～(p1∪p4)).反之，則采用直虛線所表示的配置操作，其位置為loc(Add(E))=((pC1∪pC3)～(pC2∪pC4)).

當上述第1種情況下非循環部分一致，且返回路徑上沒有活動存在時，2種操作都直接使用隱變遷連接循環路徑，從而準確回放當前變體中的所有偏差.值得注意的是，如果可預測適合度在合理閾值范圍內，則對循環部分統一實行直虛線描述的配置操作.

算法2是在默認非循環部分可回放的前提下，構建循環路徑產生變體的2種操作.首先，將空集賦予循環路徑的修復操作集COloop和配置操作集ROloop(行①).根據網系統N*是否包含循環路徑分2部分進行討論：1)僅事件日志包含循環路徑，此時若返回路徑上沒有活動則修復操作與配置操作相同(行⑤～⑥).當返回路徑上存在活動時，判定可預測適合度是否在合理范圍內，如果在合理范圍內則統一使用配置操作修復所有偏差(行⑦～)，如果不在合理范圍內就根據循環變體中是否包含迭代插入偏差選擇合適的操作(行～).2)事件日志與網系統都包含循環路徑時，仍需要判定可預測適合度是否在合理范圍內，如果在合理范圍內則統一使用配置操作修復所有偏差(行～)，如果不在合理范圍內就根據具體情況在返回路徑上執行配置操作和修復操作(行～).最終，返回對循環路徑上所有情況下可能執行的配置操作集COloop與修復操作集ROloop(行).

算法2.循環部分產生變體的選擇性修復.

輸出：配置操作集COloop、修復操作集ROloop.

①COloop←?，ROloop←?;

② for eache∈Lloopdo

③ for eacht∈Tdo

④ for eacha∈Zdo

⑤ iflend…lf(entry)∈Lloop∧lreturn=? then

⑦ end if

⑨ ifpre_fitness≥0.9 then

⑩CO(∑dloop)；

4.3 基于偏差子結構改善修復操作

對包含迭代插入偏差的變體執行修復操作，無法準確修復其中所有的非迭代插入偏差.針對這一問題，將此類變體中滿足一定行為關系的非迭代插入偏差構造成子結構[42].多個偏差被看作為一個整體會減少事件日志中需要被修復的插入偏差個數.這種方法對于精度改善的邏輯表達式為

Esert((e1),(e2))+/→

其中，E_Devcost為插入偏差的總成本，Esert((e1),(e2),…)+/表示在一個變體中滿足并發/序列關系的偏差元素.插入偏差的個數不能通過沖突子結構減少，因而修復操作的偏差子結構僅由并發和因果關系組成.

5 評 估

實驗將本文方法R與現存3種方法進行比較，并通過分析不同數據集上4種方法修復后的適合度與精度評估它們的性能.現存3種方法分別為：1)在過程模型上使用自循環的方式插入事件日志中可觀測的單個偏差，記作R1；2)構建隱變遷與可配置行為的沖突子結構，從而將事件日志中可配置行為添加到過程模型，記作R2；3)構建滿足并發/序列關系的插入偏差子結構，并使用自循環的方式將其插入過程模型，記作R3.值得注意的是，由于模型中跳過偏差的修復不影響精度，因而4種方法都使用隱變遷跳過的方式對其進行修復.部分現存模型修復方法的性能可以使用Prom框架進行驗證，但它的原始代碼并沒有提供其他方法的改變部分.為保證實驗結果的公平性，我們在此基礎上使用Java語言編寫程序驗證4種修復方法的性能.

5.1 數據集

Table 1 Information of Data Sets表1 數據集信息

5.2 實驗結果

為保證適合度與精度的改善能夠被更加清楚地觀測到，實驗數據默認4種方法的精度初始值均為所有插入偏差都無法被準確修復的結果，并通過變體的逐個修復不斷產生變化.

5.2.1 人造業務流程數據集的實驗結果

圖12中3個數據集的方法R可預測適合度分別為0.76，0.89，0.84，因此R需要通過校驗各種變體中是否包含迭代插入偏差，并根據校驗結果選擇合適的操作對每個變體進行修復.R2使用配置操作對所有偏差進行修復，因此能夠使精度最終為1.然而，R2不能修復迭代插入偏差，以至于適合度無法得到保證.R2修復后的適合度分別為0.76，0.89，0.84，且均不在適合度的合理范圍內.R能夠修復所有偏差，但不能準確修復包含迭代插入偏差變體中的非迭代插入偏差.因此，包含迭代插入偏差變體中的非迭代插入偏差成本占比越小，R的精度就越高.圖12(b)中包含迭代插入偏差變體中的非迭代插入偏差成本在總成本中的占比最小，因此其修復后的精度比圖12(a)(c)分別高出0.16和0.19.相較于R1，R3來說，R能夠準確修復不包含迭代插入偏差變體中的所有非迭代插入偏差.因此，在適合度一樣的前提下R修復后的精度始終高于或等于R3,且R3始終高于或等于R1.圖12中的結果表明，提出方法R在確保適合度合理的情況下，精度在4種方法中最高.

Fig. 12 The running results of an artificial business process圖12 人造業務流程的運行結果

5.2.2 真實業務流程數據集的實驗結果

圖13(a)(c)中方法R的可預測適合度分別為0.86和0.83，因此需要切換執行2種操作修復不同的變體.圖13(a)中使用R修復后的精度遠高于R1和R3，這是由于這個數據集中迭代插入偏差在總偏差成本的占比最大.如圖13(c)所示，雖然R1與R之間精度的差異很大，但R3與R之間精度的差異卻僅為0.05.這是由于圖13(c)的數據集中能夠組建為子結構的偏差最多，其可以有效減少日志中需要修復的插入偏差個數.圖13(a)(c)中，使用R2修復后的適合度為0.86和0.83，因而不在合理范圍內.圖13(b)中R的可預測適合度為0.95，因此使用配置操作對所有偏差進行修復.這種情況下R2和R修復后的適合度與精度相同，也就是適合度為0.95而精度則能夠達到1.圖13中3個數據集的結果均顯示，提出方法R能夠在保證適合度合理的前提下使得精度達到最高.

Fig. 13 The running results of an real-life business process圖13 真實業務流程的運行結果

5.2.3 有循環數據集的實驗結果

圖14中描述了有循環數據集的修復性能，結果表明使用提出方法R修復后可在保證適合度合理的情況下使精度最優.圖14(a)(b)中方法R的預測適合度均為0.92，并使用配置操作修復所有偏差.圖14(c)的預測適合度為0.89，則需要根據當前變體是否包含迭代插入偏差選擇合適的操作.由于循環可能產生很多重復的偏差，因此當非循環部分產生變體中不包含迭代插入偏差時，會造成使用R與R1修復后的精度差異很大.迭代插入偏差成本在總偏差成本中占比越小，R與R1之間精度的差異越大.圖14(b)中迭代插入偏差的占比比圖14(c)低0.09，然而圖14(c)中R相較于R1在精度上的改善反而比圖14(b)高了0.04.造成這種情況的原因為圖14(c)中僅事件日志中有循環，且其返回路徑上無活動.因此，R與R1，R3都使用隱變遷連接循環路徑，從而使3種方法對這種循環產生的偏差具有相同的修復效果.

Fig. 14 The running results of an business process with loop圖14 有循環路徑的業務流程運行結果

5.3 召回度、準確度以及修復活動的數量

召回度是指修復后模型能夠回放的偏差成本在總偏差成本中的占比，準確度是指能夠準確回放的偏差成本在總插入偏差成本中的占比，修復活動是指修復過程中不同標簽或不同位置的偏差個數.選擇圖13(a)、圖14(b)(c)中的3個數據集進行驗證，圖15(a)(c)中方法R的數據集的可預測適合度分別為0.86和0.89，R1，R3，R的召回度最終都能夠達到1,且R的準確度高于R1，R3.然而，圖15(a)和15(c)中R2受迭代插入偏差無法被修復的影響，它們的召回度分別為0.55和0.71.圖15(b)中方法R的數據集的可預測適合度為0.92，R2與R的召回度均為0.78，且準確度為1.

Fig. 15 Recall, accuracy, and number of repair activities圖15 召回度、準確度以及修復活動個數

6 總 結

本文提出一種新的方法來修復事件日志無法回放于過程模型的行為，并根據不同情況選擇合適的修復方式.該方法能夠在確保適合度合理的前提下，盡可能改善精度，其主要從3方面進行分析：

1) 根據迭代插入偏差預測適合度，并設定合理的閾值范圍.

2) 預測適合度合理時，使用配置操作對所有偏差進行修復，從而能夠很好地兼顧適合度與精度.反之，則需要發現事件日志與過程模型之間的變體，并檢測每個變體中是否包含迭代插入偏差.

3) 一個變體包含迭代插入偏差時，將其中所有直接跟隨的非迭代插入偏差根據行為關系構建為子結構，并執行修復操作.反之，則對其執行配置操作.由于本文的修復方法將配置優化引入到模型修復中，因此使部分修復后的變體在精度上得到完整提升.

此外，本文將循環路徑的修復問題單獨提出，根據循環路徑產生變體的不同類型從3方面進行分析.這樣可以針對不同情況對修復方案進行調整，從而進一步改善循環部分的修復性能.

作者貢獻聲明：張力雯調研相關文獻，確定文章的創新點，撰寫文章，設計實驗方案；方賢文把控文章的創新點，對文章內容進行修改與凝練；邵叱風完成文章的實驗；王麗麗檢查文章，配合完成實驗.