吳 軍，李 昭，陳 鵬，何克清

(1.三峽大學 計算機與信息學院，湖北 宜昌 443002；2.武漢大學 計算機學院，湖北 武漢 430072)

0 引 言

全球化、虛擬化、網(wǎng)絡(luò)化組織(包括企業(yè))的業(yè)務(wù)流程管理變得日益復雜,給業(yè)務(wù)流程的柔性建模、高效調(diào)度、智能分析、合規(guī)控制等方面提出了一系列新的挑戰(zhàn)[1]。業(yè)務(wù)流程管理技術(shù)(business process management，BPM)致力于為流程的分析、定義、執(zhí)行、監(jiān)視和管理提供支持，其目標在于改進產(chǎn)品質(zhì)量,提升服務(wù)水平。

BPM是現(xiàn)代眾多信息系統(tǒng)的共性基礎(chǔ)技術(shù)，并在學術(shù)和工業(yè)領(lǐng)域發(fā)展迅速。例如，SAP公司擁有超過600種業(yè)務(wù)流程模型，其收集了荷蘭地方政府大量的流程模型[2]，這些業(yè)務(wù)流程模型通常用于描述組織提供和實現(xiàn)某些服務(wù)的內(nèi)部過程。隨著企業(yè)業(yè)務(wù)流程模型集的增大，愈發(fā)需要符合特定標準的業(yè)務(wù)流程模型管理方法和工具。

文中重點闡述了基于元數(shù)據(jù)的流程模型相似性度量方法。由于流程注冊元模型框架(MFI-5)[3]忽略了業(yè)務(wù)流程的順序特征，導致缺少用于描述不同流程元素間執(zhí)行順序的特征。為了解決該問題并在實際應用中有效實現(xiàn)流程建模的目標，對MFI-5中位于抽象元類(abstract metaclass)層的元素進行適當裁剪，同時對在實際應用中不直接參與流程構(gòu)建的元素進行刪減，并添加用于描述流程執(zhí)行順序的有向關(guān)聯(lián)特征(association)，構(gòu)建出流程模型描述框架(process model description framework，PMDF)。然后依據(jù)PMDF定義流程模型相似性特征集(similarity feature set，SFS)，同時采用業(yè)界廣泛使用的業(yè)務(wù)流程建模標注語言[4](business process modeling and notation，BPMN)對實際流程進行建模，得到BPMN模型。再利用SFS對BPMN模型進行標識與量化，得到模型在多個特征中的向量，最后通過基于距離的相似性算法計算任意兩個模型在某一特征中向量的相似性，進而綜合依據(jù)兩個模型在7個特征中向量的相似性獲取兩個流程模型的相似性。

1 相關(guān)工作

流程模型相似性度量的研究越來越受學術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注。兩個流程模型間的相似性度量通常涉及三個方面：文本概念相似性、結(jié)構(gòu)相似性、行為相似性[5]。

對于文本概念相似性，Akkiraju等[6]從流程文本概念的角度來評估相似性；Dijkman等[7]綜合度量流程每個節(jié)點文本概念的相似性，并將其作為度量兩個流程模型相似性的一個重要指標。

對于結(jié)構(gòu)相似性，Yan等[9]選擇特定特征來描述業(yè)務(wù)流程模型，然后通過兩個流程模型間匹配的特征個數(shù)來評估其相似性；曹斌等[9]提出用最大公共圖代替圖編輯距離，以便在查詢響應時間方面達到更好的性能；黃子乘等[10]提出了一種基于流程相似性的自動服務(wù)發(fā)現(xiàn)框架。

對于行為相似性，除了文本標簽相似性和結(jié)構(gòu)相似性，基于行為相似性的流程模型搜索也引起了學術(shù)界的關(guān)注。Zha等[11]提出基于轉(zhuǎn)換鄰接關(guān)系集(TAR)的流程相似性度量方法；Jin等[12]從流程模型中提取四類行為特征：存在性、因果關(guān)系、沖突關(guān)系和并發(fā)關(guān)系，然后基于這些特征計算兩個流程模型的行為相似性。同時，Jin等[13]也度量了基于行為的流程模型之間的相似性，并使用索引進行查詢處理。Grigori等[14]利用兩個流程模型間相似性的思想來發(fā)現(xiàn)滿足用戶需求的服務(wù)。

