過(guò)程挖掘中增強(qiáng)活動(dòng)依賴(lài)的最優(yōu)對(duì)齊算法

邵叱風(fēng) 方賢文 楊慧慧

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

0 引 言

BPM(Business Process Management)業(yè)務(wù)流程管理[1-2]伴隨著大數(shù)據(jù)時(shí)代的到來(lái)得到了進(jìn)一步發(fā)展。從業(yè)務(wù)流程出發(fā),基于信息及管理技術(shù)提供統(tǒng)一的建模、運(yùn)行和監(jiān)控環(huán)境。經(jīng)過(guò)業(yè)務(wù)流程的不斷執(zhí)行,信息系統(tǒng)將生成大量的事件日志文件[3],其記錄了與流程密切相關(guān)可用于進(jìn)一步業(yè)務(wù)流程分析的重要數(shù)據(jù),因此,流程挖掘?qū)μ岣邩I(yè)務(wù)流程管理水平而言受到人們?cè)絹?lái)越多的重視[4-7]。在企業(yè)管理中,完整的信息管理系統(tǒng)要求流程模型和事件日志之間具有很高的重構(gòu)性,即希望模型的過(guò)程行為和性質(zhì)可以從完整描述的日志中表現(xiàn)出來(lái)[8]。然而,通過(guò)比較模型和事件日志可知,信息系統(tǒng)中記錄的事件日志與基于業(yè)務(wù)流程構(gòu)建的模型之間總是存在一些偏差,因而使得日志中的部分行為無(wú)法在模型上重放[9-10]。針對(duì)上述問(wèn)題,對(duì)過(guò)程模型與記錄系統(tǒng)實(shí)際運(yùn)作的事件日志之間進(jìn)行一致性校驗(yàn)變得至關(guān)重要[11]。

近年來(lái),校驗(yàn)給定模型和事件日志之間一致性的多種方法已被提出[4-5,12-19],其中文獻(xiàn)[16]所做的對(duì)齊方法是最先進(jìn)的方法之一。文獻(xiàn)[17]將日志與模型進(jìn)行對(duì)齊,提出一個(gè)復(fù)雜的方法用以指出偏差發(fā)生的位置及偏差程度;文獻(xiàn)[18]分析那些最優(yōu)對(duì)齊包含的移動(dòng)集合完全相同,只是移動(dòng)出現(xiàn)順序不同,繼而提出相似最優(yōu)對(duì)齊的概念;一般而言能夠檢測(cè)到最小偏差成本的一組對(duì)齊被認(rèn)為是事件日志與業(yè)務(wù)流程之間的最優(yōu)對(duì)齊[19]。使用現(xiàn)有方法可以得到事件日志中的跡與Petri網(wǎng)的發(fā)生序列之間的所有最優(yōu)對(duì)齊。對(duì)齊處理與偏差檢測(cè)作為很多研究工作的重要組成部分,因而在過(guò)程挖掘領(lǐng)域中越來(lái)越重要,例如,模型修復(fù)[20-22]和遺傳優(yōu)化過(guò)程挖掘[23]等。

現(xiàn)有的最優(yōu)對(duì)齊方法在計(jì)算對(duì)齊成本時(shí)大多僅考慮對(duì)齊中的移動(dòng)個(gè)數(shù)(包括相似性最優(yōu)對(duì)齊),缺乏對(duì)單一活動(dòng)成本即活動(dòng)依賴(lài)的考慮。在此提出一種基于依賴(lài)增強(qiáng)的最優(yōu)對(duì)齊計(jì)算方法,目的提高計(jì)算序列對(duì)齊的效率、最優(yōu)對(duì)齊對(duì)活動(dòng)的依賴(lài)性。基于自定義得分矩陣的配置,使用動(dòng)態(tài)規(guī)劃的方法計(jì)算日志中所有序列與模型可觀測(cè)跡的對(duì)齊;分析對(duì)齊集合中移動(dòng)的信息,通過(guò)加權(quán)的方式計(jì)算模型與日志上合法移動(dòng)的總成本;最后利用分組排序得到日志與模型的最優(yōu)對(duì)齊序列及對(duì)齊成本。

