加權Petri網的字符串序列相似性度量

胡迎城，邢瑪麗，吳元清

（廣東工業大學 自動化學院, 廣東 廣州 510006）

流程管理的基礎在于流程的檢索定位，即從流程模型庫中尋找指定的相似流程，檢索定位的關鍵技術在于如何度量流程之間的相似性。因此，只有好的流程相似性度量方法才能保障流程檢索定位的有效性和準確性[1]。有了好的(快速精準)相似性算法，就能夠對繁雜冗余的流程庫進行整理更新以實現有效的流程管理，大大提高企業的運行效率及市場競爭力，從而促進企業的發展。流程相似性問題[2]是指給一個流程模型，如何從已經構建的流程模型庫中檢索出與給定流程相似的流程模型，主要思想是將給定的流程模型與流程庫中的每個流程模型進行比對，快速精準地計算流程間的相似度值。目前主要是基于文本、結構和行為相似性3個方面[3]來展開研究的，但仍然存在不足，下面將簡單介紹其中的一些缺陷。

文獻[4-5]提出的相似性度量方法都是針對流程中相關標簽(一般有任務標簽、角色標簽、資源標簽和屬性標簽等)的文本內容進行相似性分析，但很難篩選出在流程模型本身特征上(即結構和行為特征)的相似流程。李東月等[6]提出的基于活動發生關系(Activity Occurrence Relation，AOR)的流程相似性算法和基于行為輪廓的流程模型及其流程變體的距離相似性分析等，定義了一系列關系來度量模型結構相似性。董子禾等[7]還考慮了循環結構，但計算過程過于復雜且花費時間過長。而針對流程結構的相似性，文獻[8]采用圖編輯的方法來進行度量。雖然有較高的準確性，但其計算復雜度很高，而且該類方法往往很難識別出結構相似但行為不同的模型，不太適用于實際應用。吳亞鋒等[9]提出的基于鄰接矩陣的業務流程間距離計算方法，宋金鳳等[10]提出的基于任務發生關系的流程模型相似性度量，將行為信息轉換成矩陣進行相似性計算，有比較高的度量效果和時間效率，但卻是在單一維度上考慮流程間的相似性。對于多維度的相似性度量方法，周長紅等[11]提出將模型結構和行為信息相結合，從而提高流程相似度的準確率，但其結構方面的度量仍是采用圖編輯距離來計算，其圖的編輯操作需要對邊和節點進行處理，這些操作的定義困難、復雜度高且時間效率較低。

文獻[12]通過對經典工作流網進行數據讀寫語義的擴展，提出了一種數據感知工作流網，將數據流信息整合到業務流程控制流中，基于數據感知行為從不同角度來量化流程相似度。文獻[13]通過建立流程、路徑和節點之間的函數表達式，使用獨熱編碼對節點進行向量化表示，建立單層神經網絡模型，從而量化流程相似度。文獻[14]基于機器學習的方法來計算具有結構和標簽差異的一對流程模型之間的相似度。文獻[15]將任務流建模為圖結構，根據層次劃分方法計算圖的相似度然后通過譜聚類算法對圖進行聚類，使圖被劃分為聚類。文獻[16]在業務流程中使用推薦技術包括某個點提出相關任務，從而使用決策樹的方法來度量流程相似性。

本文使用廣度優先遍歷的方法將Petri網轉換為字符串序列，在不降低準確率的基礎上，避免了復雜度高的圖編輯距離，很大程度上提高了流程的檢索效率。

1 相關知識

1.1 加權Petri網

Petri網是一種形式化的方法，用來描述業務流程的執行過程，將業務流程的執行過程表達成一個圖的形式。其中，圖中的每個節點都代表一個活動或狀態信息。另外，現在很多企業都將Petri網作為業務流程的表達形式，并將Petri網作為相關軟件的輸入輸出，因此，選擇Petri網作為業務流程相似性的研究對象，其定義如下。

