基于行為輪廓的模塊化流程模型修復方法

盛夢君 方賢文 邵叱風

摘 要：模型修復是業務流程領域中新的優化方法。為了讓流程模型對系統的描述更加準確，使模型修復方法系統化，且進一步降低成本，減少以往修復算法的迭代次數和時間復雜度，可運用基于行為輪廓的模塊化修復新方法，由分解、過濾、選擇、修復、組合五個模塊構成。首先，使用極大分解算法對模型進行分解，使流程模型呈片段狀，便于篩選出問題片段;然后，使用過濾算法對所有片段進行線性過濾從而縮短通過行為輪廓來選擇劣子模型的時間，再使用感應挖掘算法對劣子模型進行修復;接著，再對修復后的劣子模型和優子模型進行組合，從而使得修復后的模型能夠重放事件日志，且能夠與原始模型盡可能保持行為相似性，最后通過實驗分析驗證了所提方法的可行性。

關鍵詞：模型修復;過程挖掘;行為輪廓;分解;線性過濾

中圖分類號： TP391.9文獻標志碼：A

文章編號：1672-1098（2021）02-0080-07

收稿日期：2020-11-10

基金項目：國家自然科學基金資助項目（61402011，61572035）;安徽省自然科學基金資助項目（1508085MF111，1608085QF149）;安徽省高校自然科學基金資助項目（KJ2016A208）

作者簡介：盛夢君（1996-），女，安徽合肥人，在讀碩士，研究方向：perit網理論。

Modular Process Model Repair Method Based on Behavioral Contours

SHENG Mengjun，FANG Xianwen，SHAO Chifeng

（School of Mathematics and Big data， Anhui University of Science and Technology， HuainanAnhui232001， China）

Abstract：Model repair is a new optimization method in the field of business process.To make the process model describe the system precisely， and to systemize the model repair method ， cut the cost and reduce the iteration times and time consumption of the previous repair algorithm， a new modular repair method based on model decomposition and behavioral contours may be applied， which consists of five modules of decomposition， filter， selection， repair and combination. Firstly， the maximum decomposition algorithm is used to decompose the model into fragments， easy to filter out the problem fragments. Then， the filtering algorithm is used to filter all fragments linearly therefore shortening the time of selecting the inferior sub model， which will be repaired by applying the induction mining algorithm， with the behavioral contours. Finally， the repaired inferior sub model and the superior sub model are combined to make the repaired model able to replay the event log （i.e. the consistent log） and maintain the behavior similarity with the original model as much as possible. The feasibility of the proposed method is verified by experimental analysis.

Key words：process model repair; process mining; behavioral contours; decomposition; linear filtering

模型修復是一種新的過程挖掘技術，它將事件日志和流程模型作為輸入，通過對日志進行分析來發現流程模型中的偏差，進而對模型進行修復。目前，可以通過事件日志來研究系統的真實情況，運用過程挖掘技術得到流程模型。但是，由于挖掘出能夠確切描述現實生活的系統模型是困難的，且流程往往會在系統的生命周期中發生變化。因此，對于模型修復問題的研究具有重要意義。

關于模型修復國內外學者已經做了很多工作。過程挖掘技術一共有三類應用：模型發現、一致性檢測和過程增強，模型修復屬于過程增強。評價過程模型的質量有四個標準：擬合度、精確度、泛化度和簡化度。工作流網中適應性感知控制流修復的方法通過事件日志將不符合要求和符合要求的跡分開，將不合格的跡分解為不合格的子日志，每個子日志都能在相應的子流程工作流網中被發現，然后以這種方式將這些子流程添加到初始模型中，使得修復后的模型能夠成功重放給定的事件日志[1]。這種方法還允許刪除不常使用的模型片段，令修復后的模型更簡單，但這種刪除方式略顯暴力，并不是簡化模型的最佳方法。基于此，通過一種簡化模型結構的方法，使得模型仍然可以重放日志中描述的大多數行為[2-3]。現有的模型修復方法大多側重于通過一致性檢驗找到事件日志與模型之間的偏差，但未側重修復偏差問題[4]。基于對齊的概念，建議改變運營分配成本，通過調查所有可能的修復空間，提出并評估了一組最優修復算法，將Petri網的修復問題簡化為了優化問題[5]。通過考慮過程挖掘中應用分而治之原則的問題，提出一個過程發現的模式，該修復方法也是利用分而治之的思想進行模塊化修復[6]。通過分析事件日志來研究系統的真實情況，發現真實系統模型，工程師可以使用一致性檢驗技術來診斷觀察事件日志和流程模型之間的差異[7]。但一味地提高修復后模型的適應度或簡化度會讓修復成本大大提高，并且修復過程中事件日志遍歷的次數過大，與其修復模型不如重新通過事件日志挖掘新模型。因此，進一步降低修復成本，減少以往修復算法的迭代次數和遍歷事件日志的次數以及修復算法的時間復雜度是本文針對的問題。

