基于不完備日志的塊狀并發(fā)過(guò)程挖掘

杜海森,杜玉越

(山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院,山東 青島 266590)

0 概述

過(guò)程挖掘即從事件日志中提取有價(jià)值的過(guò)程相關(guān)信息,其出發(fā)點(diǎn)是在過(guò)程模型與從事件日志中捕捉到的“現(xiàn)實(shí)”之間建立有效關(guān)聯(lián)。過(guò)程挖掘主要有3種類型的應(yīng)用:使用不包括任何先驗(yàn)信息的事件日志生成模型,將一個(gè)已知的過(guò)程模型與它產(chǎn)生的事件日志相比較以檢測(cè)日志中的記錄與實(shí)際情況是否相符,利用實(shí)際過(guò)程產(chǎn)生的事件日志來(lái)擴(kuò)展或改進(jìn)一個(gè)已存在的過(guò)程[1-3]。

在過(guò)程挖掘中,完備性的概念很重要,它表示日志中含有的數(shù)據(jù)是否過(guò)少。完備性假設(shè)所有可能直接跟隨彼此的活動(dòng)在日志中的一些跡中直接相互跟隨,這導(dǎo)致傳統(tǒng)的基于跟隨關(guān)系的局部完備日志需要在日志中存在大量的跡。例如,針對(duì)存在10個(gè)并發(fā)執(zhí)行活動(dòng)的過(guò)程模型,α算法[1]需要90次不同的觀察。

挖掘不完備日志時(shí),由于日志中跡的數(shù)量過(guò)少,導(dǎo)致活動(dòng)間的關(guān)系不能被正確表示,而隱含的活動(dòng)間關(guān)系不能被表示會(huì)導(dǎo)致挖掘結(jié)果不正確。通過(guò)引入間接關(guān)系的表示,可以從不完備的日志中獲得完備的并發(fā)關(guān)系,該過(guò)程通過(guò)分層可以發(fā)現(xiàn)潛在的因果跟隨關(guān)系并得到相應(yīng)的過(guò)程模型。

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

1 相關(guān)工作

過(guò)程挖掘領(lǐng)域已經(jīng)出現(xiàn)了很多挖掘算法。α算法是較基本的過(guò)程發(fā)現(xiàn)算法,針對(duì)α算法的缺陷進(jìn)行的改進(jìn)算法也相繼被提出,例如α+算法[4]和α++算法[5]。α+算法主要使α算法能處理短循環(huán),如長(zhǎng)度為2的短循環(huán)。α++算法則處理非自由選擇結(jié)構(gòu)。雖然α算法和其改進(jìn)算法可以發(fā)現(xiàn)具有完備日志的過(guò)程模型,但在處理不完備日志、罕見行為和一些特定結(jié)構(gòu)時(shí),存在很多限制和缺陷。因此,研究者又提出較多高級(jí)挖掘算法。

啟發(fā)式挖掘算法[6]作為一種高級(jí)挖掘算法,利用一種類似因果網(wǎng)表示法進(jìn)行描述,并在構(gòu)建過(guò)程模型時(shí)考慮事件和序列頻次,其設(shè)計(jì)思想是只將頻繁路徑納入模型中。因果網(wǎng)表示偏好和頻次使用,使得該算法比其他多數(shù)算法更加健壯。模糊挖掘[7]提供一種新的方式來(lái)發(fā)現(xiàn)模型,其利用一種路線圖表示可視化過(guò)程模型。遺傳算法[8]不同于其他挖掘算法,其不是以一種直接、確定方式提供過(guò)程模型,而是通過(guò)演化方法,使用一個(gè)迭代過(guò)程模仿自然演變,并通過(guò)精英主義進(jìn)行篩選?；趨^(qū)域挖掘算法[9]包含基于狀態(tài)區(qū)域過(guò)程發(fā)現(xiàn)和基于語(yǔ)言區(qū)域過(guò)程發(fā)現(xiàn)?；跔顟B(tài)區(qū)域過(guò)程發(fā)現(xiàn)可以從一個(gè)變遷系統(tǒng)中發(fā)現(xiàn)一個(gè)Petri網(wǎng)[10],基于語(yǔ)言區(qū)域過(guò)程發(fā)現(xiàn)可以從語(yǔ)言中發(fā)現(xiàn)一個(gè)Petri網(wǎng)。

上述算法在運(yùn)行過(guò)程中均對(duì)日志的完備性有較高要求。對(duì)不完備日志進(jìn)行挖掘,主要有2種方法:

1)歸納挖掘算法,即IM算法[11]。歸納挖掘處理不完備日志時(shí)將其看作一個(gè)優(yōu)化問(wèn)題。對(duì)活動(dòng)間的關(guān)系進(jìn)行統(tǒng)計(jì),并搜索這些關(guān)系的概率估計(jì),將其與設(shè)定閾值作比較,然后確定活動(dòng)間的關(guān)系。這種方法需要大量日志來(lái)統(tǒng)計(jì)分析,在生成的模型中存在精確度問(wèn)題。

