王麗麗，方賢文

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

0 引言

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

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

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

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

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

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

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

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

1 動(dòng)機(jī)例子

由于隱變遷不出現(xiàn)在任何事件日志中，有效地挖掘所有的隱變遷是過程挖掘的一個(gè)具有挑戰(zhàn)性的問題。下面通過實(shí)例說明目前技術(shù)在隱變遷挖掘方面存在的問題。對于事件日志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，在不考慮跡的頻度的前提下，分別采用文獻(xiàn)[3]和文獻(xiàn)[5]提出的挖掘算法得到如圖1和圖2所示的過程模型，采用本文方法得到的過程模型如圖3所示。顯然，文獻(xiàn)[3]無法發(fā)現(xiàn)沒有直接跟從關(guān)系的活動(dòng)對間的隱變遷，如圖1中活動(dòng)F和活動(dòng)I之間的隱變遷，而且模型非常復(fù)雜。對于IM方法[5]產(chǎn)生了大量的冗余隱變遷,從而導(dǎo)致如圖2所示的模型變得非常復(fù)雜。針對上述問題，本文提出一個(gè)基于日志行為關(guān)系和行為矩陣的帶有無冗余隱變遷的過程模型發(fā)現(xiàn)方法，并通過一組實(shí)驗(yàn)驗(yàn)證了該方法的有效性，解決了目前在隱變遷挖掘上存在的問題。

2 基本概念

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

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

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

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

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

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

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

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

(1)

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

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

(2)

若活動(dòng)a和活動(dòng)b處于排他序關(guān)系，顯然它們不可能同時(shí)出現(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中的所有活動(dòng)集合，設(shè)|AL|=n，則日志的行為距離矩陣BDisMatrix是n×n維的矩陣，?a,b∈AL，活動(dòng)a和活動(dòng)b間的行為距離等于矩陣中活動(dòng)a所在的行和活動(dòng)b所在列對應(yīng)的值Ma,b=x,y，其中x=BDismin(a,b,L)，y=BDismax(a,b,L)。表1給出了第1章日志L1中各活動(dòng)對的行為距離矩陣。

表1 日志L1中活動(dòng)對間的行為距離矩陣

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

定義7基于日志的基本行為關(guān)系。設(shè)L是活動(dòng)T上事件日志，設(shè)a,b∈T：

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

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

表2 基于日志L1的基本行為關(guān)系矩陣

定義8隱變遷類型。設(shè)N:=(P,T,F,λ)是一個(gè)標(biāo)簽Petri網(wǎng)，A∪τ表示所有活動(dòng)標(biāo)簽，對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)關(guān)類型隱變遷的示例。

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

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

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

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

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

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

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

輸入: 事件日志L;

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

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

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

3.If活動(dòng)集S和活動(dòng)集T處于排他序關(guān)系，

4.then活動(dòng)集S和活動(dòng)集T處于結(jié)構(gòu)排他關(guān)系，構(gòu)造由S和T組成排他結(jié)構(gòu)。

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

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

7.If活動(dòng)集S和活動(dòng)集T處于循環(huán)交叉序關(guā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活動(dòng)集S和活動(dòng)集T處于順序結(jié)構(gòu)中的循環(huán)交叉。

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

12.then活動(dòng)集S和活動(dòng)集T處于排他結(jié)構(gòu)中的循環(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活動(dòng)集S和活動(dòng)集T處于并發(fā)結(jié)構(gòu)中的循環(huán)交叉。

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

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

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

18.遍歷BRelMatrix中的因果依賴關(guān)系，通過因果依賴關(guān)系將塊結(jié)構(gòu)組合在一起，

19.遍歷BRelMatrix中的嚴(yán)格序關(guān)系，將剩余的塊結(jié)構(gòu)合為一個(gè)完整的Petri網(wǎng)模型,

20.for(所有的and-split和and-join類型的隱變遷檢查是否冗余)設(shè)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)關(guān)類型和循環(huán)類型隱變遷的初始Petri網(wǎng)模型。

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

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

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

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

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

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

(3)

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

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

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

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

(4)

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

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

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

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

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

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

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

算法2發(fā)現(xiàn)skip類型隱變遷，構(gòu)建基于事件日志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的活動(dòng)對(a,b))

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

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

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

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

設(shè)t1為and-split變遷，t2為and-join變遷

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

8.then計(jì)算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設(shè)?c∈·(t1)T,?d∈(t2)T·,a,b∈(t1)·T，

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

14.then計(jì)算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可知，在活動(dòng)對(a,d),(a,e),(b,d),(b,e)之間存在隱變遷t1。同理可以發(fā)現(xiàn)skip類型的隱變遷t3和t4，最終得到帶多類型隱變遷的優(yōu)化Petri網(wǎng)模型M1，如圖11所示。

5 實(shí)驗(yàn)分析

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

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

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

6 結(jié)束語

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