基于BPDF的流程相似性度量

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

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

0 引 言

新興信息技術正在改變甚至顛覆社會組織的經營運作方式，企業及組織通常維護大量的業務流程集，例如，中國移動公司維護了超過1000種業務流程[1]。業務流程對于企業和組織來說，是提供一種描述某些具體服務的內部過程的機制。隨著各類信息技術在人類社會方方面面的深入應用，致使業務流程管理變得日益復雜，給業務流程管理帶來了一系列新的挑戰[2]，尤其是對業務流程的相似性度量提出了更高的新的要求。例如，現有業務流程模型相似性度量方法中存在缺失典型業務流程特征和預處理缺少自動化處理方法，業務流程推薦策略缺失業務流程典型特征的問題。業務流程管理的目標在于改進產品質量，提升服務水平，確切提高業務流程的描述能力、分析能力以及改進流程的能力。業務流程管理作為現代信息系統的共性基礎技術，已經被工業界和學術界廣泛關注，并在領域內快速發展，業務流程相似性度量作為BPM研究的重要組成部分愈發需要符合特定標準的方法和工具。

業務流程相似性度量方法通常用于計算兩個給定的流程間的相似性。本文基于現有相似性度量方法的研究，為了提高業務流程相似性度量的準確性和有效性，有效實現流程建模的目標，更好地體現業務流程的典型特征和描述業務流程，提出了基于BPDF的流程相似性度量方法。該方法基于作者前期研究工作[3]，并且使用機器學習和統計學方法對業務流程元層數據特征進行處理，以及提出一種新的基于元數據標準的業務流程三層管理框架，以提高業務流程相似性度量的科學性和準確性。

在實際的生產業務中，隨著業務需求的改變和新的市場因素的產生，業務流程通常需要進行變更，以應對新的市場變化與業務需求；或者在新的市場環境驅動下，急需在現有流程庫中尋找功能相近的其它流程來替代已整體失效或異常的業務流程。此時，可以使用該方法對流程庫中的流程進行分級，并優先推薦相似性處于較高級別的流程對故障流程進行替換或為故障流程的變更提供決策支持[4]。

1 相關工作

近年來業務流程的相似性度量已經被廣泛研究，現有業務流程相似性度量通常涉及3個方面：①文本概念相似性；②結構相似性；③行為相似性[5]。事實已經證明業務流程結構相似性與文本概念相似性等業務流程相關特征相結合可以提高業務流程相似性度量的準確性。

Michael等[6]對業務流程相似性度量方法進行了比較研究，得出對于不同目的和規范的服務都建議使用業務流程模型的相似性度量，從文本的角度評估業務流程的相似性。Huang等[7]提出了一種改進的基于流程圖結構的流程模型搜索方法。Li等[8]基于流程模型之間的結構相似性，研究流程模型的存儲機制，并改進模型存儲，便于用戶查詢和變更業務流程。Sun等[9]提出了一種基于語義任務鄰接和重要性(ISTAR)語義工作流的包含領域知識的行為相似性度量方法。ISTAR相似性基于兩個ISTAR集之間的相似性，表示語義工作流之間的相似性。Matthias等[10]提出了一種查詢流程模型的方法，以流程樣本為輸入，發現所有允許查詢行為的模型，并提供基于跟蹤語義和抽象行為包含的概念。除了相似性匹配度的決定之外，還提供了一個親密度評價，并可用于排名。Becker等[6]闡述了相似度度量應該具有的8個屬性, 并分析了在學術文獻中發表的22種如何實現這些屬性的不同的相似性度量方法。

以上這些有關于業務流程相似性度量的研究，對于本文的研究有極強的指導和啟示作用。

2 Metadata_based業務流程描述框架的構建

2.1 流程注冊元模型框架

本節的研究工作基于武漢大學何克清教授、李昭副教授團隊前期研究中研發的ISO國際標準[11]：流程注冊元模型框架(metamodel framework for interoperability-part 5：metamodel for process model registration，MFI-5)，如圖1所示。該國際標準的主要功用是通過具體的建模語言描述業務流程模型，然后從多個維度選取該模型中相關的業務流程元數據特征，并對所選元數據特征進行注冊與管理。

圖1 流程注冊元模型框架(MFI-5)

