基于聯合發生類的業務過程挖掘方法

李 娟，王麗麗，劉祥偉

（安徽理工大學 數學與大數據學院，安徽 淮南 232001）

1 引言

過程挖掘的目的在于從事件日志中提取信息構建流程過程模型，合理的流程模型能夠對日志中的行為進行重演.目前，過程發現技術面臨問題是事件日志往往不能包含一個業務過程模型的所有信息（如不完整日志）.這將導致所挖掘的流程模型與實際業務流程不一致，達不到企業或者客戶的期望.造成日志不完整的原因有很多，其中最常見的原因是并行結構的出現，因為大量并行活動的交互不能在執行日志中展現.文獻[1]提供了幾種度量維度(合適度、精度、泛化)評估所挖掘的流程模型與日志的一致性程度，如是否明確的表達活動之間的因果關系和并行關系，是否體現了所提供信息的所有可以觀察的行為.在工作流管理系統領域里，已經提出相關過程發現技術去發現業務過程模型.文獻[2]提供一種算法，通過捕獲業務過程日志將業務過程非結構化得到業務流程圖滿足日志中活動依賴關系和執行情況.實驗證明此技術更容易引入工作流系統還可以對實際業務流程進行評估.實際的工作流過程和管理所執行的業務過程往往存在差異，然而創建工作流設計是一個復雜耗時的過程，文獻[3]提出一種算法從日志中的活動之間發生順序來推斷業務過程模型.顯然該方法具有一定局限性只能發現簡單的業務流程模型.隨后許多技術對此算法進行拓展，文獻[4]提出一種能夠檢測到Petri網中活動之間依賴關系，其中包括顯式依賴和隱式依賴，實驗結果表明該方法在非自由選擇結構的挖掘中能夠顯著提高業務過程模型的合適性.為了從事件日志中發現并發行為模式，文獻[5]提出一種基于事件的概率分析，使用事件發生的次數、頻率和規律性指標確定系統中可能出現的并發行為可以幫助業務過程設計人員更好改進業務流程模型.從事件日志中提出控制流和相關數據參數的算法在文獻[6]提出，演示了運用條件偏序圖(CPOG)將事件日志可視化揭示業務過程中控制流和數據流之間隱藏的相互作用，為新的過程挖掘開辟道路.感知挖掘算法[7]能夠處理不完整日志，采用分而治之的方法遞歸處理所有日志構建流程模型.文獻[8]使用了遺傳算法發現過程樹從而減少搜索空間并且用戶在最終的業務過程模型中可以選擇自己需要的業務流程模型質量維度.

本文從新的角度提出聯合發生類概念從不完整日志中能夠構建合理的業務過程模型.從日志中檢測出每個活動的不變優先集、不變后續集、不變發生活動集，最后得到活動的聯合發生類推測出具有強因果關系的活動類.再運用刪除活動函數找出日志中隱藏的活動之間的因果關系和并發關系用于完善業務過程模型，提高過程模型的合適度.提出的聯合發生挖掘算法已經在Prom中實現，實驗結果表明與其他算法比較該算法能夠在不完整日志中或執行跡較少的情況下構建出更合理的業務過程模型.

2 基本概念

定義1[9]滿足下列條件的三元組N=(S,T;F)稱作一個網：

定義2[9]設N=(S,T;F)為一個網，對于x∈S∪T,記

稱·x為x的前集或輸入集，x·為x的后集或輸出集.稱·x∪x·為元素 x的外延.

定義3[10]（行為輪廓）令S=(N,M0)是一個網系統，其中N=(S,T;F)且T'?T是一個變遷集.一對變遷(x,y)∈(T'×T')若滿足下面條件之一：

（1）嚴格序→：當且僅當x?y,y≯x.

（2）排他序+：當且僅當x≯y,y≯x.

（3）較差序||： 當且僅當x?y,y?x.

（4）嚴格逆序→-1：當且僅當 x≯y,y?x.

以上幾種關系構成了網N的行為輪廓，記作BP={→,+,||}.

定義4[10]（完整日志）N是一個合理工作流網，λ是N的工作流日志.λ是N的完整工作流日志必須滿足下面兩個條件：

（1）對 N 中任一個工作流日志 λ'：→λ'?→λ.

（2）N中的每一個活動都在日志λ中出現.

定義5[10]（不變優先集和不變后繼集）在日志λ的每一條跡σk中總是出現在活動a之前（之后）的活動集，稱為a的不變優先集記為InvPred(a.λ)（a的不后繼變集 InvSucc(a,λ)）.其中

定義6[10]（不變發生活動集）在日志λ中活動a的不變發生活動集是指當a發生時，該活動集總是和活動a一起發生.記為Oi(a)=InvPred(a,λ)∪InvSucc(a,λ)∪{a}

例如，日志 λ 中有條跡 σ1=＜x,a,b,d,e,a,c,a,b,y＞，σ1=＜x,d,e,a,b,y＞.在日志λ中對活動a運用前集和后集函數可得，

