基于全局最優(yōu)對齊的業(yè)務(wù)流程偏差分析*

馬婷婷, 王 娟

(安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院， 安徽 淮南 232001)

0 引 言

當今商業(yè)環(huán)境的動態(tài)性要求流程模型需要靈活性，能夠快速地適應(yīng)不斷變化的業(yè)務(wù)需求。在很多情況下，流程設(shè)計者無法考慮所有可能的執(zhí)行情況，因此允許流程模型具有偏差。在給定一個流程模型及事件日志時，已經(jīng)有很多基于對齊的一致性指標來檢測偏差[1,2]，這些方法不僅可以挖掘偏差類型及位置，也提供度量指標來衡量事件日志和模型的一致性程度。但是通常情況下，管理員需要更具體的信息來確定流程的修復(fù)意見，如偏差發(fā)生的頻數(shù)及根本原因[3]。當然，有理由優(yōu)先改進模型中高頻偏差部分，以更好地反映現(xiàn)實情況[4]。

雖然挖掘偏差的方式有很多，但是近十年來的研究多是在對齊的基礎(chǔ)下進行的。然而，大多數(shù)傳統(tǒng)基于對齊的研究缺點有二，其一是對齊的成本多數(shù)采用標準成本函數(shù)[2，5，6]。然而，標準成本函數(shù)并非總是計算對齊的最佳函數(shù)，因為其更易出現(xiàn)成本等低最優(yōu)對齊的情況。所以Vincent Bloemen[7]等人通過最大化同步移動及定義不可跳過活動來更改成本函數(shù)； Polyvyanyy A[8]等人通過增加部分移動的成本值以及設(shè)定某類移動成本為0的思想獲得最優(yōu)對齊。本文借鑒上面的思想引入了嚴重成本函數(shù)，同時提出了全局最優(yōu)的思路處理成本等低最優(yōu)對齊。其二是，對于不一致的行為沒有提供可靠的綜合信息，因此我們通過偏差分析做出綜合診斷。

1 基本概念

定義1(Petri網(wǎng)[9]) 設(shè)A為一個活動集合，有關(guān)A的Petri網(wǎng)是一個元組N=(P,T,F,α,mi,mf)，其中P是有限庫所集，T是有限變遷集，F(xiàn)是有向弧集，α:T→A是一個將變遷映射到活動的函數(shù)，mi是初始標識，mf是最終標識。

給定一個活動標簽集Λ(τ?Λ)，λ：T→Λτ代表一個將變遷映射到標簽并集Λτ=Λ∪τ的函數(shù)。

定義2(跡，事件日志[10]) 跡是一個有限的標簽序列，而事件日志(日志)是關(guān)于跡σ的多重集L=(σ1p1,σ2p2,…,σnpn)。跡中的每一個標簽都是一個事件，即一個活動的發(fā)生。一般地，將跡表示為σ=<σ1,σ2,…,σ|σ|>，其中σi表示跡中的第i個活動。

定義3(對齊[8]) 給定一個Petri網(wǎng)N和事件日志L中的一條跡σ，已知??A∪T∪Λ,其中?≠τ。那么，序列γ∈(A?×T?)*是一個對齊當且僅當：

①(π1(γ))↓A=σ：序列γ的第一行在映射為活動序列，該序列等于跡σ；

③?(a,t)∈γ(a≠?∨t≠?)，其中(?,?)在對齊中是不合法的。

(x，?)稱為日志移動，其中x∈A；

(?,y)稱為模型移動，其中y∈T，此外當α(y)=τ時，特地稱之為沉默變遷模型移動；

(x,y)稱為同步移動，當且僅當x∈A∧y∈T并且x=α(y)。

定義4(標準成本函數(shù)[3]) 設(shè)A是一個活動集合，N=(P,T,F,α,mi,mf)是活動集A上的Petri網(wǎng)。定義標準成本函數(shù)lc:A?×T?→IR，該函數(shù)將所有移動匹配一個值IR，稱該值為移動成本，所有移動(x,y)∈A?×T?的具體成本如下：

◆lc((x,y))=0，當且僅當x∈A，y∈T且x=α(y)或者x=?，y∈T且α(y)=τ；

◆lc((x,y))=+∞，當且僅當x∈A，y∈T且x≠α(y)或者x=y=?；

◆lc((x,y))=1，其它。

定義6(嚴重成本函數(shù)[10]) 對于活動x∈A及變遷y∈T，嚴重成本函數(shù)ac:(x，?)∪(?，y)→N，它是標準成本函數(shù)的一個推廣，也可表示為ac:A?×T?→IR，即根據(jù)需求人為地調(diào)整其成本，比如：

當然，也可以根據(jù)偏差事件發(fā)生的嚴重程度，對不同的移動賦予不同的成本值。

圖1 Petri網(wǎng)的患者就醫(yī)流程

2 基于調(diào)整成本函數(shù)的全局最優(yōu)對齊