針對上述問題，本文提出了基于行為輪廓的流程模型修復方法，運用模型分解及線性過濾的方法對模型進行修復，盡可能地保持初始模型結構不改變、原模型可讀以及結構良好的性能來進一步降低修復成本，降低修復算法的時間復雜度。此外，還給出了過濾模塊以及選擇模塊中相應的算法，從而較好地提升了模型修復的有效性。

1 基礎知識

定義1[8]（流程模型Petri網）滿足以下條件的四元組N=（P，T，F，C）稱作一個流程模型Petri網：

（1）P是有限非空庫所集，T是有限非空變遷集;

（2）P∪T≠φ且P∩T=φ;

（3）F（P×T）∪（T×P）是N中的流關系，（P∪T，F）是強連通圖;

（4）dom（F）∪cod（F）=P∪T，其中dom（F）={x∈P∪T|y∈P∪T∶（x，y∈F）} cod（F）={x∈P∪T|y∈P∪T∶（y，x∈F）};

（5）C={and，xor，or}是流程網的結構類型。

定義2[10]（行為輪廓）設P=（A，I，C，F，T）是一個流程模型（x，y）∈（（N∪F）×（N∪F））是滿足下列關系中的一個：

（1）嚴格序關系→p，如果xpy且ypx;

（2）排他關系+p，如果xpy且ypx;

（3）交叉序關系‖P，如果xpy且ypx。

以上三種關系的集合是P=（A，I，C，F，T）的行為輪廓。

定義3（流程模型）將流程模型設定為一個元組M=（P，T，F，J，ε，σ，Mi，Mf），P是庫所集p∈P;T是變遷集t∈T;F是連接所有直接跟隨庫所與變遷之間的流關系，F（P×T）（T×P）;J是排序的有限集合;ε是滿射函數，將每個變遷關聯到一個排序，T→J;σ是指定函數，將所有變遷映射到活動集或靜默變遷中，T→A∪{τ}，σ（ti）=（ei）=a，a∈A，τ∈T，σ（τ）A;Mi是初始標識;Mf是終止標識。

定義4（事件日志，跡）事件日志是一個數學模型，用于捕獲有關動態系統執行的歷史信息。從形式上講，定義Σ是一組動作集，跡l∈Σ*是一個動作序列，L∈ΙΒΣ*）是一個事件日志即一組跡的多元集。其中每組跡都是將系統（即流程實例）的執行描述為一系列觀察到的事件。因為可以存在多個具有相同跡的情況，如果跡的頻率不相關，將記錄日志稱為一組跡L={l1，…，ln}。

定義5[11]（工作流網的有效分解）設N∈UN是一個帶標簽函數l的工作流網。D={N1，N2，…，Nn}UN是一個有效的分解，當且僅當：

—任意1≤i≤n，Ni=（Pi，Ti，Fi，li）是一個Petri網，

—任意1≤i≤n，li=lΓTi，

—任意1≤i

—任意1≤i

—N=∪1≤i≤nNi

D（N）對任意網N是一個有效分解集。

2 本文方案

（1） 模塊化修復框架