在MFI-5中，流程模型(Process_Model)是一種元類，用于流程的描述，并在使用一個具體的流程建模語言(Process_Modelling_Language)時，描述所包含的流程模型元素(Process_Model_Element)。流程模型元素包括流程(Process)以及流程間的依賴關系(Dependency)。對于每一個流程模型元素，存在某些事件(Event)能夠觸發該流程模型元素，或者由該流程模型元素產生相應的事件。為了實現特定的業務目標，在執行一個流程模型元素時，會創建、使用或消耗相關的資源(Resource)。

依賴用于描述流程間的控制約束，并能夠歸為順序依賴(Sequence_Dependency)、分支依賴(Split_Dependency)，以及聯結依賴(Join_Dependency)。順序依賴指明流程模型元素是按照一定的順序執行的。分支依賴則指出當前驅的流程模型元素執行完后，將并行地執行一個或多個后繼的流程模型元素。聯結依賴指出當前驅的一個或多個流程模型元素執行完后，將開始執行后續的流程模型元素。分支依賴的類型用于為后繼流程指明邏輯選擇，同理，聯結依賴的類型則為前驅流程指明邏輯選擇。分支依賴類型以及聯結依賴類型的值可以為異或(XOR)、或(OR)以及和(AND)。分支依賴類型XOR意味著有且僅一個后繼流程模型元素允許執行，OR是指一個或多個后繼流程模型元素允許執行，而AND指出所有后繼流程模型元素必須執行。聯結依賴類型XOR意味著當且僅當一個前驅的流程模型元素執行完成，后繼的單個流程模型元素才可執行，OR是指當且僅當一個或多個前驅的流程模型元素執行完成，后繼的單個流程模型元素才可執行，AND是指當且僅當全部的前驅流程模型元素執行完成，后繼的單個流程模型元素才可執行。此外，在分支依賴類型的值確定以后，分支依賴選項(Split_Dependency_Option)表達了后繼流程模型元素執行的安全條件。類似的，在聯結依賴類型的值確定以后，聯結依賴選項(Join_Dependency_Option)指明了前驅流程模型元素執行的安全條件。

2.2 基于BPDF構建業務流程相似性特征集

當前流程注冊元模型框架(MFI-5)研究成果顯著，但是其忽略了業務流程的順序特性，導致在含有復雜結構，例如循環結構，并行結構等業務流程中缺少用于描述不同業務流程元素間執行順序的特征。為了解決該問題并在實際應用中實現有效度量業務流程的目標，并作為以前工作[11]的擴展，我們通過研究流程注冊元模型框架和業務流程的元層數據特征，基于MFI-5構建業務流程描述框架BPDF，這被證明比以前的適用性更有效用于描述業務流程執行順序的有向性，以很好地體現業務流程典型的元數據特征。

圖2 業務流程描述框架(BPDF)

業務流程描述框架(business process description framework，BPDF)是對業務流程的一種規范而形象化的數據描述。一個業務流程是一個由圖形對象組成的有向網狀圖，可以用如下七元組表示

BP=(NL，R，E，α，β，γ，A)

其中，NL表示由L標號的業務活動節點(Process_Activity)的有限集合，N→L表示活動節點標號映射函數，標號主要用于區分每個流程活動節點，可用任意字符序列表示；R表示業務流程的執行實體資源(Resource)；E表示業務流程開始，結束，異常停止等特定情況(Event)；α表示業務流程的順序依賴(Sequence_Dependency)，是流程活動節點間的控制約束，指明若一個前驅活動執行完畢，一個后繼活動將開始執行；β表示業務流程的分支依賴(Split_Dependency)，是流程活動節點間的控制約束，指明若一個前驅流程執行完畢，一個或多個后繼流程將開始執行，類型主要指and-split，or-split不同組合；γ表示業務流程的聯結依賴(Join_Dependency)，是流程間的控制約束，指明若前驅的多個流程執行完畢，后繼的一個流程將開始執行，and-join，or-join不同組合；A表示業務流程的關聯關系(Association)，用于描述業務流程活動或任務間有向的關聯關系。

為了便于對業務流程模型進行準確標識與量化，本文須采用上述7個元數據特征。元數據特征構成業務流程模型相似性特征集SFS，本文定義SFS內容如式(1)所示

(1)

