基于模型結構和事件日志的流程相似度計算

,吳玨

(1.西南科技大學 計算機科學與技術學院，四川 綿陽 621000;2.中國空氣動力研究與發展中心 計算空氣動力研究所，四川 綿陽 621000)

0 引言

作為企業業務的一種描述，業務流程模型在企業的發展過程中扮演著重要的角色，能夠有效提高公司的效率，對企業的業務運營具有重要的指導意義。隨著企業業務的增多，相應的業務流程也越來越多，大型企業往往保存著成千上萬的業務流程。構建新的流程復雜且耗時，若能為相關人員推薦流程庫中的相似流程，并在已有流程的基礎上進行修改將大幅度縮短工作時間，減少重復工作，而流程推薦的核心是流程相似度的計算，因此流程相似度計算成為一個研究熱點[1-3]。

1 相關工作

近年來流程相似度計算的問題取得了較好的成果，現有的方法主要包含基于文本內容相似度[4-5]、基于模型結構相似度[6-16]和基于流程行為相似度[17-19]三種。

基于文本內容的相似度主要是根據流程對應節點的文本內容相似度來度量，包括字符串編輯距離、語義相似度等，這種方法不考慮模型結構僅比較對應節點的文本內容，比較簡單，然而當流程模型結構發生改變而文本內容不變的時候，該方法無法識別，導致準確率較低。

作為流程的重要屬性，模型結構能夠很好地表示活動間的邏輯關系，決定數據以及控制流的前進方向。目前基于模型結構相似度的方法有三種，包括矩陣間距離、樹的編輯距離和圖的編輯距離。文獻[6-10]根據變遷緊鄰關系，將流程模型結構轉化鄰接矩陣，定義矩陣間的距離來計算流程結構相似度。文獻[11-12]將流程模型結構轉化成對應的結構樹，通過計算樹的編輯距離得到流程相似度。文獻[13-16]的相關工作是將流程模型轉化為標準的業務流程圖，通過圖之間的匹配度來衡量流程之間的相似度。這些算法以更直觀的方式表示模型結構，從而更方便的計算流程相似度，相比文本內容相似度，準確率更高。不足之處在于將模型結構轉化為鄰接矩陣、樹或圖的過程中會損失能夠區分不同流程行為的語義信息，導致無法區分流程活動之間的復雜關系，如選擇、并行關系和循環關系，因此需要結合流程結構和行為信息來更準確的表示業務流程，使得計算結果更加精確。

基于流程行為相似度的計算方法[17-19]主要是根據流程的模型結構，模擬流程中活動間的邏輯關系得到活動執行序列，從而獲取流程行為信息。由于流程的執行過程與相關人員關系緊密，流程的行為信息往往會包含參與者的行為習慣，因此通過模擬的形式獲取行為信息的方式在大多數實際應用中是無效的，需要一種更加客觀的方法記錄行為信息。事件日志是流程執行過程的客觀觀察，包含流程的語義、軌跡以及參與者的執行習慣，反映了流程的真實執行情況，具有極高的參考意義。

針對上述問題，周長紅等人[20-21]提出了一種將模型結構和行為信息結合的方法，該方法根據行為信息對圖進行加權得到加權業務流程圖，基于加權圖的編輯距離來計算流程相似度，提高了準確率。但是加權圖的編輯操作需要對節點和邊進行處理，包括節點和邊的的插入、刪除和替換，這些操作的定義困難，復雜度高且時間效率較低。

本文在此基礎上提出一種改進的將模型結構和事件日志結合的相似度計算方法。首先用鄰接矩陣表示流程模型結構，然后根據事件日志中的軌跡頻次對鄰接矩陣進行加權，得到加權鄰接矩陣，最后給出矩陣間距離算法的定義，計算流程相似度。本文基于矩陣間距離的計算只需要對差異矩陣求和，比加權圖的編輯距離計算更簡單，效率更高。

2 流程相似度計算方法

本文改進的基于模型結構和事件日志的流程相似度計算方法的流程如圖1所示，主要包含三部分：1)首先對流程模型文件中的流程進行預處理，即將原始流程轉化為僅包含緊鄰活動關系的鄰接矩陣；2)獲取流程的事件日志，對預處理后的鄰接矩陣進行加權；3)根據矩陣間距離算法對加權矩陣進行計算，得到矩陣間距離，返回相似度。

圖1 流程相似度計算流程

2.1 模型預處理