1 基本概念

本節(jié)內(nèi)容列出了文章所需的部分基本概念,用以輔助文章的閱讀。Petri網(wǎng)相關(guān)定義參考文獻(xiàn)[24]。

1)Move(x,y)是一個(gè)日志跡上的移動(dòng),當(dāng)且僅當(dāng)x∈且y=→。

2)Move(x,y)是一個(gè)系統(tǒng)上的移動(dòng),當(dāng)且僅當(dāng)x=→且y∈T。

3)Move(x,y)是一個(gè)同步移動(dòng),當(dāng)且僅當(dāng)x∈,y∈T且λ(y)=x。

定義2(對(duì)齊) 跡υ∈*和網(wǎng)系統(tǒng)=(N,Mini,Mfin),其中=(P,T,F,λ)上的執(zhí)行σ之間的對(duì)齊是擁有S上合法移動(dòng)的有限序列其中π1(γ)|=υ且π2(γ)|T=σ。

例如,γ1和γ2展示了指定兩個(gè)域的兩個(gè)序列的移動(dòng)分別為<(a,t1),(c,t4),(b,t2),(d,t5),(→,t7),(f,t8),(g,t9),(→,t11)>和<(a,t1),(c,t4),(b,t2),(d,t5),(→,t5),(→,t4),(→,t3),(→,t5),(→,t7),(f,t8),(g,t9),(→,t11)>,并且π1(γ1)|=,π2(γ1)|T=,π1(γ2)|=,π2(γ2)|T=,同一個(gè)跡之間的兩個(gè)對(duì)齊顯示了觀察到的跡和建模的流程實(shí)例之間的不同偏差,比較對(duì)齊的常用方法是根據(jù)對(duì)齊包含的移動(dòng)對(duì)其進(jìn)行量化。

定義3(對(duì)齊成本) 網(wǎng)系統(tǒng)S上的合法移動(dòng)成本可表示為一個(gè)函數(shù)c:MS→N0,將成本分配到S上的合法移動(dòng)。故跡υ∈*和網(wǎng)系統(tǒng)=(N,Mini,Mfin),其中=(P,T,F,λ)上的執(zhí)行σ之間的對(duì)齊γ對(duì)應(yīng)成本依據(jù)合法移動(dòng)成本函數(shù)c,以及γ上所有的移動(dòng)成本總和定義為:

(1)

即日志跡υ與模型中可觀測(cè)跡的對(duì)齊成本最小的對(duì)齊為最優(yōu)對(duì)齊,可能有多個(gè)最優(yōu)對(duì)齊。比如兩個(gè)對(duì)齊均插入或跳過(guò)一個(gè)活動(dòng),為體現(xiàn)日志與網(wǎng)系統(tǒng)中變遷的重要程度,降低最優(yōu)對(duì)齊個(gè)數(shù)。下面給出定義5和定義6如下:

定義5(標(biāo)簽加權(quán)) 依據(jù)活動(dòng)不同重要性,考慮單一活動(dòng)成本,對(duì)對(duì)齊序列中的標(biāo)簽γi進(jìn)行加權(quán)處理,對(duì)于權(quán)函數(shù)w:

w(π1(γi)|)=w(π2(γi)|T)=w(γi),w(γi)∈N

在輸入過(guò)程中,輸入形式如下:

Weightactivity:(A1,w(A1),A2,w(A2),…,Ai,w(Ai)),A=(∪{τ})*

定義6(移動(dòng)加權(quán)) 依據(jù)偏差出現(xiàn)位置,考慮其對(duì)對(duì)齊成本的影響,在計(jì)算總的對(duì)齊成本時(shí)對(duì)于系統(tǒng)上的合法移動(dòng),跡上的合法移動(dòng)按類(lèi)別Weightskip、Weightinsert進(jìn)行加權(quán)處理。輸入形式如下:

Weightskip/Weightinsert:

(Costskip,W(Costskip),Costinsert,W(Costinsert))

Costtotal=Costskip×W(Costskip)+Costinsert×W(Costinsert)

(2)

則:

(3)

(4)

通過(guò)對(duì)活動(dòng)的加權(quán)區(qū)分了對(duì)其中不同活動(dòng)的成本;對(duì)偏差類(lèi)別的加權(quán)區(qū)分了偏差發(fā)生位置的重要程度;相較于單一量化偏差個(gè)數(shù)的對(duì)齊成本求解進(jìn)行了改進(jìn)。

2 算法及其實(shí)現(xiàn)

此部分主要介紹基于動(dòng)態(tài)規(guī)劃求解兩個(gè)序列的對(duì)齊,通過(guò)循環(huán)調(diào)用求得υ∈*和網(wǎng)系統(tǒng)=(N,Mini,Mfin),其中=(P,T,F,λ)上的執(zhí)行σ的對(duì)齊;然后利用加權(quán)函數(shù)w對(duì)每個(gè)對(duì)齊的成本c(γ)進(jìn)行計(jì)算,并按照日志的大小分成L.Size()組進(jìn)行排序,求得日志跡與模型的最優(yōu)對(duì)齊

2.1 序列對(duì)齊

基于動(dòng)態(tài)規(guī)劃計(jì)算日志跡與模型可觀測(cè)序列的對(duì)齊,主要是構(gòu)建日志跡與模型可觀測(cè)序列的打分矩陣,并回溯出得分最高的對(duì)齊結(jié)果。其中參數(shù)包括打分矩陣中的匹配得分、不匹配得分及間隙罰值,即同步移動(dòng)、錯(cuò)誤對(duì)齊及合法移動(dòng)的分值。方法有以下幾個(gè)主要步驟:

1) 矩陣初始化。對(duì)于日志跡υ=a1,a2,…,an和模型可觀測(cè)序列σ=b1,b2,…,bm,然后創(chuàng)建大小為(n+1)×(m+1)的打分矩陣,其中:n為行數(shù)且是當(dāng)前日志跡υ的長(zhǎng)度;m是列數(shù)且是當(dāng)前模型可觀測(cè)序列σ的長(zhǎng)度。然后用間隙罰值填充值矩陣的第一行和第一列。間隙懲罰是將對(duì)齊中未匹配字符與空白字符(間隙)進(jìn)行比較時(shí)獲得的值。

序列A和序列B的打分矩陣如圖3所示。

2) 矩陣填充。假設(shè)打分矩陣稱(chēng)為矩陣M,則矩陣M的元素的公式為:

(5)

式中:M(i-1,j-1)為矩陣元素M(i,j)對(duì)角線左上角;M(i,j-1)為M(i,j)的左側(cè);M(i-1,j)為M(i,j)的上方;m(ai,bj)為序列a中的殘基i和序列b中的殘基j的殘差矩陣;d為間隙懲罰的符號(hào)。假設(shè)間合法移動(dòng)模型s(→,a)=s(a,→)=-d對(duì)于a∈Q,d>0,那么長(zhǎng)度為L(zhǎng)的間隙區(qū)域的值等于-dL。

假設(shè)合法移動(dòng)分?jǐn)?shù)是d,那么s(0,j)=-j×d,s(i,0)=-i×d,s(0,0)=0。

(6)

部分打分矩陣代碼如Code_1和Code_2所示。

Code_1:Calculate the first row and first column of matrix according to gapvalue

1 private voidInitScore(intGap,intX,intY) {

2SCORE[0][0]=0;

3for(inti=1;i<=X;i++) {

4SCORE[i][0]=SCORE[i-1][0]+Gap;

5 }

6for(intj=1;j<=Y;j++) {

7SCORE[0][j]=SCORE[0][j-1]+Gap;

8 }

9 }

Code_2:Calculatethescorematrixaccordingtotheinterfaceinput

