王 穎，劉 聰+，聞立杰，曾慶田，程 龍

(1.山東理工大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,山東 淄博 255000；2.清華大學(xué) 軟件學(xué)院，北京 100084；3.山東科技大學(xué) 電子信息工程學(xué)院，山東 青島 266590;4.華北電力大學(xué) 控制與計算機(jī)工程學(xué)院，北京 102206)

1 問題的提出

作為業(yè)務(wù)過程管理[1]領(lǐng)域的一個新的研究熱點，過程挖掘旨在為傳統(tǒng)模型驅(qū)動方法和新型數(shù)據(jù)驅(qū)動方法之間構(gòu)建橋梁，從業(yè)務(wù)過程事件日志中提取相關(guān)過程信息，來為企業(yè)業(yè)務(wù)過程的理解、改進(jìn)和重構(gòu)提供事實依據(jù)[2-3]。過程挖掘的一個主要方面是發(fā)現(xiàn)過程的控制流信息，通過分析事件日志中記錄的活動執(zhí)行信息，自動構(gòu)造一個能夠描述活動間因果依賴關(guān)系的過程模型。為了評估挖掘的模型質(zhì)量，需要對事件日志和模型進(jìn)行合規(guī)性度量，常用的合規(guī)性度量指標(biāo)有契合度[4]、精確度[5]、泛化度[6]等。

大多數(shù)過程發(fā)現(xiàn)技術(shù)(如Alpha Miner[7]，Inductive Miner[8]和Heuristic Miner[9]，Split Miner[10])，以事件日志為輸入，通過分析活動間的依賴關(guān)系構(gòu)造扁平過程模型，如Petri網(wǎng)[11]、業(yè)務(wù)流程建模標(biāo)注(Business Process Model Notations, BPMN)[12]、事件驅(qū)動過程鏈(Event-driven Proccess Chain, EPC)[13]等。傳統(tǒng)的事件日志假設(shè)所有活動都屬于同一個業(yè)務(wù)過程，活動之間不存在調(diào)用關(guān)系，而且日志中的每條軌跡記錄了業(yè)務(wù)過程的一次執(zhí)行，即每條軌跡僅記錄單一過程實例的行為。當(dāng)事件日志中存在多實例子過程[14-15]時，即在父過程與子過程的業(yè)務(wù)場景中，父過程可能會調(diào)用子過程中的活動，被調(diào)用的子過程可能會被多次實例化，因此在一條軌跡中存在活動間的調(diào)用關(guān)系和多實例子過程交叉行為，在這種場景中已有假設(shè)并不成立，因此不能使用已有方法。以電子商務(wù)物流過程為例(如圖1)，用戶提交訂單后進(jìn)行付款，即活動USO(user submit order)執(zhí)行結(jié)束后，活動UPO(user payment order)調(diào)用子過程payment process,其中子過程payment process包括活動FOI(fill order information)，PO(payment order)，PC(payment complete)；之后商家確認(rèn)訂單，并進(jìn)行物流運輸，即活動MCO(merchant comfirms order)執(zhí)行結(jié)束后，活動TL(transport logistics)可能多次調(diào)用子過程logistics process,其中子過程logistics process包括活動GLI(generate logistics information)，LG(load goods)，TG(transport goods)，IU(inform user)。子過程logistics process調(diào)用結(jié)束后用戶收取貨物，整個過程結(jié)束，即活動URG(user receive goods)執(zhí)行結(jié)束后，整個過程隨活動OC(order complete)的結(jié)束而結(jié)束。整個過程產(chǎn)生的事件日志的部分片段如表1所示，其中活動UPO調(diào)用1次子過程，活動TL調(diào)用2次子過程。

表1 事件日志片段

續(xù)表1

為了保證挖掘到模型的可用性，通常需要對模型進(jìn)行正確性驗證，確保沒有死鎖、活鎖等結(jié)構(gòu)缺陷。已有大多數(shù)業(yè)務(wù)過程模型的正確性驗證技術(shù)均在扁平Petri網(wǎng)或工作流網(wǎng)基礎(chǔ)上建立，如合理性(soundness)等。然而，當(dāng)前扁平Petri網(wǎng)僅能描述單一實例過程行為，對于父過程與子過程活動之間的調(diào)用關(guān)系以及多實例子過程行為缺乏有效的形式化模型支持和模型挖掘方法。

