過程挖掘中增強(qiáng)活動依賴的最優(yōu)對齊算法

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

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

0 引 言

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

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

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

1 基本概念

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

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

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

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

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

例如,γ1和γ2展示了指定兩個域的兩個序列的移動分別為<(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=,同一個跡之間的兩個對齊顯示了觀察到的跡和建模的流程實例之間的不同偏差,比較對齊的常用方法是根據(jù)對齊包含的移動對其進(jìn)行量化。

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

(1)

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

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

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

在輸入過程中,輸入形式如下:

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

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

Weightskip/Weightinsert:

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

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

(2)

則:

(3)

(4)

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

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

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

2.1 序列對齊

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

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

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

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

(5)

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

假設(shè)合法移動分?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ù)合法移動分值計算打分矩陣首行首列,Gap、X、Y分別為間隙罰值、序列X的長度、序列Y的長度。Code_1(2)對打分矩陣[0,0]位置元素賦值為0,Code_1(3-5)對首列除[0,0]位置外元素依據(jù)間隙罰值進(jìn)行賦值處理,Code_1(6-8)對首行除[0,0]位置外元素依據(jù)間隙罰值進(jìn)行賦值處理。

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

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

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

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

若回溯到上邊單元格,將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用于回溯出對齊序列X,StringX(對齊序列X)、OptimalX(對齊后序列X),i、j為元素在矩陣中的位置,依據(jù)確認(rèn)對齊結(jié)果中的描述進(jìn)行OptimalX的拼接,Code_4同理回溯對齊后序列Y。

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

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

2.2 對齊成本

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

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

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ǔ)上實現(xiàn)序列對齊方法的循環(huán)調(diào)用,Code_5(4-6)計算日志L中每條跡與模型S的所有可觀測序列的對齊。

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

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

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

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

Code_6用于對齊結(jié)果的分組,list為日志與模型的對齊結(jié)果,groupSize為分組大小,Code_6(2-4)用于計算分組數(shù),Code_6(5-9)用于分組結(jié)果newList的賦值。分類加權(quán)計算對齊成本的方法由Java編程實現(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 實驗分析

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

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

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

3.1 對齊耗時

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

圖1 同一序列的兩個不同對齊

圖2 增強(qiáng)活動依賴的最優(yōu)對齊算法實現(xiàn)流程

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

圖4 回溯步驟

圖5 對齊序列計算界面

圖6 打分矩陣及回溯過程

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

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

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

圖10 不同長度序列對齊計算耗時

3.2 可行性及有效性

對于加權(quán)計算對齊成本方法的可行性,利用表1所示的日志與圖9所示網(wǎng)系統(tǒng)進(jìn)行對齊,并計算對齊成本(活動成本分別為默認(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)兩種),插入及跳過成本權(quán)重設(shè)置為默認(rèn)1和(WSkip=1.5,WInsert=0.5),對齊成本計算結(jié)果如圖11所示,方法是可行的。

(a)

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

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

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

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

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

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

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é) 語

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

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