1privatevoidCalcScore(intMatch,intMiss,intGap,intX,intY,

2StringstringX,StringstringY) {

3intdiag,up,left;

4for(intj=1;j<=Y;j++) {

5for(inti=1;i<=X;i++) {

6diag=Diag(Match,Miss,i,j,stringX,stringY);

7up=Up(Gap,i,j);

8left=Left(Gap,i,j);

9if(diag>=up&&diag>=left) {

10SCORE[i][j]=diag;

11DIRECTION[i][j]=′D′;

12 }elseif(up>=left) {

13SCORE[i][j]=up;

14DIRECTION[i][j]=′U′;

15 }else{

16SCORE[i][j]=left;

17DIRECTION[i][j]=′L′;

18 }

19 }

20 }

21 }

Code_1依據(jù)合法移動(dòng)分值計(jì)算打分矩陣首行首列,Gap、X、Y分別為間隙罰值、序列X的長(zhǎng)度、序列Y的長(zhǎng)度。Code_1(2)對(duì)打分矩陣[0,0]位置元素賦值為0,Code_1(3-5)對(duì)首列除[0,0]位置外元素依據(jù)間隙罰值進(jìn)行賦值處理,Code_1(6-8)對(duì)首行除[0,0]位置外元素依據(jù)間隙罰值進(jìn)行賦值處理。

Code_2依據(jù)錯(cuò)誤對(duì)齊、同步移動(dòng)、合法移動(dòng)計(jì)算首行首列外的打分矩陣及方向矩陣,Match(合法移動(dòng)得分)、Miss(錯(cuò)誤對(duì)齊得分)、Gap(間隙罰值得分)、X(序列X的長(zhǎng)度)、Y(序列Y的長(zhǎng)度)、StringX(序列X)、StringY(序列Y),Diag()、Up()、Left()為分值計(jì)算函數(shù)。Code_2(3-19)使用兩層嵌套對(duì)打分矩陣首行首列外的位置元素進(jìn)行賦值。

3) 回溯步驟。在完全填充大小為(n+1)×(m+1)的打分矩陣之后,對(duì)齊得分(所有替換值之和加上所有間隔懲罰之和)是兩個(gè)序列的打分矩陣最右下角元素的值,M(n+1,m+1)=m(n,m)。回溯步驟如圖4所示。

從起點(diǎn)M(n,m)開(kāi)始回溯到終點(diǎn)m(0,0)。如果M(i,j)=M(i-1,j-1)+m(ai,bj),那么回溯軌跡為(i,j)→(i-1,j-1)。

4) 確定對(duì)齊結(jié)果。若回溯到左上角單元格,將ai添加到匹配字串A(即日志跡),將bj添加到匹配字串B(即模型可觀測(cè)序列)。

若回溯到上邊單元格,將ai添加到匹配字串A,將→添加到匹配字串B。

若回溯到左邊單元格,將→添加到匹配字串A,將bj添加到匹配字串B。

部分回溯代碼及界面右側(cè)矩陣輸出代碼如Code_3和Code_4所示。

Code_3:Backtracking matrix output stringX

1 privateStringPrintOptimalX(StringStringX,StringOptimalX,inti,intj) {

2if(i==0&&j==0) {

3returnOptimalX;

4 }

5if(DIRECTION[i][j]==′D′) {

6OptimalX=PrintOptimalX(StringX,OptimalX,i-1,j-1);

7OptimalX=OptimalX+StringX.charAt(i-1);

8 }elseif(DIRECTION[i][j]==′L′‖j==0) {

9OptimalX=PrintOptimalX(StringX,OptimalX,i-1,j);

10OptimalX=OptimalX+StringX.charAt(i-1);

11 }else{

12OptimalX=PrintOptimalX(StringX,OptimalX,i,j-1);

13OptimalX=OptimalX+′→′;

14 }

15returnOptimalX;

16 }

Code_4:Backtracking matrix output stringY

