過程挖掘算法研究綜述

敬思遠(yuǎn)

(1.樂山師范學(xué)院 人工智能學(xué)院，四川 樂山 614000；2.互聯(lián)網(wǎng)自然語言智能處理四川省高校重點實驗室(樂山師范學(xué)院)，四川 樂山614000)

0 引言

過程挖掘(Process Mining)，也稱為工作流挖掘，是數(shù)據(jù)挖掘領(lǐng)域的一個重要分支。該研究的目的，是從信息系統(tǒng)的事件日志中發(fā)現(xiàn)業(yè)務(wù)流程的真實執(zhí)行過程，并以可視化的方式提供給用戶進(jìn)行分析和決策[1]。當(dāng)前，過程挖掘已經(jīng)被廣泛應(yīng)用于智能制造、流程建模、內(nèi)部安全檢測與審計等諸多領(lǐng)域。舉例來說，ASML公司采用過程挖掘技術(shù)對其光刻機(jī)制造芯片的各個環(huán)節(jié)進(jìn)行分析，并提供優(yōu)化決策[2]；飛利浦公司針對其醫(yī)療設(shè)備，從全球范圍采集所有設(shè)備的事件日志，并通過過程挖掘技術(shù)發(fā)現(xiàn)用戶的使用習(xí)慣，從而優(yōu)化其產(chǎn)品設(shè)計[3]；SAP公司將過程挖掘集成到ERP系統(tǒng)中協(xié)助用戶進(jìn)行過程建模[4]。

過程挖掘的研究方向主要有三方面：過程發(fā)現(xiàn)，符合性檢測和過程增強(qiáng)[1]。過程發(fā)現(xiàn)(Process discovery)的目的是“重現(xiàn)”業(yè)務(wù)流程的真實執(zhí)行過程。該任務(wù)的輸入是信息系統(tǒng)的歷史記錄(稱為事件日志)，輸出為算法“觀測到”的過程模型。根據(jù)不同的應(yīng)用，該任務(wù)可以從控制流、資源分配、組織管理等不同的角度進(jìn)行挖掘。符合性檢測(Conformance checking)用于檢測事件日志和過程模型是否一致，并對二者的符合性進(jìn)行量化。符合性檢測常用于評價過程發(fā)現(xiàn)算法的性能，以及用于安全審計、內(nèi)部安全分析等任務(wù)。過程增強(qiáng)(Process Enhancement)是對已有的過程模型進(jìn)行完善和增強(qiáng)，例如過程模型修復(fù)，為過程模型增加新的屬性等等。本文集中討論基于控制流的過程發(fā)現(xiàn)算法。

過程挖掘領(lǐng)域在近10年里發(fā)展迅速，期間涌現(xiàn)出很多高效的算法。遺憾的是，目前還沒有研究對這些新算法進(jìn)行梳理和比較。本文從過程挖掘的一些基本概念出發(fā)，對過程模型的表示，過程挖掘中的一些關(guān)鍵問題進(jìn)行逐一回顧。最后，對當(dāng)前主流的過程挖掘算法進(jìn)行分類比較，總結(jié)了各自的優(yōu)勢和不足。

1 過程挖掘相關(guān)知識

1.1 事件日志

過程感知信息系統(tǒng)能夠?qū)I(yè)務(wù)流程中活動(以下統(tǒng)稱為活動)的執(zhí)行記錄持久化到本地文件系統(tǒng)或數(shù)據(jù)庫中，形成事件日志。圖1中給出了一個事件日志片段。從圖中可以看出，事件日志是一種基于XML的層次化結(jié)構(gòu)。一個事件日志由若干trace(稱為“軌跡”或“跡”)組成，而一個trace是由若干event(稱為“事件”)組成。Event是活動發(fā)生的一個實際案例，其中包含了與活動相關(guān)的若干屬性，例如事件名(concept:name)、生命周期(lifecycle:transition)、時間戳(time:timestamp)，等等。圖1中給出的trace是一個關(guān)于保險公司理賠流程的實際發(fā)生序列，受理→在線審查→票據(jù)審查→決策→理賠。IEEE Task Force on Process Mining于2016年正式發(fā)布了事件日志的國際標(biāo)準(zhǔn)，稱為IEEE 1849-2016 XES Standard[5]。該標(biāo)準(zhǔn)對事件日志的內(nèi)容和格式進(jìn)行了規(guī)范統(tǒng)一。

