楊麗琴 康國(guó)勝 蔡偉剛 周 強(qiáng)

業(yè)務(wù)流程挖掘算法研究

楊麗琴1,2康國(guó)勝2蔡偉剛1周 強(qiáng)1

1(上海中醫(yī)藥大學(xué)圖書信息中心 上海 201203)

2(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 201203)

流程挖掘能夠根據(jù)流程的執(zhí)行日志重構(gòu)出流程模型，有助于實(shí)現(xiàn)業(yè)務(wù)流程的優(yōu)化和智能管理。首先，指出目前流程挖掘技術(shù)需要解決的關(guān)鍵問(wèn)題。然后，介紹幾種具有代表性的流程挖掘算法，并指出每種算法解決的問(wèn)題和存在的不足。接著，從日志完整性、控制流結(jié)構(gòu)、噪聲處理和模型質(zhì)量控制等方面對(duì)流程挖掘算法進(jìn)行分析和比較。最后，指出流程挖掘技術(shù)未來(lái)的研究方向。

流程挖掘 α算法 啟發(fā)式算法 遺傳算法 日志分類

0 引 言

目前，大多數(shù)企業(yè)使用信息系統(tǒng)來(lái)支持業(yè)務(wù)流程的執(zhí)行，如工作流管理系統(tǒng)(WFMS)、企業(yè)資源規(guī)劃系統(tǒng)(ERP)、客戶關(guān)系管理系統(tǒng)等。這些信息系統(tǒng)可能包含顯式的流程模型，也可能僅支持流程所涉及的任務(wù)而無(wú)需定義顯式的流程模型，或僅僅保留了執(zhí)行任務(wù)的軌跡。然而，這些信息系統(tǒng)都可以自動(dòng)生成執(zhí)行日志來(lái)記錄業(yè)務(wù)流程的實(shí)際執(zhí)行情況。流程挖掘的目標(biāo)就是從這些執(zhí)行日志中自動(dòng)發(fā)現(xiàn)和流程有關(guān)的信息。挖掘結(jié)果可用于設(shè)計(jì)一個(gè)新的業(yè)務(wù)流程，或者作為反饋工具審計(jì)、分析和改進(jìn)現(xiàn)有的業(yè)務(wù)流程。因此，流程挖掘?qū)?shí)現(xiàn)業(yè)務(wù)流程的優(yōu)化和智能管理有著十分重要的意義[1]。

流程挖掘分為三個(gè)視圖[2]：控制流視圖、組織視圖和實(shí)例視圖。其中，控制流視圖關(guān)注流程中活動(dòng)的執(zhí)行順序和控制流結(jié)構(gòu)，常用的建模語(yǔ)言[2,3]有WF-net、C-net、EPCs、BPMN和YAWL等。組織視圖關(guān)注流程的資源信息，如哪個(gè)活動(dòng)由哪個(gè)執(zhí)行者實(shí)施以及它們之間的關(guān)系。目標(biāo)是發(fā)現(xiàn)和展示人之間的關(guān)系，即建立一個(gè)社會(huì)關(guān)系網(wǎng)。實(shí)例視圖關(guān)注與流程實(shí)例相關(guān)的屬性，既可用活動(dòng)表示，也可用實(shí)例中的執(zhí)行者表示，還可以用流程處理的數(shù)據(jù)對(duì)象來(lái)表示。本文僅從控制流角度論述流程挖掘技術(shù)的關(guān)鍵問(wèn)題和研究現(xiàn)狀。文獻(xiàn)[1]僅介紹了較早期的部分工作流挖掘算法。針對(duì)近幾年國(guó)內(nèi)在流程挖掘綜述方面的文章較少，本文較全面地介紹了具有代表性的流程挖掘算法，包括基于遺傳算法的流程挖掘、基于日志分類的挖掘算法和基于執(zhí)行模式的挖掘算法。從日志完整性、控制流結(jié)構(gòu)、噪聲處理和模型質(zhì)量控制等方面對(duì)它們進(jìn)行了分析和比較。

1 流程挖掘的基本概念

1.1 日 志

流程挖掘的輸入是執(zhí)行日志，表1是一個(gè)會(huì)議流程的執(zhí)行日志。每一行表示一個(gè)事件，記錄了與事件有關(guān)的各種信息，如：該事件對(duì)應(yīng)的活動(dòng)，事件發(fā)生的時(shí)間等，用事件ID標(biāo)識(shí)。實(shí)例是流程的一次執(zhí)行過(guò)程，用實(shí)例ID標(biāo)識(shí)，每個(gè)事件屬于某一實(shí)例。如果只關(guān)注流程的控制流視圖，一個(gè)實(shí)例可用其所有事件所對(duì)應(yīng)的活動(dòng)序列來(lái)表示。因此，可對(duì)表1中的日志進(jìn)行化簡(jiǎn)，化簡(jiǎn)后的日志如表2所示。表中共包含6個(gè)流程實(shí)例，14個(gè)活動(dòng)。

表1 會(huì)議流程的部分日志

表2 會(huì)議流程日志的化簡(jiǎn)形式

日志的形式化定義[3]如下：

定義1 設(shè)T是活動(dòng)的有限集合，σ∈T*是一條活動(dòng)序列，L∈(T*)是一個(gè)流程執(zhí)行日志。其中，T*表示集合T的Kleene閉包。

例如：T={a,b,c,d},L=[3,2,]是一個(gè)包含6個(gè)實(shí)例的執(zhí)行日志。

1.2 流程模型表示方法