2)針對(duì)塊狀并發(fā)結(jié)構(gòu)的α‖算法[12]。該算法可以挖掘因果完備日志,但并不能挖掘因果不完備日志,包括并發(fā)完備日志。

2 基本概念

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

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

塊狀工作流網(wǎng)[11]是一個(gè)分層的工作流網(wǎng),可遞歸地分為工作流網(wǎng)。在塊狀并發(fā)過(guò)程模型中僅含有并發(fā)結(jié)構(gòu)和順序結(jié)構(gòu)。

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

定義1(基于日志的次序關(guān)系) 用L表示事件日志,a,b∈L為L(zhǎng)中任意2個(gè)活動(dòng)。

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

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

a→Lb當(dāng)且僅當(dāng)aLb并且不存在bLa也不存在bLa。

a?Lb當(dāng)且僅當(dāng)aLb并且不存在bLa也不存在bLa。

a#Lb當(dāng)且僅當(dāng)不存在aLb,不存在bLa,不存在aLb,也不存在bLa。

a‖Lb當(dāng)且僅當(dāng)aLb∧bLa,或aLb∧bLa,或aLb∧bLa,或bLa∧aLb。

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

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

定義4(α‖算法) α‖算法基于因果完備日志被提出,其可以挖掘因果完備日志得到塊狀并發(fā)過(guò)程模型。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網(wǎng)。

3 α‖+算法

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

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

在并發(fā)完備日志中,存在潛在的因果跟隨關(guān)系,因此不能發(fā)現(xiàn)活動(dòng)間所有的因果跟隨關(guān)系。為解決該問(wèn)題,針對(duì)并發(fā)完備日志,本文利用層次樹的相關(guān)屬性來(lái)發(fā)現(xiàn)活動(dòng)間潛在的關(guān)系。

定義7(層次樹) 層次樹是一種特殊的樹,每個(gè)父節(jié)點(diǎn)擁有至多一個(gè)子節(jié)點(diǎn),在層次樹的每一層中只有一個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)中含有多個(gè)活動(dòng)。在同一節(jié)點(diǎn)中,任意2個(gè)活動(dòng)都為并發(fā)關(guān)系。LTL={l1,l2,…,li,…,lm}為層次樹,則LTL具有如下性質(zhì):

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

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

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

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

層次樹根據(jù)已有足跡和日志中的跡構(gòu)造,依據(jù)活動(dòng)之間關(guān)系將跡中活動(dòng)按層次放入層次樹中。層次樹構(gòu)造算法描述如下。

算法1層次樹構(gòu)造算法

輸入足跡Footprint,跡Trace

輸出層次樹LayerTree

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

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進(jìn)行初始化;步驟3循環(huán)遍歷Trace中所有活動(dòng);步驟4判斷層次樹當(dāng)前層為空時(shí),則添加當(dāng)前活動(dòng);步驟5判斷層次樹當(dāng)前層為非空時(shí),將標(biāo)識(shí)置于最后;步驟6判斷當(dāng)前層中所有活動(dòng)與當(dāng)前活動(dòng)全部平行,層次樹向上取值;步驟7層次樹向下取值;步驟8判斷當(dāng)前層為空,將當(dāng)前層添加到層次樹;步驟9將當(dāng)前活動(dòng)添加到當(dāng)前層;步驟10將當(dāng)前活動(dòng)向后取值;步驟11返回構(gòu)造之后的層次樹。

算法1中存在2層循環(huán),算法的時(shí)間復(fù)雜度為O(n2)。本文利用層次樹的性質(zhì)和日志足跡發(fā)現(xiàn)潛在的因果跟隨關(guān)系。發(fā)現(xiàn)潛在因果跟隨關(guān)系的算法描述如下:

算法2發(fā)現(xiàn)潛在因果跟隨關(guān)系算法

輸入足跡Footprint,層次樹LayerTree

輸出潛在因果跟隨關(guān)系集合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利用層次樹和足跡發(fā)現(xiàn)潛在因果跟隨關(guān)系集合:步驟1初始化所有集合;步驟2遍歷所有因果跟隨關(guān)系;步驟3～步驟5尋找不在因果跟隨關(guān)系前集和后集的活動(dòng),并放入集合,但不包含第一個(gè)活動(dòng)和最后一個(gè)活動(dòng);步驟6～步驟13通過(guò)層次樹為缺少前集或后集的活動(dòng)發(fā)現(xiàn)前、后集;步驟7、步驟11分別表示當(dāng)前活動(dòng)所在層次樹的位置;步驟8、步驟12分別表示向下和向上遍歷層次樹;步驟14返回TP集合。

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

定義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)。

α‖+算法根據(jù)活動(dòng)在層次樹中的位置發(fā)現(xiàn)潛在的因果跟隨關(guān)系,在得到正確的因果跟隨關(guān)系集合后挖掘出正確的過(guò)程模型。

定理1對(duì)于塊狀并發(fā)過(guò)程模型的并發(fā)完備日志,α‖+算法可得到正確的過(guò)程模型。