圖1 事件日志

下面給出事件日志的形式化定義。

定義 1. 設(shè)A是業(yè)務(wù)流程中活動的有限集合，則σ∈A*是活動的有限序列，L∈Β(A*)是事件日志。其中，A*表示集合A的Kleene 閉包。

例如，令A(yù)={A=“受理”, B=“在線審查”, C=“線下審查”, D=“票據(jù)審查”, E=“決策”, F=“重審”, G=“理賠”, H=“拒絕”}，L={10, 5, 3}是一個包含有18個trace的事件日志，其中10表示這條軌跡在日志中出現(xiàn)了10次。

1.2 過程模型表示

常用的過程模型表示方法主要有佩特里網(wǎng)(Petri net)、因果網(wǎng)(Causal net)、過程樹(Process tree)，等。這些過程模型的表示方法各有優(yōu)劣。不同的過程挖掘算法采用的模型表示方法也不盡相同。采用不同方法表示的過程模型之間一般可以相互轉(zhuǎn)化，比如可以將一個causal net轉(zhuǎn)換成與其對應(yīng)的petri net。此外，還有一些語義表示能力更強(qiáng)的過程建模語言，如BPMN、YAWL等。這些語言常作為建模工具提供給用戶使用，但是在過程挖掘研究中使用較少，本文不做介紹。接下來，本節(jié)對以上三種表示方法進(jìn)行重點介紹。

首先介紹petri net(也稱為Place/Transition Net，簡稱P/T net)。P/T net是一種數(shù)學(xué)表示能力非常強(qiáng)的建模語言。通常，P/T net由庫所(Place)和變遷(Transition)組成，Place和Transition之間采用有向弧連接。它的形式化定義如下所示。

定義 2[6].P/T net是一個三元組(P,T,F)，其中：a)P表示Place的有限集合；b)T表示Transition的有限集合；c)F=(P×T)γ(T×P)表示有向弧的集合。

在P/T net基礎(chǔ)上加上一個起始Place和一個終止Place，即得到表示過程模型的工作流網(wǎng)(Workflow Net，簡稱Wf-net)。圖2中是一個與上節(jié)給出實例對應(yīng)的Wf-net，圖中圓圈表示Place，方框表示Transition。可以看到，每個Transition上都有一個活動名稱，說明Transition和活動是一一對應(yīng)的。當(dāng)某個Transition的所有前驅(qū)結(jié)點(即Place)均處于就緒狀態(tài)時，該Transition即可觸發(fā)，并產(chǎn)生一個Event。在P/T net中，一個Place處于就緒狀態(tài)指的是位于該結(jié)點的Token數(shù)大于0(即圖2中的小黑點)。舉例來說，圖2中的“開始”結(jié)點目前已處于就緒狀態(tài)，因此它的下一個Transition(受理)可以觸發(fā)。需要說明的是，圖中B和C之間，G和H之間是選擇關(guān)系(即每次只有一個Transition可以觸發(fā))，而{B,C}和D之間是并行關(guān)系。因此，該過程模型可能產(chǎn)生的trace包括，，，等等。

圖 2Wf-netFig 2 Wf-net

定義 3[7].C-net表示為一個四元組CM=(T,C,I,O)，其中：a) T表示所有活動的有窮集合；b) C∈T×T是因果關(guān)系的有限集；c) I:T→I(T)為輸入映射函數(shù)，?t∈T，I(t)={t'|(t',t)∈C}；d) O:T→O(T)為輸出映射函數(shù)，?t∈T，O(t)={t'|(t,t')∈C}。

表1中給出了由上述Wf-net轉(zhuǎn)化的C-net。其中，T={A,B,C,D,E,F,G,H}。I(A)=表示活動A的輸入為空集；O(A)={{B,C},{D}}表示活動A的輸出為{B,C}和{D}，其中活動B和活動C之間是選擇關(guān)系，而{B,C}和{D}之間是并列關(guān)系。因此，A之后的活動發(fā)生序列可能是BD，CD，DB，DC。

表1 C-netTable 1 C-net