流程的控制流結(jié)構(gòu)可用不同的建模語(yǔ)言[2]來(lái)描述，如：WF-net、C-net、Process Tree等。不同挖掘算法使用的流程模型表示方法也不同，例如：α系列算法使用的是WF-net，啟發(fā)式算法使用的是C-net，而基于遺傳算法的流程挖掘使用的是Petri網(wǎng)或Process Tree。因此，算法具有各自的表達(dá)偏好。這些建模語(yǔ)言之間可以相互轉(zhuǎn)換，也可以轉(zhuǎn)換成語(yǔ)義表達(dá)能力更強(qiáng)的高級(jí)流程建模語(yǔ)言，如YAWL、BPMN、EPCs等。高級(jí)建模語(yǔ)言一般提供給業(yè)務(wù)人員建模使用，本文不做介紹。下面介紹幾種常用的流程模型表示方法。

1.2.1 工作流網(wǎng)WF-net(Workflow Net)

首先，介紹經(jīng)典的Petri net[4]，它是由庫(kù)所和變遷這兩類節(jié)點(diǎn)組成的二部圖，節(jié)點(diǎn)之間通過(guò)有向弧連接。形式化定義如下：

定義2 一個(gè)Petri網(wǎng)是一個(gè)三元組(P,T,F)，其中：

(a) P是一個(gè)有限的庫(kù)所集;

(b) T是一個(gè)有限的變遷集(P∩T=?);

(c) F?(P×T)∪(T×P)是弧的集合。

Petri網(wǎng)的狀態(tài)通常被稱為標(biāo)記，是token在各庫(kù)所的分布情況的描述。Petri網(wǎng)在執(zhí)行過(guò)程中，變遷根據(jù)觸發(fā)規(guī)則[31]改變Petri網(wǎng)的狀態(tài)。

標(biāo)簽化的Petri網(wǎng)是一個(gè)五元組(P,T,F,A,l)，其中(P,T,F)同定義2，A是一組活動(dòng)的集合，l∈T→A是Petri網(wǎng)中變遷到活動(dòng)的映射。直觀地，就是為Petri網(wǎng)中的變遷打上活動(dòng)的標(biāo)簽，變遷一旦被觸發(fā)則說(shuō)明對(duì)應(yīng)的活動(dòng)也被執(zhí)行。

定義3 一個(gè)標(biāo)簽化的Petri網(wǎng)PN=(P,T,F,A,l)是一個(gè)工作流網(wǎng)WF-net[2]，當(dāng)且僅當(dāng)：

(a) 存在一個(gè)起始庫(kù)所i∈P使得·i=?;

(b) 存在一個(gè)終止庫(kù)所o∈P使得o·=?;

(c) 每個(gè)節(jié)點(diǎn)都位于從i到o的一條路徑上。

若對(duì)會(huì)議流程日志(表2)使用合適的挖掘算法，得到的流程模型如圖1所示。

圖1 會(huì)議流程的WF-net模型

圖1中，矩形表示變遷，圓圈表示庫(kù)所，變遷和庫(kù)所之間使用有向弧連接。每個(gè)庫(kù)所上都標(biāo)有活動(dòng)的名稱，當(dāng)觸發(fā)庫(kù)所時(shí)，相應(yīng)的活動(dòng)被執(zhí)行。根據(jù)定義3，該流程是一個(gè)WF-net。

定義4 一個(gè)WF-net N=(P,T,F,A,l)是一個(gè)SWF-net[2]，當(dāng)且僅當(dāng)：

(a) 對(duì)于所有的p∈P，t∈T，(p,t)∈F，若|p·|>1，則|·t|=1;

(b) 對(duì)于所有的p∈P，t∈T，(t,p)∈F，若|·t|>1，則|·p|=1;

(c) 不存在隱式庫(kù)所。

1.2.2 Causal net (C-net)

Causal net表達(dá)流程中活動(dòng)和活動(dòng)之間的依賴關(guān)系。每個(gè)活動(dòng)有一組輸入約束和輸出約束。如圖2 (a)所示，活動(dòng)a是開(kāi)始活動(dòng)，因此，沒(méi)有輸入約束，輸出約束是{b,d}和{c,d}，表示執(zhí)行活動(dòng)a后，執(zhí)行b和d，或者c和d?；顒?dòng)e是結(jié)束活動(dòng)，沒(méi)有輸出約束，輸入約束為{b,d}和{c,d}，說(shuō)明在執(zhí)行活動(dòng)e之前，執(zhí)行了b和d，或者c和d。

圖2 一個(gè)C-net例子

與圖2(a)中的C-net等價(jià)的WF-net模型如圖2(b)所示。它們所有的可執(zhí)行流程實(shí)例相同，有,,,。以下是Causal net的形式化定義。

定義5 Causal net[2]是一個(gè)六元組(A,ai,ao,D,I,O)。

其中：

A是活動(dòng)的有限集合;

{ai}={a∈A|I(a)={?}}是開(kāi)始活動(dòng);

{ao}={a∈A|O(a)={?}}是結(jié)束活動(dòng);

D={(a1,a2)∈A×A|a1∈∪as∈I(a2)as∧a2∈∪as∈O(a1)as}是依賴關(guān)系;

I∈A→AS是活動(dòng)的輸入約束;

O∈A→AS是活動(dòng)的輸出約束;

AS={X?ρ(A)|X={?}∨??X}2。

例如，圖2(a)所示的Causal net，A={a,b,c,d,e}，ai=a，ao=e，D={(a,b),(a,c),(a,d),(b,e),(c,e),(d,e)}，I(a)={?}，O(a)={{b,d},(c,d)}，I(b)={{a}}，O(b)={{e}}，I(c)={{a}}，O(c)={{e}},I(d)={{a}},O(d)={{e}},I(e)={{b,d},{c,d}},O(e)={?}。

1.2.3 流程樹(shù)

流程樹(shù)[5]也可作為流程模型的表示方式。其中，節(jié)點(diǎn)分為葉子節(jié)點(diǎn)和非葉子節(jié)點(diǎn)。葉子節(jié)點(diǎn)(也稱為活動(dòng)節(jié)點(diǎn))表示活動(dòng)。非葉子節(jié)點(diǎn)(也稱為操作節(jié)點(diǎn))表示流程的控制流結(jié)構(gòu)。四種控制流結(jié)構(gòu)的流程樹(shù)表示方法如圖3所示?！痢姆謩e表示順序、選擇、并行和循環(huán)結(jié)構(gòu)。