定義1 加權Petri網[11,17]。加權Petri網是一個四元組N=(P,T,F,λ) ， 其中P是所有庫所的有限集合，T是所有變遷的有限集合，有P∩T=?；F是所有邊的有限集合，指P,T之間的連接關系，即F?(P×T)∪(T×P) ，是一個映射到集合{0,1}的函數，如F(p,t)=1， 則表示p到t是通過一條有向弧相連接的；λ:F →R是一個函數，該函數將每一條有向邊映射為一個權值，其中R為實數集。把Petri網中所有節點記為集合X=P∪T，對于任意節點x∈X，節點相鄰的邊包括輸入邊和輸出邊；其相鄰節點集合表示為Y={y∈X|(x,y)∈F,(y,x)∈F} ，其 中，·x={y∈X|(y,x)∈F}為前置節點，x·={y∈X|(x,y)∈F}為后繼節點。

1.2 流程事件日志

流程事件日志記錄了業務流程的各種運行狀態信息，包括任務活動、執行角色、資源以及任務事件發生和結束的時間等，能夠在很大程度上直觀地反映事件的執行情況。下面對流程事件日志中涉及到的一些基本概念[18]進行定義：

定義2 事件(Event)。事件也稱為任務活動，是流程中的最小單元，由該事件的一系列屬性組成，定義為

式中：事件e的屬性C aseID 是 指案例的ID值，EventID是指事件的ID值，E ventName是事件活動名稱，是唯一的；S tartTime 和E ndTime是該事件發生和結束的時間戳，該事件的執行時間就可以用e(EndTime)-e(Start Time)來 表示；而A tt1,···,Attm是指該事件的其他相應屬性，比如執行角色、所用資源等屬性。

定義3 事件軌跡(Event Trace)。通常事件軌跡也稱為案例，指流程模型的一次執行結果，是由流程中的一系列事件有序構成的集合，定義t=＜e1,e2,···,en＞ 是一個長度為n的 事件軌跡，其中，ei∈t是事件軌跡t的 第i個 事件，同一個事件軌跡的C aseID值相同。

定義4 事件日志(Event Log)。事件日志是由一系列事件軌跡構建的集合，定義L=＜t1,t2,···,tk＞是一個包含了k個事件軌跡的事件日志。其中ti∈L是事件日志中的第i個事件軌跡，同一事件日志中的所有事件軌跡都是由同一業務流程運行產生的。如表1所示為某流程被執行后生成的事件日志實例，記為L=＜t1,t2,t3,t4,t5,t6＞，表示該流程被執行了6次，生成了6個事件軌跡，對應的事件為{e1,e2,e3,···,e17}，其出現的任務活動有{a,b,c}。

表1 流程事件日志實例Table 1 The instance process event log

1.3 變遷發生關系的相關定義

對于流程模型變遷之間的發生關系，有如下5個定義[19]。

定義5順序關系。無論庫所節點的前置節點和后繼節點的個數，該庫所節點的任意前置節點和任意后繼節點之間的發生關系均為順序關系，用符號 →表示，即當x∈P,·x={y1,y2∈T},x·={z1,z2∈T}時，有y1→z1,y1→z2,y2→z1,y2→z2。

定義6并行關系。當且僅當不同的庫所節點的前置節點或后繼節點為同一變遷節點時，其不同的庫所節點對應的后繼節點或前置節點之間的發生關系為并行關系，用符號 &表示，即當且僅當x1,x2∈P，·x1=·x2={y∈T},x1·={z1∈T},x2·={z2∈T} 或·x1={y1∈T},·x2={y2∈T},x1·,x2·={z∈T} ， 分別有yz1&yz2或y1z&y2z。

定義7選擇關系。當且僅當庫所節點的前置節點或后繼節點為多個變遷節點時，該庫所節點的前置節點之間或后繼節點之間的發生關系為選擇關系，用符號|表 示， 當x∈P,·x={y1,y2∈T},x·={z1,z2∈T}， 有y1z1|y1z2,y2z1|y2z2,y1z1|y2z1,y1z2|y2z2。