相似性特征集(SFS)的成功定義為業務流程模型的描述提供了元數據支持，并為向量的相似性計算奠定了基礎。

2.3 業務流程三層管理框架

業務流程的描述作為業務流程管理中的一項重要的工作，越來越多的研究人員因為研究工作的需要制定了自己的業務流程描述規則和管理框架。本文提出了一種業務流程“三層模式”的概念，并將業務流程應用劃分為：業務流程描述層、業務流程管理層和業務流程應用層，如圖3所示。這種“高內聚低耦合”業務流程管理框架，為后文的研究工作奠定了基礎。

圖3 業務流“三層”管理框架

該框架主要分為4個功能模塊：業務流程描述、流程挖掘與存儲、相似性度量、個性化推薦。模塊內高度耦合而模塊間高度松散。業務流程描述模塊作為業務流程描述層的基礎模型為其它模塊提供輔助功能。業務流程挖掘與存儲模塊聯系緊密，而個性化推薦模塊通過原始流程模型和挖掘出來的模型的相似性來評估挖掘算法，是流程相似性度量的一個應用功能。

(1)業務流程描述層

業務流程描述層主要目的是對業務流程進行一個形象而規范的描述，該框架提出可以采用特定的建模語言，例如BPMN[12]、Petri Net[13]等，結合基于元數據的業務流程描述框架BPDF對業務流程進行描述，滿足用戶的特定目標需求。

(2)業務流程管理層

業務流程管理層主要目的是對業務流程挖掘、業務流程存儲、業務流程相似性度量、業務流程個性化推薦等操行為進行管理和規范化說明。

(3)業務流程應用層

業務流程應用層整理歸納為以下幾個方面：業務流程特征轉換與提取、業務流程模型圖像化展示、業務流程模型檢索、業務流程變更、業務流程替換等，主要為業務流程的相關應用提供支撐。

3 業務流程相似性計算

3.1 流程模型的描述

基于業務流程三層管理框架可知，在業務流程相似性度量、業務流程挖掘、業務流程推薦等領域，選擇一種合適的建模語言尤為重要，業內常用的建模語言有BPMN、Petri Net等。本文選擇其抽象級別位于實際業務流程與MFI-5之間的業務流程建模標注語言(BPMN)作為業務流程建模語言。BPMN由于其具有圖形化特征，尤其能描述多方參與的復雜應用場景，因此適合進行業務流程的描述。

首先對數據集中3個在線售貨服務進行業務流程解釋，以便于對其進行業務流程進行描述，并獲得相應的圖4中的業務流程BPMN模型，為業務流程BPMN模型的標識與量化奠定基礎。

圖4 在線售貨服務BPMN模型

在Model 1(M1)中，用戶首先執行“購買商品”，然后執行分支依賴中的“排他邏輯門”，流程將在所有輸出分支中依據情境(條件)僅選取其中一個分支執行，即僅執行“獲得商品”或僅執行聯結依賴中的“相容邏輯門”。若選擇執行“獲得商品”，則依次執行分支依賴中的“并行邏輯門”、聯結依賴中的“相容邏輯門”、“驗證發票”、“儲存商品”、聯結依賴中的“并行邏輯門”，最后結束流程；若選擇執行聯結依賴中的“相容邏輯門”，則依次執行“驗證發票”、聯結依賴中的“并行邏輯門”，最后結束流程。

在Model 2(M2)中，用戶首先執行“購買商品”，然后執行分支依賴中的“排他邏輯門”，流程將在所有輸出分支中依據情境(條件)僅選取其中一個分支執行，即僅執行“獲得商品”或僅執行聯結依賴中的“排他邏輯門”。若選擇執行“獲得商品”，則依次執行聯結依賴中的“排他邏輯門”、“儲存商品”，最后結束流程；若選擇執行聯結依賴中的“排他邏輯門”，則執行“儲存商品”并結束流程。

在Model 3(M3)中，用戶依次執行“購買商品”、“獲得商品”、分支依賴中的“并行邏輯門”、“驗證發票”、“儲存商品”、聯結依賴中的“并行邏輯門”，最后結束流程。

此外，為進一步體現流程的直接參與者，并增強BPMN模型的可理解性，本文在BPMN模型中額外考慮模型的資源特征(Resource)，對BPMN模型的Resource進行描述。