近些年來，對齊技術(shù)已經(jīng)逐漸發(fā)展成一致性檢測及偏差分析的主要途徑，并且為模型修復(fù)提供了參考建議。然而，對于同一條跡，往往選擇成本最低的作為最優(yōu)對齊，但是也會出現(xiàn)成本值相同低的對齊結(jié)果。Vincent Bloemen[6]及Polyvyanyy A[7]等人提出的方法的原理是調(diào)整成本函數(shù)，即便如此，仍然可能出現(xiàn)該現(xiàn)象。因此為了在等低成本對齊中選擇出更優(yōu)的對齊，不僅引入嚴重成本函數(shù)，同時采用全局最優(yōu)的思路，即總體修復(fù)建議最少的原則抉擇出等低成本對齊中的最優(yōu)對齊，最終確定日志L的對齊多重集，總體思想結(jié)構(gòu)由表1算法一中偽代碼展示。

在對齊過程中，同步移動或者模型移動相對應(yīng)的變遷的發(fā)生，會改變Petri網(wǎng)的狀態(tài)。即，對齊中所有關(guān)于同步移動或者模型移動的信息會映射到模型中相對應(yīng)的變遷，所以采用變遷來表示模型移動。而對于日志移動，模型中的元素不能表達其信息，所以通過日志移動前的標識來定位此類移動。為了更正式化的捕獲日志中移動的總類型，引入一個修復(fù)建議的概念，見定義8。值得注意的是，不同跡中出現(xiàn)相同類型的偏差的根源可能不同，(如下一節(jié)中γ52與γ6中同類型的日志移動(e，?)，其主要根源便不相同)，因此，將相同位置的同類型偏差視為一個修復(fù)建議，而不同位置的同類型偏差分開處理。當然，基于調(diào)整成本函數(shù)的原理，由于修復(fù)某些偏差的成本明顯高于其他偏差，則視這些修復(fù)建議的成本與調(diào)整成本函數(shù)中一致。

表1 全局最優(yōu)對齊多重集偽代碼

3 全局最優(yōu)對齊實例分析

在這一節(jié)中，使用圖1關(guān)于門診就醫(yī)的Petri網(wǎng)，該模型包括患者就醫(yī)時通常經(jīng)歷的掛號、選醫(yī)、咨詢專家、繳費、檢查、手術(shù)等步驟。其中圓圈代表庫所，白色方框代表正常變遷，灰色方框代表沉默變遷。通常情況下，在信息系統(tǒng)中無法觀察到的變遷，稱為沉默變遷(不可見變遷)。如圖1中的變遷t10，患者掛號后由于各種原因直接離開醫(yī)院，醫(yī)生系統(tǒng)中無法獲知患者已離開，所以視為沉默變遷。為了發(fā)現(xiàn)給定模型與實際生活就醫(yī)流程的偏差及偏差位置，現(xiàn)引用一個有關(guān)門診就醫(yī)的人工日志(共計700條跡)，具體日志如表2所示。

表2 患者就醫(yī)流程的非擬合日志

由于在現(xiàn)實生活中，患者在檢查或手術(shù)之后未支付費用便直接離院，對醫(yī)生及醫(yī)院的工作帶來不便，同樣，若患者在繳費時，系統(tǒng)重復(fù)扣款，給患者帶來的經(jīng)濟影響較大。因此根據(jù)這兩種偏差事件導(dǎo)致的嚴重程度，定義嚴重成本函數(shù)lc((x,y))。

表3 每條跡的最優(yōu)對齊成本

根據(jù)嚴重成本函數(shù)，分別對齊日志中的八條跡，并選擇成本最低的視為最優(yōu)對齊，每條跡的具體最優(yōu)對齊如圖2。

明顯地，對于跡σ5而言存在兩條最優(yōu)對齊，雖然偏差個數(shù)不同，但是兩種對齊的成本均為2。根據(jù)算法一，最優(yōu)對齊已知后，匯總出兩種對齊多重集的修復(fù)建議總數(shù)rsu(LS)，具體修復(fù)建議見表4。

表4 事件日志修復(fù)建議匯總

圖2 日志L中每條跡的最優(yōu)對齊

顯然，兩個對齊多重集的總成本相同(每條跡的成本相同)，而rsu(LS2)

+1×116+3×37+2×71=501

圖3 對齊在日志上的可視化

圖4 模型移動修復(fù)方案

4 偏差分析

不管是統(tǒng)計學(xué)還是大數(shù)據(jù)分析中，面對大量、動態(tài)、模糊數(shù)據(jù)時，通常采用可視化方式進一步分析數(shù)據(jù)，以便更為直觀詳細地了解數(shù)據(jù)分布情況。本文中，分別從日志及模型兩個角度出發(fā)，使用對齊的可視化方式，來判斷偏差位置、挖掘高頻偏差、以及偏差根源。