除上述三類工作外，還存在建模語言、查詢方法、聚類等其他工作。標準的業(yè)務(wù)流程建模符號對于流程的描述具有重要意義，其提供了廣泛的建模方式。Cheikhrouhou等[15]描述了BPMN在時間約束下的局限性。Geiger等[16]對基于BPMN2.0的支持和實施進行了研究和分析。Syukriilah等[17]對基于Petri網(wǎng)的業(yè)務(wù)流程模型的結(jié)構(gòu)相似性進行了分析。BPMN可根據(jù)參與者在業(yè)務(wù)流程中扮演的角色來分配相應的流程資源，這種分配方式是一致且結(jié)構(gòu)化的[18]。薛智山等[19]對基于BPMN的工作流程執(zhí)行過程進行了適應性方法研究。為了研究個人和相關(guān)因素對流程模型的可理解性造成的影響，Qiao等[20]在統(tǒng)計語言建模技術(shù)和結(jié)構(gòu)匹配的基礎(chǔ)上，提出了一種聚類并檢索業(yè)務(wù)流程的方法。

文中同時關(guān)注流程模型的結(jié)構(gòu)相似性和行為相似性，且精簡并補充了元數(shù)據(jù)(MFI-5)，提出了基于元數(shù)據(jù)的流程模型相似性度量方法，為流程推薦提供決策支持。

2 流程模型描述框架與相似性特征集的構(gòu)建

文中所提方法基于作者前期研究中研發(fā)的ISO國際標準：流程注冊元模型框架[3](meta-model for process model registration，MFI-5)。采用一種具體的建模語言來描述特定的流程模型，然后從該模型中選擇出相關(guān)的元數(shù)據(jù)，并利用MFI-5對所選的元數(shù)據(jù)進行注冊與管理，這是MFI-5的主要功用。

基于MFI-5構(gòu)建流程模型描述框架(PMDF)。通過經(jīng)驗主義研究，對MFI-5中位于抽象元類層的元素進行適當裁剪，同時對在實際應用中不直接參與流程模型構(gòu)建的元素進行刪減，根據(jù)流程建模的目標構(gòu)建出PMDF，如圖1所示。

PMDF由6個類特征(Class)和1個關(guān)聯(lián)特征(Association)共7個相似性特征組成。其中類特征為：Process、Resource、Event、Sequence_Dependency、Split_Dependency、Join_Dependency，分別用于指出流程模型執(zhí)行過程中涉及的各種流程模型元素，關(guān)聯(lián)特征是指任意兩個類特征間的關(guān)聯(lián)關(guān)系，用于指出流程模型元素的執(zhí)行順序。

在PMDF中須均等考慮上述7個相似性特征，表1闡述了各個特征描述的范疇。

闡明7個相似性特征后，為了便于對流程模型進行準確描述并獲取模型在每個特征中的向量，文中后續(xù)內(nèi)容采用表1闡述的7個相似性特征。

圖1 流程模型描述框架

NOFEATURESCOPE1Process用于特定目標的架構(gòu)化活動(activities)或任務(wù)(tasks)2Resource流程利用、創(chuàng)建、消耗的實體或虛擬資源3Event特定情況的發(fā)生4Sequence_Dependency流程間的控制約束,指明流程按順序執(zhí)行5Split_Dependency流程間的控制約束,指明若一個前驅(qū)流程執(zhí)行完畢,一個或多個后繼流程將并行執(zhí)行6Join_Dependency流程間的控制約束,指明若前驅(qū)的多個流程執(zhí)行完畢,后繼的一個流程將開始執(zhí)行7Association指明流程間有向的關(guān)聯(lián)關(guān)系

相似性特征構(gòu)成流程模型相似性特征集SFS，定義SFS的內(nèi)容如下：

SFS={Process,Sequence_Dependency,Resource,Split_Dependency,Event,Join_Dependency,Association}

(1)

相似性特征集的成功定義為流程模型的描述提供了元數(shù)據(jù)支持，并為基于距離的向量相似性計算奠定基礎(chǔ)。

3 流程模型相似性度量

3.1 流程模型的標識與向量化

在業(yè)務(wù)流程相似性度量和流程挖掘領(lǐng)域，業(yè)務(wù)流程建模標注語言(BPMN)已成為一種通用的圖形化描述語言，廣泛應用于流程建模[18]。BPMN由于其具有圖形化特征，且其抽象級別位于實際流程與MFI-5之間，尤其能描述多方參與的復雜應用場景，因此適合進行流程的描述。為了度量流程模型間的相似性，采用SFS對BPMN模型進行標識與量化，得到模型在多個特征中的向量，為基于距離的特征向量相似性計算奠定基礎(chǔ)。以圖2中的3個在線售貨服務(wù)BPMN模型為例(Model1、Model2、Model3分別記為M1、M2、M3)，通過7個相似性特征中的向量來標識并量化BPMN模型。

