基于行為距離的帶隱變遷過程模型挖掘方法

王麗麗，方賢文

(1.安徽理工大學 數(shù)學與大數(shù)據(jù)學院，安徽 淮南 232001；2.同濟大學 嵌入式系統(tǒng)與服務計算教育部重點實驗室，上海 201804)

0 引言

過程挖掘的目標是從事件日志中自動發(fā)現(xiàn)有價值的信息，從而監(jiān)控并指導增強業(yè)務過程管理[1]。在過程挖掘中存在很多問題，如短循環(huán)、復制變遷、不可見變遷、非自由選擇結構、噪音、低頻行為、不完備性等，其中不可見變遷又稱為隱變遷，本文重點研究隱變遷的挖掘方法?，F(xiàn)實生活中由于各種因素可能導致過程模型中存在隱變遷，它們主要起到路由的目的，隱變遷之所以難以挖掘是因為它不出現(xiàn)在事件日志的任何跡中。其中隱變遷出現(xiàn)的主要原因有以下幾種[2]：

(1)在過程模型中存在沒有實際意義僅用于路由目的任務；

(2)某些實際任務在某些事件跡中可以被缺失執(zhí)行；

(3)用于過程模型增強服務，允許存在跳過、重做當前任務或跳轉到任意的先前任務，但是這些執(zhí)行邏輯在過程模型的控制流中沒有被表達出來。

目前已存在一些隱變遷的挖掘方法,如α# 算法[2-3]，α$[4]，IM(inductive mining)方法[5]，耦合隱馬爾可夫模型-不可見任務 (Coupled Hidden Markov Model-Invisible Task，CHMM-IT)[6]，耦合隱馬爾可夫模型-非自有選擇的不可見任務(Coupled Hidden Markov Model-Nonfree Choice Invisible Task，CHMM-NCIT)[7]等。文獻[3]在文獻[2]的基礎上提出了帶基本不可見任務的過程模型的挖掘方法，但是無法解決并發(fā)結構中的隱變遷問題。文獻[4]提出了α$算法，討論了非自由選擇網(wǎng)中的隱變遷的挖掘問題，但是仍然不能發(fā)現(xiàn)并發(fā)結構中的隱變遷。IM方法[5]通過流程樹切實現(xiàn)了帶隱變遷的過程模型挖掘，但是該方法發(fā)現(xiàn)的過程模型中存在大量的冗余變遷，導致過程模型非常復雜。文獻[6-7]采用隱馬爾可夫的方法給出了自由和非自由選擇網(wǎng)在日志不完備情況下的隱變遷挖掘方法，其中CHMM-NCIT和CHMM-IT都使用了耦合隱馬爾可夫模型(CHMM)，同時利用Baum-Welch算法來決定CHMM的變量權重，然而這些算法的時間復雜度非常高，實現(xiàn)起來較困難。文獻[8]提出一個優(yōu)于MINERful算法的方法，該方法能夠構建一個帶有不可見任務的聲明式模型和非自由選擇的命令式模型中的不可見任務，但是其中控制流通過聲明模型中的組合規(guī)則建立，沒有明確的不可見任務輸出。文獻[9]提出一個基于圖的算法，但是當事件日志較大時，數(shù)據(jù)庫圖很難表達事件之間的依賴關系。綜上所述，本文提出一種基于行為距離發(fā)現(xiàn)隱變遷的新方法，主要工作如下：

(1)提出了行為距離的概念，量化了日志或模型中活動對之間的發(fā)生依賴關系。

(2)通過日志基本行為關系對日志中的活動對間的行為關系進行了定性分析，進一步細化了傳統(tǒng)的行為輪廓。

(3)從行為的角度給出了帶隱變遷的過程模型挖掘方法，該方法能發(fā)現(xiàn)多種類型的隱變遷，解決并發(fā)結構中隱變遷發(fā)現(xiàn)困難的問題，而且不會產(chǎn)生大量的冗余隱變遷。

1 動機例子