1privateStringPrintOptimalY(StringStringY,StringOptimalY,inti,intj) {

2if(i==0&&j==0) {

3returnOptimalY;

4 }

5if(DIRECTION[i][j]== ′D′) {

6OptimalY=PrintOptimalY(StringY,OptimalY,i-1,j-1);

7OptimalY=OptimalY+StringY.charAt(j-1);

8 }elseif(DIRECTION[i][j]==′U′‖i==0) {

9OptimalY=PrintOptimalY(StringY,OptimalY,i,j-1);

10OptimalY=OptimalY+StringY.charAt(j-1);

11 }else{

12OptimalY=PrintOptimalY(StringY,OptimalY,i-1,j);

13OptimalY=OptimalY+′→′;

14 }

15returnOptimalY;

16 }

Code_3用于回溯出對(duì)齊序列X,StringX(對(duì)齊序列X)、OptimalX(對(duì)齊后序列X),i、j為元素在矩陣中的位置,依據(jù)確認(rèn)對(duì)齊結(jié)果中的描述進(jìn)行OptimalX的拼接,Code_4同理回溯對(duì)齊后序列Y。

計(jì)算單條日志跡與單條模型可觀測(cè)序列對(duì)齊的方法通過(guò)Java編程實(shí)現(xiàn),通過(guò)設(shè)定MatchScore(同步移動(dòng))、MismatchScore(錯(cuò)誤對(duì)齊)、GapScore(合法移動(dòng))三個(gè)預(yù)值,并輸入需要對(duì)齊的兩個(gè)序列,點(diǎn)擊ALIGNMENT按鈕即可計(jì)算得出兩對(duì)序列之間的最優(yōu)對(duì)齊,并輸出得分、運(yùn)行耗時(shí),且在界面右側(cè)打印序?qū)R計(jì)算時(shí)生成的打分矩陣。SAVE按鈕功能可將計(jì)算結(jié)果進(jìn)行.txt或.rtf格式的保存。

插件進(jìn)行日志跡與系統(tǒng)可觀測(cè)行為的對(duì)齊處理,結(jié)果如圖5所示,打分矩陣與回溯過(guò)程如圖6所示。

2.2 對(duì)齊成本

使用常規(guī)成本計(jì)算方法在計(jì)算日志與模型的最優(yōu)對(duì)齊時(shí),大多僅考慮對(duì)齊中的移動(dòng)個(gè)數(shù),一條日志跡可能與多個(gè)模型可觀測(cè)跡形成最優(yōu)對(duì)齊。在實(shí)際系統(tǒng)中,每個(gè)活動(dòng)的重要程度必然不是完全相等的,且日志上移動(dòng)與模型上移動(dòng)的成本在模型修復(fù)時(shí)顯然也是不等的。在此使用加權(quán)函數(shù)w加權(quán)計(jì)算對(duì)齊成本c(γ),考慮對(duì)齊計(jì)算時(shí)不同活動(dòng)的權(quán)重、插入及跳過(guò)的權(quán)重,增加對(duì)齊計(jì)算時(shí)需考慮的因素,增加對(duì)齊成本計(jì)算結(jié)果對(duì)活動(dòng)的依賴(lài)性,差異化具有相同移動(dòng)個(gè)數(shù)且包含不同活動(dòng)的對(duì)齊序列的成本。加權(quán)計(jì)算如圖7所示。

加權(quán)計(jì)算對(duì)齊成本具體方法如Code_5所示,展示calculateCost函數(shù)進(jìn)行對(duì)齊序列計(jì)算及其加權(quán)成本計(jì)算,tWeightstr(標(biāo)簽加權(quán)字符串)、logSEQstr(對(duì)齊后的日志序列)、modelSEQstr(對(duì)齊后的模型可觀測(cè)跡)、MatchValue(同步移動(dòng)分值)、MisMatchValue(錯(cuò)誤對(duì)齊分值)、GapValue(合法移動(dòng)分值)、weightofskip(跳過(guò)操作的權(quán)值)、weightofinsert(插入操作的權(quán)值),getAlignment()是對(duì)序列匹配的重復(fù)調(diào)用求解日志與模型的對(duì)齊序列,getCharacterPosition()獲取移動(dòng)的位置,getPositionCharacter()獲取移動(dòng)中包含的活動(dòng)。

