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

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

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

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

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

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

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

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

0 引 言

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

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

1 流程挖掘的基本概念

1.1 日 志

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

表1 會議流程的部分日志

表2 會議流程日志的化簡形式

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

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

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

1.2 流程模型表示方法

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

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

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

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

(a) P是一個有限的庫所集;

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

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

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

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

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

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

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

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

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

圖1 會議流程的WF-net模型

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

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

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

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

(c) 不存在隱式庫所。

1.2.2 Causal net (C-net)

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

圖2 一個C-net例子

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

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

其中：

A是活動的有限集合;

{ai}={a∈A|I(a)={?}}是開始活動;

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

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

I∈A→AS是活動的輸入約束;

O∈A→AS是活動的輸出約束;

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 流程樹

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

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

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

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

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

2.2 日志噪聲和不完整性

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

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

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

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

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

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

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

2.3 日志多樣性

日志多樣性指由于流程本身錯綜復(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ù)雜、難以理解。

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

2.4 流程模型質(zhì)量評價

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

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

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

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

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

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

3 流程挖掘算法

3.1 直接算法

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

以α算法[13]為例，活動之間的基本關(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(無關(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：并行合并。

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

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

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

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

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

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

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

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

3.2 啟發(fā)式算法

α及其擴(kuò)展算法雖然分別能夠處理各種控制流結(jié)構(gòu)，但卻不能處理日志中的噪聲。而在實(shí)際應(yīng)用中，日志中的噪聲是不可避免的。噪聲出現(xiàn)的原因可能是日志記錄錯誤或流程執(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)。

第一步 計算活動之間的依賴度，計算公式如下：

(1)

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

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

(2)

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

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

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

表4 各活動之間的依賴度

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

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

(3)

3.3 遺傳算法

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

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

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

(4)

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

(1) 雜交

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

圖5 流程樹的雜交示意圖

(2) 變異

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

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

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

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

3.4 基于日志分類的算法

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

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

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

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

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

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

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

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

圖7 層次模型挖掘示意圖

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

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

圖8中，{a,b,c}和{a,c,d}是Hasse圖中最上層的頂點(diǎn)，因此作為模式摘要。處理日志實(shí)例時，頂點(diǎn){a,b,c}及其所覆蓋的所有子節(jié)點(diǎn){a,b},{a,c},{b,c}所對應(yīng)的通用執(zhí)行模式用抽象活動A表示；頂點(diǎn){a,c,d}及其所覆蓋的子節(jié)點(diǎn){a,d}所對應(yīng)的通用執(zhí)行模式用抽象活動B表示。節(jié)點(diǎn){a,c}同時被{a,b,c}和{a,c,d}包含，可人為規(guī)定{a,c}屬于{a,b,c}。對抽象處理后的日志可進(jìn)一步抽取模式摘要，用它對當(dāng)前日志進(jìn)一步處理得到新的抽象日志。不斷重復(fù)以上操作，可獲得各層次的抽象日志。對頂層日志施用已有的挖掘算法得到全局流程模型。對各層次的模式摘要所對應(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ù)活動(dup)，以及噪聲處理等方面對這些算法進(jìn)行分析和比較，比較結(jié)果如表6所示。基于日志分類和執(zhí)行模式的算法都是對日志進(jìn)行預(yù)處理，挖掘階段仍使用現(xiàn)有的流程挖掘算法，因此處理控制流結(jié)構(gòu)的能力與選用的具體挖掘算法有關(guān)。

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

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

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

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

5 結(jié) 語

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

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

[1] 趙衛(wèi)東,范力.工作流挖掘研究的現(xiàn)狀與發(fā)展[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ù)計算，醫(yī)學(xué)信息。康國勝，碩士。蔡偉剛，講師。周強(qiáng)，研究員。

TP3

A

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