吳亞鋒　譚文安，2

（1.南京航空航天大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院　南京　211106）（2.上海第二工業(yè)大學(xué)計算機(jī)與信息學(xué)院　上?！?01209）

1　引言

在當(dāng)今飛速發(fā)展的商業(yè)環(huán)境中，工作流技術(shù)得到工業(yè)界和學(xué)術(shù)界的廣泛關(guān)注和深入研究，業(yè)務(wù)流程已經(jīng)成為各類企業(yè)規(guī)范業(yè)務(wù)邏輯、高效處理業(yè)務(wù)流程的重要手段。通常為了保證企業(yè)的正常運作，不同企業(yè)部門的業(yè)務(wù)流程需要進(jìn)行配合。同時，隨著商業(yè)環(huán)境、客戶需求和業(yè)務(wù)邏輯的不斷變化，企業(yè)需要及時制定新的業(yè)務(wù)流程或改進(jìn)原有業(yè)務(wù)流程來應(yīng)對外界環(huán)境的變化。因此，一個大型集團(tuán)企業(yè)大多會積累成百甚至數(shù)以千計的業(yè)務(wù)流程。為了高效管理積累下來的業(yè)務(wù)流程，各企業(yè)一般會建立自己的業(yè)務(wù)流程庫。復(fù)雜的大規(guī)模業(yè)務(wù)流程庫管理需要建立有效的流程索引和檢索機(jī)制，而流程的索引和檢索問題，首先要解決的就是流程間距離的計算問題，即業(yè)務(wù)流程的相似性問題。流程的相似性需求有著及其廣泛的應(yīng)用前景，例如：在業(yè)務(wù)流程整合過程中分析相似的業(yè)務(wù)流程，可以避免重復(fù)存儲對整合效率的影響；在對流程庫進(jìn)行壓縮時，可以選擇相似流程類中的一個業(yè)務(wù)流程作為代表流程進(jìn)行存儲；不同組織部門的業(yè)務(wù)流程進(jìn)行相似性分析，可以發(fā)現(xiàn)不同部門之間的合作關(guān)系，從而可以相互借鑒、相互學(xué)習(xí)；過程挖掘以及過程集成等許多業(yè)務(wù)過程管理的應(yīng)用，都需要度量業(yè)務(wù)流程之間的相似性。

目前業(yè)務(wù)流程相似性度量一般基于三個方面：1）文本、節(jié)點標(biāo)簽；2）業(yè)務(wù)流程拓?fù)浣Y(jié)構(gòu)；3）業(yè)務(wù)流程行為軌跡。文本內(nèi)容相似度的計算主要從節(jié)點的語法、語義、屬性、類型和節(jié)點上下文進(jìn)行計算［1～7］，這類方法計算簡單、快捷，只需計算節(jié)點對應(yīng)標(biāo)簽文本的相似度。然而，當(dāng)流程結(jié)構(gòu)發(fā)生改變影響流程間相似度時，該方法卻無法捕獲，因此準(zhǔn)確性不是很高。流程結(jié)構(gòu)相似度計算主要指流程拓?fù)浣Y(jié)構(gòu)的相似度。流程的拓?fù)浣Y(jié)構(gòu)主要體現(xiàn)了流程中的各個業(yè)務(wù)邏輯單元是通過何種邏輯關(guān)系連接起來的?，F(xiàn)有的流程結(jié)構(gòu)相似度［8～12］的研究大都是基于某種編輯距離來取得的，如圖編輯距離、樹編輯距離等。然而，流程結(jié)構(gòu)相似度的計算僅考慮其靜態(tài)拓?fù)浣Y(jié)構(gòu)并不能完全體現(xiàn)業(yè)務(wù)流程的具體行為和真實功能，無法響應(yīng)動態(tài)改變的外部環(huán)境。關(guān)于流程行為相似度的計算，早期的方法主要集中于流程行為等價方面，如軌跡等價［13］、互模擬等價［14］等。然而，這些等價概念只能得到一個布爾值，即等價與非等價，不能精確地給出流程間的相似度值，因此，在大多數(shù)實際應(yīng)用中是無效的?，F(xiàn)有計算結(jié)果比較好的流程行為相似度計算方法有：因果足跡法［1］、緊鄰變遷關(guān)系法［15］、行為輪廓法［16～17］和主變遷序列法［18］等。

