過程挖掘算法研究綜述

敬思遠

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

0 引言

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

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

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

1 過程挖掘相關知識

1.1 事件日志

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

圖1 事件日志

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

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

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

1.2 過程模型表示

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

首先介紹petri net(也稱為Place/Transition Net，簡稱P/T net)。P/T net是一種數學表示能力非常強的建模語言。通常，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基礎上加上一個起始Place和一個終止Place，即得到表示過程模型的工作流網(Workflow Net，簡稱Wf-net)。圖2中是一個與上節給出實例對應的Wf-net，圖中圓圈表示Place，方框表示Transition。可以看到，每個Transition上都有一個活動名稱，說明Transition和活動是一一對應的。當某個Transition的所有前驅結點(即Place)均處于就緒狀態時，該Transition即可觸發，并產生一個Event。在P/T net中，一個Place處于就緒狀態指的是位于該結點的Token數大于0(即圖2中的小黑點)。舉例來說，圖2中的“開始”結點目前已處于就緒狀態，因此它的下一個Transition(受理)可以觸發。需要說明的是，圖中B和C之間，G和H之間是選擇關系(即每次只有一個Transition可以觸發)，而{B,C}和D之間是并行關系。因此，該過程模型可能產生的trace包括，，，等等。

圖 2Wf-netFig 2 Wf-net

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

表1中給出了由上述Wf-net轉化的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之間是選擇關系，而{B,C}和{D}之間是并列關系。因此，A之后的活動發生序列可能是BD，CD，DB，DC。

表1 C-netTable 1 C-net

圖3 P-treeFig 3 P-tree

2 過程挖掘中的關鍵問題

2.1 一些特殊挖掘任務

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

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

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

圖4 不可見活動

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

圖5 非自由選擇結構

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

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

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

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

2.3 如何平衡性能指標

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

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

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

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

Simplicity指標用于評價過程模型的結構復雜度。在保證Fitness、Precision和Generalization三個指標的前提下，過程模型的結構復雜度越低越好。一個過程模型結構越簡單，越容易被用戶理解。

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

3 過程挖掘算法研究現狀

3.1 ɑ系列過程挖掘算法

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

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

3.2 啟發式過程挖掘算法

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

(1)

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

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

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

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

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

3.4 基于Region的過程挖掘算法

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

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

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

3.5 基于大數據的過程挖掘算法

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

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

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

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

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

4 算法比較

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

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

綜上可以發現，ETM算法能夠得到高質量的、強合理的過程模型，理論上能夠發現所有可能的模型結構，但是它的執行時間長，且挖掘結果很難重現；IM算法同樣可以得到高質量的、強合理的過程模型，并且它的執行時間短，挖掘結果也能重現，但是它只能發現局部模型結構，難以發現一些遠距離的依賴關系；Hybrid ILP Miner算法能夠發現大部分的模型結構，并且它的執行時間短，挖掘結果能夠重現，但是它挖掘到的過程模型泛化性較低，并且是弱合理的。

表2 三種算法的比較

5 總結和展望

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

此外，隨著過程挖掘領域的不斷研究和發展，目前又涌現出很多新的問題。

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

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

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