基于不完備日志的塊狀并發過程挖掘

杜海森,杜玉越

(山東科技大學 計算機科學與工程學院,山東 青島 266590)

0 概述

過程挖掘即從事件日志中提取有價值的過程相關信息,其出發點是在過程模型與從事件日志中捕捉到的“現實”之間建立有效關聯。過程挖掘主要有3種類型的應用:使用不包括任何先驗信息的事件日志生成模型,將一個已知的過程模型與它產生的事件日志相比較以檢測日志中的記錄與實際情況是否相符,利用實際過程產生的事件日志來擴展或改進一個已存在的過程[1-3]。

在過程挖掘中,完備性的概念很重要,它表示日志中含有的數據是否過少。完備性假設所有可能直接跟隨彼此的活動在日志中的一些跡中直接相互跟隨,這導致傳統的基于跟隨關系的局部完備日志需要在日志中存在大量的跡。例如,針對存在10個并發執行活動的過程模型,α算法[1]需要90次不同的觀察。

挖掘不完備日志時,由于日志中跡的數量過少,導致活動間的關系不能被正確表示,而隱含的活動間關系不能被表示會導致挖掘結果不正確。通過引入間接關系的表示,可以從不完備的日志中獲得完備的并發關系,該過程通過分層可以發現潛在的因果跟隨關系并得到相應的過程模型。

本文挖掘含有較少跡的日志,這些跡可能不完整,但是足夠有效,利用這些跡可以發現潛在的因果跟隨關系。在此基礎上,提出一種塊狀并發過程挖掘算法α‖+,以得到具有代表性的并發過程模型。

1 相關工作

過程挖掘領域已經出現了很多挖掘算法。α算法是較基本的過程發現算法,針對α算法的缺陷進行的改進算法也相繼被提出,例如α+算法[4]和α++算法[5]。α+算法主要使α算法能處理短循環,如長度為2的短循環。α++算法則處理非自由選擇結構。雖然α算法和其改進算法可以發現具有完備日志的過程模型,但在處理不完備日志、罕見行為和一些特定結構時,存在很多限制和缺陷。因此,研究者又提出較多高級挖掘算法。

啟發式挖掘算法[6]作為一種高級挖掘算法,利用一種類似因果網表示法進行描述,并在構建過程模型時考慮事件和序列頻次,其設計思想是只將頻繁路徑納入模型中。因果網表示偏好和頻次使用,使得該算法比其他多數算法更加健壯。模糊挖掘[7]提供一種新的方式來發現模型,其利用一種路線圖表示可視化過程模型。遺傳算法[8]不同于其他挖掘算法,其不是以一種直接、確定方式提供過程模型,而是通過演化方法,使用一個迭代過程模仿自然演變,并通過精英主義進行篩選。基于區域挖掘算法[9]包含基于狀態區域過程發現和基于語言區域過程發現。基于狀態區域過程發現可以從一個變遷系統中發現一個Petri網[10],基于語言區域過程發現可以從語言中發現一個Petri網。

上述算法在運行過程中均對日志的完備性有較高要求。對不完備日志進行挖掘,主要有2種方法:

1)歸納挖掘算法,即IM算法[11]。歸納挖掘處理不完備日志時將其看作一個優化問題。對活動間的關系進行統計,并搜索這些關系的概率估計,將其與設定閾值作比較,然后確定活動間的關系。這種方法需要大量日志來統計分析,在生成的模型中存在精確度問題。

2)針對塊狀并發結構的α‖算法[12]。該算法可以挖掘因果完備日志,但并不能挖掘因果不完備日志,包括并發完備日志。

2 基本概念

Petri網是一個三元組,表示為N=(P,T;F)。其中,P是庫所的有限集合,T是變遷的有限集合,且P∩T=?,F?(P×T)∪(T×P)是有向弧的集合,也稱為流關系。

工作流網是Petri網的一個子類,可表示為WN=(P,T;F,i,o),其是一個以i為輸入庫所、o為輸出庫所的Petri網。工作流網的合理性必須滿足安全性、正確完成性、可完成性以及無死鎖[13]。