本文方法參考文獻(xiàn)［19］中使用的鄰接矩陣來計算流程間距離，然而文獻(xiàn)［19］的方法沒有考慮不同控制節(jié)點的語義信息，因而無法區(qū)分不同控制節(jié)點間的差異。本文方法從流程模型的結(jié)構(gòu)入手，首先給出帶邊權(quán)重的工作流網(wǎng)，然后使用帶邊權(quán)重的工作流網(wǎng)關(guān)聯(lián)矩陣表示流程模型結(jié)構(gòu)，通過計算對應(yīng)帶邊權(quán)重的工作流網(wǎng)關(guān)聯(lián)矩陣之間的距離來表示相應(yīng)流程模型間的距離。

2　基礎(chǔ)知識

首先介紹本文方法需要的一些基礎(chǔ)知識，主要包括Petri網(wǎng)基本概念、工作流網(wǎng)概念，工作流網(wǎng)建模所用的基本組件以及Petri網(wǎng)的關(guān)聯(lián)矩陣表示。

2.1　Petri網(wǎng)

Petri網(wǎng)是一種用于描述離散的、分布式系統(tǒng)的數(shù)學(xué)建模工具。它既能描述系統(tǒng)的結(jié)構(gòu)，又能描述系統(tǒng)的運行。描述系統(tǒng)結(jié)構(gòu)的部分稱為網(wǎng)。從形式上看，一個網(wǎng)就是一個沒有孤立節(jié)點的有向二分圖。

定義1（Petri網(wǎng)）滿足下列條件的三元組（P，T，F(xiàn)）稱為Petri網(wǎng)：

1）P∪T≠?

2）P∩T=?

3）F?(P×T)∪(P×T)

4）dom(F)∪cod(F)=P∪T其中：P是庫所的有限集合，T是變遷的有限集合，F(xiàn)是網(wǎng)的流關(guān)系。在建模過程中，一般使用庫所代表條件，變遷代表事件。一個變遷有一定數(shù)量的輸入和輸出庫所，分別代表可以使用的資源或者數(shù)據(jù)。

如圖1所示的Petri網(wǎng)實例是由4個庫所{p1，p2，p3，p4}和4個變遷{t1，t2，t3，t4}組成，由圖1可知該Petri網(wǎng)中存在有分支結(jié)構(gòu)，所以該Petri網(wǎng)有兩種可能的運行軌跡，分別為：{p1，t1，p2，t2，p3，t4，p4} 和 {p1， t1， p2， t3， p3， t4， p4} 。

圖1　一個Petri網(wǎng)實例

定義2（前集，后集）設(shè) PN=(P，T，F(xiàn))為一個Petri網(wǎng)，對于 x∈P∪T ，記

稱·x為x的前集，x·為 x的后集。

2.2　工作流網(wǎng)

在Petri網(wǎng)的基礎(chǔ)上，Aalst提出了工作流網(wǎng)的概念，工作流網(wǎng)是一種特殊的Petri網(wǎng)，其定義如下：

定義3（工作流網(wǎng)）一個Petri網(wǎng) PN=(P，T，F(xiàn))被稱為工作流網(wǎng)，當(dāng)且僅當(dāng)其滿足下面的條件：

1）PN有兩個特殊的庫所：i和o。庫所i是一個起始庫所，即·i=φ；庫所o是一個終止庫所，即o·=φ。

2）如果在PN中加入一個新的變遷t*，使t*連接庫所 i和 o，即 ·t*={o}，t*·={i}，這時所得到的PN是強連通的。

從以上這兩個對Petri網(wǎng)的約束條件不難看出：條件1）是使工作流網(wǎng)必須具有一個起始點和一個終止點；條件2）是使得工作流網(wǎng)中不存在處于孤立狀態(tài)的活動和條件，所有的活動與條件都位于起始點到終止點的通路上。