定義8循環關系。當且僅當不同的庫所節點的前置節點和后繼節點為同一變遷節點時，其不同的庫所節點對應的后繼節點和前置節點之間的所有變遷節點與上述同一變遷節點所構成的發生關系為循環發生關系，用符號@ 表示，即當x1,x2,x4∈P，x1·={z1∈T},x2·={z2∈T},·x4={z3∈T}，·x1=x4·={y∈T}，有yz1@yz2@yz3。

定義9緊鄰變遷對。對于同一個庫所節點，無論前置節點和后繼節點的個數，只要是分別由該庫所節點的前置節點和后繼節點構成的一對變遷，均稱為緊鄰變遷對，且變遷對的變遷節點關系是順序關系，即當x∈P,·x={y1,y2∈T},x·={z1,z2∈T}時，有緊鄰變遷對(y1,z1),(y1,z2),(y2,z1),(y2,z2)， 且有y1→z1,y1→z2,y2→z1,y2→z2。

2 流程相似性度量方法

基于廣度優先遍歷的加權序列的流程相似度計算方法主要分為3個步驟：(1) 將事件日志中的行為信息進行處理，獲取活動之間的頻次比，并作為Petri網中相鄰變遷的邊系數；(2) 使用廣度優先遍歷將帶邊系數的加權Petri網模型轉換為字符串序列；(3) 最后計算流程之間的相似度值。

2.1 加權Petri網的構建

對企業內流程實際運行過程中產生的事件日志，或是對模擬生成的事件日志進行操作；然后得到流程模型的行為序列軌跡及其在事件日志中出現的次數，記為：

式中：根據定義9，緊鄰變遷對在流程事件日志中表現為兩兩相鄰的一對任務，即緊鄰任務對，記作σi=(ei,ei+1)，并將所有緊鄰任務對組合的集合稱為緊鄰任務對集，記作Λ =(σ1,σ2,···,σn)。 緊鄰任務對σi∈Λ在流程事件日志中出現的頻次與軌跡總數的占比記為F(σi,L) ， 并將F(σi,L)作為Petri網的緊鄰變遷對與庫所節點分別相連的兩條邊的權重系數，當Petri網的某條邊有多個權重系數時，則將這多個權重系數的和作為該條邊的權重系數，從而構建加權的Petri網流程模型。

如圖1所示為某一流程的Petri網流程模型以及對應的加權Petri網，該流程模型的行為序列軌跡及各軌跡在事件日志中出現的次數表示為

圖1 Petri網流程模型及對應的加權Petri網Fig.1 Petri net flow model and the corresponding weighted Petri net

2.2 廣度優先遍歷序列

廣度優先遍歷序列(Breadth-First Traversal Sequence，BFTS)是指在圖中先定義一個起始節點，然后把與起始節點相鄰的幾個節點依次進行遍歷，再遍歷距離起始節點稍遠一些的節點(相隔一層)，然后再遍歷距離起始節點更遠一些的節點(相隔兩層)，一層一層地向外遍歷，直到遍歷所有節點，最后按遍歷順序將這些節點排序，形成廣度優先遍歷序列。

在Petri網中，基于圖的廣度優先遍歷序列[15]，在每一層遍歷中，根據字母表的順序判斷遍歷結果的順序，即將遍歷得到的變遷節點(活動任務)以字典序列的方式進行排序，形成字符串序列，定義為StringBFTS=S#σ1Rσ2#···#σn-1Rσn#E。其中，為了使轉換后的序列能夠有效描述Petri網的完整信息，首尾的S,E是添加的虛擬變遷節點，作為遍歷的開始標志和結束標志；σi是指上文中提到的緊鄰變遷對，σiRσj中R表示緊鄰變遷對之間的關系，具體指變遷之間的關系：順序、并行、選擇和循環關系；為了更好地分析業務流程中活動任務之間的關系，對廣度優先遍歷所得到的每一層結果進行分層，符號“#”作為每層的分隔標志。

2.3 加權Petri網與BFTS的轉換

