邵叱風，方賢文，盛夢君

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

數(shù)據(jù)挖掘與過程挖掘之間既有區(qū)別又有共性。就目的而言，數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中提取或挖掘出有用信息[1]，而過程挖掘是從表示流程執(zhí)行工作流的數(shù)據(jù)中挖掘流程模型。故數(shù)據(jù)是數(shù)據(jù)挖掘以及過程挖掘的基礎(chǔ)。從存儲方式來看二者又是不同的，前者使用的數(shù)據(jù)常用數(shù)據(jù)庫、數(shù)據(jù)倉庫、萬維網(wǎng)或其他信息存儲庫[2]存儲信息，而后者使用的數(shù)據(jù)通常存儲在捕獲系統(tǒng)工作流的日志中。

在傳統(tǒng)的過程挖掘研究中使用的日志稱為事件日志，其用于從控制流角度記錄和觀察進程工作流。事件表示任務的執(zhí)行。不同的挖掘算法使用不同的事件日志，文獻[2]提出α算法，使用跡矩陣定義活動間的順序操作符，從基本事件日志中發(fā)現(xiàn)結(jié)構(gòu)化事件模型；文獻[3]提出β算法為每個事件標記一個類型；文獻[4]提出λ算法將后繼任務添加到事件中。以上方法提出了不同的日志處理方案，生成不同算法所需的日志形式。

過程挖掘形式化定義用于從事件日志的一組實際執(zhí)行中提取結(jié)構(gòu)化流程的方法。過程挖掘至少在兩個方面是有用的。首先，它可以被用作一個用來查明程序真實運作的工具；其次可用于增量分析，即將實際過程與一些預定義的過程進行比較?；?①多核和并行技術(shù)的發(fā)展導致數(shù)字世界的驚人增長[5]②隨著數(shù)字世界的發(fā)展和組織進程的緊密結(jié)合，使得記錄和分析更多的事件[6]成為可能，過程挖掘成為工作流技術(shù)的熱點之一。文獻[7]提出了遺傳挖掘算法，該算法提出一種有效的因果矩陣結(jié)構(gòu)來提高空間搜索的效率；文獻[8]使用Rule-induction過程挖掘技術(shù)，提出RIPPER算法產(chǎn)生活動間的規(guī)則；文獻[9]使用分治策略遞歸地構(gòu)建過程模型，直到所有的跡都被處理為止，該方法稱為歸納式挖掘算法；文獻[10]提出一種由α-算法產(chǎn)生的啟發(fā)式挖掘算法，該方法僅考慮了事件的順序；文獻[11]闡述了靈活啟發(fā)式挖掘算法，它是一個靈活的控制流挖掘算法，提出的兩個算法都能處理噪音和低頻行為。針對過程挖掘方法有時不能獲得完備事件日志的問題，文獻[12]提出一種從不完備日志中發(fā)現(xiàn)塊結(jié)構(gòu)過程模型的方法，該方法利用對完備性不敏感的概率行為關(guān)系，給出了一個適用性更強的過程發(fā)現(xiàn)算法；文獻[13]提出一種挖掘局部過程模型的方法，該方法通過生成過程樹并依據(jù)5種評估標準選擇局部過程模型，擴展生成新的過程樹，以此迭代直到完成任務。但以上挖掘方法多以基本事件日志作為輸入，且均不能挖掘出系統(tǒng)中的場景信息。

本文主要工作有：首先提出增強日志的相關(guān)定義，繼而提出基于增強日志的挖掘算法(Process Mining-Enhanced Log，PM-EL)，通過顏色Petri網(wǎng)的加入用以表達具有場景信息的挖掘結(jié)果；使用UML轉(zhuǎn)換結(jié)果模型說明其可擴展性；對比實驗展示PM-EL算法在結(jié)構(gòu)識別上的能力。以上工作就基于事件內(nèi)部屬性對模型做出優(yōu)化[14]的工作提供了可切入點。

本文第1節(jié)介紹準備知識；第2節(jié)提出增強日志的概念以及基于增強日志的過程挖掘方法；第3節(jié)通過仿真實驗驗證所提方法的可行性及可擴展性；最后總結(jié)全文并展望未來。

1 準備知識

在本節(jié)中，將給出一些定義以及基本概念，用以輔助解釋提出的方法。限于篇幅，有關(guān) Petri網(wǎng)的概念及結(jié)構(gòu)的定義在此不做贅述，具體內(nèi)容可以參考文獻[15]。