在庫所與變遷的基礎(chǔ)上，為了定義出串行、并行、選擇、循環(huán)等常見的過程邏輯，工作流網(wǎng)構(gòu)造了一些結(jié)構(gòu)化的組件來實現(xiàn)這些功能，在建模時用戶可以直接使用這些組件，從而加快用戶的建模過程。圖2給出了工作流網(wǎng)的四類基本組件結(jié)構(gòu)。

1）順序組件。最簡單的組件結(jié)構(gòu)，活動按順序一個接著一個地執(zhí)行。

2）選擇組件。兩個或兩個以上的活動存在選擇關(guān)系且必須選擇其中之一。選擇組件開始于OR-split節(jié)點，最后匯合于OR-join節(jié)點。

3）并行組件。兩個或兩個以上的活動能按同時或以任意次序執(zhí)行，且執(zhí)行過程互不影響。并行組件開始于AND-split節(jié)點，最終匯聚于AND-join節(jié)點。

4）循環(huán)組件。某個活動需要被多次執(zhí)行，直至滿足跳出循環(huán)的條件。

圖2　工作流網(wǎng)基本組件

2.3　Petri網(wǎng)關(guān)聯(lián)矩陣

Petri網(wǎng)的關(guān)聯(lián)矩陣可以很好的描述一個Petri網(wǎng)的結(jié)構(gòu)特征，下面給出Petri網(wǎng)關(guān)聯(lián)矩陣的定義。

定義4（Petri網(wǎng)關(guān)聯(lián)矩陣）設(shè) PN=(P，T，F(xiàn))為一個 Petri網(wǎng)，P={p1，p2，…，pm}，T={t1，t2，…，tn}，則Petri網(wǎng) PN=(P，T，F(xiàn))可以用一個n行m列的矩陣來表示A=(aij)n×m，其中：aij=aij+-aij-，i∈{1，2，…，n}，j∈{1，2，…，m}

3　流程間距離計算

本節(jié)首先給出節(jié)點邊權(quán)重和帶邊權(quán)重工作流網(wǎng)的定義，然后介紹構(gòu)造帶邊權(quán)重工作流網(wǎng)關(guān)聯(lián)矩陣的規(guī)則，最后使用矩陣范數(shù)來定義流程間距離。

3.1　帶邊權(quán)重的工作流網(wǎng)

現(xiàn)有工作流的定義方式并不統(tǒng)一［20］，本文在文獻(xiàn)［21～22］的基礎(chǔ)上給出了帶邊權(quán)重的工作流的定義。首先我們定義節(jié)點邊權(quán)重，然后給出帶邊權(quán)重的工作流。

定義5（節(jié)點邊權(quán)重）任意給定一個工作流網(wǎng)，每個節(jié)點相鄰的邊上可以標(biāo)記一個權(quán)重，該權(quán)重稱為節(jié)點的邊權(quán)重。

對工作流網(wǎng)的基本組件進(jìn)行研究，我們可以發(fā)現(xiàn)以下一些規(guī)則：

并行組件結(jié)構(gòu)都是由變遷引入或引出多條連接各個庫所的結(jié)構(gòu)，而且所有變遷中的事件都必將發(fā)生，只是發(fā)生的先后順序不同。如圖2中所示的AND-split和AND-join并行組件結(jié)構(gòu)，我們可以給出如下規(guī)則：

規(guī)則1：任意給定一個合理的工作流網(wǎng)，對于其中任意的變遷節(jié)點，該節(jié)點所有的邊權(quán)重都相等。

選擇組件結(jié)構(gòu)都是由庫所引出或引入多條連接各個變遷的結(jié)構(gòu)，多個選擇分支只有一個能夠發(fā)生，假設(shè)每個選擇分支的發(fā)生可能性相等，則互斥分支發(fā)生的可能性是主干分支發(fā)生可能性的若干分之一，如圖2所示的OR-split和OR-join選擇組件結(jié)構(gòu)，我們可以給出如下的規(guī)則：

規(guī)則2：任意給定一個合理的工作流網(wǎng)，對于其中任意的庫所節(jié)點，該節(jié)點共有m條出邊，出邊權(quán)重分別為 w1，w2，…，wm，則有 w1=w2=…=wm。