本文提出一種從帶多實例子過程信息的生命周期事件日志中挖掘分層多實例過程模型的方法，在分層多實例過程模型的基礎(chǔ)上給出模型質(zhì)量度量指標(biāo)。基于公開的事件日志數(shù)據(jù)集，比較本文方法與已有過程挖掘方法挖掘的模型質(zhì)量，進(jìn)一步驗證本文方法針對分層多實例過程模型挖掘的有效性。

2 相關(guān)工作

2.1 過程挖掘

當(dāng)今信息系統(tǒng)及其所支持的運作過程緊密連接，記錄了大量事件日志。業(yè)務(wù)過程挖掘技術(shù)的目的是從現(xiàn)代信息系統(tǒng)普遍產(chǎn)生的事件日志中抽取有用信息，為各應(yīng)用領(lǐng)域中的過程發(fā)現(xiàn)、檢測和改進(jìn)提供手段[1]。過程挖掘技術(shù)有4種典型的方法[1]：

(1)直接的算數(shù)方法 該方法從事件日志中抽取足跡信息，并用這些足跡直接構(gòu)建過程模型，已有的過程挖掘算法如Alpha Miner[7]，Tsinghua Alpha Miner[16]，Inductive Miner[8]，Heuristic Miner[9]等。

(2)兩階段方法 該方法包括兩個步驟：①構(gòu)建一個低層模型，如一個變遷系統(tǒng)或Markov模型；②將底層模型轉(zhuǎn)化為能夠表達(dá)活動間并發(fā)關(guān)系和其他(更高級的)控制流模式的高層模型。

(3)計算智能方法 即計算智能領(lǐng)域的技術(shù)，如蟻群算法、遺傳算法、模擬退火等，這些方法并不直接將日志轉(zhuǎn)化為模型，而是用迭代過程模擬自然演化的過程。

(4)局部方法 該方法將關(guān)注點放在規(guī)則和頻繁模式上，例如Apriori算法可以有效生成頻繁項集。

采用這4種典型過程挖掘方法挖掘出一個扁平過程模型。

2.2 分層過程挖掘

面向子過程模型，MAGGI等[17]提出子過程中的事件為結(jié)構(gòu)化(以序列行式分布并可由后續(xù)事件預(yù)測)和非結(jié)構(gòu)化，在同一子日志中對所有序列結(jié)構(gòu)化事件分組，而非結(jié)構(gòu)化事件位于結(jié)構(gòu)化事件序列之間時被分為一組，因此利用結(jié)構(gòu)化和非結(jié)構(gòu)化事件從事件日志中提取子日志；SUN等[18]利用屬于同一子過程中的活動具有緊密聚集的特性，提出基于因果依賴圖的圖聚類技術(shù)，利用產(chǎn)生的集群生成若干個子日志，其中每個子日志包括屬于同一集群內(nèi)活動的所有事件；WANG等[19]提出兩種方法，這兩種方法依賴事件的內(nèi)鍵和外鍵信息構(gòu)造實例樹進(jìn)而構(gòu)造分層樹，挖掘帶有多實例子過程信息的BPMN[12]模型；劉聰?shù)萚15,20]系統(tǒng)地提出一種從事件日志中識別子過程從而發(fā)現(xiàn)分層Petri網(wǎng)的方法，并給出分層Petri網(wǎng)模型的質(zhì)量度量方法，然而該方法并不支持識別子過程的多實例特征；WEBER等[21]提出一種可以挖掘子過程模型的方法，然而挖掘過程采用分層有向圖描述，缺少嚴(yán)格的執(zhí)行語義；LIU等[14]針對多實例子過程提出多實例Petri網(wǎng)的概念并給出執(zhí)行語義，同時提出一種分層模型挖掘方法，從帶有多實例子過程的事件日志中挖掘分層事件日志，并使用已有的過程模型發(fā)現(xiàn)方法挖掘出分層模型，然而該方法依賴多實例子過程行為被唯一標(biāo)記。

另一個相關(guān)的研究領(lǐng)域是軟件過程挖掘[22-23]，從軟件執(zhí)行軌跡中挖掘行為模型。軟件行為模型通常表現(xiàn)為具有層次子過程的過程模型，而且子過程的發(fā)現(xiàn)取決于方法之間的調(diào)用關(guān)系。最近，LEEMANS等[24]提出一個集成工具，可以從軟件執(zhí)行日志中發(fā)現(xiàn)分層過程模型，然而該工具無法挖掘帶有多實例子過程的分層過程模型。