定義1[16](顏色petri網(wǎng))一個簡單的(帶有k種顏色的)顏色Petri網(wǎng)是一個五元組Σ=(S,T;F,W,M)其中(S,T;F)是一個網(wǎng)，W∶F→{0,1,2,…}k,M∶S→{0, 1, 2,…}k對t∈T，如果s∈·t→M(S)≥W(s,t)，那么變遷t在標識M有發(fā)生權(quán)(M[t>)，在標識M下發(fā)生變遷t,產(chǎn)生一個新的標識M′(M[t>M′)，

定義2[17](UML2.0序列圖)序列圖是常用的且偏向于捕獲對象間行為的圖。它通?？梢耘c正在開發(fā)的系統(tǒng)的邏輯視圖中的用例相關(guān)聯(lián)。高級序列圖(High-level Sequence Diagrams，HLSD)是一個序列圖，它引用一組基本序列圖(Basic Sequence Diagram，BSD)，并使用一組交互操作符組合它們。主要的操作符是:弱順序(SEQ)、選擇(ALT)、 循環(huán)(LOOP)和并行(PAR)。

在Petri網(wǎng)的許多現(xiàn)有變種中，CPN被用于以序列圖的形式表示的組合和集成場景。庫所表示BSD，變遷表示操作符，如ALT、LOOP、SEQ和PAR。顏色用于區(qū)分庫所。圖1顯示了HLSD如何映射到CPN。T3表示條件為C1的操作符LOOP。操作符PAR和SEQ也可以映射，如圖2所示。可見對于HLSD，可以相互轉(zhuǎn)換生成一個可表示主要的UML序列圖操作符的CPN。

圖1 序列圖將操作符LOOP和ALT映射到CPN

圖2 序列圖將操作符PAR和SEQ映射到CPN

2 基于增強日志的過程挖掘方法

過程挖掘起源于系統(tǒng)日志的使用，定義和統(tǒng)一系統(tǒng)日志是過程挖掘的關(guān)鍵步驟。過程挖掘1995年由J.E.Cook提出至今，技術(shù)方面取得了長足的發(fā)展，且取得了諸多較完善的研究成果，但多以行為間控制流結(jié)構(gòu)挖掘過程模型；不同類型的事件日志(其中可能包含略微不同的信息)被不同的挖掘算法所使用，但大多數(shù)僅從控制流角度記錄和觀察工作流。

2.1 增強日志

在軟件系統(tǒng)運行時會產(chǎn)生大量的日志，常用來作為挖掘算法輸入的事件日志往往只記錄了執(zhí)行的事件。在此對文獻[18]中的日志數(shù)據(jù)格式進行擴展，針對事件執(zhí)行信息中一些可利用的屬性，提出增強日志的概念。

定義3(增強日志)若Traces是任務集,且滿足如下兩個條件，則稱ω∈Traces*是一條事件軌跡,W?Traces*為一個增強日志。

(1)Trace是一個四元組Trace= (線程號；發(fā)送方，消息，接收方),其中:發(fā)送方是調(diào)用對象，形如threadNumber: package:class:object，消息是接收方對象的調(diào)用方法，形如mathodName ( param1, param2,…);接收方是被調(diào)用對象，形如package:class:object。

(2)方法調(diào)用之間的等價性:方法調(diào)用如A1=(sender1;message1;receiver1)和A2 =(sender2;message2;receiver2)是等價調(diào)用，當且僅當：兩個對象隸屬同一實體類(可創(chuàng)建相同屬性值對象)，并在同一線程中以相同的參數(shù)值創(chuàng)建，那么等價。信息對象message1與message2涉及相同的方法且具有相同的簽名。

其中有4個函數(shù)操作TLineNumb(Trace)=線程號，TSend(Trace)=發(fā)送方，TMsg(Trace)=消息，TReceive(Trace)=接收方。其中的線程號可用來分析事件執(zhí)行的內(nèi)部聯(lián)系，其他三個屬性可用來生成場景化信息。

2.2 過程挖掘算法PM-EL

現(xiàn)有的過程挖掘算法從事件日志中挖掘任務之間的因果依賴關(guān)系和并行關(guān)系，發(fā)現(xiàn)過程模型中所有庫所的前后任務，然后重建整個過程模型。文章在此提出了一種新的算法PM-EL。在這一部分，我們首先介紹了算法的定義和數(shù)據(jù)結(jié)構(gòu)。然后詳細介紹了該算法的偽代碼及運行過程。

在增強日志中，因果依賴、并發(fā)及選擇關(guān)系定義如下。

定義4(因果依賴)：設(shè)Traces={t1,t2,…,tn}是WF-netPN= (P,T,F)的變遷集.?a,b∈T，變遷之間的因果關(guān)系記為′→w′,a→wb,當且僅當:

(1)TLineNumb(a)=TLineNumb(b),

(2)TReceive(a)=TSend(b)。

定義5(并發(fā)關(guān)系)：設(shè)Traces={t1,t2,…,tn}是WF-netPN= (P,T,F)的變遷集.?a,b∈T，變遷之間并發(fā)關(guān)系記為‘||w’,a||wb當且僅當： ?c∈Traces

(1)(c→a,c→b)∨(a→c,b→c)

(2)TLineNumb(a)≠TLineNumb(b),

(3)(TSend(a)=TSend(b)=TReceive(c))∨

(TReceive(a)=TReceive(b)=TSend(c))。

定義6(選擇關(guān)系)：設(shè)Traces = {t1,t2,…,tn}是WF-netPN= (P,T,F)的變遷集. ?a,b∈T，變遷之間選擇關(guān)系記為‘+’,a+b當且僅當：?c∈Traces

(1)(c→a,c→b)∨(a→c,b→c)

(2)TLineNumb(a)=TLineNumb(b),

(3)(TSend(a)=TSend(b)=TReceive(c))∨

(TReceive(a)=TReceive(b)=TSend(c))。

對于相同用例(場景)的CPN被迭代合并,以獲得用例的集CPNs，其顏色用于區(qū)分不同輸入場景。算法PM-EL描述了這一步操作。它可以輸入多個執(zhí)行序列,并且增量的生成一個可表示系統(tǒng)行為的CPNs。首先，算法逐行掃描執(zhí)行序列，如果是新執(zhí)行序列，則分析每一個執(zhí)行跡，創(chuàng)建一個新庫所。其中表示執(zhí)行跡的所有庫所都具有相同的顏色，這些顏色幫助我們區(qū)分場景，變遷表示場景的執(zhí)行。算法還可以創(chuàng)建變遷，它通過分析前面的執(zhí)行跡和當前的執(zhí)行跡，為每個庫所關(guān)聯(lián)相應的變遷(UML操作符)。該算法主要通過執(zhí)行跡內(nèi)部屬性來進行結(jié)構(gòu)化模型的提取。如用線程的ID來區(qū)分線程，如果這些執(zhí)行跡屬于同一線程,則可以通過在不同的序列中對以前的跡和當前的跡進行簡單的比較，然后識別操作符”SEQ”和”ALT”。通過分析線程號信息識別主線程及其子線程來檢測操作符”PAR”。如果執(zhí)行跡已經(jīng)存在并且屬于相同的執(zhí)行序列(相同的場景)，那么與當前線對應的變遷將被標記為臨時循環(huán)。如果一個變遷已經(jīng)被標記為一個臨時循環(huán)，就會更改變遷的關(guān)聯(lián)操作符為“LOOP”。PM-EL算法如下所示。

算法PM-EL

1.Data:Trace trace set；

2.Result：CPN cpn；

3.Place NewPlace；

4.Color New_Color;

5.CPN New_CPN；

6.For each trace T in trace set New_Color=createNewCPNColor();//為每一條執(zhí)行序列創(chuàng)建一個CPN顏色

7.For each activity a in T New_Place =creatPlace WithColor(a,New Color);

8.If(isCPNImpty())/若是CPN為空，直接添加庫所到CPN中

9.Add_Place_To_CPN( New Place);

10.else If(is Not New(a))// New Placea不是新的

11.If(is ln Same Trace(a))/已經(jīng)存在并且屬于相同的執(zhí)行序列即相同的場景

12.If(is Loop Marked( New CPN))

13.change_pervious_Transition(LOOP,New_CPN)；//修改變遷關(guān)聯(lián)‘LOOP’

14.else

15.mark pervious_Transition(LOOP,New CPN)；

16.EndIf

17.else

18.If(is The Same thread())//屬于在同一線程中

19.If(previous place have Transition( New CPV))//庫所前已有變遷

20.Change_Transition_To_CPN('ALT,New CPN)；//修改變遷類型為’ALT’

21.Add_Place_To_CPN( New Place,New CPN);

22.else Add_Place_To_CPN( New Place,New CPN);

23.Add_Transition_To_CPN('SEQ,New_CPN)；

24.End If

25.else

26.If(is previous Main ThreadID())/如果前一個線程ID為主線程

27.Add Transition To CPN('PAR,New CPN);

28.Add Place To CPN( New Place,New CPN);//加入前置變遷‘par'

29.else

30.Add Place To CPN( New Place,New CPN);

31.End If

32.End If

33.End If

34.End If

35.End Foreach

36.End Foreach

37.return New CPN

3 仿真實驗

在本節(jié)中，我們選擇了一個信息查看程序示例。使用應用程序?qū)Χ鄨鼍暗卿浺约靶畔⒉榭催M行操作并產(chǎn)生日志。信息查看程序檢測登錄類型如果是普通用戶登錄，使用系統(tǒng)的登錄線程(場景1)；員工登錄增加兩個部分，校驗工號以及工種，每部分都是由不同的線程來解決(場景2)；管理員賬號登錄，需要對登錄IP地址進行檢測(場景3)；普通用戶登陸后查看信息(場景4)；員工登錄后查看信息(場景5)；管理員登陸后查看信息并對信息進行過濾(場景6)。不同用戶登陸后查看信息是不同的。經(jīng)過以上操作獲得系統(tǒng)日志文件，這個文件包含系統(tǒng)當前運行時被檢測類的對象的所有創(chuàng)建和銷毀事件。對象請求的方法調(diào)用和返回事件也同時被記錄。依據(jù)執(zhí)行的父ID對日志進行聚類并記錄執(zhí)行次數(shù)，表1中數(shù)據(jù)字典對日志中的方法名及對象名進行相應替換，生成的最終增強日志如表2所示。

表1 事件坐標對應方法或?qū)ο?/p>

表2 增強日志詳情

文章在此利用Java編程實現(xiàn)了算法，其算法復雜度為O(m*n),圖形化界面如圖3所示，功能包括txt、rtf格式日志導入及算法結(jié)果保存，CPN結(jié)果以節(jié)點形式輸出。

圖3 算法的實現(xiàn)插件(PMEL)及挖掘結(jié)果展示

圖4形象的表達了算法的執(zhí)行步驟，且每條執(zhí)行序列均對應不同場景進行了遍歷迭代，故日志的每一條執(zhí)行序列與模型中的可達路徑都是一一對應的。

通過定義4、5、6的描述可知L3、L8、L4,L10、L12、L14為選擇關(guān)系，L6、L7為并發(fā)關(guān)系。在PM-EL算法結(jié)果中這些結(jié)構(gòu)均被識別且通過顏色區(qū)別不同場景；

通過CPNtool4.0.1對PM-EL所獲結(jié)構(gòu)模型進行仿真實驗(見圖5)，此CPN模型為可運行的。另外通過定義2及圖1、圖2表述的映射規(guī)則，可將此CPN模型轉(zhuǎn)化為UML模型，可更加直觀展示系統(tǒng)的運行，并驗證此方法結(jié)果的可擴展性。

圖4 過程挖掘算法PM-EL執(zhí)行示例圖

圖5 使用cpn tools 4.0.1對結(jié)果模型進行模擬可行

在此將日志導入Prom平臺中，并利用Alpha Miner及IDHM(interactive Data-aware Heuristic Miner)進行挖掘，以突出PM-EL算法在不完備日志基礎(chǔ)上對模型結(jié)構(gòu)的識別能力。

圖6 Alpha Miner挖掘結(jié)果

圖7 IDHM挖掘結(jié)果(Frequency為0.1，Dependency為0.9，Binding為0.1，Conditions為0.5)

三個算法實驗結(jié)果均有完整回路(即循環(huán)結(jié)構(gòu))，現(xiàn)就結(jié)果中選擇結(jié)構(gòu)和并發(fā)結(jié)構(gòu)數(shù)量進行對比，如表3所示。

表3 選擇、并發(fā)結(jié)構(gòu)數(shù)量對比

4 結(jié)論

文章通過分析數(shù)據(jù)挖掘與過程挖掘的異同，說明日志的重要性，然后提出增強日志的概念。將系統(tǒng)日志中除事件執(zhí)行外的一些可利用信息加入事件日志，基于增強日志提出過程挖掘算法PM-EL，依賴事件執(zhí)行的附加屬性識別結(jié)構(gòu)關(guān)系。依據(jù)定義4、5、6，結(jié)果過程模型也是符合源增強日志的。通過UML序列圖的轉(zhuǎn)換說明了算法結(jié)果的可擴展性。即從增強日志中挖掘出附帶場景信息的過程模型。

通過PM-EL算法所提取的過程模型可以為后續(xù)的模型修復及優(yōu)化工作提供支持。在此文章的研究基礎(chǔ)之上，未來可以利用增強日志提升模型修復精度，將模型優(yōu)化細分為多場景有針對性的優(yōu)化。