由于隱變遷不出現(xiàn)在任何事件日志中，有效地挖掘所有的隱變遷是過程挖掘的一個具有挑戰(zhàn)性的問題。下面通過實例說明目前技術在隱變遷挖掘方面存在的問題。對于事件日志L1={σ1,σ2,σ3,σ4,σ5,σ6,σ7,σ8,σ9,σ10,σ11}，其中：σ1=ACDDFGHI，σ2=BCDEEFHGI，σ3=ADEDEGHI，σ4=AEDGHI，σ5=BEDHGI，σ6=BDEHGI，σ7=BCEDFHI，σ8=AJKDEFGHI，σ9=BJKDHGI，σ10=AKJEEDFHGI，σ11=BKJDEDDEGHI，在不考慮跡的頻度的前提下，分別采用文獻[3]和文獻[5]提出的挖掘算法得到如圖1和圖2所示的過程模型，采用本文方法得到的過程模型如圖3所示。顯然，文獻[3]無法發(fā)現(xiàn)沒有直接跟從關系的活動對間的隱變遷，如圖1中活動F和活動I之間的隱變遷，而且模型非常復雜。對于IM方法[5]產(chǎn)生了大量的冗余隱變遷,從而導致如圖2所示的模型變得非常復雜。針對上述問題，本文提出一個基于日志行為關系和行為矩陣的帶有無冗余隱變遷的過程模型發(fā)現(xiàn)方法，并通過一組實驗驗證了該方法的有效性，解決了目前在隱變遷挖掘上存在的問題。

2 基本概念

關于Petri網(wǎng)的基本定義和相關知識請參見文獻[10]，標簽Petri網(wǎng)相關知識請參見文獻[11]，本章只給出與本文相關的核心定義。Petri網(wǎng)的變遷用來表示動作，通?？梢苑譃榭梢娮冞w和不可見變遷(又稱為隱變遷)，它們分別描述具有明確含義的動作和沒有明確解釋的動作。假設A表示變遷所代表的有明確含義的所有動作標簽;τ表示特殊的標簽，其中τ?A;T是一些列活動集合。

定義1[11]標簽Petri網(wǎng)。一個標簽Petri網(wǎng)是一個四元組N:=(P,T,F,λ)，其中：(P,T,F)是一個Petri網(wǎng)，λ:T→A∪{τ}是一個將標簽分配給變遷的函數(shù)。如果λ(t)≠τ，則t是可見的，否則t是不可見或沉默的。

定義2[11]執(zhí)行序列(或出現(xiàn)序列)。設S:=(N,M0)是一個標簽網(wǎng)系統(tǒng)，其中N:=(P,T,F,λ)。網(wǎng)系統(tǒng)S的所有帶標簽的執(zhí)行序列是所有遵循網(wǎng)系統(tǒng)S的可執(zhí)行語義的形如{ai}·(Aτ)*·{af}組成的序列集合，其中ai,af分別是人工添加的開始變遷和結束變遷。記網(wǎng)系統(tǒng)S的所有帶標簽的執(zhí)行序列為T(S)。

定義3[12]直接跟從關系(日志)。設L是活動T上事件日志。設a,b∈T，若存在一條跡σ=t1t2…tn使得σ∈L，且ti=a,ti+1=b(其中i∈{1,2,…..,n-1})，則稱活動a和活動b之間存在直接跟從關系，記為a>Lb。