3.2 業務流程BPMN模型的標識與量化

為了有效度量業務流程間的相似性，我們基于Metadata_based業務流程描述框架BPDF中元數據特征與BPMN圖形化標識映射關系，見表1，具體的，基于元數據特征與業務流程BPMN模型的映射關系使用SFS對業務流程進行標識與量化，分別得到業務流程在7個元數據特征中的向量，為元數據特征向量的相似性計算奠定基礎。

表1 元數據特征的圖形化標識映射關系

本文中Metadata_based業務流程描述框架(BPDF)認為，對于業務流程描述、相似性度量以及業務流程推薦等應滿足一些常見的特征性質。元數據特征1～元數據特征7是基于BPDF推理而得的業務流程元數據特征，業務流程BPMN模型的標識與量化結果見表2，具體的，7個業務流程模型元數據特征(Process_Activity，Resource，Event，Sequence_Dependency，Split_Dependency，Join_Depende-ncy，Association)的標識與向量化請參見文獻[3]。

表2 業務流程元數據特征向量表示

3.3 基于元數據特征向量的流程相似性度量

業務流程元數據特征向量相似性計算是業務流程相似性度量的重要步驟，本文將業務流程間的相似性計算過程等價轉換為計算兩個業務流程在7個元數據特征的向量相似性，并進行綜合考慮，從而得出兩個業務流程間的相似性。

本文中，我們基于元數據特征構成流程相似性特征集(SFS)。基于SFS對BPMN模型進行標識和量化，以通過每個特征中向量的相似性確保BPMN模型的相似性。基于流程在7個特征中的向量，使用相似性度量算法計算任意兩個業務流程在某一特征中向量的相似性，并充分考慮元數據特征權重，進而獲取整體業務流程模型的相似性。

本文基于對經典相似性度量算法的研究，采用余弦相似度對業務流程集中任意兩個BPMN模型在每一個元數據特征中向量的相似性進行計算。參考余弦相似度，定義式(2)對任意兩個BPMN模型的元數據特征向量相似性進行計算

(2)

其中，MA和MB分別代表數據集MS中任意兩個業務流程模型；MAi=(x1，x2，…，xn)、MBi=(y1，y2，…，yn) 分別代表MS中任意兩個模型在第i個元數據特征中的n維向量，且i=1，2，3，4，5，6，7； Sim(MAi,MBi) 表示向量MAi與MBi間的相似性值，即任意兩個業務流程模型在第i個元數據特征的相似性，其值域處于[0,1]的范圍。

基于式(2)計算得到MS中任意兩個業務流程BPMN模型的元數據特征中向量的相似性，結果見表3。

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

依據表3的計算結果并考慮7個元數據特征權重，進而根據式(3)獲取兩個BPMN模型的相似性

(3)

其中， Sim(MA,MB) 表示業務流程BPMN模型MA與MB間的相似性，w是根據向前逐步回歸算法處理元層數據特征得到的權重。

為了更清晰地展示業務流程模型間的相似性，為業務流程的相似性進行分析提供支持，依據計算結果構建出BPMN模型的相似性表示矩陣(SM)。

業務流程模型相似性的成功獲取為業務流程分析、討論提供了支持，并為業務流程推薦奠定了基礎。根據本文所提方法可以對流程庫中的流程進行分級，并優先推薦相似性處于第一級的流程對故障流程進行替換或為故障流程的變更提供決策支持。

4 實驗研究

4.1 實驗數據準備

為了驗證所提方法的有效性，本文利用實際的修車流程數據集進行了驗證。我們將100個修車服務業務流程模型隨機分成10組，然后從每一組數據中抽取3個業務流程模型得到擁有30個業務流程模型組成的測試數據集，對提出的方法進行實驗實證。

4.2 實驗實施

依據本文所提方法，首先利用BPMN對測試數據集中的30個業務流程進行描述，隨機選取10個業務流程模型組成實驗數據集MS

MS={TM1,TM2,TM3，…，TM10}

其次，輸入MS，依據業務流程相似性特征集(SFS)，對MS中任意業務流程BPMN模型的每個元數據特征進行標識與量化，得到每個BPMN模型在每個元數據特征中的向量。最后，輸入得到的元數據特征向量，依據式(3)計算出MS中任意兩個修車業務流程的相似性，并獲取相似性矩陣，如圖5所示。