圖3 四種控制流結(jié)構(gòu)的流程樹(shù)表示

使用流程樹(shù)表示的流程模型是一種“塊結(jié)構(gòu)”的流程模型，其最大的好處是流程可避免死鎖。

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

2.1 控制流結(jié)構(gòu)

以WF-net為例，常用的控制流結(jié)構(gòu)包括：順序結(jié)構(gòu)、并行結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)、非自由選擇結(jié)構(gòu)[6]、隱式活動(dòng)和重復(fù)活動(dòng)。會(huì)議流程的WF-net模型(圖1)包含了上述所有的控制流結(jié)構(gòu)。觀察執(zhí)行日志(表2)，若參會(huì)者坐火車前往開(kāi)會(huì)，則同樣坐火車返回；若開(kāi)車前往，則同樣開(kāi)車返回?？梢?jiàn)，返程的方式取決于前去開(kāi)會(huì)的方式。在圖1中，庫(kù)所i后面的選擇不是由前面的“返程”活動(dòng)決定，而是由庫(kù)所c后面的活動(dòng)決定。若庫(kù)所c后選擇的是坐火車，則庫(kù)所i后選擇的也是坐火車；若庫(kù)所c后選擇的是開(kāi)汽車，則庫(kù)所i后選擇的也是開(kāi)汽車，這稱為是非自由選擇結(jié)構(gòu)。另外，流程中兩個(gè)活動(dòng)的名稱相同，導(dǎo)致了重復(fù)活動(dòng)。在日志中，有的參會(huì)者在會(huì)上沒(méi)有發(fā)表演講，這通過(guò)隱式活動(dòng)實(shí)現(xiàn)。隱式活動(dòng)是WF-net模型中黑色的矩形，常用來(lái)輔助實(shí)現(xiàn)某些控制流結(jié)構(gòu)。在日志中，有的參會(huì)者沒(méi)有提問(wèn)，而有的提問(wèn)多次，這通過(guò)循環(huán)結(jié)構(gòu)實(shí)現(xiàn)。

流程挖掘算法應(yīng)當(dāng)盡可能多的支持各種控制流結(jié)構(gòu)。但由于各種因素，如：日志信息不完整、建模語(yǔ)言表達(dá)能力有限，算法本身的局限性等，算法可能無(wú)法處理某些控制流結(jié)構(gòu)。

2.2 日志噪聲和不完整性

大多數(shù)挖掘算法假設(shè)日志數(shù)據(jù)是正確的。但實(shí)際上，由于流程執(zhí)行異常或日志記錄錯(cuò)誤，日志數(shù)據(jù)往往存在一些噪聲。噪聲的特點(diǎn)是出現(xiàn)頻率低。利用這個(gè)特點(diǎn)，一種方法是對(duì)日志進(jìn)行預(yù)處理，或?qū)Y(jié)果模型進(jìn)行“剪枝”。但這種方法沒(méi)有體現(xiàn)算法本身的健壯性，而有些挖掘算法本身能夠處理日志噪聲，如啟發(fā)式算法、遺傳挖掘算法等。

日志的完整性對(duì)挖掘結(jié)果也起到重要的作用。但實(shí)際上，某些合法的流程實(shí)例可能沒(méi)有記錄在日志中。例如，流程模型中有10個(gè)可并發(fā)執(zhí)行的活動(dòng)，要滿足日志完整性，則至少包含10！條流程實(shí)例，但實(shí)際上可能只有其中1000條流程實(shí)例被記錄在日志中。如果模型中存在循環(huán)結(jié)構(gòu)，則可執(zhí)行的流程實(shí)例無(wú)窮多，顯然不可能全部記錄在日志中。日志完整性可分成不同級(jí)別[7]，不同的挖掘算法對(duì)日志有不同的完整性要求。

(1) 全局完整性GC：流程模型描述的所有可能的流程實(shí)例都至少在日志中出現(xiàn)一次。通常情況下，全局完整性是一種理想情況，很多情況下日志信息是不完整的或者不可能做到完整，例如流程中有循環(huán)結(jié)構(gòu)時(shí)。

(2) 繼發(fā)完整性DS：任何兩個(gè)允許相繼執(zhí)行的任務(wù)，它們相繼執(zhí)行的流程實(shí)例至少在日志中出現(xiàn)一次。

(3) 2元短循環(huán)完整性DS+：若活動(dòng)a和b組成長(zhǎng)度為2的循環(huán)結(jié)構(gòu)，則序列必須至少在日志中出現(xiàn)一次。

(4) 長(zhǎng)循環(huán)完整性DS++：長(zhǎng)循環(huán)指流程中包含長(zhǎng)度大于2的循環(huán)結(jié)構(gòu)。長(zhǎng)循環(huán)的實(shí)例必須至少在日志中出現(xiàn)一次。

(5) 頻率完整性FS：日志中記錄流程實(shí)例發(fā)生的次數(shù)。因此，通過(guò)日志可以得出哪些活動(dòng)經(jīng)常相繼發(fā)生。

2.3 日志多樣性

日志多樣性指由于流程本身錯(cuò)綜復(fù)雜而導(dǎo)致日志中的實(shí)例也呈現(xiàn)出復(fù)雜多樣的特征。例如，醫(yī)療系統(tǒng)的執(zhí)行日志就存在多樣性的特點(diǎn)。因?yàn)槊课换颊叩牟∏椤Ⅲw質(zhì)或者經(jīng)濟(jì)狀況都不同，采取的治療手段也互不相同。如果使用傳統(tǒng)的流程挖掘算法，得到的流程模型結(jié)構(gòu)非常復(fù)雜、難以理解。