本文考慮的修復問題：給定工作流網N和事件日志L，事件日志L不完全符合N，提出了一種基于模型分解及線性過濾的模塊化修復方法，構造模型Nr（修復后模型），讓Nr能夠重放L。主要思想是基于分而治之的原則篩選出需要修復的片段，修復方法由構建的塊組成，每個塊執行其中一個步驟，模塊化模型修復方法如圖2所示，構建的塊分別為：①分解;②過濾;③選擇;④修復;⑤組合;⑥案例分析。弧表示塊之間的數據傳輸。

本文基于模塊化模型修復的一般方法如下：該方法的輸入是一組（L，N），其中L是一組事件日志，N是一個不完全符合事件日志的初始模型。在分解塊中，使用極大分解算法[12]將模型N分解成幾個片段，分解結果是唯一的。在過濾塊中，本文給出了一個包含在過濾塊中線性過濾算法，算法將這些模型片段即子模型的直鏈結構進行過濾篩除，直鏈結構不執行下一步選擇過程，從而直接保留直鏈的原始模型片段，最后與修復后的模型片段組合。在選擇塊中，選擇算法將分解后的子模型的執行序列與新增的兩條事件日志的跡運用行為輪廓相關知識進行比對，符合事件日志的跡即為優子模型，反之為劣子模型。在修復塊中，將剩下的劣子模型與事件日志對比分析運用感應挖掘算法[13]進行修復。在組合塊中，將過濾掉的直鏈結構、優子模型和修復后的子模型進行組合，得到能夠重放事件日志修復后的模型。

（2）使用極大分解方法進行模塊化修復

本文提出的模塊化修復方法在每個構建的塊中使用特定算法。其中分解塊中使用的極大分解方法是一個有效分解，極大分解是基于邊緣的劃分，其定義如下：每個變遷嚴格地位于單個片段中，具有唯一標簽的變遷被放置在片段的邊界上，在片段之間需要有因果關系的支持。因此，對于每個變遷，一個在初始網中具有唯一標簽的變遷將存在于兩個或者多個片段中，最后，拆分保存了網絡的初始標識。如果庫所在初始網中被標記了，那么它在片段中也是被標記的。在給定的系統網中，有且僅有一個極大分解，且分解結果是唯一的。極大分解網能夠很容易地通過融合有相同標簽的變遷組合回完整的網。

將文獻中提出的極大分解算法應用到分解塊中，并在此基礎上開發了過濾塊和選擇塊的算法，其工作原理如下：如果網片段發現可見的變遷，可依據decompose、handlePlace、handlePlace recursively三個函數的工作原理調用以后對其進行分解。即decompose函數從初始網中任意庫所開始，當有庫所需要遍歷時調用handlePlace函數，調用handlePlace函數后，調用handlePlace recursively函數來遍歷此流程中庫所的前置節點和后繼節點。以初始網圖1中庫所p2為例，調用后三個函數后它的前置節點為變遷A和變遷G，后繼節點為變遷B，因此分解后片段為圖3中SN2片段。

初始網圖1中完整流程模型分解后得到的全部子模型如圖3所示;過濾塊中運用線性過濾算法再將其進行過濾，若子模型中的庫所前、后集個數分別為1或0，則可直接過濾此直鏈結構，直鏈結構不執行下一步選擇過程，過濾后的模型片段如圖4所示;過濾后選擇劣子模型進行修復，選擇塊中的選擇算法將過濾后模型片段的執行序列與增加的事件日志運用Petri網中行為輪廓定義進行比對，符合的為優子模型，反之為劣子模型。過濾算法及選擇算法如下：

輸入：ModelSet ε

輸出：ModelSet φ

ModelSetε;

ModelSetφ=Null;

1）for each part model A in ModelSetε;

2）pre setof place=prsp;

3）post setof place=posp;

4）if |prsp|=|posp|=1 || （|prsp |=1 and |posp|=0）|| （|posp |=1 and |prsp|=0）

5）part model A is null;

6）break;

7）else

8）Return （prsp X posp） of A

9）end if

10）φ.add（part model）;

11）end for each

12）for each （x，y） in（prsp X posp）

13）for each Trace in New Log

14）if x in Trace and y not in pre of x;

15）return （x，y） ， part Model of （x，y）

16）end for each

17）end all

