李 增,方賢文

(安徽理工大學(xué))

0 引言

在廣泛的過程挖掘領(lǐng)域中，一個令人感興趣的領(lǐng)域是流程發(fā)現(xiàn)，它從事件日志中挖掘出流程模型,但在挖掘業(yè)務(wù)流程模型的過程中發(fā)現(xiàn)一種有趣的情況，一些活動沒有在事件日志中發(fā)現(xiàn)，而在許多IT系統(tǒng)的業(yè)務(wù)流程模型中存在，這種活動被稱為隱變遷.從事件日志中挖掘隱變遷可以還原更符合實際情況的流程模型，提高模型的運(yùn)轉(zhuǎn)效率，從而業(yè)務(wù)流程模型更加完善.

過程挖掘的目標(biāo)之一是研究頻繁行為，以便在過程挖掘的不同任務(wù)(發(fā)現(xiàn)、監(jiān)控和增強(qiáng))中關(guān)注過程中更常見的部分.文獻(xiàn)[1-5]提出了幾種算法來發(fā)現(xiàn)涵蓋最常見行為的流程模型，并直接在日志中搜索頻繁的結(jié)構(gòu).在發(fā)現(xiàn)流程模型的過程中，文獻(xiàn)[6-7]也使用了對不常見情況(偏差或異常痕跡)的搜索，去除它們以降低模型的復(fù)雜性，同時不大幅降低適合度.文獻(xiàn)[8]提出了一種WoMine-i算法用于從過程模型中檢索不頻繁的行為模式，實驗表明，可找到所有類型的模式，提取無法用最先進(jìn)的技術(shù)挖掘的信息.文獻(xiàn)[9]提出一種活動過濾方法的新技術(shù)，比基于頻率的方法過濾異常活動更有效.文獻(xiàn)[10] 提出基于規(guī)則的合并方法和規(guī)則建議算法，用于流程日志的合并，并在Prom中實現(xiàn).文獻(xiàn)[11]根據(jù)區(qū)域理論尋找非平凡區(qū)域,建立了一個具有隱式變遷的分片子模型, 將子模型與初始模型相結(jié)合，挖掘出具有隱變遷的目標(biāo)模型.

目前已有研究主要針對事件日志中活動之間的依賴關(guān)系進(jìn)行隱變遷的挖掘，很少關(guān)注模型的結(jié)構(gòu)，算法執(zhí)行效率比較低.該文通過行為輪廓塊結(jié)構(gòu)來挖掘日志中的隱變遷.在進(jìn)行流程挖掘之前,預(yù)先定義一個合理的截斷系數(shù),再通過序列編碼過濾對事件日志進(jìn)行處理.事件日志經(jīng)過截斷系數(shù)過濾劃分為平凡序列和非平凡序列，并利用α+算法挖掘出初始模型.利用塊結(jié)構(gòu)對初始模型進(jìn)行層次分解.將非平凡子序列與模型分解的塊結(jié)構(gòu)進(jìn)行匹配，找出模型結(jié)構(gòu)中可能存在的隱變遷.最后利用擬合度和精確度對疑似隱變遷進(jìn)行進(jìn)一步的檢驗, 過濾掉異常的變遷,從而挖掘出含有隱變遷的目標(biāo)優(yōu)化模型.通過該方法所得到的業(yè)務(wù)流程模型更加精確、完善, 提高了業(yè)務(wù)流程模型的利用效率.

該文第1節(jié)介紹了基本概念；第2節(jié)提出基于塊結(jié)構(gòu)的隱變遷挖掘方法；第3節(jié)給出了相應(yīng)的案例分析，并通過相關(guān)度量值進(jìn)行檢驗該方法的可行性；最后總結(jié)全文并展望未來.

1 基本概念

定義1[12]：(工作流Petri網(wǎng) WF-PN) 一個Petri網(wǎng)N=(S,T;F,i,o)稱為WF-PN, 當(dāng)且僅當(dāng)滿足條件:

(1) 該P(yáng)etri網(wǎng)有唯一的開始庫所i:′i=?；

(2) 該P(yáng)etri網(wǎng)有唯一的終止庫所o:o′=?；

(3) 該P(yáng)etri網(wǎng)上的每一個節(jié)點都屬于i到o的一條路徑上, 即Petri網(wǎng)N是強(qiáng)連通的.

定義2[12](行為輪廓)設(shè)(N，M0)是一個網(wǎng)，初始標(biāo)識為M0.對任給的變遷對(ti,tj)，弱序關(guān)系 >?(T×T)，滿足下面關(guān)系

(1)若t1>t2且t2>/t1，則稱嚴(yán)格序關(guān)系，記作t1→t2；

(2)若t1>/t2且t2>/t1，則稱排他關(guān)系，記作t1+t2；

(3)若t1>t2且t2>t1，則稱交叉序關(guān)系，記作t1‖t2.

定義3[13](塊結(jié)構(gòu))設(shè)Petri網(wǎng)

N=(S,T;F)為一個WF-PN，

N′=(S′,T′;F′)為N的一個子網(wǎng).

(1)若N′為一個順序塊,記為SB，當(dāng)且僅當(dāng)

|S′|>1∧?ti1,ti2∈T′?ti1→ti2∨ti1→ti2

(2)若N′為一個并發(fā)塊，記為CB，當(dāng)且僅當(dāng) ?t∈T′??t′∈T′,t‖t′.

(3)若N′為一個選擇塊，記為ChB，當(dāng)且僅當(dāng)?t∈T′??t′∈T′,t+t′.

定義4 (隱變遷)設(shè)T′是Petri網(wǎng)業(yè)務(wù)流程模型中的變遷集，L′是記錄日志事件集.

λ:T′→L′ 是標(biāo)記映射，變遷t′為隱變遷,當(dāng)且僅當(dāng)t′?dom(λ),即t′不屬于λ的定義域內(nèi).

定義5[12](事件日志)T是任務(wù)集,σ∈T*是一個執(zhí)行跡,L∈P(T*) 是一個事件日志.P(T*)是T*的冪集,L?T*.

定義6[14]日志對模型的擬合度f(M,L)計算如下，其中：k為給定日志中的不同軌跡數(shù)，n日志跡中所含實例的數(shù)目,m丟失令牌的數(shù)量,r剩余令牌的數(shù)量,c使用令牌的數(shù)量.

定義7[15](行為精確度和查全率) 設(shè)σ是一個事件日志的跡,L(σ)為跡σ在一個事件日志中所發(fā)生的次數(shù),Nr和Nm分別表示Petri網(wǎng)的參考模型和挖掘模型,Cr和Cm分別表示Nr和Nm的因果關(guān)系,行為精確度和查全率的計算式分別為

定義8[15](結(jié)構(gòu)精確度和查全率) 設(shè)Nr和Nm分別表示Petri網(wǎng)的參考模型和挖掘模型,Cr和Cm分別表示Nr和Nm的因果關(guān)系,結(jié)構(gòu)精確度和查全率的計算公式分別為:

2 基于行為輪廓挖掘隱變遷的方法

在結(jié)構(gòu)良好的流程中，模型支持的行為被設(shè)計就期望被執(zhí)行，而執(zhí)行頻率較低的模型子結(jié)構(gòu)可能會暗示流程中的一條路徑，為了增加其頻率，必須加強(qiáng)該路徑；相反地，可以重新構(gòu)造分配的資源以優(yōu)化流程.恰好隱變遷的挖掘能很好地還原某些低頻日志代表的意義，提高日志在模型中擬合度，完善系統(tǒng)模型，有利于業(yè)務(wù)流程管理的高效生產(chǎn)與服務(wù).因此從事件日志中挖掘隱變遷是一個值得研究的課題.