一種解決方法是采用聚類方法對(duì)日志中的執(zhí)行實(shí)例進(jìn)行聚類從而產(chǎn)生多個(gè)子日志，降低日志的多樣性。然后對(duì)每個(gè)子日志分別實(shí)施已有的挖掘算法。這種方法得到的模型結(jié)構(gòu)大大簡(jiǎn)化，但得到的不是完整的流程模型。另一種方法是抽取日志中的通用執(zhí)行模式(活動(dòng)序列片段)，根據(jù)模式對(duì)日志進(jìn)行迭代化簡(jiǎn)，然后對(duì)化簡(jiǎn)后的日志和執(zhí)行模式分別施用已有的挖掘算法得到層次流程模型。

2.4 流程模型質(zhì)量評(píng)價(jià)

通常從四個(gè)方面[8-10]來(lái)評(píng)價(jià)流程模型的質(zhì)量：重現(xiàn)度、精確度、通用性和簡(jiǎn)單性。

重現(xiàn)度：指流程模型對(duì)日志中執(zhí)行實(shí)例的可重現(xiàn)程度。給定一個(gè)流程模型和一個(gè)執(zhí)行實(shí)例，如果執(zhí)行實(shí)例可通過(guò)執(zhí)行該流程獲得，則稱該流程可重現(xiàn)該實(shí)例。流程模型可重現(xiàn)的執(zhí)行實(shí)例越多，對(duì)日志的重現(xiàn)度就越高。

精確度：如果通過(guò)執(zhí)行流程模型可以產(chǎn)生許多日志中不包含的實(shí)例，那么該流程模型的精確度就較低，稱為弱擬合。

通用性：與精確度相反，通用性指流程模型不僅反映日志中的行為，還允許日志以外的正確行為。這是因?yàn)閷?shí)際應(yīng)用中，日志通常是不完整的。好的流程模型應(yīng)當(dāng)有這樣的“預(yù)見(jiàn)性”使得新的執(zhí)行實(shí)例符合流程模型的規(guī)范。如果通用性過(guò)低，稱流程模型過(guò)擬合。

簡(jiǎn)單性：在保證其他三個(gè)指標(biāo)的情況下，流程模型越簡(jiǎn)單越好。可從模型中節(jié)點(diǎn)的數(shù)量或節(jié)點(diǎn)的出入度等方面來(lái)評(píng)價(jià)。

精確度和通用性存在一定程度的對(duì)立，精確度較高的流程模型，通用性往往較差，反之亦然。簡(jiǎn)單性與精確性和通用性也有一定的關(guān)系，通常通用性較高的模型結(jié)構(gòu)較簡(jiǎn)單，而精確性較高的模型結(jié)構(gòu)較復(fù)雜。如何使流程模型質(zhì)量在這四個(gè)方面達(dá)到一種平衡，或者能夠控制這四個(gè)方面的不同需求也是流程算法應(yīng)該解決的問(wèn)題。

3 流程挖掘算法

3.1 直接算法

這類算法的基本思想是：首先，掃描日志中的所有實(shí)例，抽象出活動(dòng)之間的基本關(guān)系。然后，根據(jù)基本關(guān)系的類型，直接構(gòu)造流程的控制流結(jié)構(gòu)。這類算法的代表是α及其擴(kuò)展算法[6,11-14]，包括α、α+、α++、α#、α*等。

以α算法[13]為例，活動(dòng)之間的基本關(guān)系有：

a>Lb(伴隨):?α∈L,α=，1?i?n-1,ti=a，ti+1=b;

a→Lb(因果):?α∈L,α=,a>Lb且b≯La;

a||Lb(并行):?α∈L,α=,a>Lb且b>La;

a#Lb(無(wú)關(guān)):?α∈L,α=,a≯Lb且b≯La。

根據(jù)四種基本關(guān)系，構(gòu)造控制流結(jié)構(gòu)。構(gòu)造方法為：a→b：順序結(jié)構(gòu)；a>Lb,a>Lc,b#Lc：選擇分叉；a>Lc,b>Lc,a#Lb：選擇合并；a>Lb,a>Lc,b‖Lc：并行分叉；a>Lc,b>Lc,a‖Lb：并行合并。

α算法無(wú)法處理長(zhǎng)度為2的短循環(huán)結(jié)構(gòu)。因?yàn)閷?duì)這樣的活動(dòng)序列，α算法抽象出兩種基本關(guān)系：a>Lb和b>La。根據(jù)構(gòu)造方法把a(bǔ)和b做并行結(jié)構(gòu)處理。事實(shí)上，α算法的結(jié)果流程模型是不包含短循環(huán)結(jié)構(gòu)的SWF-net，且流程中沒(méi)有隱式活動(dòng)和重復(fù)活動(dòng)。

α+算法[11]是對(duì)α算法的第一次擴(kuò)展，它能夠處理α算法不能處理的長(zhǎng)度為1或2的短循環(huán)結(jié)構(gòu)。為了識(shí)別長(zhǎng)度為2的循環(huán)活動(dòng)序列，α+算法首先擴(kuò)展了活動(dòng)之間的基本關(guān)系：

a△Wb：當(dāng)且僅當(dāng)存在一個(gè)流程實(shí)例σ=t1,t2,…,tn,i∈{1,…,n-2},ti=ti+2且ti=1=b;

a◇Wb:當(dāng)且僅當(dāng)a△Wb且b△Wa。

然后對(duì)原來(lái)的三個(gè)基本關(guān)系a→Lb，a‖Lb，a#Lb也作了相應(yīng)的改進(jìn)。α+算法的具體過(guò)程是：先識(shí)別日志中長(zhǎng)度為1的循環(huán)活動(dòng)序列，將它們暫時(shí)從日志中過(guò)濾掉。對(duì)過(guò)濾后的日志，使用與α算法相同的方法得到中間模型。然后，將長(zhǎng)度為1的循環(huán)結(jié)構(gòu)添加到相應(yīng)的位置。α+算法的結(jié)果流程模型是不帶隱式活動(dòng)和重復(fù)活動(dòng)的SWF-net。