定義7[10]（聯合發生類）設是上的一個二元關系，定義，是粗粒度的等價關系，稱是聯合發生關系，稱等價類為聯合發生類.同一個聯合發生類的兩個活動具有很強的因果關系記作.

定義8[10]（過濾函數）活動集X?T,跡σ1∈λ，函數?X(σi)表示在跡σi中過濾掉活動X后得到的跡.如 ?(a,b)(σ1)=＜x,d,e,c,a,b,y＞.

通過上面引入Petri網和聯合發生類的相關概念，下面介紹運用聯合發生挖掘算法從不完整日志中構建合理的業務流程模型.

3 聯合發生挖掘算法

從不完整日志或者較少的跡中直接構建業務流程模型是粗糙的，不能反映真實業務流程的實際運行情況.基于第二部分的基礎知識，下面提出一種聯合發生的挖掘算法，盡可能挖掘隱藏在日志中更多有用的活動之間關系來構建更加合理的業務流程模型.首先檢測不完整日志中所有聯合發生類找出具有強因果關系活動對.再利用過濾函數找出隱藏在日志中活動之間關系.最后得出所有活動之間的關系表構建業務流程模型.算法的具體步驟如下：

輸入：日志 λ={σ1,σ2,σ3…σn}.

輸出：合理工作流網N.

1.對不完整日志中的每一個活動，運用定義4和定義5計算活動的不變優先集和不變后繼集.根據定義6計算出每個活動a∈T的不變發生活動集.Oi(a)=InvPred(a,λ)∪InvSucc(a,λ)∪{a}.

2.根據步驟1和2繪制發生不變量活動集表，其中包含InvPred，InvSucc和Oi.

3.根據發生不變量活動集表得出活動關系矩陣，并且從該矩陣中找出聯合發生類COci.

4.同一個聯合發生類的活動a,b∈COci具有很強的因果關系用a?b表示.

5.根據定義8運用過濾函數?X(σi)將聯合發生類COci里的具有很強因果關系的活動過濾掉發現不完整日志中存在隱藏活動之間關系.

6.繪制日志中的活動之間關系表.

7.構建業務過程模型.

下面通過實例分析驗證聯合發生挖掘算法的可行性.

4 實例分析

為了驗證上述算法的可行性，下面運用算法構建出不完整日志 λ={σ1,σ2,σ3,σ4,σ5}的模型.其中

以活動B為例計算活動B的不變優先集、不變后繼集、不變發生活動集.

表1 活動集發生不變量

同理可得日志 λ={σ1,σ2,σ3,σ4,σ5}中其他活動的不變優先集、不變后繼集、不變發生活動集.

計算結果見表1.根據表1的不變發生活動集可以得到活動之間的關系矩陣，在關系矩陣中兩個活動在不變發生活動集中就用1表示.具體的活動關系矩陣見

圖1 活動之間關系矩陣

在活動之間關系矩陣中可以明顯看到6個聯合發生不變量，在圖1中用方框表示出了，其中COci={B,C}可以觀察到B∈COci，當活動B出現在日志λ={σ1,σ2,σ3,σ4,σ5}中時，活動 C 也出現在日志 λ={σ1,σ2,σ3,σ4,σ5}中.且他們都是以 B,C 順序發生在日志中所以B,C是強因果關系對B?C.同理還有兩個聯合發生不變量COci={D}，COci={A,E,F,G,H,I}.強因果關系對A?E,E?F,F?H,H?I，COci={J}.COci={K,L,M}強因果關系對K?L,L?M，COci={N}.

根據算法步驟6運用過濾函數?X(σi)發現日志中隱藏的活動對之間關系.從日志 λ={σ1,σ2,σ3,σ4,σ5}中運用過濾函數刪除活動B,C可得：

從過濾后的日志σ'1，σ'3中可以得出F||D,

從過濾后的日志σ'4，σ'3中可以得出J+K，A→K,A→J.

同理運用過濾函數在日志 λ={σ1,σ2,σ3,σ4,σ5}刪除活動對E,F可得：

從過濾后日志σ"1，σ"3可以得出C→D,D→B.

運用聯合發生類可以得到在原日志中不易被發現發現的活動對關系F||D，J+K，A→J,C→D,C→D,D→B再結合行為輪廓知識得出原日志明顯活動對關系可以得出活動之間關系表，呈現在表2.

根據活動之間關系表可以構建該業務過程模型.

圖2 運用聯合發生類挖掘算法得到合理業務流程模型

5 結論

本文提出一種從不完整日志中挖掘業務過程模型的新方法，是以活動之間聯合發生關系為基礎，將日志中活動劃分為聯合發生類用來推斷在不完整日志中丟失的因果關系和并行關系，明顯地提高了業務過程模型的合適度.相關實驗表明，該方法提出的概念和算法在其他相關的發現領域具有重要作用.盡管此方法在處理不完整日志具有明顯的優勢，局限性在于不易發現模型中短循環結構，在以后的學習中會進一步優化算法，找到更合理的方法從事件日志中發現活動之間關系構建更合理的業務過程模型.