基于子組行為關系的過程模型修復

李麗，方賢文

摘要：提出基于子組行為關系的模型修復方法.依據必要事件保序對日志進行過濾，將日志與模型分解成子組日志和模型子塊;基于最優對齊提取子組日志中不擬合的子日志，分析子日志活動間行為關系;對于增加、刪除的行為關系，在子塊中插入、刪除活動及相應的弧和庫所;對于發生變化行為關系，在子塊中改變相應的弧以支撐新行為.

關鍵詞：模型修復;行為關系;子組;塊結構

[中圖分類號]TP301[文獻標志碼]A

Process Model Repair Based on Subgroup Behavior Relationship

LI Li，FANG Xianwen

（College of Mathematics and Big Data，Anhui University of Science and Technology，Huainan 232001，China）

Abstract：A model repair method based on subgroup behavior relationship is proposed.Filter the log according to the necessary event sequence，and decompose the log and model into subgroup logs and model sub blocks.Based on the optimal alignment，the non fitting sub logs in the subgroup logs are extracted，and the behavior relationship between sub log activities is analyzed.For the behavior relationship of adding and deleting，insert and delete activities and corresponding arcs and place in sub blocks.For changing behavior relationships，change the corresponding arc in the sub block to support the new behavior.

Key words：model repair;behavior relationship;subgroup;block structure

現代過程感知信息系統可以使用參考模型驅動軟件工程方法設計.設計的參考模型在實際系統中很難精確實現，流程往往在系統的生命周期中發生變化，人們需要最新的描述流程的模型，通過分析系統的事件日志研究系統的真實行為，從而得到最符合真實流程執行的模型.Vander A H[1]等引入了一種能夠處理不確定映射的概率一致性檢查技術，通過考慮所有可能的映射，避免了選擇單一映射的需要，解決了由于特定映射的使用直接影響到規范事件跡的一致性檢測的問題.如果現有的流程模型不符合實際情況，原則上可以使用流程發現來獲得符合實際情況的模型.Fahland D[2]認為，發現的模型很可能與原始模型沒有相似之處，因此，對已有相關方法對模型進行修復，以得到更加完善的模型.王媛媛[3]等利用已有的一致性檢測技術計算最優校準，通過標識所在庫所定位偏差位置，解決現有模型修正方法僅考慮擬合度而忽略精確度以及簡潔度等指標的問題.Zhang X[4]等通過LPN構建流程模型，研究選擇結構中變遷之間的關系，以確定修復模型的位置，提出一種基于邏輯Petri網（LPN）的模型修復方法.Leemans S[5]等基于模型的塊結構引入對不完備性不太敏感的概率行為關系，研究日志的不完備性對過程發現技術中經常使用的行為關系的影響.Y Xu[6]等考慮新活動與原始活動之間的關系，定義了新活動和原始活動間的邏輯并發關系和因果關系，構造梯形矩陣檢測偏差，添加新活動與原活動構建并行關系，或插入原活動后構建因果關系實現對模型的修復.范濤和方賢文[7]利用因果關系矩陣進行過程挖掘，所得過程模型與事件日志的符合度更高.現有的模型修復方法基本是單線程從全局上進行修復，對檢測的偏差位置與待修復區域之間的對應性考慮較少.本文依據必要事件保序，將模型和日志分解成子塊模型和子組日志，基于最優對齊定位模型偏差位置，在對應模塊中，多線程同時執行模型修復工作.實驗分析結果顯示，本文基于塊結構多線程的模型修復工作較傳統的單線程修復效率更高.

1基礎知識

定義1標簽Petri六元組LN=（P，T;F，ΦP，M0）稱為一個標簽Petri網，滿足下列條件：P表示庫所的有限集合;T表示變遷的有限集合;F（P×T）∪（T×P）為流關系，即有向弧的集合.L：T→Φ∪{ε}是標簽映射函數，Φ為活動標簽的集合.Petri網是一個包含庫所和變遷的二部圖，由有向弧相互連接，記為N=（P，T;F）.