文獻[13]已有許多流程發現的算法，本文使用感應挖掘[14]保證模型發現的適應性（零噪音閾值的不頻繁感應挖掘）。它使用順序和回歸的感應推理來構建一個可以轉化為工作流網結構的過程樹。

假設圖3中的模型中變遷C和E與其行為順序不完全一致，如果二者同時出現，則在事件日志的跡中E總是在C之前出現，根據行為輪廓，即E和C是嚴格序關系，記作E→C，也就是說事件日志包含跡和，沒有C在E之前出現的跡。應用本文提出的選擇算法，如圖4所示，得到的片段SN4不完全適合日志，因此我們使用感應挖掘算法發現了這個正確的工作流網片段SN4′如圖5所示。

在發現正確的模型片段并組合所有片段之后，得到了如圖6所示的網。這個模型與事件日志的跡和完全適應。可以看到修復過的模型不是工作流網，它包含源位置的標識和初始標識中的初始庫所。網的最終標識包括在接收器和庫所中的兩個托肯，這個模型可以通過添加靜默的開始和結束變遷很容易地轉換成等效的工作流網。考慮到開始庫所和結束庫所限制模型的行為并可能產生死鎖，從而將它們刪除。但在模型運行中增加可能發生的變遷，會稍微降低模型的精度，避免這樣的問題最好不要在修復過程中更改片段邊界節點變遷，因此可以通過考慮更大的片段來完成修復。

3 案例分析

本節以上述退換貨系統為例計算修復前后模型的適合度來評估所提方法的可行性，并與Fahland修復方法進行對比實驗。

在給定事件日志L和模型M上進行實驗評估。如表2所示，事件日志L一共包含事件總數為：|N|=12 781，其運行次數依次為{58，87，230，270，198，205，109，26，100，12，49，210，180，33，101}。事件日志中總共有15條完整有效的執行序列，大小分別為{6，7，10，11，12，15，16，14，13，15，14，13，10，8，7}，預定義模型上的所有發生序列大小依次為{7，7，10，10，12，15，16，14，12，15，15，12，10，7，7}。將日志與模型進行最優校準，得到15組最優校準。

分析得到的15組最優校準，這些校準中的不一致由偏差引起，偏差分為日志插入偏差和網N跳過偏差，如案例1即n=1中是日志插入偏差，n=2中是網N跳過偏差。因此，日志與初始模型之間的擬合度為

f初始=1-∑ni=1Li∑mij=1Ccostj（ML（εi）+MM（δj））Li=1-2 63221 996≈0.880 34<1（1）

式中：L表示每組發生序列的發生次數即實例數，n表示校準的組數（本文有15組），Ccost表示每組校準的偏差成本，這里將所有偏差成本設為1，ML表示日志發生序列，MM表示模型中的發生序列，ε表示日志發生序列的元素個數，δ表示模型發生序列的元素個數，而日志與修復后模型之間的適合度為1，因此本文的修復方法具有可行性。

根據本文所提算法的第12～17兩層嵌套循環可以看出，其算法的時間復雜度為O（MN）。運用Fahland方法對案例模型修復結果如圖7所示，與本文所提方法的對比實驗結果如表3所示。

4 結論

本文在已有研究的基礎上提出了一種基于模型分解和線性過濾的模塊化流程模型修復方法，通過線性過濾算法進一步有效降低了修復的成本和修復算法的時間復雜度，并且盡可能保持了初始模型結構。首先將初始模型運用極大分解算法分解，其次使用過濾算法進行線性過濾，再使用選擇算法選擇劣子模型然后通過感應挖掘重新發現模型片段，最后對模型片段進行組合得到修復后模型。

本文的方法可能略微降低了模型的精度，對于此問題，計劃提出更細微的分解技術以避免片段邊界節點的相關問題。基于分解的模型修復也會考慮到擬合度，精確度，泛化度和簡化度的組合度量，此外修復是基于模型，對模型分解的相關問題可能非常有幫助，這也是未來可以研究的方向之一。

參考文獻：

[1] FAHLAND D，VAN DER AALST，W M P.Model Repair-Aligning Process Models to Reality[J].Information Systems，2015，47（2）： 220-243.