塊狀工作流網[11]是一個分層的工作流網,可遞歸地分為工作流網。在塊狀并發過程模型中僅含有并發結構和順序結構。

跡是活動的有序序列,例如,σ=表示一條跡,事件日志是跡的多集。例如,L=[3,2]表示一個日志。本文引用6種關系描述活動間關系,定義如下:

定義1(基于日志的次序關系) 用L表示事件日志,a,b∈L為L中任意2個活動。

aLb當且僅當σ=,i∈{1,2,…,n-1}使得σ∈L,ti=a并且ti+1=b。

aLb當且僅當σ=,i∈{1,2,…,n-1},j∈{i+2,i+3,…,n},使得σ∈L,ti=a并且tj=b,并且不存在aLb。

a→Lb當且僅當aLb并且不存在bLa也不存在bLa。

a?Lb當且僅當aLb并且不存在bLa也不存在bLa。

a#Lb當且僅當不存在aLb,不存在bLa,不存在aLb,也不存在bLa。

a‖Lb當且僅當aLb∧bLa,或aLb∧bLa,或aLb∧bLa,或bLa∧aLb。

定義3(因果完備日志) 因果完備日志指滿足基礎因果關系的日志。WN=(P,T;F,i,o)為合理工作流網,當Lc滿足以下條件時,日志Lc為WN的因果完備日志:

2)?t∈T,σ∈Lc使得t∈σ。

定義4(α‖算法) α‖算法基于因果完備日志被提出,其可以挖掘因果完備日志得到塊狀并發過程模型。L為事件日志,T為事件集合,α‖算法定義如下:

1)TL={t∈T|(σ∈L)t∈σ}

2)TI={t∈T|(σ∈L)t=first(σ)}

3)TO={t∈T|(σ∈L)t=last(σ)}

4)XL={(A,B)|A?TL∧A≠φ∧B?TL∧B≠φ∧(?a∈A)(?b∈B)(aLb)}

5)PL={p(A,B)|(A,B)∈XL}∪{iL,oL}

6)FL={(a,p(A,B))|(A,B)∈XL∧a∈A}∪{(p(A,B),b)|(A,B)∈XL∧b∈B}∪{(iL,t)|t∈TI}∪{(t,OL)|t∈TO}

7)α‖(L)=(PL,TL,FL)

α‖算法的輸入為因果完備日志,輸出為Petri網。

3 α‖+算法

根據前文所述,不完備日志是關系不完備日志。根據不完備定義,本節給出并發完備日志的定義,并提出一種挖掘并發完備日志的α‖+算法。并發完備日志是一種不完備日志,含有完備的并發關系和不完備的直接因果關系。

3)?t∈T,σ∈Lp使得t∈σ。

在并發完備日志中,存在潛在的因果跟隨關系,因此不能發現活動間所有的因果跟隨關系。為解決該問題,針對并發完備日志,本文利用層次樹的相關屬性來發現活動間潛在的關系。

定義7(層次樹) 層次樹是一種特殊的樹,每個父節點擁有至多一個子節點,在層次樹的每一層中只有一個節點,每個節點中含有多個活動。在同一節點中,任意2個活動都為并發關系。LTL={l1,l2,…,li,…,lm}為層次樹,則LTL具有如下性質:

1)|LTL|表示樹的深度,|LTL|=m。

2)li表示第i層所有活動,li={a1,a2,…,aj}。|li|表示第i層中的活動個數,|li|=j。li(k)表示第i層的第k個元素,k∈{1,2,…,|li|}。

3)每一層中的任意2個活動間為‖L關系,即?li(j),li(k)∈li,li(j)‖Lli(k),k≠j,k,j∈{1,2,…,|li|},i∈{1,2,…,|LTL|}。

日志L1={2,1},通過分析可得b‖L1c、b‖L1d和c‖L1d。則層次樹LTL1={{a},{b,c,d},{e}}。|LTL1|=3,l2={b,c,d},|l2|=3,l2(1)=b。

層次樹根據已有足跡和日志中的跡構造,依據活動之間關系將跡中活動按層次放入層次樹中。層次樹構造算法描述如下。

算法1層次樹構造算法

輸入足跡Footprint,跡Trace