定義2工作流網（WFN） 工作流網是一個具有一個起始庫所和一個結束庫所的Petri網，用來表示建模進程的開始和結束狀態，其結構特性便于業務流程分析.工作流網所有節點都位于從開始到結束的一條有向路徑上.塊結構工作流網是一個可以遞歸地劃分為具有單個入口和出口子網的層次化工作流網.如圖2中（c）流程可以劃分為圖1所示塊結構工作流網的兩個子網.

定義3跡、日志設流程活動的集合為A，事件e是指一個活動的發生，e∈A.跡σ可能是一個空的事件序列，用ε表示跡為空，有σ∈A*.日志L是一個有限非空的跡集合，用LA*表示.

定義4弱序關系設S=（N，M0）是一個網系統，其中，N=（P，T;F）為一個petri網，初始標識為M0.變遷對（t1，t2）∈（T′×T′）滿足弱序關系，當且僅當存在一個由網系統N在初始狀態M0下觸發得到的執行序列σ=t1，t2，…，tn，即N（N，M0）[σ︿ ，且對于j，k∈N，1≤j≤k≤n，有tj=x，tk=y.

定義5[2]行為輪廓設S=（N，M0）是一個網系統，其中，N=（P，T;F）為一個petri網，初始標識為M0，任意的變遷對（t1，t2）∈（T×T）滿足下面關系之一：

（1）若t1t2且t2/ t1，則稱t1和t2為嚴格序關系，記作t1→t2;

（2）若t1/t2且t2t1，則稱t1和t2為嚴格逆序關系，記作t1→-1t2;

（3）若t1/t2且t2/ t1，則稱t1和t2為排他序關系，記作t1+t2;

（4）若t1t2且t2t1，則稱t1和t2為交叉序關系，記作t1‖t2;將所有關系的集合叫做網系統的行為輪廓，記作BP={→，→-1，+，‖}.圖2所示的流程（a）中，活動X和活動Y之間是嚴格序關系，那么，活動Y和活動X之間就是嚴格逆序關系.在流程（b）中，活動X和活動Y之間為排他序關系，那么，活動X和活動Y不會同時出現在同一條跡中，說明活動X和活動Y之間為選擇發生關系.在流程（c）中，活動X和活動Y之間為交叉序關系，那么，活動X和活動Y同時出現在同一條跡中，但活動X和活動Y之間的發生順序不唯一.

定義6必要事件依據活動對業務流程運行的影響程度以及考慮整個業務流程的完整性，將活動分為必要事件活動和一般事件活動.必要事件活動是指在業務流程運行過程中一定會發生的事件活動，必要事件之間的相對發生順序始終保持一致;一般事件活動指在流程運行過程中可以選擇發生的事件活動.

定義7[7]左集和右集設六元組WFN=（P，T;F，Φ，L，M0）為一個工作流網，TP為WFN中所有執行路徑，對于a，b，c∈T，若存在σ=（…，ti-1，ti.ti+1，…）∈TP，使得ti-1=b，ti=a，ti+1=c，那么，b稱為a的左集活動，c稱為a的右集活動.a的所有左集活動稱為a的左集La，類似的有，a的所有右集活動稱為a的右集Ra.

定義8[11]最優對齊最優對齊是跡與模型中從初始狀態到終止狀態的所有完整路徑進行對齊，基于成本函數下，將具有最小對齊成本的對齊結果稱為最優對齊.設σ∈A*，且LN=（P，T;F，Φ，L，M0）為一個Petri網，γ∈（a>>，tτ >>）*是跡σ與LN網的一種對齊，在成本函數c的情況下，對齊成本為C（γ）.其中，C（γ）=∑|γ|-1i=0c（γi）.γopt為最優對齊，當且僅當任意的對齊結果的成本都大于等于最優對齊，即C（γopt）≤C（γ）.其中，C（γopt）表示最優對齊成本.

定義9[7]相似性令W1，W2為兩個工作流網，若ti∈T1∧ti∪T2，則W1，W2關于活動ti的相似性SW1，W2（ti）=a·LW1ti∩LW2tiLW1ti∪LW2ti+β·RW1ti∩LR2tiRW1ti∪RW2ti，那么，流程模型之間的相似性為

SW1，W2=∑ti∈T1∩T2SW1，W2（ti）max‖T1|-2|，‖T2|-2|.

2基于子組行為關系的模型修正

本文提出基于子組行為關系的模型修復，將整個流程模型以必要事件為界限分解成幾個塊結構的子模型，對應地將事件日志以必要事件為界限分解成幾個子組日志，然后將子組日志重放到子塊中，提取出不能完全重放的子日志.分析子日志中活動間的行為關系，將新的行為關系取代參考模型中活動間的行為關系.依據更新后的子組行為關系，在對應子塊的相應位置，對模型進行插入、刪除、改變操作進行修復.

必要事件按照一定的順序發生，從粗粒度的角度看整個流程執行，反映了整個流程的完整性.記錄：日志中流程實際執行數據，會出現與參考模型不完全一致的情況，如插入新活動、刪除一些原活動以及改變原來活動間的行為關系等.算法1描述了依據流程中必要事件間的保序過濾事件日志，以必要事件集合Z和日志L作為算法輸入，對于日志中的每一條跡，依次訪問跡中的每個活動，按順序存儲搜索得到必要活動集合Z′，直至跡中的最后一個活動（算法1中1～3行）;比較搜索得到的必要事件個數、元素以及它們間的相對順序.當搜索得到的必要事件個數|Z′|與給定必要事件集合個數|Z|不一致時，直接拋棄當前跡;當|Z′|=|Z|時，比較集合Z中元素與Z′中元素是否相同，若不相同則拋棄當前跡，若相同則比較必要事件集合中事件間的相對順序，若相對順序保持一致則保留當前跡，反之則拋棄當前跡（算法1中4～9行）.

為了能夠更有針對性地找到日志與模型中出現偏差的位置，根據必要事件集Z，將參考模型M和由算法1得到的過濾后日志L′分解成模型子塊Mi和子組日志L′i，并提取模型子塊活動間行為關系Bi（算法2中1～5行），將子組日志L′i與相應的子塊Mi分別對齊.基于最優對齊，從出現的第一個偏差的前集活動到最后一個偏差的右集活動提取出子組日志中不能完全重放的子日志L″i，并分析得出活動間行為B′i（算法2中6～12行）.

利用算法2得到的子行為關系B′i，與模型子塊活動間的行為關系Bi之間存在差別.算法3描述了依據子組行為關系對參考模型進行修復.以行為關系Bi和B′i作為輸入，比較Bi和B′i中保留相同的活動間行為關系.若活動間關系發生變化，將B′i中的關系替代Bi中對應的關系，在模型中的對應子塊中，對于發生變化的行為關系，刪除維持原行為關系的弧和變遷庫所，插入支撐新行為關系的弧和變遷庫所（算法3中1～7行）;若B′i中出現的新的行為關系b′k，合并到Bi中，在對應子塊模型中插入相應的活動和連接活動的弧（算法3中8～10行）;若Bi中存在B′i中沒有出現的行為關系bk，從Bi中刪除，在模型的對應子塊中，刪除相應活動和連接活動的弧，最終得到一個新的子組行為關系B″i和修復后的模型M′（算法3中10～15行）.

3實例分析與實驗仿真

隨著電商行業的崛起，傳統的貨品交易流程在一定程度上發生了變化.貨物交易業務流程主要包括以下步驟：買方下單、訂單排號、倉庫備貨、選擇快遞發出、貨物送達、確認收貨、退換貨、結清貨款、交易成功、交易失敗、關閉訂單等.表1列出了貨物交易流程中各個字母代表的事件，貨物交易流程的事件日志如表2所示，圖3為貨物交易業務流程的參考模型.表2所示的事件日志與參考模型并不擬合，比如物流退回M，買方寄回N，運費險理賠R等事件的出現，在日志與模型差別較大的情況下，有必要依據事件日志對參考模型進行修正.將日志與整個模型對齊，這種全局搜索對偏差檢測缺乏針對性，有必要將日志與模型區塊化，有針對性的對模型相應子塊中出現偏差的位置進行修復.

本文以動機例子所示的貨物交易流程為例，驗證本文算法的有效性.給定必要事件集Z={A，E，I，U}，即買方下單后，經倉庫備貨到貨物送達后訂單關閉這一完整流程.經過算法1得到過濾后日志L′如表3所示.

為了確定偏差出現的具體位置，將圖3參考模型M依據必要事件分解成3個子塊模型，日志也分解成對應的三個子組日志，每個子組之間的最優對齊：對于每個自組日志而言，從出現的第一個偏差的左集活動開始，到最后一個偏差的右集活動結束提取出不能完全重放到模型中的子日志.

圖4為修復后模型.通過刪除、增加、變化操作進行修復的位置已經用虛線所示的橢圓高亮顯示.與參考模型對比可知，在子塊M1中，活動D與活動B在參考模型中為排他關系，而修復后模型中活動B與D為嚴格序關系;在子塊M2中，修復后對應子塊刪除了活動G，刪除了與其相連的所有弧，增加了與活動E為嚴格序關系的活動V和相應的庫所，構成了一個自循環的子結構;在子塊M3中，增加了兩個活動M和N，分別與活動J和K為嚴格序關系，增加了相應的庫所和與活動S為排他關系的活動R.應用定義9中的公式計算參考模型M1和修復后模型M′1的相似性為SM1，M′1=11.621≈0.552 4，具體的計算方法見參考文獻[9].

若參考模型中平均有m個活動，平均每個活動對齊所需的時間為n，檢測出所需修復偏差的個數為s，平均完成一次修復花費的時間為t，依據必要事件將模型分解成的子塊個數為u，則一般單線程的修復工作所需時間復雜度為O（mn+st）.本文所提出的基于子組的多線程修復工作所需時間復雜度為Omn+stn，分解的子組個數越多，所需的時間越少，工作效率越高.

依據定義的必要事件，提出了基于模型塊結構分段將事件日志與模型進行對齊，將單線程的對齊問題轉換為多線程進行，在基于對齊的偏差檢測階段減少了所需時間.基于子組行為關系的模型修復工作也將以多線程代替原來的單線程工作，使修復工作更具針對性，提高了模型修復的效率.

4結束語

本文提出了基于子組行為關系的模型修正方法.筆者基于必要事件將日志轉換為子組日志，將參考模型轉換為對應模型子塊.將子組日志與模型子塊分別對齊，依據最優對齊提取子組日志不能完全重放到模型中的子日志，分析子日志中各活動間的行為關系，與參考模型對應子塊的活動間行為關系進行對比，通過增加、刪除、改變操作，得到新的子組行為關系.在對應子塊中進行插入、刪除變遷和庫所及連接二者之間的弧，對模型進行修復.

參考文獻

[1]Van der Aa H，Leopold H，Reijers H A.Efficient process conformance checking on the basis of uncertain eventtoactivity mappings[J].IEEE Transactions on Knowledge and Data Engineering，2019，32（5）：927940.

[2]Fahland D，Van der Aalst W M P.Model repair—aligning process models to reality[J].Information Systems，2015（47）：220243.

[3]王媛媛，杜玉越，祁宏達.基于邏輯Petri網的模型修正方法[J].計算機集成制造系統，2018，24（7）：17361746.

[4]Zhang X，Du Y，Qi L，et al.A Method for Repairing Process Models Containing a Choice With Concurrency Structure by Using Logic Petri Nets[J].IEEE Access，2019（7）：1310613120.

[5]Leemans S，D Fahland，Aalst W.Discoveonal Conference on Applications and Theory of Petri Nets and Concurrency. Springer，Cham，ring BlockStructured Process Models from Incomplete Event Logs[C]//Internati 2014.

[6]Y Xu ，Y Du，Luan W，et al.Repairing Process Models with Logical Concurrent and Casual Relations via Logical Petri Nets[J].IEEE Access，2018（99）：116.

[7]范濤，方賢文.一種基于Petri網和因果關系矩陣的事件日志過程挖掘方法[J].牡丹江師范學院學報;自然科學版，2020（4）：1014.

[8]段瑞，方歡.基于Petri網的電梯控制系統建模與分析[J].牡丹江師范學院學報：自然科學版，2018（3）：2428.

[9]李東月，方歡.基于活動發生關系的流程相似性度量方法[J].控制理論與應用，2020，37（9）：20112019.

編輯：琳莉