在進行轉換的過程中，基于廣度優先遍歷算法的特點，對每一個遍歷節點記錄它的相鄰節點及其關系，并且使用符號“#”對每一個遍歷層的遍歷結果進行分層，這樣能夠更好地體現流程之間的結構信息。Petri網與BFTS的轉換步驟如下：

(1) 對Petri網進行預處理，輸入所有的庫所節點和其相鄰的變遷節點及邊系數值，定位起始庫所節點，其前置節點為S。

(2) 對當前遍歷的庫所節點搜索其前置節點和后繼節點并存儲；然后以簡化后的帶權重值的緊鄰變遷對形式記錄這些前置節點和后繼節點。

(3) 根據1.3節的相關定義，判斷步驟2記錄的緊鄰變遷對之間的關系，并用相關符號將這些緊鄰變遷對隔開以表示其關系，每層的遍歷結果用符號“#”隔開。

(4) 如果當前遍歷的庫所節點的后繼節點是E，則該庫所節點為最后一個遍歷節點，遍歷結束，形成以S為開頭，E為結尾的BFTS。

為了更好地描述節點之間的關系和緊鄰變遷對之間的關系的判斷過程，將前置節點用Y表示，后繼節點用Z表示，下面對判斷規則進行介紹。

(1) 庫所節點的前置節點集合和后繼節點集合里分別選擇一個節點組成節點對，稱為緊鄰變遷對，取它們中較小的邊系數值作為該緊鄰變遷對的權重值，帶權重值的緊鄰變遷對記為σ 。其中，節點對的關系為順序關系Y→Z，為了方便記錄，將符號” →”省略，若其權重值為0.5，則將簡化的帶權重值的緊鄰變遷對記為σ =0.5YZ。

(2) 當遍歷的庫所節點的前置節點或后繼節點有多個時，則分別從前置節點和后繼節點各選擇一個節點，節點構成的緊鄰變遷對 σi,σj之間的關系若為選擇關系，記為σi|σj。

(3) 若當前遍歷庫所節點的前置節點(后繼節點)與另一已遍歷庫所節點的前置節點(后繼節點)相同時，則其緊鄰變遷對 σi,σj之間為并行關系，記為σi&σj。

(4) 如果當前遍歷庫所節點的某一后繼節點是另一已遍歷庫所節點的前置節點，該后繼節點與另一已遍歷庫所節點的前置節點內之間的所有變遷節點組成新的緊鄰變遷對,等之間的關系為循環關系，其新的權重值為循環邊系數與原緊鄰變遷對的權重值的乘積，記為σ@σ@σ。

下面用一個加權Petri網流程模型的例子對每一條規則進行詳細說明，如圖2所示。

圖2 加權Petri網流程模型Fig.2 Weighted Petri net flow model

(1) 首先定位在起始庫所節點，其前置節點為添加的節點S，對該庫所節點搜索到后繼節點a，并且其邊系數值為1，從而得到緊鄰變遷對σ1=S a，第一層結束，并添加符號“#”。

(2) 遍歷第二層，其第二層的第一個庫所節點搜索到前置節點a、f，后繼節點b、c，并且其邊系數分別為1、1.2和0.7、0.5，從而得到緊鄰變遷對σ2=0.7ab，σ3=0.5ac，σ4=0.7fb，σ5=0.5fc，這些緊鄰變遷對之間的關系為選擇關系，有σ2|σ3|σ4|σ5；第二層的第二個庫所節點搜索到前置節點a，后繼節點d，邊系數均為1，得到緊鄰變遷對 σ6=ad，由于這兩個庫所節點的前置節點a相同，所以有并行關系σ6&(σ2|σ3)，第二層結束，添加符號“#”。

(3) 遍歷第三層，第一個庫所節點搜索到前置節點b、c，后繼節點e，邊系數分別為0.7、0.5和1.2，得到緊鄰變遷對σ7=0.7be，σ8=0.5ce， 有選擇關系σ7|σ8；第二個庫所節點搜索到前置節點d，后繼節點g，邊系數均為1，得到緊鄰變遷對σ9=dg，第三層結束，添加符號“#”。

