李麗，方賢文

摘要：提出基于子組行為關(guān)系的模型修復(fù)方法.依據(jù)必要事件保序?qū)θ罩具M(jìn)行過濾，將日志與模型分解成子組日志和模型子塊;基于最優(yōu)對齊提取子組日志中不擬合的子日志，分析子日志活動間行為關(guān)系;對于增加、刪除的行為關(guān)系，在子塊中插入、刪除活動及相應(yīng)的弧和庫所;對于發(fā)生變化行為關(guān)系，在子塊中改變相應(yīng)的弧以支撐新行為.

關(guān)鍵詞：模型修復(fù);行為關(guān)系;子組;塊結(jié)構(gòu)

[中圖分類號]TP301[文獻(xiàn)標(biāo)志碼]A

Process Model Repair Based on Subgroup Behavior Relationship

LI Li，F(xiàn)ANG 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

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

1基礎(chǔ)知識

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

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

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

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

定義5[2]行為輪廓設(shè)S=（N，M0）是一個網(wǎng)系統(tǒng)，其中，N=（P，T;F）為一個petri網(wǎng)，初始標(biāo)識為M0，任意的變遷對（t1，t2）∈（T×T）滿足下面關(guān)系之一：

（1）若t1t2且t2/ t1，則稱t1和t2為嚴(yán)格序關(guān)系，記作t1→t2;

（2）若t1/t2且t2t1，則稱t1和t2為嚴(yán)格逆序關(guān)系，記作t1→-1t2;

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

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

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

定義7[7]左集和右集設(shè)六元組WFN=（P，T;F，Φ，L，M0）為一個工作流網(wǎng)，TP為WFN中所有執(zhí)行路徑，對于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]最優(yōu)對齊最優(yōu)對齊是跡與模型中從初始狀態(tài)到終止?fàn)顟B(tài)的所有完整路徑進(jìn)行對齊，基于成本函數(shù)下，將具有最小對齊成本的對齊結(jié)果稱為最優(yōu)對齊.設(shè)σ∈A*，且LN=（P，T;F，Φ，L，M0）為一個Petri網(wǎng)，γ∈（a>>，tτ >>）*是跡σ與LN網(wǎng)的一種對齊，在成本函數(shù)c的情況下，對齊成本為C（γ）.其中，C（γ）=∑|γ|-1i=0c（γi）.γopt為最優(yōu)對齊，當(dāng)且僅當(dāng)任意的對齊結(jié)果的成本都大于等于最優(yōu)對齊，即C（γopt）≤C（γ）.其中，C（γopt）表示最優(yōu)對齊成本.

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

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

2基于子組行為關(guān)系的模型修正

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

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

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

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

3實例分析與實驗仿真

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

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

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

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

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

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

4結(jié)束語

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

參考文獻(xiàn)

[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]王媛媛，杜玉越，祁宏達(dá).基于邏輯Petri網(wǎng)的模型修正方法[J].計算機集成制造系統(tǒng)，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網(wǎng)和因果關(guān)系矩陣的事件日志過程挖掘方法[J].牡丹江師范學(xué)院學(xué)報;自然科學(xué)版，2020（4）：1014.

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

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

編輯：琳莉