圖3 P-treeFig 3 P-tree

2 過程挖掘中的關(guān)鍵問題

2.1 一些特殊挖掘任務(wù)

在過程挖掘算法中，除了需要發(fā)現(xiàn)一些基本的流程結(jié)構(gòu)外(如順序結(jié)構(gòu)、選擇結(jié)構(gòu)、并行結(jié)構(gòu)、循環(huán)結(jié)構(gòu)，等等)，還需要處理一些特殊問題，例如重名活動、不可見活動、非自由選擇結(jié)構(gòu)等等。

重名活動指的是有兩個或兩個以上的活動具有相同的名字。引起該問題的原因有幾方面。一是由事件日志中的Event屬性不完備所導(dǎo)致。例如在醫(yī)院的住院信息管理系統(tǒng)中，護(hù)士需要對病人進(jìn)行術(shù)前化驗檢查和術(shù)后化驗檢查，但由于系統(tǒng)中只有“化驗”這一項活動，并沒有事件屬性對“術(shù)前”還是“術(shù)后”進(jìn)行標(biāo)注，因此事件日志中也不會對其進(jìn)行區(qū)分。二是由活動“粒度”不同引起的重名活動。例如，病人在醫(yī)院進(jìn)行化驗，可以細(xì)分為血常規(guī)檢查、肝功檢查、胃鏡檢查等不同項目，但是在日志中它們均統(tǒng)稱為“化驗”，因此算法很難將其進(jìn)行區(qū)分。

不可見活動在流程設(shè)計中又稱為“skip”模式。該活動并沒有實際的意義，僅起到路由的作用。圖4中給出了一個不可見活動的例子，其中黑色的方框即表示一個不可見活動。從圖中可以看出，當(dāng)P1處于就緒狀態(tài)時，既可以觸發(fā)活動A執(zhí)行，也可以從不可見活動通過，從而跳過活動A的執(zhí)行。由于不可見任務(wù)并不會出現(xiàn)在事件日志中，因此很難被算法發(fā)現(xiàn)。

圖4 不可見活動

非自由選擇結(jié)構(gòu)是一種同步和選擇同時出現(xiàn)的復(fù)雜結(jié)構(gòu)。在該結(jié)構(gòu)中，后面的Transition的觸發(fā)依賴于前面的Transition的選擇。圖5中給出了一個非選擇結(jié)構(gòu)的例子。其中P1是一個選擇結(jié)構(gòu)，要么A被觸發(fā)，要么B被觸發(fā)。假設(shè)觸發(fā)的是Transition A，接下來出現(xiàn)一個并行結(jié)構(gòu)P2和P3，然后Transition C被觸發(fā)。注意到，Transition C被觸發(fā)后又是一個選擇結(jié)構(gòu)，若不考慮其他因素，則Transition D和Transition E都可能被觸發(fā)。但由于Transition D依賴于P3和P5，Transition E依賴于P5和P4，因此最終只能觸發(fā)Transition D。這種遠(yuǎn)程的依賴關(guān)系在過程挖掘中很難被發(fā)現(xiàn)。

圖5 非自由選擇結(jié)構(gòu)

2.2 事件日志的噪聲和不完備性

所有過程挖掘算法的起點都是事件日志。因此，事件日志的質(zhì)量會直接影響最后的挖掘結(jié)果。事件日志處理中經(jīng)常會遇到以下兩方面的問題。

首先是噪聲數(shù)據(jù)。真實環(huán)境下，事件日志中出現(xiàn)噪聲是非常常見的。引起噪聲的情況非常多，例如事件日志服務(wù)器工作異常(斷電、宕機(jī)、網(wǎng)絡(luò)擁塞等)，分布式環(huán)境下某個生產(chǎn)服務(wù)器工作異常，等等。噪聲數(shù)據(jù)的特點是出現(xiàn)頻率低，因此一般采用數(shù)據(jù)清洗技術(shù)對噪聲進(jìn)行過濾，或者對挖掘得到的過程模型進(jìn)行剪枝。但是，如何有效區(qū)分噪聲和低頻Trace是一個難點。