(5) 遍歷第五層，該庫所節點搜索到前置節點g，后繼節點為添加的節點E，邊系數為1，得到緊鄰變遷對為σ12=gE，遍歷結束。得到Petri網的轉換結果為

將轉換得到的廣度優先遍歷序列展開有

將帶邊系數值的Petri網流程模型轉換成BFTS的算法，具體如算法1所示。

算法1使用廣度優先遍歷將加權Petri網流程模型N=(P,T,F)轉換成字符串序列Str，字符串序列Str存儲了流程模型的所有活動節點、活動序列及其邏輯結構，保存著活動節點之間依賴的行為信息及相應活動節點之間邏輯的結構信息。

2.4 相似度計算

從模型結構和流程行為兩個維度進行流程相似性的計算。在由Petri網轉換成的字符串序列中，字符對與字符對之間的邏輯關系表示模型結構，字符與字符的依賴關系表示流程行為。首先將BFTS序列中含手動添加的首尾節點S、E的緊鄰變遷對刪除，再將其他代表活動與活動之間依賴關系的緊鄰變遷對提取出來，并獲取該緊鄰變遷對的權重值，形成一個帶權重值的緊鄰變遷對集，稱為行為集合，用來表示流程行為信息。然后再將BFTS序列中代表字符對與字符對之間邏輯關系的特殊符號提取出來，其中，循環部分的特殊符號只提取一個符號“@”，然后形成一個結構字符串，用來表示模型結構信息，稱為結構序列。最后，運用多集的交并運算和字符串編輯距離的方法分別計算其相似度，并將這兩個相似度值進行加權求和，最終得到兩個流程模型之間的相似度值。

2.4.1 多集的交并運算過程及計算公式

由帶權重值的緊鄰變遷對組合成的行為集合可以被看作是一個多集，該多集中每個元素由兩個部分組成：一是用數值表示的權重大小，二是用兩個相鄰的活動名稱形成的一對字符。因此，計算該多集的相似度不能簡單地通過判斷集合中相同元素的個數來計算，而是需要根據交并運算來計算。假設A和B是兩個由上述部分組成的多集，下面具體介紹A和B的交并運算過程。

定義這兩個多集A={α1e1e2,···,αmei-1ei}和B={β1e1e2,···,βnej-1ej}， 其多集的元素個數分別為m和n，緊鄰變遷對用 σ表示，每個緊鄰變遷對 σ的權重值分別為α1,···,αm和 β1,···,βn。則這兩個多集的交并運算如下：

2.4.2 字符串編輯距離

字符串編輯距離定義為將一個字符串轉換成另一個字符串的最小字符編輯操作數，其編輯操作包括字符的插入、刪除和替換，每個操作的權重值均設定為1。然后，將字符串之間的編輯距離除以字符串中較長字符串的長度值，使編輯距離值轉換為字符串的相似度值，這樣便將多個字符串之間的距離計算結果統一化，從而有效對比分析字符串之間的相似性。給定兩個結構字符串S1和S2，定義它們之間的相似度為

式中： SimS(S1,S2)表示兩個字符串之間的相似度，max(len(S1),len(S2))表示兩個字符串中較長字符串的長度值， dist(S1,S2)表示字符串的編輯操作數，|skip|表示字符串轉換過程中需要插入或刪除的字符個數， |sub|表示字符串轉換過程中需要替換的字符個數。

2.4.3 加權求和計算

最后，對行為集合相似度和結構序列相似度進行加權，最終得到兩個流程模型之間的相似度，其計算公式為

式中：S im(N1,N2)表 示兩個流程模型N1和N2之間的相似度， θ表示流程的行為集合對流程模型的重要性系數，記為流程行為相似性的權重參數，可以根據所檢索的流程模型對活動名稱、模型結構和流程行為的注重程度進行賦值，假設流程模型中行為和結構對最終結果的重要性相同，對θ 參數賦值為0.5。