輸出層次樹LayerTree

1.初始化LTL={},i表示當前的活動位置,j表示當前的層次樹位置。

2.if (LTL==null) {

i=0,j=0;

LTL.add(lj);}

3.while(i<|Trace|){

4.if(lj==null){

lj.add(Trace(i))}

5.else {

j=|LTL|-1;

6.while (Trace(i)‖Llj){

j--;}

7.j++;

8.if(lj==null){

LTL.add(lj)}

9.lj.add(Trace(i));}

10.i++;}

11.return LTL.

在算法1中:步驟1、步驟2進行初始化;步驟3循環遍歷Trace中所有活動;步驟4判斷層次樹當前層為空時,則添加當前活動;步驟5判斷層次樹當前層為非空時,將標識置于最后;步驟6判斷當前層中所有活動與當前活動全部平行,層次樹向上取值;步驟7層次樹向下取值;步驟8判斷當前層為空,將當前層添加到層次樹;步驟9將當前活動添加到當前層;步驟10將當前活動向后取值;步驟11返回構造之后的層次樹。

算法1中存在2層循環,算法的時間復雜度為O(n2)。本文利用層次樹的性質和日志足跡發現潛在的因果跟隨關系。發現潛在因果跟隨關系的算法描述如下:

算法2發現潛在因果跟隨關系算法

輸入足跡Footprint,層次樹LayerTree

輸出潛在因果跟隨關系集合TP

1.初始化ps={},fs={},nc={},nf={},Ts={}

2.for (each a→Lb in Fp){

ps.add(a);

fs.add(b);}

3.for (each active A){

4.if(!ps.contains(A)){

nc.add(A);}

5.if(!fs.contains(A)){

nf.add(A);}}

6.for (each active A in nc){

7.int pos = LTL.get(A);

8.for(;pos<|LTL|;pos++){

9.for (each active C in lpos){

if(A ?LC){

TP.add((A,C));

break;}}}}

10.for (each active A in nf){

11.int pos = LTL.get(A);

12.for(;pos>=0;pos--){

13.for (each active C in lpos){

if(C ?LA){

TP.add((C,A));

break;}}}}

14.return TP.

算法2利用層次樹和足跡發現潛在因果跟隨關系集合:步驟1初始化所有集合;步驟2遍歷所有因果跟隨關系;步驟3～步驟5尋找不在因果跟隨關系前集和后集的活動,并放入集合,但不包含第一個活動和最后一個活動;步驟6～步驟13通過層次樹為缺少前集或后集的活動發現前、后集;步驟7、步驟11分別表示當前活動所在層次樹的位置;步驟8、步驟12分別表示向下和向上遍歷層次樹;步驟14返回TP集合。

算法2中存在3層循環嵌套,其時間復雜度為O(n3)。α‖算法可以挖掘因果完備日志,但挖掘并發完備日志時存在缺陷。對于并發完備日志的挖掘,本文提出α‖+算法。算法定義如下:

定義8(α‖+算法)L為事件日志,T為事件集合。α‖+算法定義如下:

1)TL={t∈T|(σ∈L)t∈σ}。

2)TI={t∈T|(σ∈L)t=first(σ)}。

3)TO={t∈T|(σ∈L)t=last(σ)}。

4)XL={(A,B)|A?TL∧A≠φ∧B?TL∧B≠φ∧(?a∈A)(?b∈B)(aLb)}。

5)XL=XL∪TP。

6)PL={p(A,B)|(A,B)∈XL}∪{iL,oL}。

7)FL={(a,p(A,B))|(A,B)∈XL∧a∈A}∪{(p(A,B),b)|(A,B)∈XL∧b∈B}∪{(iL,t)|t∈TI}∪{(t,OL)|t∈TO}。

8)α‖+(L)=(PL,TL,FL)。

α‖+算法根據活動在層次樹中的位置發現潛在的因果跟隨關系,在得到正確的因果跟隨關系集合后挖掘出正確的過程模型。

定理1對于塊狀并發過程模型的并發完備日志,α‖+算法可得到正確的過程模型。

α‖+算法通過發現潛在的因果跟隨關系集合Ts,擴展了α‖算法中的因果跟隨關系集合,因此,可得到更準確的Petri網。