工作流網(wǎng)可以看成一個流網(wǎng)絡(luò)，我們可以使用圖論中的相關(guān)結(jié)論對其進(jìn)行研究。在一個流模型G=(V，E)中，其中V和E分別代表流模型的頂點集和邊集，設(shè)s∈V和t∈V分別為流模型的源點和匯點，對于任意的邊(u，v)∈E均有一非負(fù)容量c(u，v)≥0，可以在該流模型上定義流函數(shù) f，該函數(shù)滿足流守恒性，即對所有 u∈V{s，t}，要求f(u，v)=0。將該結(jié)論應(yīng)用到工作流網(wǎng)中，則對于任意的非起始庫所和非終止庫所的出邊的權(quán)重之和等于入邊的權(quán)重之和。因此，我們可以給出如下規(guī)則：

規(guī)則3：任意給定一個合理的工作流網(wǎng)PN=(P，T，F(xiàn))，i和o分別為其起始庫所和終止庫所，?p∈P{i ， o}，庫所 p的m條出邊和n條入邊的權(quán)重分別為 w1，w2，…，wm和θ2，…，θn，則滿足=。

3.2　節(jié)點邊權(quán)重的確定算法

對于一個合理的工作流網(wǎng)，按照一定順序遍歷工作流網(wǎng)中的所有節(jié)點，如果可以按照上述三個規(guī)則確定其邊權(quán)重，則標(biāo)記其權(quán)重，否則計算下一個節(jié)點，直到所有節(jié)點均被標(biāo)記。

確定工作流網(wǎng)的邊權(quán)重的算法如下：

算法1：確定工作流網(wǎng)的邊權(quán)重。

1）首先添加兩個庫所Ps，Pe，兩個變遷Ts，Te；

2）創(chuàng)建四條新邊 (Ps，Ts)，(Ts，i)，(o，Te)，(Te，Pe)，同時將邊 (Ps，Ts)和 (Te，Pe)的權(quán)重設(shè)置為1，其余邊的權(quán)重設(shè)置為0；

3）創(chuàng)建一個隊列Q，同時將隊列初始化為Q={Ps}，所有節(jié)點設(shè)為未被訪問過；

4）當(dāng)隊列不為空時，對于隊列中的每一個節(jié)點x，如果x未被訪問過，使用所給的三條規(guī)則計算節(jié)點x的邊權(quán)重，并對該節(jié)點x進(jìn)行廣度優(yōu)先搜索 BFS_Search(PN，x)；

5）當(dāng)隊列為空時，所有節(jié)點都被訪問過，此時根據(jù)以上三個規(guī)則得到一個n元一次方程組，計算此方程組，將結(jié)果標(biāo)記到PN的邊上。

其中廣度優(yōu)先搜索節(jié)點x的步驟為

1）如果節(jié)點x可以根據(jù)上文規(guī)則求出邊權(quán)重，則計算其邊權(quán)重并標(biāo)記，否則添加n個未知數(shù)x1，x2，…，xn，設(shè)為節(jié)點 x 的 n 條邊的權(quán)重；

2）將該節(jié)點x標(biāo)記為已訪問過，并將其從隊列Q中去除；

3）令A(yù)djSet為與節(jié)點x緊鄰且未被訪問過的節(jié)點的集合；

4）對于AdjSet中的每個節(jié)點 y，將其添加到隊列Q中，并遞歸地廣度優(yōu)先搜索該節(jié)點y。

定義6（帶邊權(quán)重的工作流網(wǎng)）任意給定一個合理的工作流網(wǎng)PN=(P，T，F(xiàn))，如果所有節(jié)點的邊權(quán)重都被標(biāo)注完成，則稱標(biāo)注了邊權(quán)重的工作流網(wǎng)為帶邊權(quán)重的工作流網(wǎng)，記為WPN。

圖3為給圖1所示的Petri網(wǎng)按照上面規(guī)則加上邊權(quán)重后所得的帶邊權(quán)重的工作流網(wǎng)。

圖3　帶權(quán)重的工作流網(wǎng)