Code_5:Weighted calculation of alignment costs

1 publicListcalculateCost(StringtWeightstr,StringlogSEQStr,StringmodelSEQStr,StringMatchValue,

2StringMismatchValue,StringGapValue,StringWeightofskip,StringWeightofinsert) {

3HashMaptWeight=operationOfWeight(tWeightstr);

4String[]logseq=logSEQStr.split(" ");

5String[]modelseq=modelSEQStr.split(" ");

6Listresult=getAlignment(MatchValue,MismatchValue,GapValue,logseq,modelseq);

7for(intj=0;j

8Doubleskipscore=0.00,insertscore=0.00;

9if(result.get(j).getLogResult().contains("→")) {

10ListLogindex=getCharacterPosition(result.get(j).getLogResult(),"→");

11ListModelstr=getPositionCharacter(Logindex,result.get(j).getModelResult());

12skipscore=addWeightScore(tWeight,Modelstr);

13result.get(j).setSkipCost(skipscore);

14result.get(j).setLogIndex(Logindex);

15result.get(j).setModelStr(Modelstr);

16 }

17if(result.get(j).getModelResult().contains("→")) {

18ListModelindex=getCharacterPosition(result.get(j).getModelResult(),"→");

19ListLogstr=getPositionCharacter(Modelindex,result.get(j).getLogResult());

20insertscore=addWeightScore(tWeight,Logstr);

21result.get(j).setInsertCost(insertscore);

22result.get(j).setModelIndex(Modelindex);

23result.get(j).setLogStr(Logstr);

24 }

25BigDecimalb1=newBigDecimal(Double.toString(skipscore)),b2=newBigDecimal(Double.toString(insertscore));

26BigDecimalb3=getWeightOfKind(Weightofskip),b4=getWeightOfKind(Weightofinsert);

27result.get(j).setTotalCost(Double.parseDouble(b1.multiply(b3).add(b2.multiply(b4)).toString()));

28 }

29returnresult;

30 }

1) 在2.1節(jié)的基礎(chǔ)上實(shí)現(xiàn)序列對(duì)齊方法的循環(huán)調(diào)用,Code_5(4-6)計(jì)算日志L中每條跡與模型S的所有可觀測(cè)序列的對(duì)齊。

2) 依據(jù)定義5的輸入形式,Code_5(3)初始化活動(dòng)權(quán)值Map。

3) Code_5(7-28)為加權(quán)計(jì)算對(duì)齊成本部分,其中Code_5(9-16)統(tǒng)計(jì)日志跡上的跳過(guò)位置以及對(duì)應(yīng)系統(tǒng)執(zhí)行上跳過(guò)的活動(dòng)并賦值給對(duì)象result;Code_5(17-24)統(tǒng)計(jì)系統(tǒng)執(zhí)行上的插入位置以及日志跡上的插入活動(dòng)并賦值給對(duì)象result。

4) 依據(jù)定義5的標(biāo)簽權(quán)值,定義6的移動(dòng)類(lèi)別權(quán)值,Code_5(25-27)計(jì)算對(duì)齊成本c(γ)。

5) 將對(duì)齊成本計(jì)算結(jié)果按模型可觀測(cè)序列的條數(shù)等分為多組(Code_6),并排序得到每條日志跡的最優(yōu)對(duì)齊。

Code_6用于對(duì)齊結(jié)果的分組,list為日志與模型的對(duì)齊結(jié)果,groupSize為分組大小,Code_6(2-4)用于計(jì)算分組數(shù),Code_6(5-9)用于分組結(jié)果newList的賦值。分類(lèi)加權(quán)計(jì)算對(duì)齊成本的方法由Java編程實(shí)現(xiàn)如圖8所示。

Code_6:splite result

1 private staticList>splitList(Listlist,int

2groupSize) {

3intlength=list.size();

4intnum=(length+groupSize-1)/groupSize;

5List>newList=newArrayList<>(num);

6for(inti=0;i

7intfromIndex=i*groupSize;

8inttoIndex=(i+1)*groupSize

9newList.add(list.subList(fromIndex,toIndex));

10 }

11returnnewList;

12 }

