加權(quán)Petri網(wǎng)的字符串序列相似性度量

胡迎城，邢瑪麗，吳元清

（廣東工業(yè)大學(xué) 自動化學(xué)院, 廣東 廣州 510006）

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

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

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

本文使用廣度優(yōu)先遍歷的方法將Petri網(wǎng)轉(zhuǎn)換為字符串序列，在不降低準(zhǔn)確率的基礎(chǔ)上，避免了復(fù)雜度高的圖編輯距離，很大程度上提高了流程的檢索效率。

1 相關(guān)知識

1.1 加權(quán)Petri網(wǎng)

Petri網(wǎng)是一種形式化的方法，用來描述業(yè)務(wù)流程的執(zhí)行過程，將業(yè)務(wù)流程的執(zhí)行過程表達成一個圖的形式。其中，圖中的每個節(jié)點都代表一個活動或狀態(tài)信息。另外，現(xiàn)在很多企業(yè)都將Petri網(wǎng)作為業(yè)務(wù)流程的表達形式，并將Petri網(wǎng)作為相關(guān)軟件的輸入輸出，因此，選擇Petri網(wǎng)作為業(yè)務(wù)流程相似性的研究對象，其定義如下。

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

1.2 流程事件日志

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

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

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

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

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

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

1.3 變遷發(fā)生關(guān)系的相關(guān)定義

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

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

定義6并行關(guān)系。當(dāng)且僅當(dāng)不同的庫所節(jié)點的前置節(jié)點或后繼節(jié)點為同一變遷節(jié)點時，其不同的庫所節(jié)點對應(yīng)的后繼節(jié)點或前置節(jié)點之間的發(fā)生關(guān)系為并行關(guān)系，用符號 &表示，即當(dāng)且僅當(dāng)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選擇關(guān)系。當(dāng)且僅當(dāng)庫所節(jié)點的前置節(jié)點或后繼節(jié)點為多個變遷節(jié)點時，該庫所節(jié)點的前置節(jié)點之間或后繼節(jié)點之間的發(fā)生關(guān)系為選擇關(guān)系，用符號|表 示， 當(dāng)x∈P,·x={y1,y2∈T},x·={z1,z2∈T}， 有y1z1|y1z2,y2z1|y2z2,y1z1|y2z1,y1z2|y2z2。

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

定義9緊鄰變遷對。對于同一個庫所節(jié)點，無論前置節(jié)點和后繼節(jié)點的個數(shù)，只要是分別由該庫所節(jié)點的前置節(jié)點和后繼節(jié)點構(gòu)成的一對變遷，均稱為緊鄰變遷對，且變遷對的變遷節(jié)點關(guān)系是順序關(guān)系，即當(dāng)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 流程相似性度量方法

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

2.1 加權(quán)Petri網(wǎng)的構(gòu)建

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

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

如圖1所示為某一流程的Petri網(wǎng)流程模型以及對應(yīng)的加權(quán)Petri網(wǎng)，該流程模型的行為序列軌跡及各軌跡在事件日志中出現(xiàn)的次數(shù)表示為

圖1 Petri網(wǎng)流程模型及對應(yīng)的加權(quán)Petri網(wǎng)Fig.1 Petri net flow model and the corresponding weighted Petri net

2.2 廣度優(yōu)先遍歷序列

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

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

2.3 加權(quán)Petri網(wǎng)與BFTS的轉(zhuǎn)換

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

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

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

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

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

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

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

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

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

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

下面用一個加權(quán)Petri網(wǎng)流程模型的例子對每一條規(guī)則進行詳細說明，如圖2所示。

圖2 加權(quán)Petri網(wǎng)流程模型Fig.2 Weighted Petri net flow model

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

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

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

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

將轉(zhuǎn)換得到的廣度優(yōu)先遍歷序列展開有

將帶邊系數(shù)值的Petri網(wǎng)流程模型轉(zhuǎn)換成BFTS的算法，具體如算法1所示。

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

2.4 相似度計算

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

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

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

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

2.4.2 字符串編輯距離

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

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

2.4.3 加權(quán)求和計算

最后，對行為集合相似度和結(jié)構(gòu)序列相似度進行加權(quán)，最終得到兩個流程模型之間的相似度，其計算公式為

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

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

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

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

表2 P 0 和 P1的轉(zhuǎn)換結(jié)果Table 2 The conversion results of P 0 and P1

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

3 實驗設(shè)計與分析

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

3.1 實驗數(shù)據(jù)

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

圖4 檢索流程 P0的Petri網(wǎng)模型Fig.4 Petri Net modelof the retrieval process P0

3.2 實驗結(jié)果分析

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

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

基于表4中各方法計算得到的相似度值大小對這10個相關(guān)流程進行從大到小的排序。另外，根據(jù)文獻[16]的用戶調(diào)查，采訪了23位領(lǐng)域?qū)＜遥謩e根據(jù)自己的專業(yè)知識對該檢索流程的相關(guān)流程進行相似度大小的排序，即基于相關(guān)流程與檢索流程的相似程度，從大到小進行排序，最后將這些專家的排序結(jié)果進行整合，得到這些相關(guān)流程的一個基準(zhǔn)排序結(jié)果。然后根據(jù)基準(zhǔn)排序結(jié)果賦予對應(yīng)序號的相關(guān)流程一個權(quán)重(本實驗對排在第1名的流程模型賦予權(quán)重0.9，后面依次遞減0.05，至最后第10名為0.45)，最后得到如表5所示的排序結(jié)果。

表5 相似度排序結(jié)果Table 5 The sorting results of similarity

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

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

基于表5的排序結(jié)果及相應(yīng)的權(quán)重值，通過式(5)計算各度量方法的NDCG值，從而將流程相似性度量的準(zhǔn)確率數(shù)值化，計算結(jié)果如表6所示。

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

NDCG值可以體現(xiàn)出這些方法的度量結(jié)果與專家給出的基準(zhǔn)排序結(jié)果的吻合程度，其中NDCG值越大，吻合程度越高，即度量方法越準(zhǔn)確。從表6中的數(shù)據(jù)可以看出，本文提出的度量方法有很好的度量準(zhǔn)確性，其準(zhǔn)確率高達99.51%，優(yōu)于其他3種度量方法，更符合領(lǐng)域?qū)＜遗卸ǖ慕Y(jié)果。

3.3 方法評估

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

表7 時間復(fù)雜度對比Table 7 The comparison of time complexity

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

4 結(jié)論

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