模型預處理是將模型轉化為只包含緊鄰活動關系的鄰接矩陣。本文用Petri網模型表示流程的模型結構信息，因此先給出相關定義。

定義1(Petri網)：一個流程的Petri網是一個三元組PN=(P，A，F)，其中：

a)P是一個有限的庫所集(place)；

b)A是一個有限的變遷集(transition)，P∪A≠?且P∩A=?；

c)F?(P×A)∪(A×P)是一個表示流程關系的有向弧集，包含庫所和變遷；

定義2(緊鄰活動)：對于任意流程PN，設活動集合為A，有向弧集合F={f1，f2，…，fn}，活動a，bA，判斷活動a，b是否為緊鄰活動的準則是當且僅當在PN中存在有向弧fi，fi+1，使得活動a經過有向弧fi，fi+1可以到達活動b，且a和b之間不存在其他活動，其中i({1，2，…，n-1}。

圖2 某流程BP1的Petri網模型

圖2是某流程BP1的Petri網模型，本文不考慮模型的庫所，只是為了區分復雜結構。流程BP1的活動集合A={a，b，c，d，e，f，g}，緊鄰活動有ab，bc，cd，ce，dg，eg，bf，fg。

定義3(鄰接矩陣)：以流程模型PN中的緊鄰活動關系為元素的矩陣稱為鄰接矩陣(Adjacent Matrix，AM)，流程的活動集為A，矩陣元素的值表示如下：

(1)

其中:ai，ajA。

對于任意給定流程，可以根據如下方法構建鄰接矩陣：設流程有n個不同活動，首先初始化一個n×n的矩陣，如圖2所示流程共包含7個不同的活動a、b、c、d、e、f、g，因此圖2對應一個7×7的鄰接矩陣。對于流程模型中的任意兩個活動ai，aj，若活動ai，aj為緊鄰活動，鄰接矩陣AMi,j對應位置填1，即AMi,j=1，否則AMi,j=0。根據流程BP1構建鄰接矩陣AM，

2.2 矩陣加權及同維

鄰接矩陣僅考慮流程模型結構的緊鄰活動關系，未考慮緊鄰活動關系的重要性，因此本文提出加權鄰接矩陣的概念。加權鄰接矩陣是在鄰接矩陣的基礎上，根據事件日志中的行為信息對每一組緊鄰活動進行加權，從而將日志行為信息添加到業務流程模型的鄰接矩陣。在流程實際運行過程中，可能會出現流程執行異常或日志記錄錯誤的情況，這種異常或錯誤通常被稱為噪聲，為了減小噪聲的影響，從而有效地提取與分析行為信息，本文根據文獻[10]提出的降噪方法對事件日志進行處理，刪除所占比例小于給定閾值δ的軌跡，本文設置閾值δ=0.01，活動已經按照執行時間先后排序。經過處理，流程BP1的簡單事件日志如表1所示。

表1 某流程BP1的日志信息

假設該流程的簡單事件日志為L，軌跡τ在事件日志L中的執行頻次為#frequency(τ,L)。流程BP1共包含6個不同軌跡，第i個軌跡表示為τi(1≤τ≤6)，則6個軌跡的執行頻次為#frequency(τ1,L)=64，#frequency(τ2,L) =16，#frequency(τ3,L)=56，#frequency(τ4,L)=14，#frequency(τ5,L)=12，#frequency(τ6,L) =3。

2.2.1 構建加權鄰接矩陣

定義4(加權鄰接矩陣)：以鄰接矩陣AM為基礎，每個元素對應的緊鄰活動在簡單事件日志L中出現的次數除以軌跡總數得到新的元素值，構成加權鄰接矩陣(Weight Adjacent Matrix，WAM)，即：

(2)

其中:w表示軌跡總數。

對流程模型而言，將模型結構轉化為鄰接矩陣的問題是出現分支時無法區分分支中的活動之間是選擇關系還是并行關系，而加權鄰接矩陣可以通過緊鄰活動的不同權重來區分不同的分支結構。具體來說，當兩個活動為并行關系時，這兩個活動與其最近的公共直接前驅活動組成的緊鄰活動對應的權值均相同。如圖2所示活動c，f為并行關系，活動b為兩者的公共直接前驅活動，由WAM可知，活動b，c和活動b，f對應的權值WAM2,3、WAM2,6均為1，且并行關系開始前的活動a，b緊鄰關系的權值WAM1,2也為1。當兩個活動為選擇關系時，則這兩個活動與其公共直接前驅活動組成的緊鄰活動對應的權值一般不同，且權值一定小于選擇關系開始前的緊鄰關系的權值。如圖2所示，活動d，e為選擇關系，活動c為兩者的公共直接前驅活動，由WAM可知，活動c，d對應的權值WAM3,4為0.8，活動c，e對應的權值WAM3,5為0.2，均小于選擇關系開始前的活動b，c對應權值為1的WAM2,3。此外，本文將流程模型轉換成加權矩陣后還可以區分循環結構。若加權鄰接矩陣的對角線的元素全為0，說明該流程不存在自循環結構。若加權鄰接矩陣中的某個元素的值大于1，說明對應的緊鄰活動之間存在循環，從而推斷出該流程存在循環結構。

2.2.2 同維加權鄰接矩陣

(3)

(4)

2.3 相似度計算

本文用流程矩陣間距離表示流程相似度，為了更直觀的表示矩陣間的距離，參照矩陣間距離相似度(Matrix Distance Similarity, MDS)算法[9]的定義，對公式修改如下。

(5)

相似度計算的核心是總活動集S的構建以及差異矩陣DM的計算。設m是流程P、P′的活動集個數較大值，構建活動集S的算法的時間復雜度是O(m2)，計算差異矩陣是通過兩個同維矩陣對應位置相減，矩陣的大小等于活動集S的大小n，該部分的時間復雜度是O(n2)，由于m≤n，所以總的時間復雜度為O(n2)。

計算BP1，BP2的相似度D(BP1,BP2)=0.35，因此流程BP1、BP2之間的相似度為0.35。

3 驗證實驗

3.1 實驗數據

目前相關算法的實驗結果是在不同數據集下得到的，不能直接用來比較算法。針對該問題，周長紅等人[20-21]選取了一個真實的保險理賠申請流程(表2，P0)，通過人為的增加或刪除一些分支，以及改變不同分支結構的權重，構造了13個流程變體(表2，P1-P13)，并且記錄所有變體的日志信息，最后獲得的數據集共包含5 445個軌跡，26 825個活動。該數據集能更好的滿足模型結構和事件日志結合的相關算法測試，可以更公平的進行算法對比。

表2 流程基本信息

本文將上述流程轉換為對應的加權鄰接矩陣，以進行相似度的計算，轉化結果如圖4所示。

圖4 流程轉化圖

3.2 實驗結果及分析

實驗選取相關典型算法，包括模型結構相似度、模型行為相似度、模型結構和行為結合的相似度算法，與本文方法進行比較，相關算法的信息如表3所示。

表3 對比算法相關信息

實驗選取P0為參考模型，采用上述算法計算13個變體流程與P0的相似度，結果如表4所示。

表4 不同算法的實驗結果

如表4所示，在A組中對選擇分支進行刪除或添加操作，分支的重要性發生的變化在算法A1～A3中無法體現。如P1和P2的結構相同(圖4)，但P1刪除了分支b，而P2刪除的是分支c，兩者與P0的相似度不為1，說明算法可以檢測出分支結構的差異性。但P1與P0的相似度值和P2與P0的相似度值相同，說明以上算法沒有檢測到分支重要性的變化。而算法A4和本文方法A5既能檢測出分支結構的變化，又能檢測分支重要程度發生的變化。因為兩種算法都考慮了模型結構，又根據事件日志中軌跡的執行次數對不同分支進行加權。另外，在B組中對并行分支進行刪除或添加后對模型結構影響較大，但原有分支的重要性不受影響，因此本文方法計算的結果更接近基于結構相似度的算法A1和A2計算的結果，而與基于行為相似度的算法A3計算的結果相差較大。

在C組中，P11中的選擇分支變為并行分支，P12和P13中的并行分支變為選擇分支(圖4)，而這兩種變化均未引起模型結構的改變，但會引起事件日志的執行軌跡發生變化，因此，算法A1和A2只考慮模型結構無法區分流程中活動之間的選擇關系和并行關系，而考慮了行為信息的A3-A5可以區分行為變化帶來的影響。

綜上所述，僅考慮模型結構無法檢測分支重要程度的變化，也無法區分選擇關系和并行關系，融入事件日志中的行為信息后能更準確的區分流程間的相似度。在上述算法中，只有本文方法和A4同時考慮了模型結構和行為信息，效果更理想，但本文是將原始流程轉化為加權鄰接矩陣，而算法A4是轉化為加權業務流程圖(見圖3)，兩者相似度的計算方式明顯不同，所得相似度值也不同。

3.3 準確率評估

在上節中，本文詳細分析了各種算法區分分支結構變化和重要性變化的能力。總的來講，能檢測各種分支變化的算法要優于只能檢測部分分支變化的算法。但對都能檢測出分支變化的算法而言，卻無法判斷哪種算法得到的相似度更準確。為了更好的對實驗結果進行評估，文獻[20]給出了由15位領域專家按P1～P13與P0的相似性大小排序的結果以及對應流程變體的權重，并將該排序結果作為基準排序。本文將不同算法中計算的13個流程變體與P0的相似度大小排序和基準排序結果進行比較，見表5，并計算歸一化折損累積增益(normalized discount cumulative gain, NDCG)[23]評估算法的準確率。NDCG的計算公式如下：

表5 相似度大小排序結果

(6)

(7)

其中:r(n)表示排在第n個位置的流程的權重；Dn表示某個給定流程模型與其n個相關流程的折損累積增益，In是基準排序中某個給定流程模型與其n個相關流程的理想折損累計增益(IDCG)。從公式(7)可知，DCG與IDCG越接近，算法的NDCG值越高，準確率越高。

本文計算得到基準排序的IDCG值為4.167，分別對不同算法的實驗結果進行排序，計算相應的DCG值，最后得到每種算法的NDCG值，實驗結果如表6所示。

表6 DCG與NDCG

由表6可知，上述方法準確率都比較高，原因是所有變體流程分支權重的差異變化比較小，但是仍可以看出結合模型結構和行為信息的算法(A4和A5)要比僅考慮單一因素的算法準確度要高。在實際應用中，用戶更關心較為靠前的結果，分析表5可得，本文方法前7個推薦結果和專家的排序結果一致，說明本文方法更加符合專家的判定，準確率相比算法A4更高。

3.4 復雜度分析

對于企業而言，用戶關心的不僅僅是流程推薦的準確度，還要求流程推薦具有高效性，從而節省公司的支出。本文方法與其他算法的時間復雜度如表7所示。

表7 時間復雜度對比

本文方法和算法A1都是通過將流程模型轉化為鄰接矩陣，求矩陣間的距離得到流程相似度，時間復雜度均為O(n2)，但是本文方法能區別更多不同結構的流程且準確率更高。算法A2～A4都是基于圖的編輯距離計算流程相似度。圖編輯距離指一個圖變形到另一個圖所需要的最小消耗。其中變形由一系列的變形操作完成，包括節點的插入/刪除操作、節點的替換操作、邊的插入/刪除操作和邊的替換操作，而每個操作均有一定的時間消耗。因此算法的時間復雜度非常高，通常與涉及到的兩個圖的節點數目呈指數關系，這樣的時間消耗在業務流程庫增加到更大規模時，檢索時間也將成倍增加，嚴重影響了大規模流程檢索的用戶體驗，也在一定程度上阻礙了企業業務的發展。綜上，本文的算法在準確度及時間效率上都具有非常大的優勢。

3.5 實驗說明

本文的實驗環境是：Intel(R) Core(TM) i5-4460 CPU @ 3.20 GHz 8 GB內存。實驗程序用Python實現，版本是3.7.0，運行在64位的Windows 10系統上。實驗數據中14個流程的事件日志，是使用事件日志生成工具(PLG)生成的，數據集已上傳到GitHub，地址為https://github.com/swustzzh/static/tree/master/process。

4 結束語

現有的大部分流程相似度計算方法主要根據流程模型結構計算相似度，或者根據事件日志中的行為信息計算相似度。本文嘗試以模型結構信息為主，融入一些日志行為信息的方法計算流程相似度，從而能夠更好的表示企業業務流程的行為習慣，更加貼合企業的需求。首先根據流程模型結構中的緊鄰活動關系將其轉化為鄰接矩陣，然后通過事件日志的軌跡執行頻次的對緊鄰活動進行加權。最后定義了加權鄰接矩陣的同維操作，并在此基礎上給出矩陣間距離的計算公式。實驗結果表明本文的算法能夠有效的結合流程模型結構和行為日志，相比周長紅等人的算法，計算更簡便，時間復雜度更低。本文提出的方法有利于幫助企業推薦相似的流程，可以在大規模的流程庫中進行檢索。下一步工作將會進一步優化流程間距離算法，使其能夠更好地區分差異較小的流程模型。