證畢。

α‖+算法中第5步的時間復雜度為O(n3),其余步驟為O(n1),因此,算法整體復雜度為O(n3)。

4 實驗結果與分析

4.1 α‖+算法實驗示例

本節通過一組日志展現α‖+算法的實現過程。算法的輸入為并發完備日志,輸出為Petri網。

日志L=[,]為輸入日志。日志L的足跡如下:

‖L={(b,d),(b,e),(b,f),(b,i),(c,b),(c,e),(c,f),(c,g),(c,i),(e,d),(f,d),(g,d),(g,b),(g,f),(h,b),(h,c),(h,d),(h,f),(h,g),(i,d)}

→L={(a,b),(a,e),(b,j),(c,d),(e,f),(e,h),(f,i),(h,i),(i,j),(j,k)}

?L={(a,c),(a,d),(a,f),(a,g),(a,h),(a,i),(a,j),(a,k),(b,k),(c,j),(c,k),(d,j),(d,k),(e,g),(e,i),(e,j),(e,k),(f,j),(f,k),(g,i),(g,j),(g,k),(h,j),(h,k),(i,k)}

#L={(a,a),(b,b),(c,c),(d,d),(e,e),(f,f),(g,g),(h,h),(i,i),(j,j),(k,k)}

根據日志L和足跡,構造層次樹過程如下:

執行步驟1、步驟2,LTL={{}}。

執行步驟4、步驟10,LTL={{a}}。

執行步驟6～步驟10,LTL={{a},{e}}。

執行步驟6～步驟10,LTL={{a},{e},{h}}。

執行步驟6、步驟7、步驟9、步驟10,LTL={{a},{e},{g,h}}。

執行步驟6、步驟7、步驟9、步驟10,LTL={{a},{e},{f,g,h}}。

執行步驟6～步驟10,LTL={{a},{e},{f,g,h},{i}}。

執行步驟6、步驟7、步驟9、步驟10,LTL={{a},{c,e},{f,g,h},{i}}。

執行步驟6、步驟7、步驟9、步驟10,LTL={{a},{c,e},{d,f,g,h},{i}}。

執行步驟6、步驟7、步驟9、步驟10,LTL={{a},{b,c,e},{d,f,g,h},{i}}。

執行步驟6～步驟10,LTL={{a},{b,c,e},{d,f,g,h},{i},{j}}。

執行步驟6～步驟10,LTL={{a},{b,c,e},{d,f,g,h},{i},{j},{k}}。

通過層次樹LTL和足跡,Tp集合的構造如下:

ps={a,b,c,e,f,h,i,j}

fs={b,d,e,f,h,i,j,k}

nc={c,g}

nf={d,g}

Tp={(g,i),(a,c),(d,j),(e,g)}

α‖+算法的執行過程如下:

TL={a,b,c,d,e,f,g,h,i,j,k}

TI={a}

TO={k}

XL={(a,b),(a,e),(b,j),(c,d),(e,f),(e,h),(f,i),(h,i),(i,j),(j,k)}

Tp={(g,i),(a,c),(d,j),(e,g)}

XL=XL∪Tp={(a,b),(a,c),(a,e),(b,j),(c,d),(d,j),(e,f),(e,g),(e,h),(f,i),(g,i),(h,i),(i,j),(j,k)}

PL={start,p(a,b),p(a,c),p(a,e),p(b,j),p(c,d),p(d,j),p(e,f),p(e,g),p(e,h),p(f,i),p(g,i),p(h,i),p(i,j),p(j,k),end}

FL={(start,a),(a,p(a,b)),(p(a,b),b),(a,p(a,c)),(p(a,c),c),(a,p(a,e)),(p(a,e),e),(b,p(b,j)),(p(b,j),j),(c,p(c,d)),(p(c,d),d),(d,p(d,j)),(p(d,j),j),(e,p(e,f)),(p(e,f),f),(e,p(e,g)),(p(e,g),g),(e,p(e,h)),(p(e,h),h),(f,p(f,i)),(p(f,i),i),(g,p(g,i)),(p(g,i),i),(h,p(h,i)),(p(h,i),i),(i,p(i,j)),(p(i,j),j),(j,p(j,k)),(p(j,k),k),(k,end)}