其次是日志的完備性。大部分算法在設(shè)計時都會假設(shè)日志是完備的，即所有可能出現(xiàn)的活動軌跡在事件日志中均是包含的。但是這個假設(shè)難以保證一定成立。舉例來說，假設(shè)一個過程中包含有10個并行的活動，那么這些活動出現(xiàn)在事件日志中有10！種不同的組合，如果只記錄1000條Trace，很明顯不可能覆蓋所有可能出現(xiàn)的情況。此外，在真實環(huán)境下，有些Trace可能很長時間都不會出現(xiàn)，但是這些Trace對應(yīng)的業(yè)務(wù)過程在信息系統(tǒng)中卻是真實存在的。

2.3 如何平衡性能指標(biāo)

目前常常從四個方面來評價過程挖掘算法的輸出結(jié)果[9]，分別是Fitness、Precision、Generalization以及Simplicity。

Fitness指標(biāo)用于評價挖掘得到的過程模型能夠重現(xiàn)事件日志的能力。過程模型的Fitness值等于1當(dāng)且僅當(dāng)事件日志中所有的Trace都能被該模型重現(xiàn)。換句話說，能被模型重現(xiàn)的Trace越多，該模型的Fitness值就越高。Fitness目前是評價過程模型質(zhì)量最重要的指標(biāo)。

Precision指標(biāo)用于評價過程模型的精度。如果一個過程模型能夠產(chǎn)生出很多事件日志中不存在的Trace，即可認(rèn)為該模型的精度較低。在機(jī)器學(xué)習(xí)中該現(xiàn)象也稱為“欠擬合”。舉例來說，“花”模型能夠產(chǎn)生出任意的Trace，但是它的Precision值非常低，對實際應(yīng)用也毫無價值，這是過程挖掘算法不希望得到的。

Generalization指標(biāo)用于評價過程模型的泛化度。Generalization與Precision剛好相反，它希望過程模型不僅能反應(yīng)出事件日志中“觀測到的行為”，還希望該模型能夠反應(yīng)出一些在事件日志中觀測不到但又是正確的行為。鑒于事件日志的不完備性，因此好的過程模型應(yīng)該具有一定的“預(yù)見性”，這樣才能更好地適應(yīng)真實應(yīng)用環(huán)境。

Simplicity指標(biāo)用于評價過程模型的結(jié)構(gòu)復(fù)雜度。在保證Fitness、Precision和Generalization三個指標(biāo)的前提下，過程模型的結(jié)構(gòu)復(fù)雜度越低越好。一個過程模型結(jié)構(gòu)越簡單，越容易被用戶理解。

除此之外，還有一個常常被忽略的重要指標(biāo)Soundness，用于評價一個過程模型是否合理。根據(jù)文獻(xiàn)[6]中給出的定義，一個合理的過程模型應(yīng)該滿足以下幾點：(a) 模型有且僅有一個起始結(jié)點和終止結(jié)點；(b) 模型中的每一個結(jié)點都在從起始結(jié)點到終止結(jié)點的某條路徑上(即每個活動都有可能被觸發(fā))；(c) 模型中不存在死鎖、活鎖等不合理結(jié)構(gòu)。

3 過程挖掘算法研究現(xiàn)狀

3.1 ɑ系列過程挖掘算法

van der Aalst[6]等于2004年提出的ɑ算法被公認(rèn)為是過程挖掘領(lǐng)域的一項里程碑式的成果。ɑ算法能夠基于事件日志中Event的出現(xiàn)順序，對Event之間的依賴關(guān)系進(jìn)行推理，從而發(fā)現(xiàn)其中順序、因果、選擇、并行四種結(jié)構(gòu)，得到一個合理的Wf-net。但是ɑ算法有很多關(guān)鍵問題沒解決，例如不能處理重名活動，不能發(fā)現(xiàn)不可見活動，不能挖掘出循環(huán)結(jié)構(gòu)和非自由選擇結(jié)構(gòu)等等。因此后來涌現(xiàn)出許多以ɑ算法為基礎(chǔ)進(jìn)行的研究。de Medeiros等[10]提出了能進(jìn)一步發(fā)現(xiàn)短循環(huán)(長度為1和2的循環(huán))的ɑ+算法；林雷蕾等[11]提出了ɑL+算法，能夠從從沒有“aba”模式的事件日志中挖掘出長度為2的循環(huán)結(jié)構(gòu)；聞立杰等[12]先后提出了能夠發(fā)現(xiàn)不可見活動的ɑ#算法，以及能進(jìn)一步發(fā)現(xiàn)非自由選擇結(jié)構(gòu)的ɑ++算法[13]；李嘉菲等先后提出了能解決重名活動的ɑ※算法[14]和ɑ※※算法[15]。更進(jìn)一步，為了增強(qiáng)算法的推理能力，杜玉越等[16]則提出了基于邏輯petri net的過程挖掘算法；余建波[17]則提出了一種基于統(tǒng)計的ɑ算法，同時解決了重名活動的識別，事件日志中噪聲的處理和非自由選擇結(jié)構(gòu)識別三個問題，提高了算法的魯棒性和準(zhǔn)確率。