α‖+算法通過(guò)發(fā)現(xiàn)潛在的因果跟隨關(guān)系集合Ts,擴(kuò)展了α‖算法中的因果跟隨關(guān)系集合,因此,可得到更準(zhǔn)確的Petri網(wǎng)。

證畢。

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 α‖+算法實(shí)驗(yàn)示例

本節(jié)通過(guò)一組日志展現(xiàn)α‖+算法的實(shí)現(xiàn)過(guò)程。算法的輸入為并發(fā)完備日志,輸出為Petri網(wǎng)。

日志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)}

根據(jù)日志L和足跡,構(gòu)造層次樹過(guò)程如下:

執(zhí)行步驟1、步驟2,LTL={{}}。

執(zhí)行步驟4、步驟10,LTL={{a}}。

執(zhí)行步驟6～步驟10,LTL={{a},{e}}。

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

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

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

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

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

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

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

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

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

通過(guò)層次樹LTL和足跡,Tp集合的構(gòu)造如下:

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)}

α‖+算法的執(zhí)行過(guò)程如下:

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)

以上描述了α‖+算法的執(zhí)行過(guò)程,最后輸出結(jié)果為Petri網(wǎng)。

4.2 實(shí)驗(yàn)數(shù)據(jù)分析

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

表1 實(shí)驗(yàn)日志信息

表1中的12組數(shù)據(jù)具有不同的規(guī)模,隨著編號(hào)的增加,日志中軌跡的條數(shù)也增加。表1中數(shù)據(jù)的生成過(guò)程如下:

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

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

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

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

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

4.3 實(shí)驗(yàn)結(jié)果分析

本節(jié)對(duì)比幾種不同算法的挖掘能力。α‖+算法在ProM中實(shí)現(xiàn),可在http://pan.baidu.com/s/1o8KC H8e網(wǎng)站下載源碼和實(shí)驗(yàn)數(shù)據(jù)。

在進(jìn)行合規(guī)性檢測(cè)(也稱為一致性檢測(cè)[14])時(shí),將事件日志中的事件與過(guò)程模型中的活動(dòng)關(guān)聯(lián),并且將兩者進(jìn)行對(duì)比,目標(biāo)是找到模型的行為并觀察行為之間的共性和差異。合規(guī)性檢測(cè)技術(shù)可以被用來(lái)度量過(guò)程發(fā)現(xiàn)算法的效率。本文利用ProM中Check Precision based on Align-ETConformance插件生成精確度,并比較過(guò)程模型與日志的精確度[15]。

4.3.1 α‖+算法和α‖算法對(duì)比

對(duì)于本文實(shí)驗(yàn)數(shù)據(jù),α‖+算法的挖掘結(jié)果如圖1所示。從圖1可以看出,Petri網(wǎng)不存在死鎖和懸點(diǎn),是合理的工作流網(wǎng)。在網(wǎng)中一共有16個(gè)庫(kù)所和11個(gè)變遷,其中,Start庫(kù)所表示開始庫(kù)所,End庫(kù)所表示結(jié)束庫(kù)所。

圖1 α‖+算法挖掘結(jié)果

對(duì)于本文實(shí)驗(yàn)數(shù)據(jù),α‖算法的挖掘結(jié)果如圖2所示。從圖2可以看出,Petri網(wǎng)中一共有15個(gè)庫(kù)所和11個(gè)變遷,變遷i缺少后繼庫(kù)所,使得挖掘結(jié)果中存在懸點(diǎn),即該P(yáng)etri網(wǎng)不是合理的工作流網(wǎng)。比較圖1和圖2可以看出,圖1的挖掘結(jié)果比圖2更準(zhǔn)確。

圖2 α‖算法挖掘結(jié)果

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

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

4.3.2 α‖+算法和IM算法對(duì)比

對(duì)于本文的實(shí)驗(yàn)數(shù)據(jù),α‖+算法和IM算法能得到相似的過(guò)程模型,IM算法挖掘結(jié)果如圖4所示。其中,加粗線表示無(wú)聲變遷。相比圖1,圖4存在多余的庫(kù)所和變遷,使得模型存在多余結(jié)構(gòu),最終會(huì)增加模型的復(fù)雜度,降低精確度。

圖4 IM算法挖掘結(jié)果

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

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

5 結(jié)束語(yǔ)

本文針對(duì)并發(fā)完備日志挖掘,提出一種α‖+算法,通過(guò)發(fā)現(xiàn)潛在因果跟隨關(guān)系挖掘得到合理工作流網(wǎng),實(shí)驗(yàn)結(jié)果驗(yàn)證了該算法的準(zhǔn)確性。但本文算法在實(shí)驗(yàn)數(shù)據(jù)選擇以及適應(yīng)范圍上仍存在局限性,導(dǎo)致算法應(yīng)用不夠廣泛。下一步考慮將實(shí)驗(yàn)從模擬數(shù)據(jù)擴(kuò)展到實(shí)際數(shù)據(jù),將算法應(yīng)用范圍從特殊結(jié)構(gòu)擴(kuò)展到一般結(jié)構(gòu),以提高本文算法的通用性。