3 實(shí)驗(yàn)分析

本節(jié)主要對(duì)動(dòng)態(tài)規(guī)劃序列對(duì)齊方法、對(duì)齊成本加權(quán)計(jì)算方法進(jìn)行驗(yàn)證,分析序列對(duì)齊方法的耗時(shí),不同權(quán)重對(duì)最優(yōu)對(duì)齊結(jié)果的影響。實(shí)驗(yàn)選取如圖9所示模型,該模型包含選擇、并發(fā)和循環(huán)結(jié)構(gòu),以及靜默變遷X、Y、Z。選取日志序列如表1所示。所有的實(shí)驗(yàn)均在配有I5-7300HQ 2.5 GHz四核處理器和16 GB運(yùn)存的機(jī)器上進(jìn)行的,使用Java SE 1.7開(kāi)發(fā)環(huán)境。

表1 部分運(yùn)行日志

Petri網(wǎng)模型常見(jiàn)的結(jié)構(gòu)關(guān)系包括并發(fā)、選擇和循環(huán)等[24],為增加執(zhí)行序列的多樣性及產(chǎn)生帶有偏差的日志,選取如圖9所示模型,包含靜默變遷X、Y和Z,分布在選擇、并發(fā)和循環(huán)結(jié)構(gòu)中。對(duì)文獻(xiàn)[25]中增廣Petri網(wǎng)模型模擬運(yùn)行插件進(jìn)行改進(jìn),并對(duì)圖9模型進(jìn)行日志生成,為防止?fàn)顟B(tài)爆炸,模型中循環(huán)執(zhí)行的次數(shù)限定為1,部分生成日志如表1所示。

3.1 對(duì)齊耗時(shí)

為對(duì)動(dòng)態(tài)規(guī)劃求解耗時(shí)情況進(jìn)行分析,在此取長(zhǎng)度5∶5∶40的序列進(jìn)行對(duì)齊,對(duì)齊耗時(shí)結(jié)果如圖10所示。對(duì)齊計(jì)算的耗時(shí)與序列長(zhǎng)度成正比,主要耗時(shí)為打分矩陣的構(gòu)建(算法復(fù)雜度為O(mn))與序列對(duì)齊結(jié)果的回溯(時(shí)間復(fù)雜度為O(m+n))。

圖1 同一序列的兩個(gè)不同對(duì)齊

圖2 增強(qiáng)活動(dòng)依賴(lài)的最優(yōu)對(duì)齊算法實(shí)現(xiàn)流程

圖3 序列A和序列B的打分矩陣

圖4 回溯步驟

圖5 對(duì)齊序列計(jì)算界面

圖6 打分矩陣及回溯過(guò)程

圖7 加權(quán)計(jì)算示意圖

圖8 加權(quán)計(jì)算對(duì)齊成本求解最優(yōu)對(duì)齊

圖9 含有選擇、并發(fā)和循環(huán)結(jié)構(gòu)的模型

圖10 不同長(zhǎng)度序列對(duì)齊計(jì)算耗時(shí)

3.2 可行性及有效性

對(duì)于加權(quán)計(jì)算對(duì)齊成本方法的可行性,利用表1所示的日志與圖9所示網(wǎng)系統(tǒng)進(jìn)行對(duì)齊,并計(jì)算對(duì)齊成本(活動(dòng)成本分別為默認(rèn)1和(A,1,B,2,C,2,X,4,D,1,E,1,F,1,G,1,Y,1,H,1,I,6,Z,12,J,1)兩種),插入及跳過(guò)成本權(quán)重設(shè)置為默認(rèn)1和(WSkip=1.5,WInsert=0.5),對(duì)齊成本計(jì)算結(jié)果如圖11所示,方法是可行的。

(a)