以上所有算法均可歸結(jié)為ɑ系列過程挖掘算法(因為它們都是從ɑ算法擴(kuò)展得到的)。ɑ系列算法的特點是它們都是通過掃描事件日志中的Trace，抽象出活動之間的基本關(guān)系，進(jìn)而構(gòu)造出過程模型。這類算法的優(yōu)點是時間復(fù)雜度低，執(zhí)行時間短，并且得到的過程模型結(jié)構(gòu)復(fù)雜度較低，容易理解。但是ɑ系列算法均沒有考慮fitness、precision和generalization三個指標(biāo)，因此所得模型的綜合質(zhì)量都不高，在實際應(yīng)用中較少采用。

3.2 啟發(fā)式過程挖掘算法

Weijters等[18]首次提出了過程挖掘的啟發(fā)式算法，稱為Heuristic Miner(簡稱HM)。HM算法的原理是通過統(tǒng)計事件日志中一些基本模式的出現(xiàn)頻率來計算活動之間的依賴度，以此發(fā)現(xiàn)過程模型中的主要行為。由于HM只關(guān)注主要行為，對一些異常信息(如噪聲)能自動過濾，因此算法具有較強(qiáng)的魯棒性。HM算法能夠發(fā)現(xiàn)過程模型中的一些常見結(jié)構(gòu)，如順序、選擇、并行、循環(huán)、和非自由選擇結(jié)構(gòu)，輸出模型為C-net。HM算法包含三個主要步驟。首先，通過公式(1)計算活動之間的依賴度。

(1)

其中，A?LB表示在Trace中活動A和B相鄰出現(xiàn)(即模式)，|A?LB|表示A?LB出現(xiàn)的頻率。將公式(1)中的所有?L符號替換為?L符號，則得到長度為 2 的循環(huán)結(jié)構(gòu)的依賴度，其中A?LB表示模式在事件日志中出現(xiàn)。D(A?LB)值越接近1，則說明活動A和活動B之間的依賴度越強(qiáng)；反之，越接近0則表示兩個活動的依賴度越弱。舉例來說，假設(shè)L={10, 5, 3}，則A?LB出現(xiàn)了13次，B?LA出現(xiàn)了0次，則D(A?LB)≈0.93。其次，設(shè)定閾值，構(gòu)建依賴圖。一些由噪聲引起的依賴度較低的邊此時將被過濾掉。最后，在依賴圖基礎(chǔ)上通過計算進(jìn)一步確定模型中的并行和選擇分支。

HM具有較強(qiáng)的抗噪能力和魯棒性，但是初始版本有很多不足。Weijters等[19]于2012年又進(jìn)一步提出了Flexible Heuristics Miner(FHM)，大幅提升了算法性能。此外，Greco等人基于C-net，在傳統(tǒng)方法基礎(chǔ)上融入了優(yōu)先約束，提出了CNMiner算法。魯法明等[20]則提出了一種并行化的啟發(fā)式流程挖掘算法，不僅提升了算法的計算性能，還對HM算法中的長距離依賴關(guān)系以及2度循環(huán)結(jié)構(gòu)的計算進(jìn)行了優(yōu)化。

3.3 基于計算智能的過程挖掘算法