已有的模型評估指標(biāo)有契合度[4]、準(zhǔn)確性[5]、一般性[6]和復(fù)雜性[3]，BUIJIS等[25]討論了這4個度量指標(biāo)之間的關(guān)系，然而這些評估模型質(zhì)量的指標(biāo)并不適用于帶有多實例子過程的模型。針對該問題，劉聰?shù)萚20]提出將帶有子過程的分層Petri網(wǎng)轉(zhuǎn)化為扁平Petri網(wǎng)的方法，然而該方法并不適用于子過程中帶有多實例行為的事件日志。最近，LIU等[14]提出一種將分層多實例Petri網(wǎng)轉(zhuǎn)化為扁平Petri網(wǎng)的方法，從而可以采用已有的模型質(zhì)量評估指標(biāo)。

3 基礎(chǔ)知識

事件日志是有限個事件的集合，每個事件帶有多個屬性，如活動、時間戳、生命周期信息等。

定義1事件和屬性。為事件空間，即所有可能事件標(biāo)識符的集合，為事件屬性名的集合。?e∈，?n∈，#n(e)為事件e的屬性n的值，如果事件e不含有屬性名n，則#n(e)=⊥，即為空值。

本文的事件均有如下屬性：

(1)#activity(e)∈UA為事件e相關(guān)聯(lián)的活動名屬性，其中UA是所有可能活動名的集合。

(2)#trans(e)∈UL為事件的生命周期屬性，其中UL={schedule,assign,reassign,start,suspend,resume，complete}。

(3)#time(e)∈UT為事件的時間戳屬性，其中UT為事件所有可能的時間集合。

(4)#instance(e)∈UI為事件的的案例屬性,其中UI為事件所有可能的案例集合。

事件日志中的事件都需要對應(yīng)到一個過程實例(即過程模型的一次執(zhí)行)，稱為案例。事件日志由案例組成，案例由事件組成。案例中的事件用軌跡的形式表示，即事件的序列。

定義2案例、軌跡和事件日志。Ζ為案例空間，即所有可能的案例標(biāo)識符的集合。軌跡σ為事件的一個有限序列，其中每個事件僅出現(xiàn)一次，即對1≤i

事件的生命周期信息有計劃、開始、中止、暫停、結(jié)束等，本文僅考慮開始和結(jié)束狀態(tài)，即活動在開始和結(jié)束時刻記錄的事件。?a∈,若#trans(a)=start，則表示為as；若#trans(a)=complete，則表示為ac。

定義3標(biāo)記Petri網(wǎng)[11]。標(biāo)記Petri網(wǎng)是一個4元組PN=(P,T,F,l)，滿足：①P∩T=?，P∪T≠?，P為庫所集合，T為變遷集合；②F?((P×T)∪(T×P))為流關(guān)系；③l:T→Γ為變遷標(biāo)記函數(shù)，Γ為標(biāo)記集合，τ∈Γ為不可見標(biāo)記。

4 分層多實例過程模型的構(gòu)造

本章介紹從帶有子過程多實例信息的事件日志中發(fā)現(xiàn)分層多實例Petri網(wǎng)模型，構(gòu)造分層多實例過程模型的基本原理如圖2所示。分層多實例過程模型的挖掘過程如下：

步驟1挖掘任務(wù)嵌套關(guān)系。以生命周期事件日志為輸入，挖掘任務(wù)間的嵌套關(guān)系并輸出嵌套關(guān)系樹。

步驟2構(gòu)造分層事件日志。以生命周期事件日志和嵌套關(guān)系樹為輸入，分析生命周期事件日志中任務(wù)的嵌套關(guān)系，構(gòu)造分層事件日志，并輸出分層事件日志。

步驟3識別與重構(gòu)子日志多實例。以分層事件日志為輸入，遍歷每一層級的子日志，對存在多實例行為的子日志進(jìn)行多實例識別，輸出重構(gòu)后的分層事件日志。

步驟4挖掘分層多實例過程模型。以重構(gòu)后的分層事件日志為輸入，遍歷分層事件日志中每一層級的子日志，采用Inductive Miner方法挖掘其對應(yīng)的子過程模型，輸出分層多實例過程模型。

4.1 任務(wù)嵌套關(guān)系的挖掘

