盛夢君 方賢文 邵叱風(fēng)
摘 要:模型修復(fù)是業(yè)務(wù)流程領(lǐng)域中新的優(yōu)化方法。為了讓流程模型對系統(tǒng)的描述更加準(zhǔn)確,使模型修復(fù)方法系統(tǒng)化,且進(jìn)一步降低成本,減少以往修復(fù)算法的迭代次數(shù)和時(shí)間復(fù)雜度,可運(yùn)用基于行為輪廓的模塊化修復(fù)新方法,由分解、過濾、選擇、修復(fù)、組合五個模塊構(gòu)成。首先,使用極大分解算法對模型進(jìn)行分解,使流程模型呈片段狀,便于篩選出問題片段;然后,使用過濾算法對所有片段進(jìn)行線性過濾從而縮短通過行為輪廓來選擇劣子模型的時(shí)間,再使用感應(yīng)挖掘算法對劣子模型進(jìn)行修復(fù);接著,再對修復(fù)后的劣子模型和優(yōu)子模型進(jìn)行組合,從而使得修復(fù)后的模型能夠重放事件日志,且能夠與原始模型盡可能保持行為相似性,最后通過實(shí)驗(yàn)分析驗(yàn)證了所提方法的可行性。
關(guān)鍵詞:模型修復(fù);過程挖掘;行為輪廓;分解;線性過濾
中圖分類號: TP391.9文獻(xiàn)標(biāo)志碼:A
文章編號:1672-1098(2021)02-0080-07
收稿日期:2020-11-10
基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(61402011,61572035);安徽省自然科學(xué)基金資助項(xiàng)目(1508085MF111,1608085QF149);安徽省高校自然科學(xué)基金資助項(xiàng)目(KJ2016A208)
作者簡介:盛夢君(1996-),女,安徽合肥人,在讀碩士,研究方向:perit網(wǎng)理論。
Modular Process Model Repair Method Based on Behavioral Contours
SHENG Mengjun,F(xiàn)ANG 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
模型修復(fù)是一種新的過程挖掘技術(shù),它將事件日志和流程模型作為輸入,通過對日志進(jìn)行分析來發(fā)現(xiàn)流程模型中的偏差,進(jìn)而對模型進(jìn)行修復(fù)。目前,可以通過事件日志來研究系統(tǒng)的真實(shí)情況,運(yùn)用過程挖掘技術(shù)得到流程模型。但是,由于挖掘出能夠確切描述現(xiàn)實(shí)生活的系統(tǒng)模型是困難的,且流程往往會在系統(tǒng)的生命周期中發(fā)生變化。因此,對于模型修復(fù)問題的研究具有重要意義。
關(guān)于模型修復(fù)國內(nèi)外學(xué)者已經(jīng)做了很多工作。過程挖掘技術(shù)一共有三類應(yīng)用:模型發(fā)現(xiàn)、一致性檢測和過程增強(qiáng),模型修復(fù)屬于過程增強(qiáng)。評價(jià)過程模型的質(zhì)量有四個標(biāo)準(zhǔn):擬合度、精確度、泛化度和簡化度。工作流網(wǎng)中適應(yīng)性感知控制流修復(fù)的方法通過事件日志將不符合要求和符合要求的跡分開,將不合格的跡分解為不合格的子日志,每個子日志都能在相應(yīng)的子流程工作流網(wǎng)中被發(fā)現(xiàn),然后以這種方式將這些子流程添加到初始模型中,使得修復(fù)后的模型能夠成功重放給定的事件日志[1]。這種方法還允許刪除不常使用的模型片段,令修復(fù)后的模型更簡單,但這種刪除方式略顯暴力,并不是簡化模型的最佳方法。基于此,通過一種簡化模型結(jié)構(gòu)的方法,使得模型仍然可以重放日志中描述的大多數(shù)行為[2-3]?,F(xiàn)有的模型修復(fù)方法大多側(cè)重于通過一致性檢驗(yàn)找到事件日志與模型之間的偏差,但未側(cè)重修復(fù)偏差問題[4]。基于對齊的概念,建議改變運(yùn)營分配成本,通過調(diào)查所有可能的修復(fù)空間,提出并評估了一組最優(yōu)修復(fù)算法,將Petri網(wǎng)的修復(fù)問題簡化為了優(yōu)化問題[5]。通過考慮過程挖掘中應(yīng)用分而治之原則的問題,提出一個過程發(fā)現(xiàn)的模式,該修復(fù)方法也是利用分而治之的思想進(jìn)行模塊化修復(fù)[6]。通過分析事件日志來研究系統(tǒng)的真實(shí)情況,發(fā)現(xiàn)真實(shí)系統(tǒng)模型,工程師可以使用一致性檢驗(yàn)技術(shù)來診斷觀察事件日志和流程模型之間的差異[7]。但一味地提高修復(fù)后模型的適應(yīng)度或簡化度會讓修復(fù)成本大大提高,并且修復(fù)過程中事件日志遍歷的次數(shù)過大,與其修復(fù)模型不如重新通過事件日志挖掘新模型。因此,進(jìn)一步降低修復(fù)成本,減少以往修復(fù)算法的迭代次數(shù)和遍歷事件日志的次數(shù)以及修復(fù)算法的時(shí)間復(fù)雜度是本文針對的問題。
針對上述問題,本文提出了基于行為輪廓的流程模型修復(fù)方法,運(yùn)用模型分解及線性過濾的方法對模型進(jìn)行修復(fù),盡可能地保持初始模型結(jié)構(gòu)不改變、原模型可讀以及結(jié)構(gòu)良好的性能來進(jìn)一步降低修復(fù)成本,降低修復(fù)算法的時(shí)間復(fù)雜度。此外,還給出了過濾模塊以及選擇模塊中相應(yīng)的算法,從而較好地提升了模型修復(fù)的有效性。
1 基礎(chǔ)知識
定義1[8](流程模型Petri網(wǎng))滿足以下條件的四元組N=(P,T,F(xiàn),C)稱作一個流程模型Petri網(wǎng):
(1)P是有限非空庫所集,T是有限非空變遷集;
(2)P∪T≠φ且P∩T=φ;
(3)F(P×T)∪(T×P)是N中的流關(guān)系,(P∪T,F(xiàn))是強(qiáng)連通圖;
(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}是流程網(wǎng)的結(jié)構(gòu)類型。
定義2[10](行為輪廓)設(shè)P=(A,I,C,F(xiàn),T)是一個流程模型(x,y)∈((N∪F)×(N∪F))是滿足下列關(guān)系中的一個:
(1)嚴(yán)格序關(guān)系→p,如果xpy且ypx;
(2)排他關(guān)系+p,如果xpy且ypx;
(3)交叉序關(guān)系‖P,如果xpy且ypx。
以上三種關(guān)系的集合是P=(A,I,C,F(xiàn),T)的行為輪廓。
定義3(流程模型)將流程模型設(shè)定為一個元組M=(P,T,F(xiàn),J,ε,σ,Mi,Mf),P是庫所集p∈P;T是變遷集t∈T;F是連接所有直接跟隨庫所與變遷之間的流關(guān)系,F(xiàn)(P×T)(T×P);J是排序的有限集合;ε是滿射函數(shù),將每個變遷關(guān)聯(lián)到一個排序,T→J;σ是指定函數(shù),將所有變遷映射到活動集或靜默變遷中,T→A∪{τ},σ(ti)=(ei)=a,a∈A,τ∈T,σ(τ)A;Mi是初始標(biāo)識;Mf是終止標(biāo)識。
定義4(事件日志,跡)事件日志是一個數(shù)學(xué)模型,用于捕獲有關(guān)動態(tài)系統(tǒng)執(zhí)行的歷史信息。從形式上講,定義Σ是一組動作集,跡l∈Σ*是一個動作序列,L∈ΙΒΣ*)是一個事件日志即一組跡的多元集。其中每組跡都是將系統(tǒng)(即流程實(shí)例)的執(zhí)行描述為一系列觀察到的事件。因?yàn)榭梢源嬖诙鄠€具有相同跡的情況,如果跡的頻率不相關(guān),將記錄日志稱為一組跡L={l1,…,ln}。
定義5[11](工作流網(wǎng)的有效分解)設(shè)N∈UN是一個帶標(biāo)簽函數(shù)l的工作流網(wǎng)。D={N1,N2,…,Nn}UN是一個有效的分解,當(dāng)且僅當(dāng):
—任意1≤i≤n,Ni=(Pi,Ti,F(xiàn)i,li)是一個Petri網(wǎng),
—任意1≤i≤n,li=lΓTi,
—任意1≤i —任意1≤i —N=∪1≤i≤nNi D(N)對任意網(wǎng)N是一個有效分解集。 2 本文方案 (1) 模塊化修復(fù)框架 本文考慮的修復(fù)問題:給定工作流網(wǎng)N和事件日志L,事件日志L不完全符合N,提出了一種基于模型分解及線性過濾的模塊化修復(fù)方法,構(gòu)造模型Nr(修復(fù)后模型),讓Nr能夠重放L。主要思想是基于分而治之的原則篩選出需要修復(fù)的片段,修復(fù)方法由構(gòu)建的塊組成,每個塊執(zhí)行其中一個步驟,模塊化模型修復(fù)方法如圖2所示,構(gòu)建的塊分別為:①分解;②過濾;③選擇;④修復(fù);⑤組合;⑥案例分析。弧表示塊之間的數(shù)據(jù)傳輸。 本文基于模塊化模型修復(fù)的一般方法如下:該方法的輸入是一組(L,N),其中L是一組事件日志,N是一個不完全符合事件日志的初始模型。在分解塊中,使用極大分解算法[12]將模型N分解成幾個片段,分解結(jié)果是唯一的。在過濾塊中,本文給出了一個包含在過濾塊中線性過濾算法,算法將這些模型片段即子模型的直鏈結(jié)構(gòu)進(jìn)行過濾篩除,直鏈結(jié)構(gòu)不執(zhí)行下一步選擇過程,從而直接保留直鏈的原始模型片段,最后與修復(fù)后的模型片段組合。在選擇塊中,選擇算法將分解后的子模型的執(zhí)行序列與新增的兩條事件日志的跡運(yùn)用行為輪廓相關(guān)知識進(jìn)行比對,符合事件日志的跡即為優(yōu)子模型,反之為劣子模型。在修復(fù)塊中,將剩下的劣子模型與事件日志對比分析運(yùn)用感應(yīng)挖掘算法[13]進(jìn)行修復(fù)。在組合塊中,將過濾掉的直鏈結(jié)構(gòu)、優(yōu)子模型和修復(fù)后的子模型進(jìn)行組合,得到能夠重放事件日志修復(fù)后的模型。 (2)使用極大分解方法進(jìn)行模塊化修復(fù) 本文提出的模塊化修復(fù)方法在每個構(gòu)建的塊中使用特定算法。其中分解塊中使用的極大分解方法是一個有效分解,極大分解是基于邊緣的劃分,其定義如下:每個變遷嚴(yán)格地位于單個片段中,具有唯一標(biāo)簽的變遷被放置在片段的邊界上,在片段之間需要有因果關(guān)系的支持。因此,對于每個變遷,一個在初始網(wǎng)中具有唯一標(biāo)簽的變遷將存在于兩個或者多個片段中,最后,拆分保存了網(wǎng)絡(luò)的初始標(biāo)識。如果庫所在初始網(wǎng)中被標(biāo)記了,那么它在片段中也是被標(biāo)記的。在給定的系統(tǒng)網(wǎng)中,有且僅有一個極大分解,且分解結(jié)果是唯一的。極大分解網(wǎng)能夠很容易地通過融合有相同標(biāo)簽的變遷組合回完整的網(wǎng)。 將文獻(xiàn)中提出的極大分解算法應(yīng)用到分解塊中,并在此基礎(chǔ)上開發(fā)了過濾塊和選擇塊的算法,其工作原理如下:如果網(wǎng)片段發(fā)現(xiàn)可見的變遷,可依據(jù)decompose、handlePlace、handlePlace recursively三個函數(shù)的工作原理調(diào)用以后對其進(jìn)行分解。即decompose函數(shù)從初始網(wǎng)中任意庫所開始,當(dāng)有庫所需要遍歷時(shí)調(diào)用handlePlace函數(shù),調(diào)用handlePlace函數(shù)后,調(diào)用handlePlace recursively函數(shù)來遍歷此流程中庫所的前置節(jié)點(diǎn)和后繼節(jié)點(diǎn)。以初始網(wǎng)圖1中庫所p2為例,調(diào)用后三個函數(shù)后它的前置節(jié)點(diǎn)為變遷A和變遷G,后繼節(jié)點(diǎn)為變遷B,因此分解后片段為圖3中SN2片段。 初始網(wǎng)圖1中完整流程模型分解后得到的全部子模型如圖3所示;過濾塊中運(yùn)用線性過濾算法再將其進(jìn)行過濾,若子模型中的庫所前、后集個數(shù)分別為1或0,則可直接過濾此直鏈結(jié)構(gòu),直鏈結(jié)構(gòu)不執(zhí)行下一步選擇過程,過濾后的模型片段如圖4所示;過濾后選擇劣子模型進(jìn)行修復(fù),選擇塊中的選擇算法將過濾后模型片段的執(zhí)行序列與增加的事件日志運(yùn)用Petri網(wǎng)中行為輪廓定義進(jìn)行比對,符合的為優(yōu)子模型,反之為劣子模型。過濾算法及選擇算法如下: 輸入: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 文獻(xiàn)[13]已有許多流程發(fā)現(xiàn)的算法,本文使用感應(yīng)挖掘[14]保證模型發(fā)現(xiàn)的適應(yīng)性(零噪音閾值的不頻繁感應(yīng)挖掘)。它使用順序和回歸的感應(yīng)推理來構(gòu)建一個可以轉(zhuǎn)化為工作流網(wǎng)結(jié)構(gòu)的過程樹。 假設(shè)圖3中的模型中變遷C和E與其行為順序不完全一致,如果二者同時(shí)出現(xiàn),則在事件日志的跡中E總是在C之前出現(xiàn),根據(jù)行為輪廓,即E和C是嚴(yán)格序關(guān)系,記作E→C,也就是說事件日志包含跡和,沒有C在E之前出現(xiàn)的跡。應(yīng)用本文提出的選擇算法,如圖4所示,得到的片段SN4不完全適合日志,因此我們使用感應(yīng)挖掘算法發(fā)現(xiàn)了這個正確的工作流網(wǎng)片段SN4′如圖5所示。 在發(fā)現(xiàn)正確的模型片段并組合所有片段之后,得到了如圖6所示的網(wǎng)。這個模型與事件日志的跡和完全適應(yīng)??梢钥吹叫迯?fù)過的模型不是工作流網(wǎng),它包含源位置的標(biāo)識和初始標(biāo)識中的初始庫所。網(wǎng)的最終標(biāo)識包括在接收器和庫所中的兩個托肯,這個模型可以通過添加靜默的開始和結(jié)束變遷很容易地轉(zhuǎn)換成等效的工作流網(wǎng)??紤]到開始庫所和結(jié)束庫所限制模型的行為并可能產(chǎn)生死鎖,從而將它們刪除。但在模型運(yùn)行中增加可能發(fā)生的變遷,會稍微降低模型的精度,避免這樣的問題最好不要在修復(fù)過程中更改片段邊界節(jié)點(diǎn)變遷,因此可以通過考慮更大的片段來完成修復(fù)。 3 案例分析 本節(jié)以上述退換貨系統(tǒng)為例計(jì)算修復(fù)前后模型的適合度來評估所提方法的可行性,并與Fahland修復(fù)方法進(jìn)行對比實(shí)驗(yàn)。 在給定事件日志L和模型M上進(jìn)行實(shí)驗(yàn)評估。如表2所示,事件日志L一共包含事件總數(shù)為:|N|=12 781,其運(yùn)行次數(shù)依次為{58,87,230,270,198,205,109,26,100,12,49,210,180,33,101}。事件日志中總共有15條完整有效的執(zhí)行序列,大小分別為{6,7,10,11,12,15,16,14,13,15,14,13,10,8,7},預(yù)定義模型上的所有發(fā)生序列大小依次為{7,7,10,10,12,15,16,14,12,15,15,12,10,7,7}。將日志與模型進(jìn)行最優(yōu)校準(zhǔn),得到15組最優(yōu)校準(zhǔn)。 分析得到的15組最優(yōu)校準(zhǔn),這些校準(zhǔn)中的不一致由偏差引起,偏差分為日志插入偏差和網(wǎng)N跳過偏差,如案例1即n=1中是日志插入偏差,n=2中是網(wǎng)N跳過偏差。因此,日志與初始模型之間的擬合度為 f初始=1-∑ni=1Li∑mij=1Ccostj(ML(εi)+MM(δj))Li=1-2 63221 996≈0.880 34<1(1) 式中:L表示每組發(fā)生序列的發(fā)生次數(shù)即實(shí)例數(shù),n表示校準(zhǔn)的組數(shù)(本文有15組),Ccost表示每組校準(zhǔn)的偏差成本,這里將所有偏差成本設(shè)為1,ML表示日志發(fā)生序列,MM表示模型中的發(fā)生序列,ε表示日志發(fā)生序列的元素個數(shù),δ表示模型發(fā)生序列的元素個數(shù),而日志與修復(fù)后模型之間的適合度為1,因此本文的修復(fù)方法具有可行性。 根據(jù)本文所提算法的第12~17兩層嵌套循環(huán)可以看出,其算法的時(shí)間復(fù)雜度為O(MN)。運(yùn)用Fahland方法對案例模型修復(fù)結(jié)果如圖7所示,與本文所提方法的對比實(shí)驗(yàn)結(jié)果如表3所示。 4 結(jié)論 本文在已有研究的基礎(chǔ)上提出了一種基于模型分解和線性過濾的模塊化流程模型修復(fù)方法,通過線性過濾算法進(jìn)一步有效降低了修復(fù)的成本和修復(fù)算法的時(shí)間復(fù)雜度,并且盡可能保持了初始模型結(jié)構(gòu)。首先將初始模型運(yùn)用極大分解算法分解,其次使用過濾算法進(jìn)行線性過濾,再使用選擇算法選擇劣子模型然后通過感應(yīng)挖掘重新發(fā)現(xiàn)模型片段,最后對模型片段進(jìn)行組合得到修復(fù)后模型。 本文的方法可能略微降低了模型的精度,對于此問題,計(jì)劃提出更細(xì)微的分解技術(shù)以避免片段邊界節(jié)點(diǎn)的相關(guān)問題?;诜纸獾哪P托迯?fù)也會考慮到擬合度,精確度,泛化度和簡化度的組合度量,此外修復(fù)是基于模型,對模型分解的相關(guān)問題可能非常有幫助,這也是未來可以研究的方向之一。 參考文獻(xiàn): [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網(wǎng)理論[M].北京: 機(jī)械工業(yè)出版社,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,F(xiàn)AHLAND 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. (責(zé)任編輯:李 麗,范 君)