計算智能已成為解決數(shù)據(jù)挖掘、非線性優(yōu)化等領(lǐng)域問題的一種主流方法。這類方法模擬了生物演化過程，具有非常強(qiáng)的搜索能力和魯棒性。Alves de Medeiros等[7]首次提出了基于遺傳算法的過程挖掘方法，稱為Genetic Miner。通過定義良好的適應(yīng)度函數(shù)，以及交叉、變異等過程遺傳操作算子，Genetic Miner能夠得到與事件日志非常一致的C-net模型。而且，該算法采用一種統(tǒng)一方式解決非自由選擇結(jié)構(gòu)、不可見活動、以及重名活動的挖掘。歐陽等[21]發(fā)現(xiàn)Genetic Miner不能很好地處理過程模型中的循環(huán)結(jié)構(gòu)，提出了一種集成的方法，在遺傳算法基礎(chǔ)上融合了粒子群算法和差分進(jìn)化算法，進(jìn)一步改進(jìn)了Genetic Miner算法的搜索能力。Vázquez-Barreiros等[22]則對Genetic Miner中的目標(biāo)函數(shù)、初始化方法等進(jìn)行了改進(jìn)，提出一種新的遺傳算法ProDiGen，從Fitness、Precision和Simplicity三個指標(biāo)上提升了所得過程模型的質(zhì)量。此外，李莉等[23]提出了一種基于變異粒子群優(yōu)化的過程挖掘算法，宋煒等[24]提出了一種基于模擬退火的智能算法，輸出模型均為C-net。遺憾的是，以上算法均不能保證過程模型的合理性。

基于計算智能的算法能夠采用統(tǒng)一的方式解決多種復(fù)雜問題，并且算法的魯棒性強(qiáng)，挖掘得到的模型質(zhì)量較高。但是這類方法的計算時間開銷較大 ，在應(yīng)用時需要考慮該問題。

3.4 基于Region的過程挖掘算法

基于Region的過程挖掘算法包括兩類：一類是基于狀態(tài)的Region方法(State-based region)，一類是基于語言的Region方法(Language-based region)。它們的區(qū)別在于，前者的輸入是一個變遷網(wǎng)絡(luò)(Transition System)，而后者的輸入是事件日志。基于State-based region的方法對參數(shù)的依賴非常大，不同的參數(shù)設(shè)置可能得到差異非常大的過程模型，在此不再詳細(xì)介紹。

Bergenthum等人首次提出了基于Language-based region的過程挖掘方法[27]。該方法通過事件日志計算整數(shù)點的最小線性基，從而構(gòu)造過程模型。該方法保證了最優(yōu)的Fitness值，但是卻沒有考慮模型的Precision值，并且所提算法的時間復(fù)雜度隨日志規(guī)模呈指數(shù)級增長。

在所有基于Language-based region的方法中，目前最有效的是基于整數(shù)線性規(guī)劃的過程挖掘算法(稱為ILP Miner)。首次提出過程挖掘的ILP算法的是Werf等人[28]。該方法中提出了整數(shù)線性規(guī)劃的目標(biāo)函數(shù)，并構(gòu)建了約束條件。該優(yōu)化模型不僅能夠表達(dá)對Petri net中特定庫所的偏好，而且支持一些高級petri net的發(fā)現(xiàn)(例如含有重置弧和約束弧的petri net)。van Zelst等[29]對ILP方法進(jìn)行了進(jìn)一步完善，提出了Hybrid ILPMiner。該方法不僅改進(jìn)了目標(biāo)函數(shù)，而且提出了如何處理低頻行為，從而提高了所得模型的Precision指標(biāo)。由于篇幅問題，在此不再對該方法進(jìn)行詳細(xì)介紹。

3.5 基于大數(shù)據(jù)的過程挖掘算法

目前過程挖掘領(lǐng)域面臨的主要問題之一是對過程大數(shù)據(jù)的挖掘。舉例來說，目前的醫(yī)院管理信息系統(tǒng)中包含了門診信息管理系統(tǒng)、藥品信息管理系統(tǒng)、住院信息管理系統(tǒng)等數(shù)十個系統(tǒng)，其中可能涉及上千個活動，每天產(chǎn)生數(shù)百兆的事件日志。Philips公司的醫(yī)療設(shè)備采集分布在全世界各地的設(shè)備節(jié)點的事件日志進(jìn)行分析，每天能產(chǎn)生GB級的過程數(shù)據(jù)。如何在合理的時間內(nèi)從這類“大數(shù)據(jù)”中挖掘得到高質(zhì)量的過程模型是本領(lǐng)域的一個新挑戰(zhàn)。