定義4嵌套關(guān)系[14]。在一條軌跡σ中，活動a嵌套活動b，記為aΘb當(dāng)且僅當(dāng)存在i,j,k,l∈{1,2,…,|σ|}，有#trans(σ(i))=start∧#activity(σ(i))=a∧#trans(σ(j))=start∧#activity(σ(j))=b∧#trans(σ(k))=complete∧#activity(σ(k))=b∧#trans(σ(l))=complete∧#activity(σ(l))=a,且i

以表1中的事件日志為例，活動間的嵌套關(guān)系有UPOΘFOI,UPOΘPO,UPOΘPC,TLΘGLI,TLΘLG,TLΘTG,TLΘIU。根據(jù)嵌套關(guān)系定義嵌套活動集合NA={e1∈A|?e2∈A:e1Θe2∧?e2Θe1}，表1中的事件日志對應(yīng)的嵌套活動集={UPO,TL}。

嵌套關(guān)系表示父過程與子過程的調(diào)用關(guān)系，即活動間的層次關(guān)系，用于層次過程模型?；诨顒娱g嵌套關(guān)系可以挖掘帶有子過程的分層過程模型。

下面用一個樹狀結(jié)構(gòu)表示從生命周期事件日志中挖掘的活動間的嵌套關(guān)系。

定義5嵌套關(guān)系樹。生命周期事件日志L的嵌套關(guān)系樹為HTree(L)=(rootAct,HNode(rootAct),η)，其中：①rootAct?為根節(jié)點集；②HNode(rootAct)={Actti|ti∈∧ti∈rootAct}為根節(jié)點集rootAct的子節(jié)點集合，Actti為嵌套活動ti所嵌套的活動集合，滿足?a∈Actti，有tiΘa；③η:→HNode(rootAct)為從嵌套活動集到節(jié)點集的映射，即?ti∈，有η(ti)=Actti，嵌套活動到節(jié)點集的映射構(gòu)成樹狀結(jié)構(gòu)。

嵌套關(guān)系樹節(jié)點集內(nèi)的活動不存在嵌套關(guān)系，也不存在子節(jié)點集內(nèi)的活動嵌套父節(jié)點集內(nèi)的活動，而且構(gòu)造嵌套關(guān)系樹只考慮活動間的直接嵌套關(guān)系。圖3所示為表1中事件日志的嵌套關(guān)系樹，rootAct={USO,UPO,MCO,TL,URG,OC}，而且活動之間不存在嵌套關(guān)系，活動FOI,PO,PC為嵌套活動USO的子節(jié)點集活動，活動GLI,LG,TG,IU為活動TL的子節(jié)點集活動。

4.2 分層事件日志的構(gòu)造