為了更好地描述相似度計算過程，給出兩個Petri網流程模型P0和P1， 如圖3所示。其中P1是 基于P0改變獲得的，對其刪除了一個活動節點及對應的并行結構，并且增加了一個活動節點及對應的循環結構。

圖3 P 0 和 P1的Petri網流程模型Fig.3 Petri net flow models of P 0 andP1

首先，將圖3中的兩個Petri網流程模型構造加權Petri網；然后基于轉換規則將其轉換成BFTS，得到相應的字符串序列，如表2所示；其次，對BFTS提取相應的行為集合和結構序列，其結果如表3所示；最后，通過式 (2) 和 (3) 計算行為集合相似度和結構序列相似度，有 SimB(A,B)=3/5.4 和S imS(S1,S2)=2/5，再通過式 (4) 加權求和，得到這兩個Petri網流程模型的最終相似度值為S im(P0,P1)=0.478。

表2 P 0 和 P1的轉換結果Table 2 The conversion results of P 0 and P1

表3 P 0 和P 1的BFTS提取結果Table 3 BFTS extraction results of P 0 andP1

3 實驗設計與分析

為了衡量提出的度量方法的特點和優勢，本實驗選擇了3種具有代表性的相似度計算方法與之對比：基于變遷圖編輯距離的流程相似性算法[8](TGED)、基于觸發序列集合的流程模型行為相似性算法[7](PTS++)和基于模型結構與日志行為的流程相似度算法(WBPG)[11]。TGED方法是從模型結構的角度，通過圖編輯距離的方式計算流程相似度；PTS++方法是從流程行為角度，通過統計處理任務之間的發生關系來計算相似度值，而WBPG方法則是從模型結構和流程行為的綜合角度，并通過圖編輯距離的方式計算相似度值。

3.1 實驗數據

本實驗的數據集來自文獻[20]，其數據集中的檢索流程P0來源于一個真實的業務流程，其Petri網流程模型如圖4所示。然后對其進行處理后建立基準數據集： (1) 創建混淆流程，即加入一個不相關的流程模型作為相關流程； (2) 改造相關流程，人為地改造了對應的9個相關流程； (3) 對相關流程進行排序，通過用戶調查，對所有流程模型P1～P10進行排序。改造相關流程時主要在于分支結構和權重的變化，包括刪除、添加分支結構及分支結構的性質變化；其中，分支結構有選擇、并行和循環結構。

圖4 檢索流程 P0的Petri網模型Fig.4 Petri Net modelof the retrieval process P0

3.2 實驗結果分析

實驗過程中，對檢索流程及其相關流程模型進行仿真，模擬流程模型的執行，產生事件日志并作為對應的行為信息，加權至Petri網中構造加權Petri網模型；然后經過廣度優先搜索算法獲得相應的字符串序列，再通過式 (2) 和 (3) 計算行為集合相似度和結構序列相似度，最后經式 (4) 加權計算得到相關流程P1～P10與 檢索流程P0之間的相似度值。將方法與上述提到的3種方法進行比較，其對應的相似度值如表4所示。

表4 不同方法的度量結果Table 4 The measurement results of different methods

基于表4中各方法計算得到的相似度值大小對這10個相關流程進行從大到小的排序。另外，根據文獻[16]的用戶調查，采訪了23位領域專家，分別根據自己的專業知識對該檢索流程的相關流程進行相似度大小的排序，即基于相關流程與檢索流程的相似程度，從大到小進行排序，最后將這些專家的排序結果進行整合，得到這些相關流程的一個基準排序結果。然后根據基準排序結果賦予對應序號的相關流程一個權重(本實驗對排在第1名的流程模型賦予權重0.9，后面依次遞減0.05，至最后第10名為0.45)，最后得到如表5所示的排序結果。

表5 相似度排序結果Table 5 The sorting results of similarity

該實驗選擇歸一化折損累計增益(Normalized Discounted Cumulative Gain，NDCG)對度量方法的準確率進行評估，其計算公式為