α與α+算法關(guān)注的是活動(dòng)之間的直接(顯式)依賴關(guān)系。而在有些流程中，兩個(gè)非直接相鄰的活動(dòng)之間也可能存在依賴關(guān)系，即隱式依賴。α++算法[6]考慮了依賴距離大于1的隱式依賴關(guān)系，因此能夠處理非自由選擇結(jié)構(gòu)。α++算法的關(guān)鍵是快速有效地發(fā)現(xiàn)任意兩個(gè)活動(dòng)之間的隱式依賴。

α#算法[12]是對(duì)α+算法的擴(kuò)展，能夠處理隱式變遷。如圖1所示，一個(gè)黑色的變遷上沒(méi)有標(biāo)識(shí)對(duì)應(yīng)的活動(dòng)，該變遷稱為隱式變遷。通常，隱式變遷是為了保證WF-net的正確性，或構(gòu)造復(fù)雜控制流結(jié)構(gòu)而加入的。隱式變遷分為SIDE,SKIP和SWITCH三種類型。α#算法先抽象活動(dòng)之間的虛假依賴關(guān)系，再根據(jù)構(gòu)造規(guī)則，構(gòu)造出三種不同類型的隱式變遷。

α*算法[14]用于處理重復(fù)活動(dòng)。在WF-net中，如果變遷T到活動(dòng)A的映射是1對(duì)1關(guān)系，即不存在多個(gè)變遷映射到一個(gè)活動(dòng)的情況，則流程不存在重復(fù)活動(dòng)。α、α+、α++、α#算法均不能處理重復(fù)活動(dòng)。如表2中的第1個(gè)實(shí)例：<開(kāi)始，準(zhǔn)備，坐火車，開(kāi)會(huì)，提問(wèn)，參觀，晚宴，返程，坐火車，結(jié)束>，當(dāng)掃描到第3個(gè)活動(dòng)“坐火車”時(shí)，不能確定該活動(dòng)是對(duì)應(yīng)模型(圖3)中的哪個(gè)“坐火車”變遷。α*算法是對(duì)α算法的擴(kuò)展，在抽象活動(dòng)之間關(guān)系的同時(shí)，記錄了活動(dòng)的上下文活動(dòng)。因此，可通過(guò)上下文環(huán)境判斷日志中的活動(dòng)對(duì)應(yīng)WF-net中的哪個(gè)變遷。

3.2 啟發(fā)式算法

α及其擴(kuò)展算法雖然分別能夠處理各種控制流結(jié)構(gòu)，但卻不能處理日志中的噪聲。而在實(shí)際應(yīng)用中，日志中的噪聲是不可避免的。噪聲出現(xiàn)的原因可能是日志記錄錯(cuò)誤或流程執(zhí)行異常等，日志噪聲的存在將影響算法最終的挖掘結(jié)果。啟發(fā)式算法[15,16]考慮流程實(shí)例在日志中出現(xiàn)的頻率，可用于挖掘流程的主要行為，忽略各種細(xì)節(jié)或異常處理，也可用于處理日志噪聲。啟發(fā)式挖掘算法可處理的常用控制流結(jié)構(gòu)：順序、并行、選擇、循環(huán)和非自由選擇結(jié)構(gòu)。啟發(fā)式算法的流程表示是C-net(A,ai,ao,D,I,O)。

第一步 計(jì)算活動(dòng)之間的依賴度，計(jì)算公式如下：

(1)

其中，|a>Lb|表示a>Lb在所有流程實(shí)例中出現(xiàn)的總次數(shù)。

長(zhǎng)度為2的循環(huán)結(jié)構(gòu)的依賴度的計(jì)算公式如下：

(2)

其中，|a?Lb|表示序列在所有流程實(shí)例中出現(xiàn)的總次數(shù)。計(jì)算結(jié)果的取值范圍是-1到1。越接近1，說(shuō)明依賴程度越強(qiáng)。越接近0，說(shuō)明依賴程度越弱。

第二步 設(shè)定閾值，構(gòu)造依賴圖。假設(shè)包含五個(gè)活動(dòng)a,b,c,d,e的執(zhí)行日志L=[1,10,10,1,1,1,2,1]，兩兩活動(dòng)之間相繼執(zhí)行的次數(shù)如表3所示，根據(jù)式(1)計(jì)算得到的活動(dòng)之間的依賴度如表4所示。設(shè)閾值為0.7，則依賴度大于0.7的兩個(gè)活動(dòng)之間用有向弧連接，如圖4(a)所示。例如，|a>Lb|=0.92，則活動(dòng)a到活動(dòng)b之間有一條有向弧，箭頭指向活動(dòng)b，表示b依賴于a。同時(shí)，弧上標(biāo)明了活動(dòng)之間的依賴度。

表3 活動(dòng)直接相繼執(zhí)行的次數(shù)

表4 各活動(dòng)之間的依賴度

圖4 C-net構(gòu)造過(guò)程

第三步 在依賴圖基礎(chǔ)上進(jìn)一步確定并行和選擇分支。假設(shè)依賴圖中活動(dòng)a有三個(gè)輸出b、c和e。如果b和e是并行結(jié)構(gòu)，則序列和在日志中多次出現(xiàn)。如果b和c是選擇結(jié)構(gòu)，則序列不可能出現(xiàn)。因此，計(jì)算a?Lb∧c，公式如下：

(3)

3.3 遺傳算法

遺傳算法[5,17]是一種模擬生物進(jìn)化過(guò)程的搜索技術(shù)。首先，隨機(jī)產(chǎn)生一組初始種群，利用適應(yīng)值函數(shù)計(jì)算個(gè)體的質(zhì)量，對(duì)質(zhì)量?jī)?yōu)良的個(gè)體做雜交變異操作形成新一代種群。重復(fù)這一過(guò)程，直到滿足終止條件。由于搜索空間不受限制，所以遺傳算法可以同時(shí)處理各種控制流結(jié)構(gòu)?；谶z傳算法的流程挖掘的關(guān)鍵是：(1) 流程模型的表示方式;(2) 評(píng)價(jià)流程模型的適應(yīng)值函數(shù);(3) 遺傳算子(雜交、變異)。

