敬思遠(yuǎn)

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

0 引言

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

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

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

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

1.1 事件日志

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

圖1 事件日志

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

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

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

1.2 過(guò)程模型表示

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

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

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

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

圖 2Wf-netFig 2 Wf-net

定義 3[7].C-net表示為一個(gè)四元組CM=(T,C,I,O)，其中：a) T表示所有活動(dòng)的有窮集合；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)=表示活動(dòng)A的輸入為空集；O(A)={{B,C},{D}}表示活動(dòng)A的輸出為{B,C}和{D}，其中活動(dòng)B和活動(dòng)C之間是選擇關(guān)系，而{B,C}和{D}之間是并列關(guān)系。因此，A之后的活動(dòng)發(fā)生序列可能是BD，CD，DB，DC。

表1 C-netTable 1 C-net

圖3 P-treeFig 3 P-tree

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

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

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

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

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

圖4 不可見(jiàn)活動(dòng)

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

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

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

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

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

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

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

目前常常從四個(gè)方面來(lái)評(píng)價(jià)過(guò)程挖掘算法的輸出結(jié)果[9]，分別是Fitness、Precision、Generalization以及Simplicity。

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

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

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

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

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

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

3.1 ɑ系列過(guò)程挖掘算法

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

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

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

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

(1)

其中，A?LB表示在Trace中活動(dòng)A和B相鄰出現(xiàn)(即模式)，|A?LB|表示A?LB出現(xiàn)的頻率。將公式(1)中的所有?L符號(hào)替換為?L符號(hào)，則得到長(zhǎng)度為 2 的循環(huán)結(jié)構(gòu)的依賴度，其中A?LB表示模式在事件日志中出現(xiàn)。D(A?LB)值越接近1，則說(shuō)明活動(dòng)A和活動(dòng)B之間的依賴度越強(qiáng)；反之，越接近0則表示兩個(gè)活動(dòng)的依賴度越弱。舉例來(lái)說(shuō)，假設(shè)L={10, 5, 3}，則A?LB出現(xiàn)了13次，B?LA出現(xiàn)了0次，則D(A?LB)≈0.93。其次，設(shè)定閾值，構(gòu)建依賴圖。一些由噪聲引起的依賴度較低的邊此時(shí)將被過(guò)濾掉。最后，在依賴圖基礎(chǔ)上通過(guò)計(jì)算進(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ā)式流程挖掘算法，不僅提升了算法的計(jì)算性能，還對(duì)HM算法中的長(zhǎng)距離依賴關(guān)系以及2度循環(huán)結(jié)構(gòu)的計(jì)算進(jìn)行了優(yōu)化。

3.3 基于計(jì)算智能的過(guò)程挖掘算法

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

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

3.4 基于Region的過(guò)程挖掘算法

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

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

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

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

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

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

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

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

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

4 算法比較

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

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

綜上可以發(fā)現(xiàn)，ETM算法能夠得到高質(zhì)量的、強(qiáng)合理的過(guò)程模型，理論上能夠發(fā)現(xiàn)所有可能的模型結(jié)構(gòu)，但是它的執(zhí)行時(shí)間長(zhǎng)，且挖掘結(jié)果很難重現(xiàn)；IM算法同樣可以得到高質(zhì)量的、強(qiáng)合理的過(guò)程模型，并且它的執(zhí)行時(shí)間短，挖掘結(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í)行時(shí)間短，挖掘結(jié)果能夠重現(xiàn)，但是它挖掘到的過(guò)程模型泛化性較低，并且是弱合理的。

表2 三種算法的比較

5 總結(jié)和展望

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

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

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

b)概念漂移問(wèn)題，即過(guò)程模型中的概念隨著時(shí)間的遷移發(fā)生了變化。舉例來(lái)說(shuō)，一些舊的業(yè)務(wù)過(guò)程可能會(huì)被簡(jiǎn)化(也可能變得復(fù)雜)，一些簡(jiǎn)單的業(yè)務(wù)過(guò)程可能會(huì)被合并，業(yè)務(wù)過(guò)程中的一些活動(dòng)可能會(huì)被刪除或修改，等等。

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