定義7（帶邊權(quán)重的Petri網(wǎng)關(guān)聯(lián)矩陣）任意給定一個工作流網(wǎng)PN=(P，T，F(xiàn))，對其每個節(jié)點的邊加上權(quán)重后得到帶邊權(quán)重的工作流網(wǎng)，可以表示為WPN=(P，T，F(xiàn)，W)，其中W 為邊權(quán)重集合，由WPN可以得到一個帶邊權(quán)重的Petri網(wǎng)關(guān)聯(lián)矩陣WA=(waij)n×m，其 中 ：waij=wa+ij-wa-ij，i∈{1，2，…，n}，j∈{1，2，…，M。

由于業(yè)務(wù)流程模型的數(shù)量、種類繁多，不同的業(yè)務(wù)流程模型對應(yīng)不同的Petri網(wǎng)模型，它們的庫所和變遷節(jié)點的個數(shù)往往是不同的，因此它們對應(yīng)的關(guān)聯(lián)矩陣的維數(shù)是不同的。在計算兩個不同維數(shù)矩陣的距離時，我們需要對相應(yīng)矩陣進(jìn)行正規(guī)化處理，即將它們變?yōu)橄嗤信c相同列的矩陣。下面給出Petri網(wǎng)關(guān)聯(lián)矩陣正規(guī)化的定義。