該文通過Petri網(wǎng)塊結(jié)構(gòu)的理論來挖掘事件日志中的隱變遷.首先對系統(tǒng)生成的海量流程日志進(jìn)行清洗，過濾掉異常日志，利用序列編碼過濾圖將日志劃分為平凡序列和非平凡子序列.對于高頻日志利用α+算法挖掘出初始模型M0，利用行為輪廓塊結(jié)構(gòu)對初始模型M0進(jìn)行層次分解.將非平凡子序列與模型分解的模塊進(jìn)行匹配，找出可疑模塊，查找出可能含有隱變遷的位置，插入隱變遷，形成含有隱變遷的子模塊，融合子模塊將其構(gòu)建為目標(biāo)模型M1，最后通過擬合度、行為精確度、查全率和結(jié)構(gòu)精確度、查全率等指標(biāo)對模型M1進(jìn)行評價，刪除錯誤的隱變遷，保留對模型有改善的含有隱變遷的目標(biāo)模型.

算法1 從事件日志中找出符合流程模型的低頻序列

BEGIN(算法開始)

輸入:事件日志序列L,合理的截斷系數(shù)cc，閾值tf

輸出:初始模型M0和符合流程模型的低頻日志

步驟1 對日志序列進(jìn)行預(yù)處理，直接過濾掉不完整的日志序列(明顯為異常序列)，

eg.{{A},{A,B}}.

步驟2 針對預(yù)處理后的序列，先計算其前綴閉包集，然后作出序列的編碼過濾圖 .

步驟3 以廣度的方式遍歷圖，保留頂點出弧的權(quán)值最大的分支，設(shè)最大權(quán)值為a，若該頂點其它出弧的權(quán)值小于a·cc，截斷該分支.

步驟4 步驟3的結(jié)果把日志序列劃分為平凡序列和非平凡序列，對于平凡序列，在Prom軟件運(yùn)用α+算法挖掘得到其初始模型M0.

步驟5 某些非平凡子序列對模型是有效的，而構(gòu)建的初始模型M0并未考慮,因此模型是不完善的，為了提高模型準(zhǔn)確度，將這些非平凡序列重放到模型M0中.

步驟6 將步驟4得到的非平凡序列重放到初始模型M0中,根據(jù)擬合度計算公式

計算各序列的擬合度.

步驟7 若擬合度f≤tf，則把此非平凡序列視為噪音序列，從日志中刪除；若擬合度f≥tf，則保留此非平凡序列，視為有效的序列.重復(fù)步驟6.

步驟8 輸出流程模型有效的非平凡子序列.

END(算法結(jié)束)

算法1中，通過計算將事件日志L分為平凡序列、非平凡序列以及異常序列，基于平凡序列建立初始模型M0，然后分析低頻序列中的有效序列，繼續(xù)完善模型.通過計算擬合度來判斷某序列是否有效，低于設(shè)定的閾值，將視為噪聲序列，反之即為有效.當(dāng)找到所有的低頻有效序列后，如何去修改并完善模型就是需要考慮的問題.該文需要借助有效的非平凡子序列和塊結(jié)構(gòu)完善目標(biāo)模型，再從模型的行為和結(jié)構(gòu)的精確度、查全率指標(biāo)上進(jìn)行檢驗，若滿足所設(shè)的閾值則保留，否則重新配置，若該隱變遷對模型還是沒有改善，則視為冗余刪除.算法2給出了基于塊結(jié)構(gòu)的隱變遷挖掘方法.

算法2 基于行為輪廓的隱變遷挖掘方法

BEGIN(算法開始)

輸入:算法1初始模型M0及有效的非平凡子序列

輸出:含有隱變遷的Petri網(wǎng)目標(biāo)模型

步驟1 分析初始模型M0中各變遷之間的行為輪廓關(guān)系.

