李 娟，王麗麗，劉祥偉

（安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001）

1 引言

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

本文從新的角度提出聯(lián)合發(fā)生類概念從不完整日志中能夠構(gòu)建合理的業(yè)務(wù)過程模型.從日志中檢測出每個活動的不變優(yōu)先集、不變后續(xù)集、不變發(fā)生活動集，最后得到活動的聯(lián)合發(fā)生類推測出具有強(qiáng)因果關(guān)系的活動類.再運(yùn)用刪除活動函數(shù)找出日志中隱藏的活動之間的因果關(guān)系和并發(fā)關(guān)系用于完善業(yè)務(wù)過程模型，提高過程模型的合適度.提出的聯(lián)合發(fā)生挖掘算法已經(jīng)在Prom中實(shí)現(xiàn)，實(shí)驗(yàn)結(jié)果表明與其他算法比較該算法能夠在不完整日志中或執(zhí)行跡較少的情況下構(gòu)建出更合理的業(yè)務(wù)過程模型.

2 基本概念

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

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

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

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

（1）嚴(yán)格序→：當(dāng)且僅當(dāng)x?y,y≯x.

（2）排他序+：當(dāng)且僅當(dāng)x≯y,y≯x.

（3）較差序||： 當(dāng)且僅當(dāng)x?y,y?x.

（4）嚴(yán)格逆序→-1：當(dāng)且僅當(dāng) x≯y,y?x.

以上幾種關(guān)系構(gòu)成了網(wǎng)N的行為輪廓，記作BP={→,+,||}.

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

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

（2）N中的每一個活動都在日志λ中出現(xiàn).

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

定義6[10]（不變發(fā)生活動集）在日志λ中活動a的不變發(fā)生活動集是指當(dāng)a發(fā)生時，該活動集總是和活動a一起發(fā)生.記為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運(yùn)用前集和后集函數(shù)可得，

定義7[10]（聯(lián)合發(fā)生類）設(shè)是上的一個二元關(guān)系，定義，是粗粒度的等價關(guān)系，稱是聯(lián)合發(fā)生關(guān)系，稱等價類為聯(lián)合發(fā)生類.同一個聯(lián)合發(fā)生類的兩個活動具有很強(qiáng)的因果關(guān)系記作.

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

通過上面引入Petri網(wǎng)和聯(lián)合發(fā)生類的相關(guān)概念，下面介紹運(yùn)用聯(lián)合發(fā)生挖掘算法從不完整日志中構(gòu)建合理的業(yè)務(wù)流程模型.

3 聯(lián)合發(fā)生挖掘算法

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

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

輸出：合理工作流網(wǎng)N.

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

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

3.根據(jù)發(fā)生不變量活動集表得出活動關(guān)系矩陣，并且從該矩陣中找出聯(lián)合發(fā)生類COci.

4.同一個聯(lián)合發(fā)生類的活動a,b∈COci具有很強(qiáng)的因果關(guān)系用a?b表示.

5.根據(jù)定義8運(yùn)用過濾函數(shù)?X(σi)將聯(lián)合發(fā)生類COci里的具有很強(qiáng)因果關(guān)系的活動過濾掉發(fā)現(xiàn)不完整日志中存在隱藏活動之間關(guān)系.

6.繪制日志中的活動之間關(guān)系表.

7.構(gòu)建業(yè)務(wù)過程模型.

下面通過實(shí)例分析驗(yàn)證聯(lián)合發(fā)生挖掘算法的可行性.

4 實(shí)例分析

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

以活動B為例計算活動B的不變優(yōu)先集、不變后繼集、不變發(fā)生活動集.

表1 活動集發(fā)生不變量

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

計算結(jié)果見表1.根據(jù)表1的不變發(fā)生活動集可以得到活動之間的關(guān)系矩陣，在關(guān)系矩陣中兩個活動在不變發(fā)生活動集中就用1表示.具體的活動關(guān)系矩陣見

圖1 活動之間關(guān)系矩陣

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

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

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

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

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

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

運(yùn)用聯(lián)合發(fā)生類可以得到在原日志中不易被發(fā)現(xiàn)發(fā)現(xiàn)的活動對關(guān)系F||D，J+K，A→J,C→D,C→D,D→B再結(jié)合行為輪廓知識得出原日志明顯活動對關(guān)系可以得出活動之間關(guān)系表，呈現(xiàn)在表2.

根據(jù)活動之間關(guān)系表可以構(gòu)建該業(yè)務(wù)過程模型.

圖2 運(yùn)用聯(lián)合發(fā)生類挖掘算法得到合理業(yè)務(wù)流程模型

5 結(jié)論

本文提出一種從不完整日志中挖掘業(yè)務(wù)過程模型的新方法，是以活動之間聯(lián)合發(fā)生關(guān)系為基礎(chǔ)，將日志中活動劃分為聯(lián)合發(fā)生類用來推斷在不完整日志中丟失的因果關(guān)系和并行關(guān)系，明顯地提高了業(yè)務(wù)過程模型的合適度.相關(guān)實(shí)驗(yàn)表明，該方法提出的概念和算法在其他相關(guān)的發(fā)現(xiàn)領(lǐng)域具有重要作用.盡管此方法在處理不完整日志具有明顯的優(yōu)勢，局限性在于不易發(fā)現(xiàn)模型中短循環(huán)結(jié)構(gòu)，在以后的學(xué)習(xí)中會進(jìn)一步優(yōu)化算法，找到更合理的方法從事件日志中發(fā)現(xiàn)活動之間關(guān)系構(gòu)建更合理的業(yè)務(wù)過程模型.