目前基于大數(shù)據(jù)的過程挖掘方法主要有兩大類，一類是基于分治法的算法，另一類是基于新計算范式的方法。首先，基于分治法的算法中最有效的是Leemans等[30-31]提出的Inductive Miner(簡稱IM)。IM算法采用了一種分治和遞歸的策略，從單個結(jié)點出發(fā)，通過不斷地遞歸將相鄰的結(jié)構(gòu)化的局部模型組合成更大的“局部”模型，最終得到完整的過程模型。由于在整個計算過程中，IM算法保證每一步得到的局部模型均是結(jié)構(gòu)化的，因此其最終得到的過程模型也是結(jié)構(gòu)化的。IM算法是目前過程挖掘領(lǐng)域最有效的算法之一，其優(yōu)點是能夠挖掘得到質(zhì)量很高的過程模型，并且計算時間復(fù)雜度較低，能在短時間內(nèi)分析GB級的事件日志。但是它不能發(fā)現(xiàn)一些非本地的結(jié)構(gòu)，例如長距離的循環(huán)結(jié)構(gòu)、非自由選擇結(jié)構(gòu)等等。

Verbeek等[32]則提出了一種普適的分治法框架，稱為Divide & Conquer。該方法首先通過聚類算法將活動集合劃分成若干子集；基于得到的活動子集，對事件日志進(jìn)行劃分，得到每個活動子集對應(yīng)的“局部日志”；基于活動子集和局部日志，采用現(xiàn)有算法(如ILP算法、IM算法等)得到局部的過程模型；最后，將得到的局部模型進(jìn)行融合，得到最終的過程模型。仍然基于3.2節(jié)中給出的事件日志L進(jìn)行解釋。假設(shè)通過計算得到兩個活動子集{A,B,C,D,E,F}和{G,H}，則L將被劃分為兩個局部日志L1={10, 5, 3},L2={{G}, {H}, {G}}，基于這兩個日志，可以得到兩個局部的過程模型(如圖6所示)；最后通過融合將兩個模型合并成最終的模型(圖2)。

第二類方法則是采用新的計算范式。例如，Reguieg等[33]提出了一種基于MapReduce的事件相關(guān)性計算方法，擴(kuò)展了現(xiàn)有的過程挖掘算法。Ferreira等[34]則提出了一種基于GPU和CPU協(xié)同的事件統(tǒng)計算法，實現(xiàn)了對過程挖掘算法的加速。李龔亮等[35]則提出基于GPU的并行遺傳過程挖掘算法，表現(xiàn)出較好的執(zhí)行時間加速比。在此不再一一介紹。

圖6 由分治法得到的局部模型

4 算法比較

表2從模型質(zhì)量和模型結(jié)構(gòu)兩個大的方面對三種算法進(jìn)行了比較。模型質(zhì)量指的是該算法挖掘得到的過程模型在不同評價指標(biāo)上的表現(xiàn)；模型結(jié)構(gòu)指的是該算法能夠發(fā)現(xiàn)的流程結(jié)構(gòu)。首先從模型質(zhì)量上看，ETM算法的優(yōu)點是考慮了所有的性能指標(biāo)，所得到的過程模型質(zhì)量較高，有較好的抗噪性。但是ETM算法執(zhí)行時間較慢，這也是所有基于計算智能算法的共同缺點。Hybrid ILP Miner算法在Fitness、Precision和Simplicity三大指標(biāo)上表現(xiàn)較好，且具有較好的抗噪性，執(zhí)行之間也很短。但是該算法沒有考慮算法的Generalization，換句話說，在一些真實場景下該算法可能表現(xiàn)不佳。此外，Hybrid ILP Miner挖掘得到的過程模型是弱合理的，而不能保證模型的強(qiáng)合理性。IM算法挖掘得到的過程模型則在所有性能指標(biāo)上均能達(dá)到令人滿意的效果，而且具有較好的抗噪性，執(zhí)行時間也非常短。

