李 增,方賢文

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

0 引言

在廣泛的過程挖掘領(lǐng)域中，一個(gè)令人感興趣的領(lǐng)域是流程發(fā)現(xiàn)，它從事件日志中挖掘出流程模型,但在挖掘業(yè)務(wù)流程模型的過程中發(fā)現(xiàn)一種有趣的情況，一些活動(dòng)沒有在事件日志中發(fā)現(xiàn)，而在許多IT系統(tǒng)的業(yè)務(wù)流程模型中存在，這種活動(dòng)被稱為隱變遷.從事件日志中挖掘隱變遷可以還原更符合實(shí)際情況的流程模型，提高模型的運(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]也使用了對(duì)不常見情況(偏差或異常痕跡)的搜索，去除它們以降低模型的復(fù)雜性，同時(shí)不大幅降低適合度.文獻(xiàn)[8]提出了一種WoMine-i算法用于從過程模型中檢索不頻繁的行為模式，實(shí)驗(yàn)表明，可找到所有類型的模式，提取無法用最先進(jìn)的技術(shù)挖掘的信息.文獻(xiàn)[9]提出一種活動(dòng)過濾方法的新技術(shù)，比基于頻率的方法過濾異?；顒?dòng)更有效.文獻(xiàn)[10] 提出基于規(guī)則的合并方法和規(guī)則建議算法，用于流程日志的合并，并在Prom中實(shí)現(xiàn).文獻(xiàn)[11]根據(jù)區(qū)域理論尋找非平凡區(qū)域,建立了一個(gè)具有隱式變遷的分片子模型, 將子模型與初始模型相結(jié)合，挖掘出具有隱變遷的目標(biāo)模型.

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

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

1 基本概念

定義1[12]：(工作流Petri網(wǎng) WF-PN) 一個(gè)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)上的每一個(gè)節(jié)點(diǎn)都屬于i到o的一條路徑上, 即Petri網(wǎng)N是強(qiáng)連通的.

定義2[12](行為輪廓)設(shè)(N，M0)是一個(gè)網(wǎng)，初始標(biāo)識(shí)為M0.對(duì)任給的變遷對(duì)(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)為一個(gè)WF-PN，

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

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

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

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

(3)若N′為一個(gè)選擇塊，記為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*是一個(gè)執(zhí)行跡,L∈P(T*) 是一個(gè)事件日志.P(T*)是T*的冪集,L?T*.

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

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

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

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

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

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

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

BEGIN(算法開始)

輸入:事件日志序列L,合理的截?cái)嘞禂?shù)cc，閾值tf

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

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

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

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

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

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

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

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

計(jì)算各序列的擬合度.

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

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

END(算法結(jié)束)

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

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

BEGIN(算法開始)

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

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

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

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

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

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

步驟5 根據(jù)步驟4得到目標(biāo)模型M1.根據(jù)定義7, 計(jì)算目標(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 案例分析

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

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

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

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

圖2 初始模型M0

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

低頻序列中不排除對(duì)模型有用的序列，即低頻有效序列.對(duì)于序列編碼過濾的異常序列L5,L6,L7,L9,L10，依次重放到初始模型M0中，根據(jù)定義6，計(jì)算其擬合度.先計(jì)算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ù)計(jì)算可求fL7=0.9937;fL9=0.3354;fL10=0.2683.對(duì)各日志序列的擬合度分析，L5,L6,L7的擬合度極高，可考慮進(jìn)行下一步操作，試著通過算法二挖掘模型的隱變遷，L9,L10對(duì)模型的擬合度較低，小于設(shè)定的閾值，視為噪聲序列.

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

a.子模塊1

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

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

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

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

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

通過計(jì)算得出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更符合時(shí)間日志的要求.

4 結(jié)束語

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

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