圖5 測試集流程相似性矩陣

4.3 實驗結果分析

基于實驗數據集MS的相似性矩陣SM可知，以TM1為例，TM1于實驗數據集MS中其它業務流程BPMN模型的相似性分別為：TM1與TM2為0.73，TM1與TM3為0.70，TM1與TM4為0.60，TM1與TM5為0.48，TM1與TM6為0.66，TM1與TM7為0.61，TM1與TM8為0.45，TM1與TM9為0.62，TM1與TM10為0.79。數據表明TM1與自身的相似性最高，TM1與TM10的相似性較高，TM1與TM8的相似性最低。

為了研究本文所提流程相似性度量方法的效果，選取了結構、文本和行為特征與本文針對汽車修理實際應用的業務流程進行相似性計算，結果如圖6所示。

圖6 測試集流程實例特征相似性圖

在圖6中示例的3個元數據特征中，我們可以直觀地發現，若僅僅以第三個特征(Event)度量業務流程顯然不符合客觀實際。第一個特征(Process_Activity)和第二個特征(Resource)在行為和結構上更符合直觀感受，但是較于圖5中的實驗結果誤差較大。從業務流程相似性和業務流程特征相似性的對比中可以發現，基于BPDF使用SFS度量業務流程得到的結果更科學，更符合直觀感受，更能全面地刻畫業務流程。實驗結果表明，本文提出的方法對于業務流程相似性度量具有有效性，較于傳統單一維度，能夠更好地體現業務流程的典型特征，提高了業務流程相似性度量的準確性。

為了給業務流程推薦提供有效的決策支持[14,15]，并在一定程度降低業務流程推薦的難度，我們基于業務流程相似性計算結果進行分級處理，將業務流程的相似性按其值域[0，1]劃分為4個級別：[0，0.3)，[0.3，0.6)，[0.6，0.8)和[0.8，1]，即，如果業務流程間相似性屬于[0，0.3)，則將其視為較低的相似性(第四級)，[0.3，0.6)視為中等相似性(第三級)，[0.6，0.8)視為較高的相似性(第二級)，[0.8，1] 視為高相似性(第一級)。

基于測試數據集中30個業務流程相似性進行分級，以TM1為例，其相似性從高到低依次是：[TM10，TM25，TM2，TM11，TM3，TM6，TM22，TM12，TM9，TM24，TM7，TM13，TM15，TM19，TM30，TM4，TM21，TM29，TM5，TM14，TM28，TM8，TM20，TM16，TM23，TM18，TM17，TM27，TM26]，沒有處于[0.8，1]值域(第一級)的業務流程；處于[0.6，0.8)值域(第二級)的是[TM10，TM25，TM2，TM11，TM3，TM6，TM22，TM12，TM9，TM24，TM7，TM13，TM15，TM19，TM30，TM4，TM21]；處于[0.3，0.6)值域(第三級)的是[TM29，TM5，TM14，TM28，TM8，TM20，TM16，TM23，TM18，TM17，TM27]；處于[0，0.3)值域(第四級)的是[TM26]。

隨著業務需求市場因素的改變，業務流程也會發生改變，為了適應這種變化，根據業務流程的相似性分級，可以為業務流程的變更與推薦提供決策支持。若其處于第一級，可以基于第一級中的業務流程模型有效地進行業務流程間相似性組件的替換與集成；同時，也可以在當前業務流程失效或工作異常的情況下，優先推薦相似性處于第一級的流程作為替代流程為故障流程的變更提供決策支持。

5 結束語

業務流程相似性的研究仍然存在諸多挑戰與困難[16-18]，相似性特征的選擇缺失業務流程典型特征，相似性度量方法的精度和準確性尚未完全滿足生產實際。本文主要貢獻包括：提出一種基于BPDF的流程相似性度量方法；所提方法在實際應用中能有效度量流程間的相似性，一定程度上為流程智能推薦提供支持。

下一步研究中擬進一步對流程集進行擴展，優化數據預處理和計算過程中的自動化方法，以適應未來的自動化處理，采用循環神經網絡對本文所提方法進行深入優化。例如針對BPMN模型的向量化結果進行自動化處理；基于流程相似性度量結果進行智能推薦策略研究。