α‖+(L)=(PL,TL,FL)

以上描述了α‖+算法的執行過程,最后輸出結果為Petri網。

4.2 實驗數據分析

本文模擬數據總共分為12組不同日志,日志信息如表1所示。其中,日志規模代表日志中跡的多少。日志都為并發完備日志,以保證算法輸入的正確性。

表1 實驗日志信息

表1中的12組數據具有不同的規模,隨著編號的增加,日志中軌跡的條數也增加。表1中數據的生成過程如下:

1)利用ProM中Perform a simple simulation of a (stochastic) Petri net插件,輸入塊狀并發結構Petri網,控制日志中跡的條數參數,生成軌跡條數不同的完備日志Lc,Lc的格式為XES文件,然后將Lc導出并保存。

2)利用ProM中提供的XES文件讀寫功能,編寫軌跡刪除插件ChangeLog。

3)利用ChangeLog插件對Lc刪除指定(例如刪除含有fLi、gLi或者cLd)的軌跡,生成新的日志Lc。

4)檢測新生成的Lc是否為并發完備日志,將非并發完備日志刪除。

5)選擇不同規模的并發完備日志用Lp命名(L1～L12)并保存導出。

4.3 實驗結果分析

本節對比幾種不同算法的挖掘能力。α‖+算法在ProM中實現,可在http://pan.baidu.com/s/1o8KC H8e網站下載源碼和實驗數據。

在進行合規性檢測(也稱為一致性檢測[14])時,將事件日志中的事件與過程模型中的活動關聯,并且將兩者進行對比,目標是找到模型的行為并觀察行為之間的共性和差異。合規性檢測技術可以被用來度量過程發現算法的效率。本文利用ProM中Check Precision based on Align-ETConformance插件生成精確度,并比較過程模型與日志的精確度[15]。

4.3.1 α‖+算法和α‖算法對比

對于本文實驗數據,α‖+算法的挖掘結果如圖1所示。從圖1可以看出,Petri網不存在死鎖和懸點,是合理的工作流網。在網中一共有16個庫所和11個變遷,其中,Start庫所表示開始庫所,End庫所表示結束庫所。

圖1 α‖+算法挖掘結果

對于本文實驗數據,α‖算法的挖掘結果如圖2所示。從圖2可以看出,Petri網中一共有15個庫所和11個變遷,變遷i缺少后繼庫所,使得挖掘結果中存在懸點,即該Petri網不是合理的工作流網。比較圖1和圖2可以看出,圖1的挖掘結果比圖2更準確。

圖2 α‖算法挖掘結果

2種算法挖掘結果的精確度比較如圖3所示,其中,精確度取值為0～1。從圖3可以看出,隨著日志規模的增大,α‖+算法和α‖算法的精確度都變大,且α‖+算法的精確度一直比α‖算法高。

圖3 α‖+算法和α‖算法精確度比較

4.3.2 α‖+算法和IM算法對比

對于本文的實驗數據,α‖+算法和IM算法能得到相似的過程模型,IM算法挖掘結果如圖4所示。其中,加粗線表示無聲變遷。相比圖1,圖4存在多余的庫所和變遷,使得模型存在多余結構,最終會增加模型的復雜度,降低精確度。

圖4 IM算法挖掘結果

圖5所示為2種算法挖掘結果的精確度比較。從圖5可以看出,隨著日志規模的增大,α‖+算法和IM算法的精確度都變大,但α‖+算法的精確度一直比IM算法高,且精確度差值呈現增加趨勢。

圖5 α‖+算法和IM算法精確度比較

5 結束語

本文針對并發完備日志挖掘,提出一種α‖+算法,通過發現潛在因果跟隨關系挖掘得到合理工作流網,實驗結果驗證了該算法的準確性。但本文算法在實驗數據選擇以及適應范圍上仍存在局限性,導致算法應用不夠廣泛。下一步考慮將實驗從模擬數據擴展到實際數據,將算法應用范圍從特殊結構擴展到一般結構,以提高本文算法的通用性。