定義8（Petri網(wǎng)關(guān)聯(lián)矩陣正規(guī)化）給定兩個工作流網(wǎng) PN1=(P1，T1，F(xiàn)1)與 PN2=(P2，T2，F(xiàn)2)，它們所對應(yīng)的帶節(jié)點邊權(quán)重的工作流網(wǎng)分別為WPN1=(P1，T1，F(xiàn)1，W1)和WPN2=(P2，T2，F(xiàn)2，W2)，其中W1和W2分別表示節(jié)點的邊權(quán)重集合，正規(guī)化帶邊權(quán)重的Petri網(wǎng)關(guān)聯(lián)矩陣的行數(shù)為N= | T1∪T2|，列數(shù)為M= | P1∪ P2|，T1∪ T2={t1，t2，…，tN} ，P1∪ P2={p1，p2，…，pM}，由WPN1和WPN2可以得到兩個正規(guī)化帶邊權(quán)重的Petri網(wǎng)關(guān)聯(lián)矩陣NWA1=(N×M和NWA2=N×M，其 中 ：=--n，i∈{1，2，…，N}，j∈{1，2，…，M}。

由以上分析可知，任意給定兩個Petri網(wǎng)模型PN1和 PN2，通過算法1給Petri網(wǎng)增加節(jié)點邊權(quán)重，可以得到帶邊權(quán)重的Petri網(wǎng)模型WPN1和WPN2，若所得的WPN1和WPN2維數(shù)不同，則需要對Petri網(wǎng)關(guān)聯(lián)矩陣進(jìn)行正規(guī)化處理，得到兩個正規(guī)化帶邊權(quán)重的Petri網(wǎng)關(guān)聯(lián)矩陣NWA1=(nwa1ij)N×M和 NWA2=(nwa2ij)N×M，本文認(rèn)為 NWA1和NWA2可以很好地表示Petri網(wǎng)模型PN1和PN2的結(jié)構(gòu)特性。因此，可以通過計算NWA1和NWA2之間的距離來反映Petri網(wǎng)模型PN1和PN2之間的距離。

3.3　流程間距離計算

流程間距離的計算可以分為定性分析與定量計算，所謂定性分析是指對流程模型的規(guī)模大小進(jìn)行比對，如果兩個流程模型的規(guī)模不相同，則它們之間一定存在距離，反之不然。對流程模型的定性分析是對流程模型距離定量度量的基礎(chǔ)和準(zhǔn)備，通過簡單的定性分析，確定那些一定存在距離的流程模型；而定量計算則指在確定流程模型之間存在距離之后，就需要計算出流程模型間距離的具體數(shù)值。由于本文是使用Petri網(wǎng)關(guān)聯(lián)矩陣來表示業(yè)務(wù)流程模型的結(jié)構(gòu)特征。所以兩個流程模型間的距離可以通過計算兩個關(guān)聯(lián)矩陣的距離來表示。在矩陣論中，矩陣間距離的度量可以使用范數(shù)，因此，本文給出如下的流程模型間距離的定義。

定義9（流程間距離）任意給定兩個Petri網(wǎng)模型PN1和PN2，可以得到兩個正規(guī)化帶邊權(quán)重的Petri網(wǎng)關(guān)聯(lián)矩陣NWA1=(nwa1ij)N×M和NWA2=(nwa2ij)N×M，模型 PN1和 PN2之間的距離定義為：d(PN1，PN2)=tr[(NWA1-NWA2)×(NWA1-NWA2)Τ]，其中tr[]表示矩陣的跡，即矩陣主對角線上元素之和。

定理1對于任意給定的Petri網(wǎng)模型PN1，PN2和PN3，模型間距離滿足距離度量特性，即：

1）非負(fù)性：d(PN1，PN2)≥0 ，當(dāng)且僅當(dāng) PN1=PN2成立時，有 d(PN1，PN2)=0 ；

2）對稱性：d(PN1，PN2)=d(PN2，PN1)；

3）三角 不 等 式：d(PN1，PN3)≤d(PN1，PN2)+d(PN2，PN3)。

證明：1）由流程間距離的定義可知d(PN1，PN2)≥0 ，若 d(PN1，PN2)=0 ，則說明 NWA1-NWA2是零矩陣，從而得 NWA1=NWA2，即 PN1=PN2，反之亦然；

2）由流程模型間距離的定義可得：

4　實驗驗證

首先使用人工創(chuàng)建的5個實例模型將本文方法與文獻(xiàn)［19］所給方法進(jìn)行對比，以證明本文方法的可行性與有效性。然后使用IBM所提供的真實數(shù)據(jù)集，對本文所提方法的性能進(jìn)行分析。實驗環(huán)境為：Inter（R）Core（TM）i5-6420P CPU@2.80GHz 8GB內(nèi)存。實驗程序使用Java語言編寫，運行在64位W indows7系統(tǒng)上，JDK版本為1.7.0。

4.1　實例分析

本文定義的流程模型間距離與文獻(xiàn)［19］所給的流程模型間距離定義類似，因此以文獻(xiàn)［19］的方法作為對比實驗來證明本文方法的可行性與有效性。將文獻(xiàn)［19］的方法稱為流程依賴圖（Process Dependency Graph，PDG）算法。如圖4描述了5個典型的工作流模型，其中WF1是一個簡單的順序工作流，其他4個工作流網(wǎng)都是在其基礎(chǔ)上通過簡單的增加、刪除和替換節(jié)點的操作得到，目的是保證實例中的結(jié)構(gòu)類型足夠多樣，覆蓋所有4種基本組件結(jié)構(gòu)以及基本組件的組合，以證明結(jié)論的有效性。

通過對圖4所示的5個工作流模型使用PDG算法，得到的工作流模型間距離如表1所示，其中工作流模型WF2，WF3，WF4都是在順序組件上改造后形成的帶有選擇、并行和循環(huán)等基本組件的流程模型，他們與WF1的距離都相同，說明PDG算法在對順序結(jié)構(gòu)進(jìn)行基本組件結(jié)構(gòu)改造后無法有效區(qū)分進(jìn)行了哪種修改；WF2與WF4之間的距離為0，說明這兩個工作流是完全相同，而通過人工觀察發(fā)現(xiàn)WF2和WF4的基本組件不同，說明WF2和WF4的流程模型間距離應(yīng)該大于0，可以發(fā)現(xiàn)PDG算法無法有效區(qū)分選擇組件結(jié)構(gòu)和并行組件結(jié)構(gòu)，即不能對流程運行的互斥和并行關(guān)系進(jìn)行有效的識別。

表1　PDG算法得出的流程間的距離

圖4　人工流程模型實例

表2　通過本文方法求得的流程間距離

表2是通過本文所給方法得出的流程模型間距離。通過表2可以發(fā)現(xiàn)，在對順序組件進(jìn)行選擇、并行和循環(huán)改造后所得流程模型與原流程模型間的距離是不相同的，因而可以判定所進(jìn)行的是不同的改造；WF2和WF4之間的距離大于0，因而可以有效地判定WF2和WF4是不同的流程模型結(jié)構(gòu)，即本文方法可以對選擇組件結(jié)構(gòu)和并行組件結(jié)構(gòu)進(jìn)行有效區(qū)分。

4.2　性能評估

實驗數(shù)據(jù)使用IBM公開的一組數(shù)據(jù)集［23］，包括5個流程庫，總共3000多個流程，這些流程是在對客戶項目進(jìn)行建模后獲得的。其涉及多個領(lǐng)域，如保險、供應(yīng)鏈、銀行、建筑、自動化、通信等。在這些流程中隱去了原來的詳細(xì)信息，如重命名流程庫名為A，B1，B2，B3，C，變遷名由T1，T2，T3，…來代替，庫所名由P1，P2，P3，…來代替。匿名后的流程忽略了原先的實際含義而只考慮其流程模型的結(jié)構(gòu)信息。表3展示了它們各自的庫所、變遷、邊數(shù)的最小值、最大值和平均值等信息。

表3　數(shù)據(jù)集

從每個流程庫中分別挑選出五個流程模型，挑選出的流程模型分別為：包含5個庫所和5個變遷、10個庫所和10個變遷、15個庫所和15個變遷、20個庫所和20個變遷，以及25個庫所和25個變遷的流程模型。將挑選出的25個流程模型分成5組，每組中流程模型的庫所和變遷個數(shù)相等。從而每組內(nèi)的流程模型可以形成10對。可以求出計算流程模型間距離所花的時間，如圖5（a）所示，以及每組所花時間的平均值，如圖5（b）所示。

圖5　

由圖5（a）可知，隨著流程模型規(guī)模的增大，計算流程模型間距離所花的時間也相應(yīng)增加。由圖5（b）可知，計算流程模型間距離所花時間的平均值與流程模型中變遷節(jié)點數(shù)呈現(xiàn)多項式關(guān)系。這與算法1的時間復(fù)雜度是一致的。算法1進(jìn)行了一次廣度優(yōu)先搜索，在遍歷過程中僅做了變量標(biāo)記，算法的遍歷操作的時間復(fù)雜度為O（V+E）。該時間復(fù)雜度是多項式的，即對于任意給定的工作流網(wǎng)，理論上都可以在多項式時間內(nèi)確定其邊權(quán)重。

5　結(jié)語

業(yè)務(wù)流程管理對于企業(yè)提高工作效率，改善工作質(zhì)量，實現(xiàn)流程優(yōu)化至關(guān)重要。如何計算流程模型間距離，從而實現(xiàn)流程索引與檢索技術(shù)是企業(yè)必須解決的關(guān)鍵問題。本文對現(xiàn)有的工作流相似性度量工作進(jìn)行分析研究，以Petri網(wǎng)為建?；A(chǔ)，在工作流網(wǎng)的基礎(chǔ)上定義了帶邊權(quán)重的工作流網(wǎng)，利用Petri網(wǎng)關(guān)聯(lián)矩陣表示流程模型的結(jié)構(gòu)特征，借鑒矩陣范數(shù)給出了流程間距離的定義，并且給出了流程模型間距離的計算過程。定義的流程模型間距離滿足距離度量的三個特性。

在未來工作中，需要尋找更加高效的邊權(quán)重確定算法，從而加快流程模型間距離的計算。將本文方法應(yīng)用到流程索引與檢索領(lǐng)域，實現(xiàn)業(yè)務(wù)流程的快速查找。

［1］Dijkman R，Dumas M，Dongen B V，et al.Similarity of business processmodels：Metrics and evaluation［J］.Information Systems，2011，36（2）：498-516.

［2］Akkiraju R，Ivan A.Discovering Business Process Similarities：An Empirical Study with SAP Best Practice Business Processes［C］//Service-Oriented Computing-，International Conference，ICSOC 2010，San Francisco，Ca，Usa，December7-10，2010.Proceedings.2010：515-526.

［3］Yan Z，Dijkman R，Grefen P.Fast Business Process Similarity Search with Feature-Based Similarity Estimation［C］//On the Move to Meaningful Internet Systems：OTM 2010.Springer Berlin Heidelberg，2010：60-77.

［4］Minor M，Tartakovski A，Bergmann R.Representation andStructure-BasedSimilarity Assessment for Agile Workflows［C］//International Conference on Case-Based Reasoning：Case-Based Reasoning Research and Development.Springer-Verlag，2007：224-238.

［5］Huang K，Zhou Z，Han Y，etal.An Algorithm for Calculating Process Similarity to Cluster Open-Source Process Designs［J］.2004，3252：107-114.

［6］Levenshtein V I.Binary codes capable of correcting deletions，insertions and reversals［J］.Problems of Information Transmission，1965，1（1）：707-710.

［7］Miller G A.WordNet：a lexical database for English［J］.Communicationsof the Acm，1995，38（11）：39-41.

［8］Dijkman R，Dumas M，Garc&#，et al.Graph Matching Algorithms for Business Process Model Similarity Search［C］//Business Process Management，International Conference，Bpm 2009，Ulm，Germany，September 8-10，2009.Proceedings.2009：835-842.

［9］Grigori D，Corrales JC，Bouzeghoub M，et al.Ranking BPEL Processes for Service Discovery［J］.IEEE Transactionson Services Computing，2010，3（3）：178-192.

［10］Rosa ML，Dumas M，Uba R，et al.Merging Business ProcessModels［C］//On the Move to Meaningful Internet Systems：OTM 2010.Springer Berlin Heidelberg，2010：96-113.

［11］Li C，ReichertM，Wombacher A.On Measuring Process Model Similarity Based on High-Level Change Operations.［C］//Conceptual Modeling-ER 2008，International Conference onConceptual Modeling，Barcelona，Spain， October 20-24， 2008.Proceedings.2008：248-264.

［12］Kunze M，Weske M.M.：Metric Trees for Efficient Similarity Search in Large Process Model Repositories［J］.Lecture Notes in Business Information Processing，2011，66：535-546.

［13］Pomello L，Rozenberg G，Simone C.A survey of equivalence notions for netbased systems［C］//Advances in Petri Nets 1992.Springer BerlinHeidelberg，1992：410-472.

［14］Glabbeek R JV，Weijland W P.Branching Time and Abstraction in Bisimulation Semantics（Extended Abstract）.［J］.Journalof the Acm，1991，43（3）：555-600.

［15］Zha H，Wang J，Wen L，etal.A workflow net similarity measure based on transition adjacency relations［J］.Computers in Industry，2010，61（5）：463-471.

［16］Weidlich M，Mendling J，Weske M.Efficient Consistency Measurement Based On Behavioural Profiles of Process Models［J］.Software Engineering IEEE Transactionson，2011，37（3）：410-429.

［17］Weidlich M，Polyvyanyy A，Mendling J，etal.Efficient Computation of Causal Behavioural Profiles Using Structural Decomposition［C］//Applications and Theory of PetriNets.Springer Berlin Heidelberg，2010：77-685.

［18］Wang J，He T，Wen L，et al.A Behavioral Similarity Measure between Labeled Petri Nets Based on Principal Transition Sequences［C］//On the Move to Meaningful Internet Systems：OTM 2010.Springer Berlin Heidelberg，2010：394-401.

［19］Bae J，Liu L，Caverlee J，etal.Developmentof Distance Measures for Process Mining，Discovery and Integration［J］.International Journal of Web Services Research，2007，4（4）：1-17.

［20］Guo X，Sun S X，Vogel D.A Dataflow Perspective for Business Process Integration［J］.Acm Transactions on Management Information Systems，2015，5（4）：1-33.

［21］Alonso G，Mohan C，Agrawal D，et al.Functionality and Limitations of Current Workflow Management Systems［C］//1997：754-763.

［22］Mohan C.Recent Trends in Workflow Management Products，Standards and Research［C］//Workflow Management Systems and Interoperability.Springer Berlin Heidelberg，1998.

［23］ Fahland D，F(xiàn)avre，C&#，dric，et al.Instantaneous Soundness Checking of Industrial Business Process Models［C］//International Conference on Business Process Management.Springer-Verlag，2009：278-293.