圖2 在線售貨服務(wù)BPMN模型

相似性特征1(Process)。

圖2中的BPMN模型包含4種不同類型的流程(矩形框)：購買商品(BG)、獲得商品(RG)、驗證發(fā)票(VI)、儲存商品(SG)。在Process特征中，采用具有4個特征值的向量對3個模型分別進行描述，每個特征值對應于一種類型的流程，4個特征值分別為BG、RG、VI、SG，每個特征值用數(shù)字標識了一個模型包含該特征值的數(shù)量。3個模型在Process特征中的向量表示如下：

Model IdBGRGVISG111112110131111

相似性特征2(Resource)。

M1的直接參與者為Jack、Brook、Lily，因此M1的Resource為Jack、Brook、Lily。同理可知，M2的Resource為Jack、Brook；M3的Resource為Jack。所以，圖2中的BPMN模型包含3種不同類型的資源：Jack、Brook、Lily。在Resource特征中，采用具有3個特征值的向量對3個模型分別進行描述，每個特征值對應于一種類型的資源，3個特征值分別為Jack、Brook、Lily，每個特征值用數(shù)字標識了一個模型包含該特征值的數(shù)量。3個模型在Resource特征中的向量表示如下：

Model IdJackBrookLily111121103100

相似性特征3(Event)。

圖2中的BPMN模型包含2種不同類型的事件(圓形框)：啟動(start)、結(jié)束(end)。在Event特征中，采用具有2個特征值的向量對3個模型分別進行描述，每個特征值對應于一種類型的事件，2個特征值分別為start、end，每個特征值用數(shù)字標識了一個模型包含該特征值的數(shù)量。3個模型分別在Event特征中的向量表示如下：

Model IdStartEnd111211311

相似性特征4(Sequence_Dependency)。

圖2中BPMN模型包含順序依賴。在Sequence_Dependency特征中，采用具有2個特征值的向量對3個模型分別進行描述，每一個特征值對應于順序依賴特征在3個模型實例中分別出現(xiàn)的次數(shù)。2個特征值分別為Sequence_Dependency、Substitution，每個特征值用數(shù)字標識了一個模型包含該特征值的數(shù)量。3個模型分別在Sequence_Dependency特征中的向量表示如下：

Model IdSequence_DependencySubstitution100200310

(注：特征值Substitution為補充值，以使其符合向量的形式化定義，后文同理。)

相似性特征5(Split_Dependency)。

圖2中的BPMN模型包含分支依賴。在Split_Dependency特征中，采用具有2個特征值的向量對3個模型分別進行描述，每一個特征值對應于分支依賴特征在3個模型實例中分別出現(xiàn)的次數(shù)。2個特征值分別為Split_Dependency、Substitution，每個特征值用數(shù)字標識了一個模型包含該特征值的數(shù)量。3個模型分別在Split_Dependency特征中的向量表示如下：

Model IdSplit_DependencySubstitution120210310

相似性特征6(Join_Dependency)。

圖2中的BPMN模型包含聯(lián)結(jié)依賴。在Join_Dependency特征中，采用具有2個特征值的向量對3個模型分別進行描述，每一個特征值對應于聯(lián)結(jié)依賴特征在3個模型實例中分別出現(xiàn)的次數(shù)。2個特征值分別為Join_Dependency、Substitution，每個特征值用數(shù)字標識了一個模型包含該特征值的數(shù)量。3個模型分別在Join_Dependency特征中的向量表示如下：

Model IdJoin_DependencySubstitution120210310

相似性特征7(Association)。

圖2中的BPMN模型包含5種不同類型的關(guān)聯(lián)：購買商品→獲得商品(BG→RG)、購買商品→驗證發(fā)票(BG→VI)、獲得商品→儲存商品(RG→SG)、購買商品→儲存商品(BG→SG)、獲得商品→驗證發(fā)票(RG→VI)。在Association特征中，采用5個特定值的向量對3個模型分別進行描述，每個特征值對應于一種類型關(guān)聯(lián)，5個特征值分別為(BG→RG)、(BG→VI)、(RG→SG)、(BG→SG)、(RG→VI)，每個特征值用數(shù)字標識了一個模型包含該特征值的數(shù)量。3個模型分別在Association特征中的向量表示如下：

Model IdBG→RGBG→VIRG→SGBG→SGRG→VI111101210110310101

3.2 基于距離的流程模型向量相似性計算