定義6分層事件日志。L為生命周期事件日志,HTree(L)=(rootAct,HNode(rootAct),η)為嵌套關(guān)系樹，L的分層事件日志HL(L)=(rootLog,HL(rootLog))，其中：①rootLog={σ|?σ∈ζ,i∈{1,…,|σ|}，#activity(σ(i))?rootAct:σ(〗σ(i)}}為根節(jié)點日志；②HL(rootLog)={(ti,NLogti)|ti∈NA∧ti∈rootAct}為rootLog的子日志，NLogti={σ|?σ∈ζ,i∈{1,…,|σ|},?tiΘ#activity(σ(i)):σ(〗σ(i)}}為嵌套活動ti的子日志。

以L1=[As,Ac,Bs,Cs,Cc,Cs,Cs,Cc,Cc,Bc100]為例，rootLog=[As,Ac,Bs,Bc100]，嵌套任務(wù)集NA={B}，嵌套任務(wù)B對應(yīng)的子日志NLogB=[Cs,Cc,Cs,Cs,Cc,Cc100]。

4.3 子日志多實例的識別與重構(gòu)

在一次實例中，父過程可能調(diào)用一次子過程，也可能多次調(diào)用子過程，而多次調(diào)用子過程會產(chǎn)生交錯軌跡，已有挖掘方法并不能有效處理子過程多實例行為，本節(jié)介紹子日志多實例識別方法。

多實例識別是將子日志中多實例行為的交錯軌跡分割為若干條軌跡，通過挖掘子日志活動間的緊鄰關(guān)系構(gòu)造活動頻率矩陣，基于活動頻率矩陣模擬子過程運行狀態(tài)，為活動分配最佳案例。然后根據(jù)新的子日志更新活動頻率矩陣，進(jìn)行新一輪最佳案例分配，在不斷迭代過程中縮小模擬產(chǎn)生的軌跡與實際執(zhí)行軌跡的差別，直到活動頻率矩陣中的值不再改變，多實例識別過程結(jié)束，得到重構(gòu)的子日志。

整個過程在活動的生命周期狀態(tài)為complete的情況下執(zhí)行，因此先對子日志進(jìn)行預(yù)處理，僅保留生命周期信息為complete的活動。例如將子日志NLogTL=[GLIs,GLIs,GLIc,LGs,LGc,TGs,GLIc,LGs,LGc,TGc,IUs,IUc,TGs,TGc,IUs,IUc]預(yù)處理后得到的子日志NLogTL=[GLIc,LGc,GLIc,LGc,TGc,IUc,TGc,IUc]，其中活動下標(biāo)s表示活動的生命周期狀態(tài)為start，下標(biāo)c表示活動的生命周期狀態(tài)為complete。

定義7緊鄰關(guān)系。NLogti為嵌套活動ti的子日志，?σ∈NLogti,?a,b∈σ,a緊鄰b，記為a?b，當(dāng)且僅當(dāng)?i∈{1,…,|σ|-1}，有#activity(σ(i))=a∧#activity(σ(i+1))=b。

活動間的緊鄰關(guān)系有頻次和頻率兩個屬性，下面介紹這兩個屬性的詳細(xì)定義。

定義8緊鄰關(guān)系的頻次和頻率。?a,b,c∈,∧#activity(σ(i+1))=b}|為a緊鄰b的頻次，P(a?b)=|a?b|/|a?c|為a緊鄰b的頻率。

以表1中的生命周期事件日志為例，在案例1中，|GLI?LG|=2，P(GLI?LG)=2/2=1.0。

在模擬子過程運行過程中，為了表示一條軌跡開始和結(jié)束，將軌跡中第一個活動記為開始活動，最后一個活動記為結(jié)束活動，計算其出現(xiàn)的頻率，并設(shè)置閾值?，頻率大于閾值的開始活動或結(jié)束活動構(gòu)成開始活動集或結(jié)束活動集。例如NLogTL的開始活動集和結(jié)束活動集分別為startSet={GLI}，endSet={IU}。

定義9活動頻率矩陣。NLogti為嵌套活動ti的子日志，Uti?UA為NLogti的活動集合，活動頻率矩陣用M表示，定義為?a,b∈Uti,M(a,b)=P(a?b)，即活動頻率矩陣的行和列由Uti中的所有活動形成并有序排列，活動頻率矩陣的值為活動緊鄰關(guān)系的頻率。

以表1中事件日志的嵌套活動TL對應(yīng)的子日志NLogTL為例，其活動頻率矩陣如圖4所示。

定義10子案例集。UE?UI為在模擬子過程運行過程中處于運行狀態(tài)的軌跡集合。

下面根據(jù)活動頻率矩陣給出多實例識別的定義。

定義11多實例識別。?ti∈，NLogti為嵌套活動ti的子日志，對于?σ∈NLogti，先初始化UE=?，則?e∈σ,存在兩種情況：①若UE=?∨e∈startSet,則#activity(σ1(1))=e，UE∪{σ1}，即在活動e處開始一個新的案例σ1，并將σ1加入UE集合；②否則，若?σ∈UE:c←argmaxσ(M(#activity(σ(|σ|)),e)),則#activity(c(|c|+1))=e,即從UE中找到一個案例σ，滿足M(#activity(σ(|σ|)),e)值最大，#activity(σ(|σ|))緊鄰e的概率最大，將案例σ記為c并將e分配給案例c，此時若e∈endSet，則UE∪(〗c}，即在活動e處結(jié)束案例c。

以NLogTL=[GLIc,LGc,GLIc,LGc,TGc,IUc,TGc,IUc1]為例，設(shè)置?=0.2，則startSet={GLI},endSet={IU}，根據(jù)定義9初始化M，如圖4所示。從NLogTL的第一個軌跡σ=GLIc,LGc,GLIc,LGc,TGc,IUc,TGc,IUc開始，先初始化UE=?，從第1個活動GLI開始,因為GLI∈startSet,所以從GLI處開始一個新的案例σ1并將GLI加入σ1，此時σ1=GLI，UE={σ1}；對于第2個活動LG,因為M(#activity(σ1(|σ1|)),LG)=1.0,所以將GLI加入σ1，此時σ1=GLI,LG；對于第3個活動GLI,因為GLI∈startSet，所以開始一個新的案例σ2并將GLI加入σ2，此時σ2=GLI，UE={σ1,σ2}；依次為第4個和第5個活動分配案例后,σ1=GLI,LG，TG,σ2=GLI,LG,UE={σ1,σ2};對于第6個活動IU,因為M(#activity(σ1(|σ1|)),IU)>M(#activity(σ2(|σ2|)),IU),所以將IU加入σ1，此時σ1=GLI,LG,TG,IU，因為IU∈endSet，所以案例σ1運行結(jié)束，UE={σ2}，更新后的子日志NLogTL=[GLI,LG,TG,IU2]。

以預(yù)處理后的子日志為輸入，根據(jù)定義9初始化活動頻率矩陣M，根據(jù)定義11依次為子日志軌跡中的所有活動分配最佳案例，得到新的子日志，然后根據(jù)新的子日志更新活動頻率矩陣M，進(jìn)行一輪新的子日志更新，直到活動頻率矩陣M的值不再改變，輸出重構(gòu)后的子日志。

4.4 分層多實例過程模型的挖掘

定義12帶嵌套變遷的Petri網(wǎng)。帶嵌套變遷的Petri網(wǎng)為一個二元組PNN=(PN,β)，其中PN=(P,T,F,l)為一個標(biāo)記Petri網(wǎng)；β:T→{A,N}為映射函數(shù)，滿足?t∈T,β(t)=A表示t為普通變遷；β(t)=N表示t為嵌套變遷，而且Ta={t∈T|β(t)=A}表示普通變遷集合，Tn={t∈T|β(t)=N}為嵌套變遷集合。

給定一個帶嵌套變遷的Petri網(wǎng)PNN，用單線矩形表示普通變遷，雙線矩形表示嵌套變遷，圖5所示為一個帶嵌套變遷的Petri網(wǎng)，圖中T為普通變遷，N為嵌套變遷，即Ta={T},Tn={N}。

定義13分層多實例Petri網(wǎng)。分層多實例Petri網(wǎng)定義為HMPN=(Q,PNN0,,map)，其中：Q={PNti|?ti∈}，即所有嵌套變遷對應(yīng)的子模型集合，為嵌套變遷集合；PNN0為頂層帶嵌套變遷的Petri網(wǎng)；map:→{1,+}×Q(〗PNN0},即?ti∈，若map(ti)=(1,PNti),則嵌套變遷ti調(diào)用一次子過程，否則map(ti)=(+,PNti)，嵌套變遷ti調(diào)用多次子模型PNti。

分層多實例Petri網(wǎng)的子過程模型是一個扁平Petri網(wǎng)。圖6所示為一個分層多實例Petri網(wǎng)，其中={a,c},嵌套變遷a調(diào)用一次子過程PNa,嵌套變遷c多次調(diào)用子過程PNc。

以重構(gòu)后的分層事件日志為輸入，遍歷每一層級的子日志，采用Inductive Miner方法挖掘其對應(yīng)的子過程模型，最后輸出分層多實例Petri網(wǎng)。

5 工具實驗與方法評估

本章針對分層多實例過程模型方法的有效性進(jìn)行評估,分別介紹本文方法的實驗工具，以及分層多實例過程模型的評價指標(biāo)，并基于公開的事件日志數(shù)據(jù)集與已有方法進(jìn)行定量比較。

5.1 分層多實例過程模型的支持工具

在開源業(yè)務(wù)過程挖掘平臺ProM(http://www.promtools.org/)的支持下，針對本文所提方法，進(jìn)一步開發(fā)出Hierarchical Multi-instance Business Processes Model Discovery(https://svn.win.tue.nl/repos/prom/Packages/HierarchicalProcessDiscovery/)插件，該插件可以挖掘出分層多實例Petri網(wǎng)模型，圖7所示為插件的詳細(xì)信息，開發(fā)出的Convert a Hierarchical Multi-instance Petri Net to a Flat Petri Net插件可以將分層多實例Petri網(wǎng)轉(zhuǎn)化為扁平Petri網(wǎng)。

5.2 質(zhì)量評估指標(biāo)

為了評估分層多實例Petri網(wǎng)模型的質(zhì)量，將分層多實例Petri網(wǎng)轉(zhuǎn)化為帶有生命周期信息的扁平Petri網(wǎng)，從而使用已有的度量指標(biāo)，即契合度(fitness)[4]和精確度(presicion)[5]。首先定義轉(zhuǎn)化規(guī)則。

給定一個分層Petri網(wǎng)，針對不同變遷類型定義不同的轉(zhuǎn)化規(guī)則(如圖8)：

(1)針對普通變遷 將普通變遷t轉(zhuǎn)化為兩個普通變遷ts和tc，同時增加一個庫所Pt，增加流關(guān)系(ts,Pt),(Pt,tc)。

(2)針對調(diào)用一次子過程的嵌套變遷 將嵌套變遷t轉(zhuǎn)化為兩個普通變遷ts和tc,增加庫所Pe和流關(guān)系(ts,Pe),(Pe,tc),(ts,Ps),(Pc,tc)，其中Ps和Pc為子過程的開始庫所和結(jié)束庫所。

(3)針對調(diào)用多次子過程的嵌套變遷 將嵌套變遷t轉(zhuǎn)化為兩個普通變遷ts和tc,增加兩個庫所Pe和Px,以及兩個不可見變遷τ1和τ2，增加流關(guān)系(ts,Pe),(ts,Ps),(Pe,tc),(Pe,τ1),(τ1,Pe),(τ2,Pe),(Pe,τ2),(Pc,tc),(τ1,Px),(Px,τ2),(Pc,τ2),(τ1,Ps)。

本文用契合度和精確度測量挖掘模型的質(zhì)量，具體為：①契合度旨在衡量挖掘的模型重演事件日志中案例的能力，契合度越高，模型重演事件日志中案例的能力越強(qiáng)，契合度為1.0時表示日志中的所有案例都可以被模型完全重演；②精確度旨在衡量所挖掘的模型產(chǎn)生的軌跡記錄在事件日志中的能力，精確度值越高說明所挖掘的模型產(chǎn)生的軌跡在事件日志中存在的比例越高，精確度越低說明所挖掘的模型是欠擬合的，即該模型允許存在與日志差異較大的行為。契合度和精確度之間存在一個平衡點，因此引入F-值，

F-值是契合度和精確度的調(diào)和平均數(shù)，用來均衡兩者之間的關(guān)系。當(dāng)契合度和精確度很低時，F(xiàn)-值也很低；當(dāng)契合度和精確度都接近1時，F(xiàn)-值才會接近1。F-值越高，模型質(zhì)量越好。

5.3 數(shù)據(jù)集和挖掘方法

實驗采用4個公開的數(shù)據(jù)集(https://figshare.com/articles/dataset/multi-instance_subprocessmining/20424348)。本文所用數(shù)據(jù)需保證為生命周期事件日志，即任意一個活動都對應(yīng)一個開始活動和一個結(jié)束活動，因此需對數(shù)據(jù)集進(jìn)行預(yù)處理。數(shù)據(jù)集具體介紹如下：

(1)SMTP Log 該數(shù)據(jù)集基于軟件多線程場景生成，其中一個函數(shù)或多個函數(shù)為一個模塊，一個模塊表示過程模型中的一個活動。該過程模型涉及一個子過程。

(2)CRMC Log 該數(shù)據(jù)集基于Amazon web服務(wù)上開源云資源管理工具Netflix Asgard的升級過程生成，整個過程包括升級前的準(zhǔn)備和升級過程，升級活動調(diào)用升級子過程。

(3)TSEC Log 該數(shù)據(jù)集基于跨國電子商務(wù)場景生成。用戶提交訂單后，商家聯(lián)系第三方物流；用戶收到物品后，完成訂單并支付。該過程涉及第三方物流過程和付款過程兩個子過程。

(4) CIPS Log 該數(shù)據(jù)集基于大型公司內(nèi)部采購場景生成，部門經(jīng)理和倉庫管理人員審核并通過提交的采購申請單后，采購部門進(jìn)行采購，并將采購貨物交由驗收部門驗收，驗收結(jié)束后將各種報表提交到財務(wù)部門。整個過程涉及采購、驗收和財務(wù)付款3個子過程。

4個數(shù)據(jù)集預(yù)處理后的事件日志的基本數(shù)據(jù)情況如表2所示。

表2 數(shù)據(jù)集的基本信息

因為Inductive Miner[8]，Inductive Miner Lifecycle[26]，Hierarchical Process Miner[14]3種挖掘方法能夠處理帶有生命周期的事件日志，并能定量測量挖掘得到的模型質(zhì)量，因此采用這3種挖掘方法與本文所提分層多實例過程挖掘(Hierarchical Multi-instance Process Mining, HPM2)方法進(jìn)行比較。4種挖掘方法的具體信息如下：

(1)Indcutive Miner 該方法可以處理帶有生命周期信息的事件日志，在挖掘過程中將classifier設(shè)置為任務(wù)名和生命周期信息的組合，即每個任務(wù)在挖掘的模型中均對應(yīng)一個開始任務(wù)和一個結(jié)束任務(wù)。

(2)Inductive Miner Lifecycle 該方法同樣可以處理帶有生命周期信息的事件日志。

(3)Hierarchical Process Miner 該方法以生命周期事件日志為輸入，將噪聲閾值設(shè)置為0.9，挖掘出一個分層Petri網(wǎng)模型，并可將分層Petri網(wǎng)轉(zhuǎn)化為扁平Petri網(wǎng)。

(4) HPM2該方法以生命周期事件日志為輸入，將噪聲閾值設(shè)置為0.9，挖掘出分層多實例Petri網(wǎng)模型，并提供了將分層多實例Petri網(wǎng)轉(zhuǎn)化為扁平Petri網(wǎng)的方法。

5.4 實驗結(jié)果分析

采用上述4組數(shù)據(jù)集對4種挖掘方法進(jìn)行定量分析，實驗結(jié)果如表3所示，得到如下結(jié)論：

(1)Inductive Miner方法在處理帶有生命周期信息的事件日志時，需要設(shè)置classifier為任務(wù)名和生命周期信息的組合，每個任務(wù)都對應(yīng)開始變遷和結(jié)束變遷，導(dǎo)致挖掘的模型很復(fù)雜，而且IM方法并不能識別子過程的多實例行為，雖然能保證模型契合度為1.0，但是模型精確度很低，導(dǎo)致F-值也很低。

(2)Inductive Miner Lifecycle方法雖然可以處理帶有生命周期信息的事件日志，但是并不能準(zhǔn)確識別多實例子過程行為，只簡單地將其歸并為并發(fā)行為，且不能保證模型契合度為1.0。

(3)Hierarchical Process Miner方法可以分析出任務(wù)間的嵌套關(guān)系并識別子過程，并挖掘出分層模型,其雖然不能識別任務(wù)間的多實例行為，將多實例行為歸并為并發(fā)行為，但是優(yōu)于Inductive Miner方法和Inductive Miner Lifecycle方法。

(4)HPM2方法可以精確地分析任務(wù)間的嵌套關(guān)系，從而有效分析出子過程，針對存在多實例行為的子日志，通過多實例識別，挖掘出分層多實例過程模型，從而在保證模型契合度為1.0的前提下提高模型的精確度。

表3 實驗結(jié)果

6 結(jié)束語

本文針對帶有多實例子過程的生命周期事件日志，提出一種分層多實例過程模型挖掘方法，整個過程分為4個部分：①以生命周期事件日志為輸入，挖掘活動間的嵌套關(guān)系并構(gòu)造嵌套關(guān)系樹；②根據(jù)嵌套關(guān)系樹構(gòu)造分層事件日志；③對具有多實例行為的子日志進(jìn)行多實例識別，得到重構(gòu)的分層事件日志；④遍歷重構(gòu)后的分層事件日志中每一層級的子日志，采用Inductive Miner方法挖掘子過程模型，最終挖掘出分層多實例Petri網(wǎng)。已有的質(zhì)量度量指標(biāo)只適用于扁平過程模型，并不適用于分層多實例Petri網(wǎng)模型，因此本文給出分層多實例Petri網(wǎng)轉(zhuǎn)化為扁平Petri網(wǎng)規(guī)則，并采用契合度、精確度和復(fù)雜度度量指標(biāo)分析扁平Petri網(wǎng)質(zhì)量。

針對帶有多實例子過程的事件日志，未來可在以下方面進(jìn)行擴(kuò)展和改進(jìn)：①在處理多實例中帶有循環(huán)結(jié)構(gòu)的事件日志時，可進(jìn)一步優(yōu)化算法性能或提出更高效的算法;②該方法適用于生命周期事件日志，未來可進(jìn)一步考慮非生命周期事件日志；③針對父過程和子過程異步執(zhí)行情況提出更高效的方法；④針對大規(guī)模事件日志，進(jìn)一步提高該挖掘方法的性能。