圖12展示了不同標(biāo)簽取值對(duì)CostSkip、CostInsert的影響,WeightSkip、WeightInsert的設(shè)定增加了對(duì)齊成本線圖的可區(qū)分度。圖13中的線為對(duì)齊不同可觀測(cè)跡的對(duì)齊總成本,非重疊處即出現(xiàn)了不同權(quán)值設(shè)置標(biāo)簽的插入或跳過(guò)。

圖12 設(shè)置不同標(biāo)簽權(quán)重ADEFGHJ與模型可觀測(cè)跡的對(duì)齊成本

圖13 不同標(biāo)簽權(quán)重對(duì)ADEFGHJ最優(yōu)對(duì)齊的影響

表2與表3展示了日志序列在不同標(biāo)簽權(quán)值設(shè)定時(shí)(將選擇結(jié)構(gòu)中的B,C活動(dòng)標(biāo)簽加入不同權(quán)值),最優(yōu)對(duì)齊及對(duì)齊成本會(huì)有所不同,方便在進(jìn)行日志與模型對(duì)齊時(shí)對(duì)某些活動(dòng)或結(jié)構(gòu)進(jìn)行側(cè)重,方法是有效的。

表2 標(biāo)簽權(quán)值序列為x1時(shí)最優(yōu)對(duì)齊序列

表3 標(biāo)簽權(quán)值序列為x2時(shí)最優(yōu)對(duì)齊序列

x1=A,1,B,2,C,3,X,4,D,1,E,1,F,1,G,1,Y,1,H,1,I,6,Z,12,J,1x2=A,1,B,2,C,2,X,4,D,1,E,1,F,1,G,1,Y,1,H,1,I,6,Z,12,J,1

4 結(jié) 語(yǔ)

本文認(rèn)為一致性檢驗(yàn)在信息管理系統(tǒng)中發(fā)揮著越來(lái)越重要的作用,其中對(duì)齊是最先進(jìn)、最全面的方法之一,且最優(yōu)對(duì)齊被廣泛使用。現(xiàn)有的最優(yōu)對(duì)齊計(jì)算缺乏對(duì)活動(dòng)依賴(lài)的考慮,繼而在此提出一種新的方法,用于計(jì)算Petri網(wǎng)模型和日志跡之間的最優(yōu)對(duì)齊。首先基于動(dòng)態(tài)規(guī)劃求解對(duì)齊(時(shí)間復(fù)雜度O(mn+m+n)),然后對(duì)于對(duì)齊結(jié)果依據(jù)自定義的活動(dòng)權(quán)重及插入、跳過(guò)成本的權(quán)重計(jì)算對(duì)齊成本(時(shí)間復(fù)雜度O(mn)),最后對(duì)計(jì)算結(jié)果分組排序得出模型與日志跡之間的每一對(duì)最優(yōu)對(duì)齊。實(shí)驗(yàn)結(jié)果表明動(dòng)態(tài)規(guī)劃求解對(duì)齊、加權(quán)計(jì)算對(duì)齊成本的方法是可行的,且最優(yōu)對(duì)齊的求解方法在一定程度上體現(xiàn)了不同活動(dòng)的重要性,增加了最優(yōu)對(duì)齊對(duì)活動(dòng)的依賴(lài)性,且降低了日志跡與模型之間相同最優(yōu)對(duì)齊成本的個(gè)數(shù),對(duì)原有的單一量化對(duì)齊成本求解進(jìn)行了改進(jìn)。

依據(jù)實(shí)驗(yàn)結(jié)果分析,未來(lái)工作可從以下幾個(gè)方面展開(kāi):(1) 利用BPIC的真實(shí)數(shù)據(jù)和模型對(duì)方法進(jìn)行測(cè)試和驗(yàn)證;(2) 改進(jìn)加權(quán)計(jì)算對(duì)齊成本的方法,將其與對(duì)齊的求解相結(jié)合;(3) 在求解所有對(duì)齊、排序最優(yōu)對(duì)齊時(shí)加入多線程的使用提高計(jì)算效率;(4) 加權(quán)計(jì)算后得到的對(duì)齊成本是不同的,進(jìn)一步分析其對(duì)一致性檢驗(yàn)的影響。