過程挖掘中增強活動依賴的最優對齊算法

邵叱風 方賢文 楊慧慧

(安徽理工大學數學與大數據學院 安徽 淮南 232001)

0 引 言

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

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

現有的最優對齊方法在計算對齊成本時大多僅考慮對齊中的移動個數(包括相似性最優對齊),缺乏對單一活動成本即活動依賴的考慮。在此提出一種基于依賴增強的最優對齊計算方法,目的提高計算序列對齊的效率、最優對齊對活動的依賴性?；谧远x得分矩陣的配置,使用動態規劃的方法計算日志中所有序列與模型可觀測跡的對齊;分析對齊集合中移動的信息,通過加權的方式計算模型與日志上合法移動的總成本;最后利用分組排序得到日志與模型的最優對齊序列及對齊成本。

1 基本概念

本節內容列出了文章所需的部分基本概念,用以輔助文章的閱讀。Petri網相關定義參考文獻[24]。

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

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

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

定義2(對齊) 跡υ∈*和網系統=(N,Mini,Mfin),其中=(P,T,F,λ)上的執行σ之間的對齊是擁有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=,同一個跡之間的兩個對齊顯示了觀察到的跡和建模的流程實例之間的不同偏差,比較對齊的常用方法是根據對齊包含的移動對其進行量化。

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

(1)

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

定義5(標簽加權) 依據活動不同重要性,考慮單一活動成本,對對齊序列中的標簽γi進行加權處理,對于權函數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(移動加權) 依據偏差出現位置,考慮其對對齊成本的影響,在計算總的對齊成本時對于系統上的合法移動,跡上的合法移動按類別Weightskip、Weightinsert進行加權處理。輸入形式如下:

Weightskip/Weightinsert:

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

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

(2)

則:

(3)

(4)

通過對活動的加權區分了對其中不同活動的成本;對偏差類別的加權區分了偏差發生位置的重要程度;相較于單一量化偏差個數的對齊成本求解進行了改進。

2 算法及其實現

此部分主要介紹基于動態規劃求解兩個序列的對齊,通過循環調用求得υ∈*和網系統=(N,Mini,Mfin),其中=(P,T,F,λ)上的執行σ的對齊;然后利用加權函數w對每個對齊的成本c(γ)進行計算,并按照日志的大小分成L.Size()組進行排序,求得日志跡與模型的最優對齊

2.1 序列對齊

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

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

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

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

(5)

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

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

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

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

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

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

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

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

部分回溯代碼及界面右側矩陣輸出代碼如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為元素在矩陣中的位置,依據確認對齊結果中的描述進行OptimalX的拼接,Code_4同理回溯對齊后序列Y。

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

插件進行日志跡與系統可觀測行為的對齊處理,結果如圖5所示,打分矩陣與回溯過程如圖6所示。

2.2 對齊成本

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

加權計算對齊成本具體方法如Code_5所示,展示calculateCost函數進行對齊序列計算及其加權成本計算,tWeightstr(標簽加權字符串)、logSEQstr(對齊后的日志序列)、modelSEQstr(對齊后的模型可觀測跡)、MatchValue(同步移動分值)、MisMatchValue(錯誤對齊分值)、GapValue(合法移動分值)、weightofskip(跳過操作的權值)、weightofinsert(插入操作的權值),getAlignment()是對序列匹配的重復調用求解日志與模型的對齊序列,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節的基礎上實現序列對齊方法的循環調用,Code_5(4-6)計算日志L中每條跡與模型S的所有可觀測序列的對齊。

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

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

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

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

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

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

表1 部分運行日志

Petri網模型常見的結構關系包括并發、選擇和循環等[24],為增加執行序列的多樣性及產生帶有偏差的日志,選取如圖9所示模型,包含靜默變遷X、Y和Z,分布在選擇、并發和循環結構中。對文獻[25]中增廣Petri網模型模擬運行插件進行改進,并對圖9模型進行日志生成,為防止狀態爆炸,模型中循環執行的次數限定為1,部分生成日志如表1所示。

3.1 對齊耗時

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

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

圖2 增強活動依賴的最優對齊算法實現流程

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

圖4 回溯步驟

圖5 對齊序列計算界面

圖6 打分矩陣及回溯過程

圖7 加權計算示意圖

圖8 加權計算對齊成本求解最優對齊

圖9 含有選擇、并發和循環結構的模型

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

3.2 可行性及有效性

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

(a)

圖12展示了不同標簽取值對CostSkip、CostInsert的影響,WeightSkip、WeightInsert的設定增加了對齊成本線圖的可區分度。圖13中的線為對齊不同可觀測跡的對齊總成本,非重疊處即出現了不同權值設置標簽的插入或跳過。

圖12 設置不同標簽權重ADEFGHJ與模型可觀測跡的對齊成本

圖13 不同標簽權重對ADEFGHJ最優對齊的影響

表2與表3展示了日志序列在不同標簽權值設定時(將選擇結構中的B,C活動標簽加入不同權值),最優對齊及對齊成本會有所不同,方便在進行日志與模型對齊時對某些活動或結構進行側重,方法是有效的。

表2 標簽權值序列為x1時最優對齊序列

表3 標簽權值序列為x2時最優對齊序列

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 結 語

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

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