文中將BPMN模型間的相似性計算過程轉(zhuǎn)換為計算兩個模型在7個特征中向量間的距離(相似性)[21]，即依據(jù)7個特征中向量的相似性值，計算出兩個流程模型間的相似性。依據(jù)PMDF定義流程模型相似性特征集，以通過每個特征中向量的相似性確保BPMN模型的相似性。

PMDF由6個類特征(Class feature)和1個關(guān)聯(lián)特征(Association feature)共7個特征組成。在PMDF中須均等考慮上述7個相似性特征：Process、Resource、Event、Sequence_Dependency、Split_Dependency、Join_Dependency、Association，這些特征構(gòu)成SFS，如式1所示?；赟FS對BPMN模型進行標識和量化，得到模型在7個特征中的向量，然后通過基于距離的算法計算任意兩個模型在某一特征中向量的相似性。文中采用谷本系數(shù)(Tanimoto Coefficient)[22]計算兩個模型在某一特征中向量的相似性。

依據(jù)圖2闡述的在線售貨服務(wù)BPMN模型可知，BPMN模型集(MS)包含3個BPMN模型，定義MS的內(nèi)容如下：

MS={M1,M2,M3}

(2)

定義式3對MS中任意兩個BPMN模型在某一特征中向量的相似性進行計算，其中，MA和MB分別代表MS中任意兩個模型。

Sim(MAi,MBi)=Tanimoto(MAi,MBi)=

MA,MB∈MS,i=1,2,…,7

(3)

其中，MAi和MBi分別表示MS中任意兩個模型在第i個特征中的向量，且i的取值為1至7間的整數(shù)(包含整數(shù)1和7)；Sim(MAi,MBi)指向量MAi與MBi間的相似性，其值等于Tanimoto(MAi,MBi)，即向量MAi與MBi間的距離，向量間的相似性計算結(jié)果處于[0,1]范圍內(nèi)。通過式3計算得到MS中任意兩個BPMN模型在7個特征中向量的相似性，如表2所示。

表2 BPMN模型在7個特征中向量的相似性

依據(jù)表2可知，BPMN模型M1與M2在Process特征中向量的相似性為0.75，在Resource特征中向量的相似性為0.67，在Event特征中向量的相似性為1，在Sequence_Dependency特征中向量的相似性為1，在Split_Dependency特征中向量的相似性為0.67，在Join_Dependency特征中向量的相似性為0.67，在Association特征中向量的相似性為0.40。其他模型在各特征中向量的相似性依此類推。

根據(jù)表2的計算結(jié)果進而獲取兩個BPMN模型的相似性，定義式4對MS中任意兩個模型的相似性進行計算。

MA,MB∈MS

(4)

其中，Sim(MA,MB)是指BPMN模型MA與MB間的相似性。

依據(jù)計算結(jié)果構(gòu)建出以上3個在線售貨服務(wù)BPMN模型的相似性矩陣(SM)：

依據(jù)相似性矩陣SM可知，M1與M1的相似性為1，M1與M2的相似性為0.73，M1與M3的相似性為0.63，M2與M3間的相似性為0.68。

為了給流程模型推薦提供決策支持,將模型相似性度量結(jié)果的值域進行劃分。即將值域[0，1]劃分為3個級別：[0，0.4)，[0.4，0.7)和[0.7，1]，即如果相似性屬于[0，0.4)，則將其視為較低的相似性(第三級)，[0.4，0.7)視為中等相似性(第二級)，[0.7，1]視為較高的相似性(第一級)。流程模型間的相似性所處級別越高，一方面能夠更加有效地進行流程間相似性組件的替換與集成，為流程的變更提供支持；另一方面，能夠在當前業(yè)務(wù)流程失效或異常的情況下，優(yōu)先作為替代流程。

4 結(jié)束語

業(yè)務(wù)流程相似性的研究仍然存在諸多挑戰(zhàn)與困難。文中提出一種基于元數(shù)據(jù)的流程模型相似性度量方法以度量流程模型間的相似性。構(gòu)建了基于MFI-5的流程模型描述框架及流程模型相似性特征集；從相似性特征集的7個特征維度對BPMN模型進行向量化，得到流程模型在7個特征中的向量，為相似性計算奠定基礎(chǔ)；使用基于距離的算法分別計算兩個模型在7個特征中向量的相似性；均等權(quán)衡7個特征中向量的相似性，計算出兩個流程模型間的相似性，依據(jù)任意兩個流程模型間的相似性，構(gòu)建流程模型相似性矩陣；利用所提方法對典型的在線售貨服務(wù)流程間的相似性開展度量實驗，分析討論實驗結(jié)果，為流程的變更和推薦提供決策支持。