可用流程樹(shù)[5]作為流程模型表示方式。遺傳算法適應(yīng)值函數(shù)將四個(gè)質(zhì)量指標(biāo)(見(jiàn)2.4節(jié))綜合起來(lái)，使得產(chǎn)生的結(jié)果模型具有較高的綜合質(zhì)量，適應(yīng)值函數(shù)的計(jì)算公式為：

fitness=w1×Fr+w2×Pe+w3×Gv+w4×Sm

(4)

其中，F(xiàn)r、Pe、Gv和Sm分別為流程模型在重現(xiàn)度、精確度、通用性和簡(jiǎn)單性四方面的計(jì)算值。w1、 w2、w3和w4分別是四個(gè)質(zhì)量指標(biāo)的權(quán)重。用戶可以根據(jù)自己的偏好設(shè)置流程模型在這四方面的權(quán)重。利用適應(yīng)值函數(shù)計(jì)算當(dāng)前流程模型的適應(yīng)值，按照一定比例將適應(yīng)值最高的多個(gè)流程模型直接保留到下一代。其余的流程使用錦標(biāo)賽方法選出并通過(guò)雜交變異產(chǎn)生。具體方法如下：

(1) 雜交

參與雜交的兩棵流程樹(shù)隨機(jī)選擇各自的子樹(shù)進(jìn)行交換。已知兩棵流程樹(shù)P1、P2，隨機(jī)選中各自的一棵子樹(shù)，如圖5所示， P1選中子樹(shù)st1， P2選中子樹(shù)st2。將兩棵子樹(shù)交換后,得到兩棵新的流程樹(shù)P1′和P2′。

圖5 流程樹(shù)的雜交示意圖

(2) 變異

變異分為以下三種情況：節(jié)點(diǎn)變異、刪除活動(dòng)節(jié)點(diǎn)、添加活動(dòng)節(jié)點(diǎn)。

節(jié)點(diǎn)變異包括操作節(jié)點(diǎn)(非葉子節(jié)點(diǎn))變異和活動(dòng)節(jié)點(diǎn)變異。對(duì)于操作節(jié)點(diǎn)，改變其控制流結(jié)構(gòu)類型；對(duì)于活動(dòng)節(jié)點(diǎn)，改變其代表的活動(dòng)類型。例如，將流程樹(shù)P1中的代表并行結(jié)構(gòu)的操作節(jié)點(diǎn)(節(jié)點(diǎn)E的父節(jié)點(diǎn))變成順序結(jié)構(gòu)，變異結(jié)果如圖6(b)所示；將P1中活動(dòng)節(jié)點(diǎn)D的活動(dòng)類型變成C，變異結(jié)果如圖6(c)所示。

刪除活動(dòng)節(jié)點(diǎn)時(shí)，為了保證流程樹(shù)的正確結(jié)構(gòu)，有時(shí)需要同時(shí)刪除其父節(jié)點(diǎn)。例如，要將流程樹(shù)P1中的活動(dòng)節(jié)點(diǎn)E刪除，需要同時(shí)刪除它的父節(jié)點(diǎn)，并將節(jié)點(diǎn)F變成節(jié)點(diǎn)G的兄弟節(jié)點(diǎn)，變異結(jié)果如圖6(d)所示。

添加活動(dòng)節(jié)點(diǎn)指隨機(jī)產(chǎn)生一個(gè)活動(dòng)節(jié)點(diǎn)，將它添加到任意一個(gè)操作節(jié)點(diǎn)下。為了保證流程樹(shù)的正確結(jié)構(gòu)，有時(shí)需要同時(shí)添加父節(jié)點(diǎn)。例如，在流程樹(shù)P1中，將活動(dòng)節(jié)點(diǎn)C添加到活動(dòng)節(jié)點(diǎn)D的父節(jié)點(diǎn)下。在該父節(jié)點(diǎn)下創(chuàng)建一個(gè)同樣代表順序結(jié)構(gòu)的操作節(jié)點(diǎn)，將節(jié)點(diǎn)C和D添加到該操作節(jié)點(diǎn)下，變異結(jié)果如圖6(e)所示。

遺傳算法雖然能夠處理各種控制流結(jié)構(gòu)和日志噪聲，但由于初始種群是隨機(jī)產(chǎn)生的，因此結(jié)果流程也具有隨機(jī)性，可能得不到最優(yōu)的流程模型。

圖6 流程樹(shù)的變異示意圖

3.4 基于日志分類的算法

日志的多樣性導(dǎo)致已有的流程挖掘算法得到的流程結(jié)構(gòu)錯(cuò)綜復(fù)雜，難以理解。為了解決這個(gè)問(wèn)題，一種方法是對(duì)日志中的執(zhí)行實(shí)例進(jìn)行聚類，將其劃分成多個(gè)子日志，然后對(duì)各子日志施用已有的挖掘算法。這種方法的關(guān)鍵在于如何對(duì)執(zhí)行實(shí)例進(jìn)行聚類。聚類的好壞將影響最終的挖掘結(jié)果。

聚類的基本方法[8,18]是：根據(jù)某種規(guī)則構(gòu)造執(zhí)行實(shí)例的特征向量，如：實(shí)例中各活動(dòng)(或一組活動(dòng))出現(xiàn)的次數(shù)、處理的數(shù)據(jù)對(duì)象或性能參數(shù)等。假設(shè)日志L=[,,,,,]，按照活動(dòng)出現(xiàn)與否構(gòu)造實(shí)例的特征向量，如表5所示。

表5 執(zhí)行實(shí)例的特征向量