式中：NDCG用來衡量相似性的度量準確性，DCG(Discounted Cumulative Gain)用來表示在實驗情況下的增加相關度影響比重，IDCG(Ideal Discounted Cumulative Gain)用來表示在理想情況下的增加相關度影響比重，p表示預設流程模型的數量，a表示實驗排序結果中的排序位置， rela表示實驗排序結果中排在第a位的預設流程模型對應的權重值，b表示基準排序結果中的排序位置， relb表示基準排序結果中排在第b位的預設流程模型對應的權重值。

基于表5的排序結果及相應的權重值，通過式(5)計算各度量方法的NDCG值，從而將流程相似性度量的準確率數值化，計算結果如表6所示。

表6 不同方法排序結果的評估結果Table 6 Evaluation results of sorting results based on different methods

NDCG值可以體現出這些方法的度量結果與專家給出的基準排序結果的吻合程度，其中NDCG值越大，吻合程度越高，即度量方法越準確。從表6中的數據可以看出，本文提出的度量方法有很好的度量準確性，其準確率高達99.51%，優于其他3種度量方法，更符合領域專家判定的結果。

3.3 方法評估

當前企業有著數以萬計的大規模業務流程，企業已經不僅僅關心流程檢索的準確度，也看重其檢索的效率，從而減少檢索過程中所花費的時間和成本。值得一提的是，本文方法由于將圖編輯距離替換成了字符串編輯距離，在檢索效率方面有著比較大的優勢，本文方法與其他方法的時間復雜度如表7所示。

表7 時間復雜度對比Table 7 The comparison of time complexity

本文采用廣度優先遍歷算法將流程模型轉換成了字符串序列，然后通過字符串編輯距離以及多集的交并運算來計算流程相似度，避免了高復雜度的圖編輯距離。圖編輯距離的時間復雜度為O(n3)，這在大規模的業務流程庫的流程檢索中的時間消耗會成倍增加，其檢索效率低下；而廣度優先遍歷算法的復雜度為O(n) ，字符串編輯距離的復雜度為O(m*n)，多集的交并運算的復雜度為O(m+n)，當業務流程庫的規模越大，其相對于圖編輯距離的時間消耗就越少，所以本文方法在檢索的時間效率上有著不錯的優勢。本文方法的優勢還在于，由于沒有采用圖編輯距離，從而避免了對圖的邊和節點處理的編輯操作，這些處理包括節點和邊的插入、刪除和替換，每個編輯操作代價是通過相應的代價函數得出的，而這些編輯操作的代價函數定義困難，所以本文方法計算起來更簡單，也更容易理解。另外，相比于其他方法，還對文本、結構和行為3個方面都進行了分析度量，所以，對于不同場景下的業務流程一樣具有很好的度量效果，解決了單一維度下的相似性度量帶來的適應能力不足的問題。綜上所述，在時間復雜度和準確度方面，本文方法相比于其他度量方法都有更好的效果。

4 結論

為了解決已有流程相似性度量方法存在的一些問題，提高在流程模型庫中檢索到相似流程的效率，提出一種基于廣度優先遍歷的加權序列的流程相似性度量方法。該方法同時考慮了多種屬性進行流程相似性的度量，首先基于事件日志中的信息構造加權Petri網，然后使用廣度優先遍歷將加權Petri網模型轉換為廣度優先遍歷序列(BFTS)，并且給出了詳細的轉換規則，再將該序列分為一個帶權重的緊鄰變遷對集和一個結構序列，最后通過加權這兩部分來計算流程之間的相似度值。通過實驗對比和分析，提出的方法比其他3種方法有更好的度量準確率以及有著更高的檢索效率，可以更加準確地推薦相似流程。但是，方法在計算過程中，還需要提供流程的事件日志，其計算的輸入條件相比其他方法更多一些，另外，本文的實驗基礎是相關領域專家給出的人造數據集，未來的工作主要在于如何將方法運用到實際的大量真實的流程數據集中。