首先，將每條跡的最優(yōu)對齊映射到日志中，并將每一步合法移動用箭頭表示，不同的顏色代表不同類型的移動(具體結(jié)果見圖3)。其中，淺藍色代表同步移動，深藍色代表沉默變遷模型移動，綠色代表模型移動，橙色代表日志移動。采用這種簡單的可視化方式，可以顯示每條跡出現(xiàn)的偏差具體情況，也可以顯示連續(xù)出現(xiàn)的偏差。挖掘連續(xù)出現(xiàn)的同類型偏差可以將此視為一次偏差，這在Cook等人[11]提出的量化事件流與模型之間擬合度指標NSD中應(yīng)用到，也可以在模型修復(fù)時使用。比如針對γ7中連續(xù)出現(xiàn)的(?，a)、(?，b)、(?，c)模型移動進行模型修復(fù)時，可以直接在p1與p4中間添加一個沉默變遷τ1，結(jié)構(gòu)如圖4。

給定一個Petri網(wǎng)(圖1)及一個有關(guān)對齊的多重集(表4)，第二個可視化方式是將對齊多重集映射到模型中。與上面的對齊映射到日志中有所不同，能夠從模型中了解偏差發(fā)生頻率及位置。畢竟模型修復(fù)時，可以按照頻率作為指標選擇優(yōu)先修復(fù)的對象。

圖5為第二種可視化方式，使用不同顏色、不同粗細的弧線、及頻數(shù)、比值來反應(yīng)跡對齊詳細結(jié)果。其中也包括每條弧線流經(jīng)的次數(shù)，模型移動發(fā)生的位置頻數(shù)，日志移動發(fā)生的根源及頻數(shù)。由于模型移動對應(yīng)著模型中一個變遷的發(fā)生，所以將其映射到變遷中且標記為綠色，并留下模型移動與同步移動的比例值。而對于日志移動，我們采用日志移動前的標識反應(yīng)信息，所以將日志移動映射到庫所上且標記為橙色，并賦予發(fā)生頻數(shù)。

對于模型移動，可以從圖中觀察到，共有三個變遷均標記為綠色，這表示日志里的所有跡對齊中，一共出現(xiàn)了(?，a)、(?，b)、(?，c)這三種模型移動，并且這三種中(?，c)的模型移動次數(shù)更多。同時結(jié)合第一種可視化方式了解到，共有(?，a)、(?，b)、(?，c)連續(xù)模型移動及(?，c)單獨移動兩種情況，在不考慮其他因素時可以將模型按圖4修復(fù)。

對于日志移動，將存在日志移動的對齊在Petri網(wǎng)上重放，在日志移動前其標識反應(yīng)當前網(wǎng)的狀態(tài)，日志移動后的同步移動或者模型移動顯示了token的流向。比如在模型中重放γ3時，標識[p3]為<(b,t2)>發(fā)生后(?，c)移動之前的狀態(tài)，并經(jīng)<(c,t3)>發(fā)生后到達標識[p4]，因此在庫所p3上標記日志移動。同樣地方法對齊γ52,γ8以發(fā)現(xiàn)(c，?)及(e，?)的標識為[p5]。因此，針對三種日志移動，在庫所p3添加連接活動e的自環(huán)結(jié)構(gòu)，在庫所p5添加連接活動e及c的自環(huán)結(jié)構(gòu)。

5 結(jié) 論

當流程模型與其執(zhí)行日志之間未完全擬合時，偏差分析有利于提高流程性能，并為模型修復(fù)提供建議。本文在考慮成本等低最優(yōu)對齊的情況下，基于修復(fù)建議最少原則對日志對齊多重集中的偏差提供精確詳盡的定位分析。首先，提出一種日志最優(yōu)對齊多重集的挖掘算法，即保留每條跡所有可能最低成本的對齊，組合成多個不同的對齊多重集，匯總每個多重集的模型移動，及狀態(tài)不同的日志移動整理出修復(fù)建議，將修復(fù)建議最少的視為日志最優(yōu)對齊多重集。接著，引入一個就醫(yī)流程及人工日志，按照算法一獲取日志的最優(yōu)對齊多重集，最后，分別將對齊映射到日志及模型中，以探索每條跡的偏差位置以及不同類型的偏差發(fā)生頻率及根源，并在相應(yīng)位置通過插入或跳過變遷修復(fù)原模型。

圖5 對齊在模型上的可視化

然而，可視化方式較簡單原始，雖然可以直觀看見偏差相關(guān)信息，但面對大規(guī)模日志或者復(fù)雜模型時，人工計算量較大。因此，未來可以通過編程實現(xiàn)智能化，也可以采用數(shù)據(jù)挖掘技術(shù)從大量數(shù)據(jù)中提取感興趣的知識，如使用頻繁模式挖掘技術(shù)從對齊多重集中提取共現(xiàn)偏差，與共現(xiàn)行為[11]相似。