利用已有的相似度計(jì)算方法，如：歐幾里得距離、漢明距離、Jaccard距離等，計(jì)算各特征向量之間的相似度。利用已有的聚類算法對(duì)這些執(zhí)行實(shí)例進(jìn)行聚類，形成多個(gè)子日志。

采用以上方法對(duì)聚類后的子日志施用已有的挖掘算法得到的是局部流程。要得到完整的流程模型，可使用3.5節(jié)的方法挖掘?qū)哟瘟鞒棠Ｐ汀?/p>

3.5 基于執(zhí)行模式的算法

解決日志多樣性問(wèn)題，還有一種方法是挖掘?qū)哟文Ｐ蚚19]，挖掘步驟如圖7所示。首先，通過(guò)分析日志中的所有執(zhí)行實(shí)例，發(fā)現(xiàn)所有最大重復(fù)活動(dòng)序列片段，即通用執(zhí)行模式[20]。然后，通過(guò)活動(dòng)映射得到通用執(zhí)行模式的等價(jià)類[21]。利用Hasse圖構(gòu)造等價(jià)類之間的偏序關(guān)系。Hasse圖的頂端節(jié)點(diǎn)即為模式摘要。

重新掃描日志，將所有執(zhí)行實(shí)例中屬于某摘要的通用執(zhí)行模式用一個(gè)抽象活動(dòng)代替。對(duì)處理后的日志施用已有的挖掘算法，得到完整的流程模型。其中，某些活動(dòng)是抽象活動(dòng)，代表子流程的位置。對(duì)屬于同一模式摘要的所有通用執(zhí)行模式施用挖掘算法得到子流程。

圖7 層次模型挖掘示意圖

已知通用執(zhí)行模式有{ab,ac,bc,aad,add,aba,abc,acb,acd}。按照活動(dòng)將它們映射成等價(jià)類[21]:[{a,b}]={ab,aba}，[{a,c}]={ac}，[{b,c}]={bc}，[{a,d}]={aad,add}，[{a,b,c}]={abc,acb}，[{a,c,d}]={acd}。利用等價(jià)類之間的包含偏序關(guān)系構(gòu)造Hasse圖，如圖8所示。

圖8 等價(jià)類包含關(guān)系Hasse圖

圖8中，{a,b,c}和{a,c,d}是Hasse圖中最上層的頂點(diǎn)，因此作為模式摘要。處理日志實(shí)例時(shí)，頂點(diǎn){a,b,c}及其所覆蓋的所有子節(jié)點(diǎn){a,b},{a,c},{b,c}所對(duì)應(yīng)的通用執(zhí)行模式用抽象活動(dòng)A表示；頂點(diǎn){a,c,d}及其所覆蓋的子節(jié)點(diǎn){a,d}所對(duì)應(yīng)的通用執(zhí)行模式用抽象活動(dòng)B表示。節(jié)點(diǎn){a,c}同時(shí)被{a,b,c}和{a,c,d}包含，可人為規(guī)定{a,c}屬于{a,b,c}。對(duì)抽象處理后的日志可進(jìn)一步抽取模式摘要，用它對(duì)當(dāng)前日志進(jìn)一步處理得到新的抽象日志。不斷重復(fù)以上操作，可獲得各層次的抽象日志。對(duì)頂層日志施用已有的挖掘算法得到全局流程模型。對(duì)各層次的模式摘要所對(duì)應(yīng)的通用執(zhí)行模式施用挖掘算法得到各層次的子流程。

4 算法比較

第3節(jié)介紹了經(jīng)典的流程挖掘算法的實(shí)現(xiàn)原理，以及它們各自的適用范圍和局限性。本節(jié)將從日志完整性 (cmp)，控制流結(jié)構(gòu)，如：順序結(jié)構(gòu)(seq)、選擇結(jié)構(gòu)(cho)、并行結(jié)構(gòu)(par)、循環(huán)結(jié)構(gòu)(loo)、非自由選擇結(jié)構(gòu)(nfc)、重復(fù)活動(dòng)(dup)，以及噪聲處理等方面對(duì)這些算法進(jìn)行分析和比較，比較結(jié)果如表6所示。基于日志分類和執(zhí)行模式的算法都是對(duì)日志進(jìn)行預(yù)處理，挖掘階段仍使用現(xiàn)有的流程挖掘算法，因此處理控制流結(jié)構(gòu)的能力與選用的具體挖掘算法有關(guān)。

α算法只能處理長(zhǎng)度大于2的長(zhǎng)循環(huán)結(jié)構(gòu)，而不能處理長(zhǎng)度為1或2的短循環(huán)結(jié)構(gòu)。因此，在表6中，α算法的“l(fā)oo”項(xiàng)為“√/×”，表示只能處理部分循環(huán)結(jié)構(gòu)。

表6 日志完整性要求和控制流結(jié)構(gòu)比較

表7對(duì)從處理日志噪聲、日志多樣性和模型質(zhì)量控制等方面對(duì)算法進(jìn)行了比較。啟發(fā)式算法和遺傳算法能夠處理日志噪聲。模型質(zhì)量方面，一般的流程挖掘算法得到結(jié)果流程模型后，可通過(guò)一致性檢查計(jì)算四個(gè)維度的模型質(zhì)量。而遺傳算法可通過(guò)調(diào)節(jié)適應(yīng)值函數(shù)中的權(quán)重控制結(jié)果模型在四個(gè)質(zhì)量維度上的表現(xiàn)。基于日志分類和執(zhí)行模式的算法能夠很好地處理日志多樣性問(wèn)題。

表7 日志噪聲、多樣性和質(zhì)量控制比較

5 結(jié) 語(yǔ)