[2] FAHLAND D，VAN DER AALST，W M P.Simplifying discovered process models in a controlled manner[J].Information Systems，2013，38（4）： 585-605.

[3] DE SAN PEDRO J，CARMONA J，CORTADELLA.Log-Based Simplification of Process Models[C]//Business process management： 13th International Conference.BPM 2015，Innsbruck，Austria，2015，9 253：457-474.

[4] VAN DER AALST W M P.Process mining： Discovery conformance and enhancement of business process[M].Berlin Germany： Springer-Verlag，2011：64-162.

[5] ADRIANSYAH A.Aligning observedandmodeled behavior[J].TechnischeUniversittndhoven，2014：12（3）：29-41.

[6] Verbeek H M W，VAN DER AALST W M P，Munoz-Gama J.Divide and conquer： a tool framework for supporting decomposed discovery in process mining[J].Computer Journal，2017，60（11）：1 649-1 674.

[7] VAN DER AALST W M P.Process Mining：Data Science in Action[J].Springer，Berlin，Heidelberg，2016，10（2）：3-23.

[8] 吳哲輝.Petri網理論[M].北京： 機械工業出版社，2006： 6-22.

[9] SMIRNOV S，WEIDLICH M，MENGLING J.Business Process Model Abstraction based on Behavioral Profiles [C]//International Conference on Service-Oriented Computing （ICSOC 2010）.San Francisco，US，2010： 1-16.

[10] VAN DER AALST W M P.Decomposing Petri Nets for Process Mining： A GenericApproach [J].Distributed and Parallel Databases，2013，31（4）： 471-507.

[11] MITSYUK A A，LOMAZOVA I A，et al.Process model repair by detecting unfitting fragments [C]//Supplementary Proceedings of the Sixth International Conference on Analysis of Images，Social Networks and Texts （AIST 2017）.CEUR-WS.org，Moscow，Russia，2017： 301-313.

[12] VANDONGEN B F，CARMONA J，CHATAIN T.A unified approach for measuringprecision and generalization based on anti-alignments[C]//14th International Conference on Business Process Management （BPM）.Fed Univ State Rio de Janeiro，Rio de Janeiro，Brazil，Springer，2016： 39-56.

[13] LEEMANS S J J，FAHLAND D，VAN DER AALST W M P.Discovering block-structuredprocess models fromincomplete event logs [C]//Application and theory of petri nets and concurrency： 35th International Confernece.PETRI NETS 2014，Tunis，Tunisia，Proceedings.2014：91-110.

[14] DONGEN B F V，MEDEIROS A K A D，VERBEEK H M W，et al.The ProM Framework： A New Era in Process Mining Tool Support[C]//International Conference on Application & Theory ofPetri Nets.SpringerBerlin Heidelberg，2005，3 536：444-454.

[15] HOMPES B F A.On Decomposed Process Discovery：How to Solve a Jigsaw Puzzle with Friends[D].Master's thesis，Eindhoven University of Technology，De Zaale，Eindhoven，Netherlands，2014.

[16] Aalst W，Verbeek H.Process Discovery and Conformance Checking Using Passages[J].Fundamenta Informaticae，2014，131（1）： 103-138.

[17] GNTHER C W，VAN DER AALST W M P.Fuzzy mining： Adaptive process simplification based onmulti-perspective metrics[C]//5th International Conference on Business Process Management.Brisbane，Australia，BPM，2007，4 714： 328-343.

[18] VAN DER AALST W M P，ADRIANSYAH A A，VANDDONGEN B F.Replaying History on Process Model for Conformance Checking and Performance Analysis [J].Wiley Interdisciplinary Reviews-Data Mining and Knowledge Discovery，2012，2（2）：182-192.

[19] MACEDO N，JORGE T，CUNHA A.A Feature-Based Classification of Model Repair Approaches[J].IEEE Transaction on Software Engineering，2017，43（7）：615-640.

[20] POLYVYANYY A，VAN DER AALST W M P，Terhofstede A H M，et al.Impact-Driven Process Model Repair[J].ACM Transaction on Software Engineering and Methodology，2017，25（4）：1-60.

（責任編輯：李 麗，范 君）