基于子組行為關(guān)系的過程模型修復(fù)

李麗，方賢文

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

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

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

1基礎(chǔ)知識(shí)

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

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

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

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

定義5[2]行為輪廓設(shè)S=（N，M0）是一個(gè)網(wǎng)系統(tǒng)，其中，N=（P，T;F）為一個(gè)petri網(wǎng)，初始標(biāo)識(shí)為M0，任意的變遷對(duì)（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）中，活動(dòng)X和活動(dòng)Y之間是嚴(yán)格序關(guān)系，那么，活動(dòng)Y和活動(dòng)X之間就是嚴(yán)格逆序關(guān)系.在流程（b）中，活動(dòng)X和活動(dòng)Y之間為排他序關(guān)系，那么，活動(dòng)X和活動(dòng)Y不會(huì)同時(shí)出現(xiàn)在同一條跡中，說明活動(dòng)X和活動(dòng)Y之間為選擇發(fā)生關(guān)系.在流程（c）中，活動(dòng)X和活動(dòng)Y之間為交叉序關(guān)系，那么，活動(dòng)X和活動(dòng)Y同時(shí)出現(xiàn)在同一條跡中，但活動(dòng)X和活動(dòng)Y之間的發(fā)生順序不唯一.

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

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

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

定義9[7]相似性令W1，W2為兩個(gè)工作流網(wǎng)，若ti∈T1∧ti∪T2，則W1，W2關(guān)于活動(dòng)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ù)，將整個(gè)流程模型以必要事件為界限分解成幾個(gè)塊結(jié)構(gòu)的子模型，對(duì)應(yīng)地將事件日志以必要事件為界限分解成幾個(gè)子組日志，然后將子組日志重放到子塊中，提取出不能完全重放的子日志.分析子日志中活動(dòng)間的行為關(guān)系，將新的行為關(guān)系取代參考模型中活動(dòng)間的行為關(guān)系.依據(jù)更新后的子組行為關(guān)系，在對(duì)應(yīng)子塊的相應(yīng)位置，對(duì)模型進(jìn)行插入、刪除、改變操作進(jìn)行修復(fù).

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

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

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

3實(shí)例分析與實(shí)驗(yàn)仿真

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

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

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

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

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

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

4結(jié)束語(yǔ)

本文提出了基于子組行為關(guān)系的模型修正方法.筆者基于必要事件將日志轉(zhuǎn)換為子組日志，將參考模型轉(zhuǎn)換為對(duì)應(yīng)模型子塊.將子組日志與模型子塊分別對(duì)齊，依據(jù)最優(yōu)對(duì)齊提取子組日志不能完全重放到模型中的子日志，分析子日志中各活動(dòng)間的行為關(guān)系，與參考模型對(duì)應(yīng)子塊的活動(dòng)間行為關(guān)系進(jìn)行對(duì)比，通過增加、刪除、改變操作，得到新的子組行為關(guān)系.在對(duì)應(yīng)子塊中進(jìn)行插入、刪除變遷和庫(kù)所及連接二者之間的弧，對(duì)模型進(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].計(jì)算機(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é)報(bào);自然科學(xué)版，2020（4）：1014.

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

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

編輯：琳莉