步驟2 依據(jù)定義3利用塊結(jié)構(gòu)對初始模型M0進(jìn)行層次分解，依次得到模塊m0,m1,…,mn.

步驟3 將算法1得到的有效非平凡子序列與模型的各模塊進(jìn)行對齊，找出可疑位置 ，對模塊進(jìn)行分析并添加可疑變遷.

步驟4 將步驟3構(gòu)建的子模塊融合到初始模型中，添加適當(dāng)流弧，因為算法1已經(jīng)對非平凡子序列的擬合度進(jìn)行了計算,因此當(dāng)前需要計算模型精確度和查全率.

步驟5 根據(jù)步驟4得到目標(biāo)模型M1.根據(jù)定義7, 計算目標(biāo)模型M1的行為精確度BP(L,Cr,Cm)和行為查全率BR(L,Cr,Cm),若BP≥δ& &BR≥δ，則挖掘到的模型在行為上是符合要求的，若BP<δ‖BR<δ，則模型不符合要求,需要進(jìn)行過濾操作.

步驟6 步驟5完成后,依據(jù)定義8,算模型的結(jié)構(gòu)精確度SP(Nr,Nm)和結(jié)構(gòu)查全率SR(Nr,Nm) ,若SP≥δ& &SR≥δ,則所挖掘到的模型在結(jié)構(gòu)上符合要求,否則不符合結(jié)構(gòu)要求,將其過濾掉.

步驟7 經(jīng)步驟6，所保留的變遷為最終滿足要求的變遷-隱變遷，模型為含有隱變遷的最終模型.最后輸出優(yōu)化的含有隱變遷Petri網(wǎng)模型.

END(算法結(jié)束)

3 案例分析

為了驗證算法的可行性，借助銀行保險索賠流程實例, 來挖掘出保險索賠Petri網(wǎng)流程模型中的隱變遷活動.記錄的執(zhí)行日志分別用下列大寫字母表示：A：開始申請索賠；B：申請低額索賠；C：申請高額索賠；D：政策審查；E：低額索賠成功；F：高額索賠成功；G：專家審核；H：檢查事宜；I：結(jié)束索賠.具體事件日志見表1.

對表1的事件日志集進(jìn)行初步分析，可以判斷日志集發(fā)生次數(shù)極低且無初始活動A,可以認(rèn)為是申請人異常操作造成的異常日志序列，直接去日志中刪去.

圖1 日志L′的序列編碼過濾圖

根據(jù)序列編碼過濾的結(jié)果,在PROM軟件中使用α*算法挖掘到初始模型M0,如圖2所示.

圖2 初始模型M0

圖3 初始模型M0的塊結(jié)構(gòu)化簡圖

低頻序列中不排除對模型有用的序列，即低頻有效序列.對于序列編碼過濾的異常序列L5,L6,L7,L9,L10，依次重放到初始模型M0中，根據(jù)定義6，計算其擬合度.先計算L5=< ACHDFI >,L6=,m1=r1=m2=r2=m3=r3=m4=r4=0；m5=r5=m6=r6=1；c1=p1=c4=p4=6；c5=p5=c6=p6=8；所以fL5=fL6=0.9935>λ;重復(fù)計算可求fL7=0.9937;fL9=0.3354;fL10=0.2683.對各日志序列的擬合度分析，L5,L6,L7的擬合度極高，可考慮進(jìn)行下一步操作，試著通過算法二挖掘模型的隱變遷，L9,L10對模型的擬合度較低，小于設(shè)定的閾值，視為噪聲序列.

根據(jù)定義3利用塊結(jié)構(gòu)對初始模型M0抽象化簡，例如：活動A作為一個單獨(dú)的順序塊，然后考慮活動B和C.BC之間的行為輪廓關(guān)系為B+C，符合選擇快Chb的定義，所以將其化簡為一個選擇塊.依次分析其它活動，得到結(jié)果如圖3所示，其中A、I、G和H為順序塊，B與C、E與F為選擇塊.D與G、H為并發(fā)塊.