流程挖掘技術(shù)作為流程再設(shè)計(jì)和分析的一項(xiàng)關(guān)鍵技術(shù)，為流程變化管理和診斷提供了良好的解決方案。本文總結(jié)了流程挖掘中遇到的關(guān)鍵問(wèn)題，介紹了5種流程挖掘算法，并從日志完整性、控制流結(jié)構(gòu)、處理噪聲、模型質(zhì)量控制等方面對(duì)它們進(jìn)行了分析和比較。

縱觀全文，目前各種流程挖掘算法都有其各自的特色和適用范圍。針對(duì)不同特征的日志，如何選擇最佳的挖掘算法仍然是一項(xiàng)挑戰(zhàn)。尤其是在處理復(fù)雜流程的多樣性日志時(shí)，研究一種普適性的挖掘算法是未來(lái)的一個(gè)研究方向。除此之外，日志數(shù)據(jù)處理、解決特殊控制流結(jié)構(gòu)和挖掘結(jié)果的可視化等將仍然是未來(lái)流程挖掘研究的發(fā)展方向。

[1] 趙衛(wèi)東,范力.工作流挖掘研究的現(xiàn)狀與發(fā)展[J].計(jì)算機(jī)集成制造系統(tǒng),2009,14(12):2289-2296.

[2] Aalst W.Process mining:discovery,conformance and enhancement of business processes[M].Springer,2011.

[3] Demedeiros A,Alves K.Genetic Process Mining[D].Eindhoven:Technische Universiteit Eindhoven,2006.

[4] Aalst W.Petri-net-based workflow management software[C]//Proceedings of the NFS Workshop on Workflow and Process Automation in Information Systems,1996:114-118.

[5] Buijs J,Dongen B,Aalst W.A genetic algorithm for discovering process trees[C]//Proceedings of 2012 IEEE Congress on Evolutionary Computation,2012:1-8.

[6] Wen L,Aalst W,Wang J,et al.Mining process models with non-free-choice constructs[J].Data Mining and Knowledge Discovery,2007,15(2):145-180.

[7] Dongen B,Medeiros A,Wen L.Process mining:overview and outlook of petri net discovery algorithms[J].Transactions on Petri Nets and Other Models of Concurrency II,2009,5460:225-242.

[8] Song M,Christian W,Aalst W.Trace clustering in process mining[C]//Proceedings of Business Process Management Workshops,2009:109-120.

[9] Buijs J,Dongen B,Aalst W.On the role of fitness,precision,generalization and simplicity in process discovery[C]//On the Move to Meaningful Internet Systems (OTM 2012),2012:305-322.

[10] Aalst W,Adriansyah A,Dongen B.Replaying history on process models for conformance checking and performance analysis[J].Wiley Interdisciplinary Reviews:Data Mining and Knowledge Discovery,2012,2(2):182-192.

[11] Medeiros A,Dongen B,Aalst W,et al.Process mining for ubiquitous mobile systems:an overview and a concrete algorithm[C]//Ubiquitous Mobile Information and Collaboration Systems.Springer,2005:151-165.

[12] Wen L,Wang J,Sun J.Mining invisible tasks from event logs[C]//Advances in Data and Web Management.Springer,2007:358-365.

[13] Aalst W,Weijters T,Maruster L.Workflow mining:Discovering process models from event logs[J].IEEE Transactions on Knowledge and Data Engineering,2004,16(9):1128-1142.

[14] Li J,Liu D,Yang B.Process mining:Extending α-algorithm to mine duplicate tasks in process logs[C]//Advances in Web and Network Technologies,and Information Management.Springer,2007:396-407.

[15] Weijters A,Aalst W.Rediscovering workflow models from event-based data using little thumb[J].Integrated Computer Aided Engineering,2003,10(2):151-162.

[16] Weijters A,Aalst W,Medeiros A.Process mining with the heuristics miner-algorithm[J].Technische Universiteit Eindhoven,Tech.Rep.WP,2006,166:1-34.

[17] Bratosin C,Sidorova N,Aalst W.Discovering process models with genetic algorithms using sampling[J].Knowledge-Based and Intelligent Information and Engineering Systems,2010,6276:41-50.

[18] Bose R,Aalst W.Context aware trace clustering:towards improving process mining results[C]//Proceedings of SDM,2009:401-412.

[19] Bose R,Verbeek E,Aalst W.Discovering hierarchical process models using ProM[C]//IS Olympics: Information Systems in a Diverse World,Springer,2012:33-48.

[20] Bose R,Aalst W.Trace clustering based on conserved patterns:towards achieving better process models[C]//Proceedings of Business Process Management Workshops,2010:170-181.

[21] Bose R,Aalst W.Abstractions in process mining:a taxonomy of patterns[C]//Business Process Management,Springer,2009:159-175.

ON BUSINESS PROCESS MINING ALGORITHMS

Yang Liqin1,2Kang Guosheng2Cai Weigang1Zhou Qiang1

1(LibraryandInformationCenter,ShanghaiUniversityofTraditionalChineseMedicine,Shanghai201203,China)2(SchoolofComputerScience,FudanUniversity,Shanghai201203,China)

Process mining can reconstruct a process model according to the execution log of process, which conduces to the realisation of business process optimisation and intelligent management. This paper first presents the key problems of current process mining technologies to be solved. Then it encompasses a couple of typical process mining algorithms, by which the problems each one tackled and the shortcomings of each are indicated. This paper also gives analysis and comparison on these algorithms in terms of log integrity, control-flow structure, noise processing and quality control. Finally, a set of directions for future research in process mining technology is pointed out.

Process mining α algorithm Heuristic algorithm Genetic algorithm Log classification

2014-10-20。上海中醫(yī)藥大學(xué)預(yù)算內(nèi)項(xiàng)目(2013JW 30)。楊麗琴，講師，主研領(lǐng)域：業(yè)務(wù)流程管理，服務(wù)計(jì)算，醫(yī)學(xué)信息。康國(guó)勝，碩士。蔡偉剛，講師。周強(qiáng)，研究員。

TP3

A

10.3969/j.issn.1000-386x.2016.04.011