胡迎城，邢瑪麗，吳元清

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

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

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

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

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

1 相關(guān)知識(shí)

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

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

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

1.2 流程事件日志

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

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

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

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

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

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

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

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

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

定義6并行關(guān)系。當(dāng)且僅當(dāng)不同的庫所節(jié)點(diǎn)的前置節(jié)點(diǎn)或后繼節(jié)點(diǎn)為同一變遷節(jié)點(diǎn)時(shí)，其不同的庫所節(jié)點(diǎn)對(duì)應(yīng)的后繼節(jié)點(diǎn)或前置節(jié)點(diǎn)之間的發(fā)生關(guān)系為并行關(guān)系，用符號(hào) &表示，即當(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é)點(diǎn)的前置節(jié)點(diǎn)或后繼節(jié)點(diǎn)為多個(gè)變遷節(jié)點(diǎn)時(shí)，該庫所節(jié)點(diǎn)的前置節(jié)點(diǎn)之間或后繼節(jié)點(diǎn)之間的發(fā)生關(guān)系為選擇關(guān)系，用符號(hào)|表 示， 當(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é)點(diǎn)的前置節(jié)點(diǎn)和后繼節(jié)點(diǎn)為同一變遷節(jié)點(diǎn)時(shí)，其不同的庫所節(jié)點(diǎn)對(duì)應(yīng)的后繼節(jié)點(diǎn)和前置節(jié)點(diǎn)之間的所有變遷節(jié)點(diǎn)與上述同一變遷節(jié)點(diǎn)所構(gòu)成的發(fā)生關(guān)系為循環(huán)發(fā)生關(guān)系，用符號(hào)@ 表示，即當(dāng)x1,x2,x4∈P，x1·={z1∈T},x2·={z2∈T},·x4={z3∈T}，·x1=x4·={y∈T}，有yz1@yz2@yz3。

定義9緊鄰變遷對(duì)。對(duì)于同一個(gè)庫所節(jié)點(diǎn)，無論前置節(jié)點(diǎn)和后繼節(jié)點(diǎn)的個(gè)數(shù)，只要是分別由該庫所節(jié)點(diǎn)的前置節(jié)點(diǎn)和后繼節(jié)點(diǎn)構(gòu)成的一對(duì)變遷，均稱為緊鄰變遷對(duì)，且變遷對(duì)的變遷節(jié)點(diǎn)關(guān)系是順序關(guān)系，即當(dāng)x∈P,·x={y1,y2∈T},x·={z1,z2∈T}時(shí)，有緊鄰變遷對(duì)(y1,z1),(y1,z2),(y2,z1),(y2,z2)， 且有y1→z1,y1→z2,y2→z1,y2→z2。

2 流程相似性度量方法

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

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

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

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

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

圖1 Petri網(wǎng)流程模型及對(duì)應(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)是指在圖中先定義一個(gè)起始節(jié)點(diǎn)，然后把與起始節(jié)點(diǎn)相鄰的幾個(gè)節(jié)點(diǎn)依次進(jìn)行遍歷，再遍歷距離起始節(jié)點(diǎn)稍遠(yuǎn)一些的節(jié)點(diǎn)(相隔一層)，然后再遍歷距離起始節(jié)點(diǎn)更遠(yuǎn)一些的節(jié)點(diǎn)(相隔兩層)，一層一層地向外遍歷，直到遍歷所有節(jié)點(diǎn)，最后按遍歷順序?qū)⑦@些節(jié)點(diǎn)排序，形成廣度優(yōu)先遍歷序列。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(5) 遍歷第五層，該庫所節(jié)點(diǎn)搜索到前置節(jié)點(diǎn)g，后繼節(jié)點(diǎn)為添加的節(jié)點(diǎn)E，邊系數(shù)為1，得到緊鄰變遷對(duì)為σ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存儲(chǔ)了流程模型的所有活動(dòng)節(jié)點(diǎn)、活動(dòng)序列及其邏輯結(jié)構(gòu)，保存著活動(dòng)節(jié)點(diǎn)之間依賴的行為信息及相應(yīng)活動(dòng)節(jié)點(diǎn)之間邏輯的結(jié)構(gòu)信息。

2.4 相似度計(jì)算

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

2.4.1 多集的交并運(yùn)算過程及計(jì)算公式

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

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

2.4.2 字符串編輯距離

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

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

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

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

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

為了更好地描述相似度計(jì)算過程，給出兩個(gè)Petri網(wǎng)流程模型P0和P1， 如圖3所示。其中P1是 基于P0改變獲得的，對(duì)其刪除了一個(gè)活動(dòng)節(jié)點(diǎn)及對(duì)應(yīng)的并行結(jié)構(gòu)，并且增加了一個(gè)活動(dòng)節(jié)點(diǎn)及對(duì)應(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中的兩個(gè)Petri網(wǎng)流程模型構(gòu)造加權(quán)Petri網(wǎng)；然后基于轉(zhuǎn)換規(guī)則將其轉(zhuǎn)換成BFTS，得到相應(yīng)的字符串序列，如表2所示；其次，對(duì)BFTS提取相應(yīng)的行為集合和結(jié)構(gòu)序列，其結(jié)果如表3所示；最后，通過式 (2) 和 (3) 計(jì)算行為集合相似度和結(jié)構(gòu)序列相似度，有 SimB(A,B)=3/5.4 和S imS(S1,S2)=2/5，再通過式 (4) 加權(quán)求和，得到這兩個(gè)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àn)設(shè)計(jì)與分析

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

3.1 實(shí)驗(yàn)數(shù)據(jù)

本實(shí)驗(yàn)的數(shù)據(jù)集來自文獻(xiàn)[20]，其數(shù)據(jù)集中的檢索流程P0來源于一個(gè)真實(shí)的業(yè)務(wù)流程，其Petri網(wǎng)流程模型如圖4所示。然后對(duì)其進(jìn)行處理后建立基準(zhǔn)數(shù)據(jù)集： (1) 創(chuàng)建混淆流程，即加入一個(gè)不相關(guān)的流程模型作為相關(guān)流程； (2) 改造相關(guān)流程，人為地改造了對(duì)應(yīng)的9個(gè)相關(guān)流程； (3) 對(duì)相關(guān)流程進(jìn)行排序，通過用戶調(diào)查，對(duì)所有流程模型P1～P10進(jìn)行排序。改造相關(guān)流程時(shí)主要在于分支結(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 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

表6 不同方法排序結(jié)果的評(píng)估結(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)確率高達(dá)99.51%，優(yōu)于其他3種度量方法，更符合領(lǐng)域?qū)＜遗卸ǖ慕Y(jié)果。

3.3 方法評(píng)估

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

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

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

4 結(jié)論

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