a.子模塊1

b．子模塊2圖4 含有隱變遷的子模塊

最后將子模塊1和2合并到初始模型M0中,并對初始模型進(jìn)行補(bǔ)充和完善，最終得到圖5所示的含有隱變遷的目標(biāo)模型 .在完善后的目標(biāo)模型M1中,分析所挖掘到的隱變遷J和K,可以知道變遷所表示的意義分別是：當(dāng)申請者為SVIP時，可直接跳過專家審核G，進(jìn)入政策審查；當(dāng)申請者在申請索賠過程中可能由于材料不足導(dǎo)致政策審查H失敗時，應(yīng)當(dāng)允許返回開始審查C階段，補(bǔ)充材料繼續(xù)索賠.實踐證明通過完善模型可以讓顧客的利益得到保障，提高系統(tǒng)模型的運(yùn)行效率.

圖5 含有隱變遷的目標(biāo)模型M1

根據(jù)定義7、8提出的概念以及算法2中的步驟6,計算初始模型M0和目標(biāo)模型M1的行為精確度、查全率和結(jié)構(gòu)精確度、查全率(該文中的精確度δ取值為0.85).

通過計算得出BP(L,Cr,Cm)=0.9112>0.85&&BR(L,Cr,Cm)=1>0.85, 說明在行為精確度和查全率上所構(gòu)建的目標(biāo)模型M1都比初始模型M0好，再通過算法2中的步驟7對初始模型M0和目標(biāo)模型M1的結(jié)構(gòu)精確度和結(jié)構(gòu)查全率進(jìn)行比較.

通過計算得出SP(Nr,Nm)=0.85 &&SR(Nr,Nm)=1>0.85, 可知目標(biāo)模型M1在結(jié)構(gòu)精確度和結(jié)構(gòu)查全率上都比初始模型M0好, 因此含有隱變遷J和K的模型M1即為所得到的最終目標(biāo)模型.

通過算法1、算法2挖掘的隱變遷使所構(gòu)建模型更加完善、穩(wěn)定，模型效率也得到了提高，而且不管是行為精確度、查全率還是結(jié)構(gòu)精確度、查全率，目標(biāo)模型M1都得到了提升.所以含有隱變遷的目標(biāo)模型M1更符合時間日志的要求.

4 結(jié)束語

該文在現(xiàn)有研究的基礎(chǔ)上, 提出基于塊結(jié)構(gòu)從事件日志中挖掘隱變遷的方法.首先利用序列編碼過濾將事件日志中分為序列平凡序列和非平凡序列，對平凡序列利用α+算法挖掘出初始模型，再利用塊結(jié)構(gòu)進(jìn)行層次分解.通過擬合度刪除不符合業(yè)務(wù)流程的事件日志，保留余下有效的低頻日志，然后通過這些有效的非平凡子序列對模型進(jìn)行進(jìn)一步的補(bǔ)充和優(yōu)化，構(gòu)建含有隱變遷的子模塊，最后將子模塊融合到初始模型中并完善.通過行為精確度和結(jié)構(gòu)精確度指標(biāo)，發(fā)現(xiàn)構(gòu)建的模型在優(yōu)化指標(biāo)上有很大的提高，最后結(jié)合實例驗證了該方法的可行性.

基于塊結(jié)構(gòu)對隱變遷挖掘時，并沒有將模型的復(fù)雜性考慮在內(nèi), 這是因為在復(fù)雜模型的系統(tǒng)中，設(shè)計一個合理的塊結(jié)構(gòu)對模型進(jìn)行層次分解還是比較困難的，復(fù)雜模型中子模塊的融合也仍需進(jìn)一步研究.在未來的研究工作中, 需要對復(fù)雜流程模型進(jìn)行挖掘，也可配置其它異常變遷，如：阻塞變遷，使過程挖掘技術(shù)能更加完善.