接下來從模型結(jié)構(gòu)上對三種算法進(jìn)行分析。ETM算法因為采用的是隨機(jī)搜索，因此理論上能發(fā)現(xiàn)所有的流程結(jié)構(gòu)。Hybrid ILP Miner算法盡管能發(fā)現(xiàn)表2中列出的所有流程結(jié)構(gòu)，但是對一些異常復(fù)雜的結(jié)構(gòu)，仍然難以發(fā)現(xiàn)。IM算法是一種基于分治法的算法，它從單個結(jié)點進(jìn)行遞歸，通過與相鄰結(jié)點組合來發(fā)現(xiàn)局部的流程結(jié)構(gòu)，因此難以發(fā)現(xiàn)一些長距離的依賴關(guān)系。最后，表2中還討論了所得模型的可重現(xiàn)性。ETM由于是隨機(jī)搜索算法，因此它的挖掘結(jié)果難以重現(xiàn)，而IM和Hybrid ILP Miner兩種算法的挖掘結(jié)果均是可重現(xiàn)的。

綜上可以發(fā)現(xiàn)，ETM算法能夠得到高質(zhì)量的、強(qiáng)合理的過程模型，理論上能夠發(fā)現(xiàn)所有可能的模型結(jié)構(gòu)，但是它的執(zhí)行時間長，且挖掘結(jié)果很難重現(xiàn)；IM算法同樣可以得到高質(zhì)量的、強(qiáng)合理的過程模型，并且它的執(zhí)行時間短，挖掘結(jié)果也能重現(xiàn)，但是它只能發(fā)現(xiàn)局部模型結(jié)構(gòu)，難以發(fā)現(xiàn)一些遠(yuǎn)距離的依賴關(guān)系；Hybrid ILP Miner算法能夠發(fā)現(xiàn)大部分的模型結(jié)構(gòu)，并且它的執(zhí)行時間短，挖掘結(jié)果能夠重現(xiàn)，但是它挖掘到的過程模型泛化性較低，并且是弱合理的。

表2 三種算法的比較

5 總結(jié)和展望

本文對當(dāng)前過程挖掘領(lǐng)域以Petri net、C-net和P-tree為輸出的主流算法進(jìn)行了分類總結(jié)。首先，按照過程挖掘算法的基本原理，將其劃分為五大類，分別是ɑ系列算法、啟發(fā)式算法、基于計算智能的算法、基于Region理論的算法，以及基于分治法的算法。其次，對目前最有效的三個算法ETM、IM以及Hybrid ILP Miner，進(jìn)行了進(jìn)一步的分析和比較，并給出了相關(guān)結(jié)論。但需要強(qiáng)調(diào)的是，目前該領(lǐng)域的研究還遠(yuǎn)沒有走到終點。首先，當(dāng)前的算法仍然存在諸多不足，例如ETM算法計算效率較低，且它只是理論上能發(fā)現(xiàn)所有的模型結(jié)構(gòu)，而實際應(yīng)用中仍然不能完全令人滿意；IM算法只能發(fā)現(xiàn)局部的模型結(jié)構(gòu)，難以發(fā)現(xiàn)遠(yuǎn)距離的依賴關(guān)系；Hybrid ILP Miner算法挖掘得到的過程模型泛化性較低，等等。

此外，隨著過程挖掘領(lǐng)域的不斷研究和發(fā)展，目前又涌現(xiàn)出很多新的問題。

a)異源日志的融合問題，即事件日志是來自不同的信息系統(tǒng)。這些信息系統(tǒng)可能是不同時期的，或者是不同企業(yè)開發(fā)的，它們在活動命名、業(yè)務(wù)過程設(shè)計上均不同。因此，如何將事件日志進(jìn)行融合是一個關(guān)鍵問題。

b)概念漂移問題，即過程模型中的概念隨著時間的遷移發(fā)生了變化。舉例來說，一些舊的業(yè)務(wù)過程可能會被簡化(也可能變得復(fù)雜)，一些簡單的業(yè)務(wù)過程可能會被合并，業(yè)務(wù)過程中的一些活動可能會被刪除或修改，等等。

c)大數(shù)據(jù)處理問題。盡管目前已有一些關(guān)于過程大數(shù)據(jù)處理的研究，例如分治法，或者基于MapReduce，GPU的算法，但是總體來說，該領(lǐng)域還處于起步階段，仍然有諸多問題臻待解決。