定義4[12]弱序關系(日志)。設L是活動T上事件日志。設a,b∈T，若存在一條跡σ=t1t2…tn使得σ∈L，且ti=a,tj=b(其中1≤i

3 構建帶and網(wǎng)關類型和循環(huán)類型沉默變遷的初始過程模型

本章給出了發(fā)現(xiàn)and網(wǎng)關類型和循環(huán)類型隱變遷的方法，并通過算法說明了如何根據(jù)日志的行為特征關系和行為距離構建帶and網(wǎng)關類型和循環(huán)類型的隱變遷的初始過程模型。

定義5基于跡的行為距離。設L是活動T上事件日志，a,b∈T，對于一條跡σ∈L，活動a和活動b之間的行為距離定義為：

(1)

在定義5的基礎上，定義6給出了基于日志的活動間最大行為距離和最小行為距離。

定義6基于日志的最大行為距離和最小行為距離。設L是活動T上事件日志，設a,b∈T，對于日志L，活動a和活動b基于日志的最大行為距離BDismax(a,b,L)和基于日志的最小行為距離BDismin(a,b,L)分別定義為：

(2)

若活動a和活動b處于排他序關系，顯然它們不可能同時出現(xiàn)在任何跡中，則BDismin(a,b,L)=BDismax(a,b,L)=∞。若在任意跡中滿足aLb且bLa，則BDismin(b,a,L)=-BDismin(a,b,L)。

對于事件日志L，AL代表出現(xiàn)在日志L中的所有活動集合，設|AL|=n，則日志的行為距離矩陣BDisMatrix是n×n維的矩陣，?a,b∈AL，活動a和活動b間的行為距離等于矩陣中活動a所在的行和活動b所在列對應的值Ma,b=x,y，其中x=BDismin(a,b,L)，y=BDismax(a,b,L)。表1給出了第1章日志L1中各活動對的行為距離矩陣。

表1 日志L1中活動對間的行為距離矩陣

定義7將文獻[3]中的虛假依賴關系從因果依賴關系中剔除出去，給出了基于日志的基本行為關系，細化了傳統(tǒng)的行為輪廓。

定義7基于日志的基本行為關系。設L是活動T上事件日志，設a,b∈T：

(1)因果依賴關系→L，當且僅當a>Lb且b≯La，且BDismin(a,b,L)=BDismax(a,b,L)=1；

對于第1章中的事件日志L1，根據(jù)定義7得到活動間的基本行為關系如表2所示。

表2 基于日志L1的基本行為關系矩陣

定義8隱變遷類型。設N:=(P,T,F,λ)是一個標簽Petri網(wǎng)，A∪τ表示所有活動標簽，對t1,t2,t∈A∪τ，若滿足：

(5)λ(t)=τ,·t={s},·s=?,|t·|>1或t·={s},s·=?,|·t|>1，則稱t為side類型的隱變遷。

圖4給出了side類型、skip類型、loop類型、switch類型、and網(wǎng)關類型隱變遷的示例。

根據(jù)網(wǎng)系統(tǒng)的結構特征，引理1和定理1分別給出了網(wǎng)關隱變遷和循環(huán)隱變遷的挖掘方法。

引理1對處于并發(fā)交叉序關系的活動，默認存在and-split 和and-join隱變遷。

引理1可能導致冗余的網(wǎng)關隱變遷，在算法1中，將根據(jù)隱變遷和其前置或后置變遷的結構關系，對冗余網(wǎng)關隱變遷進行刪除。

定理1設L是活動T上事件日志，若T′?T是滿足循環(huán)交叉序關系的極大活動子集，且?t∈T′均屬于loop-body部分變遷，則一定存在循環(huán)類型隱變遷作為loop-redo變遷。

證明采用反證法。若不存在循環(huán)類型的隱變遷，即存在一個可見變遷t′∈T作為loop-redo變遷。由于?t∈T′均屬于loop-body部分變遷，T′中的活動結構屬于命題5中的3種情況之一，這里不再詳細討論。T′與t′的可能網(wǎng)結構如圖5所示，易知，?t∈T′與t′滿足循環(huán)交叉序關系，故滿足循環(huán)交叉序關系的極大活動子集為T′∪t′，矛盾。故定理1成立。證畢。

由于邊界隱變遷挖掘比較簡單，本文不討論邊界類型的隱變遷挖掘的方法。算法1首先根據(jù)事件日志L建立活動對之間的行為距離矩陣和行為關系矩陣，在此基礎上構建若干個子模塊，同時采用引理1和定理1發(fā)現(xiàn)and網(wǎng)關類型和循環(huán)類型的隱變遷。最后，將這些子模塊組合成一個Petri網(wǎng)模型，同時刪除其中冗余的and網(wǎng)關類型的隱變遷。

算法1發(fā)現(xiàn)帶網(wǎng)關類型和loop類型的沉默變遷的Petri網(wǎng)模型M0。

輸入: 事件日志L;

輸出: 初始的Petri網(wǎng)模型M0。

1.根據(jù)日志L建立活動間的行為距離矩陣BDisMatrixn×n；

2.根據(jù)日志L建立活動間的行為關系矩陣BRelMatrix；

3.If活動集S和活動集T處于排他序關系，

4.then活動集S和活動集T處于結構排他關系，構造由S和T組成排他結構。

5.If活動集S和活動集T處于并發(fā)交叉序關系，

6.then活動集S和活動集T處于結構并發(fā)關系，構造由S、T、and-split和and-join隱變遷組成的并發(fā)結構。

7.If活動集S和活動集T處于循環(huán)交叉序關系，

9.if BDis(a,s′,L)min≥BDis(a,t′,L)min+1，且對于T′=S∪T

?σ∈L,|OccurTime(s′,σT′)-OccurTime(t′,σT′)|≤1，

10.then活動集S和活動集T處于順序結構中的循環(huán)交叉。

11.if BDis(a,s′,L)min=BDis(a,t′,L)min=1，且對于?σ∈L,OccurTime(s′,σT′)與OccurTime(t′,σT′)無依賴關系，

12.then活動集S和活動集T處于排他結構中的循環(huán)交叉。

13.if BDis(a,s′,L)min=BDis(b,t′,L)min=1，BDis(a,s′,L)max=BDis(a,t′,L)max=2，且對于?σ∈L,OccurTime(s′,σT′)=OccurTime(t′,σT′)，

14.then活動集S和活動集T處于并發(fā)結構中的循環(huán)交叉。

15.if活動集S和活動集T都屬于循環(huán)體(loop-body)部分，

16.then添加循環(huán)類型的隱變遷t(其中λ(t)=τ)作為循環(huán)重做(loop-redo)

17.while(存在未組合的塊)do,

18.遍歷BRelMatrix中的因果依賴關系，通過因果依賴關系將塊結構組合在一起，

19.遍歷BRelMatrix中的嚴格序關系，將剩余的塊結構合為一個完整的Petri網(wǎng)模型,

20.for(所有的and-split和and-join類型的隱變遷檢查是否冗余)設l(t)=τ。

21.if t·>1且|·(·t)|=1,l(·(·t))≠τ，

22.then刪除and-split類型的隱變遷t，并用·(·t)變遷替換t。

23.if·t>1且|(t·)·|=1,l((t·)·)≠τ，

24.then刪除and-join類型的隱變遷t，并用(t·)·變遷替換t。

25.得到帶有無冗余的網(wǎng)關類型和循環(huán)類型隱變遷的初始Petri網(wǎng)模型。

下面利用算法1對第1章中的事件日志L1構建初始Petri網(wǎng)模型。行為距離矩陣和基本行為關系矩陣如第1章中表1和表2所示。根據(jù)步驟3～步驟16構造出如圖6所示的4個子模塊，利用步驟17～步驟19將圖6所示的4個子結構組合為一個完整的過程模型如圖7所示。

最后，根據(jù)步驟20～步驟25刪除圖7中冗余的and網(wǎng)關類型的隱變遷t2和t3，得到帶有無冗余的and網(wǎng)關類型和循環(huán)類型隱變遷的初始過程模型M0如圖8所示。

4 基于模型和日志的行為距離挖掘skip類型隱變遷

本章將討論如何在算法1構建的初始過程模型的基礎上挖掘skip類型的隱變遷，從而進一步優(yōu)化初始過程模型。下面首先給出相關定義。

定義9基于模型的最小行為距離。設S=(N,M0)是一個網(wǎng)系統(tǒng)，其中:N:=(P,T,F,λ)是一個標簽Petri網(wǎng)，A∪τ表示所有的活動標簽，a,b∈A，對于網(wǎng)系統(tǒng)S，活動a和活動b基于模型的最小行為距離BDismin(a,b,S)定義為：

BDismin(a,b,S)={k|?σ∈T(S),BDis(a,b,σ)≥k}。

(3)

定理2描述了通過比較兩個活動在日志中的最小行為距離和其在模型中的最小行為距離的大小關系來挖掘skip類型隱變遷的方法。

定義10前置變遷集和后置變遷集。設S=(N,M0)是一個網(wǎng)系統(tǒng)，其中N:=(P,T,F,λ)是一個標簽Petri網(wǎng)。?t∈T，·(t)T={t′|t′∈T∧(t′)·∩·t≠?}，稱·(t)T為t的前置變遷集。同理定義t的后置變遷集(t)·T。

定義11基于模型的并發(fā)結構最小行為距離。設S=(N,M0)是一個網(wǎng)系統(tǒng)，其中N:=(P,T,F,λ)是一個標簽Petri網(wǎng)。t1,t2∈T，t1是and-split變遷，t2是and-join變遷，網(wǎng)系統(tǒng)S的所有可執(zhí)行變遷序列集合記為T(s)，t1和t2基于模型的并發(fā)結構最小行為距離

BDis‖min(t1,t2,S)={k|?σ∈T(s)∧BDis(t1,t2,σ)≥k}。

(4)

某兩個活動只要在日志的某條跡中存在直接跟從關系，利用定理2能發(fā)現(xiàn)位于它們之間的skip類型隱變遷。

定理2只能發(fā)現(xiàn)其中一類活動對之間的隱變遷，這些活動對在日志中至少存在一條跡使得它們之間有直接跟從關系，但是對于圖3中的隱變遷t4是無法發(fā)現(xiàn)的。針對這種情況，定理3給出了并發(fā)結構中的隱變遷識別方法。

定理3設L是活動A上事件日志，S=(N,M0)是一個網(wǎng)系統(tǒng)，其中N:=(P,T,F,λ)是一個標簽Petri網(wǎng)，A∪τ表示所有的活動標簽。?t1,t2∈T，其中t1為and-split變遷，t2為and-join變遷，①當λ(t1)≠τ,λ(t2)≠τ，如果BDismin(λ(t1),λ(t2),L)

證明不失一般性，這里僅給出最基本情況的并發(fā)結構作為示例證明定理的正確性。假設不存在skip類型的隱變遷。由于t1為and-split變遷，t2為and-join變遷，分兩種情況進行討論：

(1)當t1和t2都是可見變遷時，可能的子結構如圖9所示。?σ∈T(S)，若t1∈σ，則跡σ的形如…t1abt2…或…t1bat2…形式，易知BDismin(t1,t2,S)=3，若t1和t2的并發(fā)分支結構上不存在隱變遷，則BDismin(λ(t1),λ(t2),L)≥3。顯然與BDismin(λ(t1),λ(t2),L)

(2)當t1和t2都是隱變遷時，網(wǎng)結構如圖10所示，?σ∈T(s)，如果a∈σ∨b∈σ，則可執(zhí)行的變遷集為σ=…ct1abt2d…或σ=…ct1bat2d…，此時BDis‖min(t1,t2,S)=3，所以?σ∈L，若?σ∈L,a∈σ∨b∈σ則BDis(c,d,σ)≥3，所以，若t1和t2的并發(fā)分支結構上不存在隱變遷時，BDismin(c,d,σ)

算法2的基本思想是分析活動在日志中的最小行為距離和它們在模型中的最小行為距離之間的關系，通過定理2和定理3判斷其間是否存在skip類型的隱變遷，其具體實現(xiàn)步驟如算法2所示。

算法2發(fā)現(xiàn)skip類型隱變遷，構建基于事件日志L的最終Petri網(wǎng)模型M1。

輸入:事件日志L，初始Petri網(wǎng)模型M0，行為距離矩陣BDisMatrixn×n;

輸出:基于事件日志L的Petri網(wǎng)模型M1。

1.遍歷行為距離矩陣BDisMatrixn×n

2.while(存在BDismin(a,b,L)=1,BDismax(a,b,L)≠1的活動對(a,b))

3.利用定義12計算BDismin(a,b,S)

4.if BDismin(a,b,S)>1

5.then根據(jù)定理2可知活動a和活動b之間存在skip類型的隱變遷。

6.for(所有and-split變遷和and-join變遷)

設t1為and-split變遷，t2為and-join變遷

7.if(λ(t1)≠τ∧λ(t2)≠τ∧BDismin(t1,t2,L)≠BDismax(t1,t2,L))

8.then計算BDismin(t1,t2,S)

9.if BDismin(t1,t2,L)

10.then根據(jù)定理3可知在t1和t2之間的并發(fā)分支上存在skip類型的隱變遷。

11.else if(λ(t1)=τ,λ(t2)=τ)

12.then設?c∈·(t1)T,?d∈(t2)T·,a,b∈(t1)·T，

13.if(BDismin(c,d,L)≠BDismax(c,d,L))

14.then計算BDis‖min(t1,t2,S)

15.if?σ∈L,a∈σ∨b∈σ∧BDismin(c,d,σ)

16.then根據(jù)定理3可知在t1和t2之間的并發(fā)分支上存在skip類型的隱變遷。

17.得到帶多類型隱變遷的Petri網(wǎng)模型M1。

對于第3章中的初始Petri網(wǎng)模型M0，由算法2步驟5可知，在活動對(a,d),(a,e),(b,d),(b,e)之間存在隱變遷t1。同理可以發(fā)現(xiàn)skip類型的隱變遷t3和t4，最終得到帶多類型隱變遷的優(yōu)化Petri網(wǎng)模型M1，如圖11所示。

5 實驗分析

本章通過實驗比較了本文方法與現(xiàn)有的隱變遷挖掘方法，驗證了該方法的有效性。通過多組事件日志比較了幾個挖掘算法在隱變遷發(fā)現(xiàn)個數(shù)和過程模型質量方面的差異。實驗實施環(huán)境為Intel i7-6500處理器和8 GB的RAM(2.50 GHz)。采用文獻[13]中提出的“token game”的方法來計算適合度，采用文獻[14]和文獻[15]中提出的方法計算模型的精確度和量化被發(fā)現(xiàn)模型和原模型間的一致性度。

通過模擬已知過程模型的運行得到事件日志，其中產(chǎn)生日志的每個原模型中都存在數(shù)量不等的各種類型隱變遷的組合。其活動的最大數(shù)量不超過20個，在不考慮頻度的前提下，一個事件日志中的跡的總條數(shù)不超過30條。圖12給出了IM算法、α#算法和本文方法在隱變遷識別個數(shù)、模型適合性、模型精確和模型的一致性4個方面的比較結果。

其中：圖12a表明本文的方法能識別源模型中的多類型隱變遷，在識別隱變遷的個數(shù)上位于IM算法和α#算法之間，不會產(chǎn)生過多的冗余變遷。圖12b和12c表示本文方法相比IM算法和α#算法在不降低模型精確度的基礎上，進一步提高了模型的適合度，圖12d表示本文方法相比IM算法和α#算法挖掘得到模型的行為與原模型的行為一致性更高?？傊?，實驗結果表明，本文提出的基于行為距離的帶隱變遷的過程挖掘方法能發(fā)現(xiàn)多類型的隱變遷，在不降低模型精確度的前提下，提高了模型的適合度。

6 結束語

本文提出了基于行為距離的帶隱變遷過程模型挖掘新方法，首先，為了更精確地捕獲活動間的依賴關系，計算了活動基于日志的最小和最大行為距離，通過活動間的弱序關系和行為距離詳細分析了活動基于事件日志的基本行為關系。然后，利用行為關系和行為距離相結合的技術構建了帶網(wǎng)關類型和循環(huán)類型隱變遷的初始過程模型。在此基礎上，通過分析活動對基于日志、基于模型或基于并發(fā)結構的行為距離間的關系來識別skip類型隱變遷。最后，通過實驗驗證了該方法的有效性和優(yōu)越性。未來工作主要有兩個方面：①考慮如何改進該方法將其拓展到非自由選擇結構;②當日志的行為關系不完備時，如何正確的發(fā)現(xiàn)活動間的可能行為關系和隱變遷的挖掘方法。