服務(wù)流程的層次化距離度量方法

摘要：本文闡述了基于結(jié)構(gòu)化流程樹模型來(lái)度量?jī)蓚€(gè)服務(wù)流程距離的算法，該算法可以層次化的對(duì)服務(wù)流程進(jìn)行比較，以便對(duì)流程進(jìn)行層次化的歸類和檢索。

關(guān)鍵詞：服務(wù)流程 差別 層次

一、背景

服務(wù)流程在企業(yè)中得到了大規(guī)模的應(yīng)用，服務(wù)流程模型被存儲(chǔ)在模型數(shù)據(jù)庫(kù)中，另外企業(yè)業(yè)務(wù)流程的修改，服務(wù)流程也被修改或重建。服務(wù)流程數(shù)據(jù)庫(kù)中的流程越來(lái)越多，完成相同任務(wù)的服務(wù)流程的版本也不斷增加，面對(duì)龐大的服務(wù)流程模型庫(kù)，對(duì)服務(wù)流程進(jìn)行分類存儲(chǔ)勢(shì)在必行。如何對(duì)服務(wù)流程進(jìn)行精確查找，如何清除重復(fù)的服務(wù)流程模型以及如何融合相似的服務(wù)流程都是服務(wù)流程領(lǐng)域新的挑戰(zhàn)。面臨這些新的挑戰(zhàn)，必須具備的基本技術(shù)就是如何度量?jī)蓚€(gè)服務(wù)流程間的距離。在此基礎(chǔ)上，服務(wù)流程可以按照距離的大小進(jìn)行分類，有條理的存儲(chǔ)起來(lái)，便于管理；在檢索服務(wù)流程的時(shí)候，能提供一個(gè)可靠的標(biāo)準(zhǔn)，此外眾多服務(wù)流程模型中基于服務(wù)流程的距離進(jìn)行數(shù)據(jù)挖掘能為服務(wù)流程模型定義專家提供企業(yè)或者用戶的需求變化動(dòng)態(tài)，定制更加合理的服務(wù)流程。好的衡量服務(wù)流程模型的差別的算法在服務(wù)流程走向大規(guī)模應(yīng)用的歷程上有著深遠(yuǎn)的意義。

本文將基于結(jié)構(gòu)化的流程樹，提供在不同顆粒度下比較服務(wù)流程的算法。能夠在不同顆粒度上計(jì)算出從一個(gè)服務(wù)流程到另一個(gè)服務(wù)流程的修改路徑，計(jì)算出來(lái)的修改路徑就是我們衡量?jī)蓚€(gè)服務(wù)流程的差別的依據(jù)。

二、結(jié)構(gòu)化的流程樹模型

為了使本文定義的距離是在一個(gè)層次化的高度，并具有宏觀的語(yǔ)義操作，本章要引入結(jié)構(gòu)化的流程樹。

任何一個(gè)正確的流程可以唯一的被分解成一顆結(jié)構(gòu)化的流程樹(Process Structured Tree，簡(jiǎn)稱PST)[1]。在PST中，任何兩個(gè)節(jié)點(diǎn)不會(huì)存在相互重疊的關(guān)系，只可能有屬于或者隸屬于的關(guān)系，它很好的將流程模型分解成結(jié)構(gòu)化的塊，對(duì)于流程相同部分的查找和比較提供了很好的視角。

定義一 結(jié)構(gòu)塊

結(jié)構(gòu)塊分成四種類型：

(A)順序塊：若干個(gè)塊按照一定的順序鏈接而成的塊，一般來(lái)說(shuō)，這些塊在服務(wù)流程圖中是以AND_AND節(jié)點(diǎn)1連接起來(lái)的，通常一個(gè)單獨(dú)的活動(dòng)是一個(gè)最簡(jiǎn)單的順序塊。

(B)并行塊：由多個(gè)需要同時(shí)執(zhí)行的塊組成的塊。一般這些塊都是從同一個(gè)-AND節(jié)點(diǎn)開始并且從同一個(gè)AND-節(jié)點(diǎn)結(jié)束的（表示可以是AND，也可以是OR）。

(C)多選塊：由多個(gè)塊組成，但是在執(zhí)行的時(shí)候只會(huì)選擇某個(gè)滿足特定條件的塊執(zhí)行。一般這些塊都是從同一個(gè)-OR節(jié)點(diǎn)開始并且從同一個(gè)OR-節(jié)點(diǎn)結(jié)束的（表示可以是AND，也可以是OR）。

(D)循環(huán)塊：循環(huán)執(zhí)行，直到滿足某個(gè)條件的時(shí)候才終止的塊。一般這個(gè)塊由OR-AND節(jié)點(diǎn)開始并且在一個(gè)AND-OR節(jié)點(diǎn)處結(jié)束，在這個(gè)塊中既有從第一個(gè)節(jié)點(diǎn)到第二個(gè)節(jié)點(diǎn)的有向通路，又有從第二個(gè)節(jié)點(diǎn)到底一個(gè)節(jié)點(diǎn)的有向通路。

三、相關(guān)節(jié)點(diǎn)

本文希望能根據(jù)不同的顆粒度計(jì)算兩個(gè)服務(wù)流程的差別，故將根據(jù)PST樹一層一層的發(fā)現(xiàn)兩個(gè)流程的不同。在每一層都有一些相關(guān)的節(jié)點(diǎn)，也就是說(shuō)從這一層的角度看，這兩節(jié)點(diǎn)是相同的，但子節(jié)點(diǎn)并不是完全相同的，故從更小的顆粒度來(lái)看，這兩個(gè)節(jié)點(diǎn)是不一樣的。本章先給出如何查找兩個(gè)流程模型中的相關(guān)節(jié)點(diǎn)。由于流程與結(jié)構(gòu)樹轉(zhuǎn)換是唯一的，故可通過匹配結(jié)構(gòu)塊來(lái)匹配流程。

尋找相同節(jié)點(diǎn)通過遞歸算法，可找出服務(wù)流程模型中完全相同的部分，但有些部分在修改時(shí)做了一些改變，它們?cè)谛薷那昂蟠蠖鄶?shù)的活動(dòng)還是一樣的，但在上面的算法中并不能將它們匹配，有些活動(dòng)在修改前屬于同一個(gè)結(jié)構(gòu)塊，但在修改后分布到了多個(gè)結(jié)構(gòu)塊，也有可能將修改前幾個(gè)結(jié)構(gòu)塊的活動(dòng)合并，或選擇性合并到一個(gè)結(jié)構(gòu)塊中，這樣修改前后有關(guān)系的結(jié)構(gòu)塊就成一個(gè)多對(duì)多關(guān)系，對(duì)這些塊做完全的刪除再插入所有的節(jié)點(diǎn)，沒有變動(dòng)的節(jié)點(diǎn)就經(jīng)歷兩次操作：先刪除再插入，顯然不能得到最短的路徑，為了得到最短的路徑，應(yīng)該將最相似的兩個(gè)結(jié)構(gòu)塊進(jìn)行匹配，再修改它們不同的地方。在這用相似度來(lái)衡量?jī)蓚€(gè)結(jié)構(gòu)塊的相關(guān)程度。

定義二 相似度

根據(jù)上面的定義，我們?nèi)菀椎玫较嗨贫鹊膬蓚€(gè)性質(zhì)：

S(P1， P2) = S(P2， P1);

S(P1， P1) = 1;

前兩種情況是很容易處理的，關(guān)鍵是第三種情況。規(guī)定同一個(gè)父節(jié)點(diǎn)下兩個(gè)相似度最大的節(jié)點(diǎn)是匹配的，首先應(yīng)計(jì)算出所有結(jié)構(gòu)塊對(duì)的相似度，然后找出相似度最大的一對(duì)，再?gòu)年?duì)列中去除含有這兩個(gè)節(jié)點(diǎn)的結(jié)構(gòu)塊對(duì)，再找出剩下的里面相似度最大的，以此類推，直到隊(duì)列為空或隊(duì)列中的結(jié)構(gòu)塊對(duì)的相似度都為零為止。P1，P2子節(jié)點(diǎn)并集的個(gè)數(shù)就是P1，P2子節(jié)點(diǎn)的個(gè)數(shù)之和減去匹配的子節(jié)點(diǎn)對(duì)數(shù)。對(duì)根節(jié)點(diǎn)實(shí)行相似度的算法，就可找出兩棵樹中可認(rèn)為前后相同節(jié)點(diǎn)和其相似度了。

四、修改路徑

通過流程間修改路徑來(lái)描述兩個(gè)流程的不同。所謂修改路徑就是指一個(gè)流程是通過另一個(gè)流程修改得到的。本章將具體介紹如何根據(jù)相關(guān)節(jié)點(diǎn)的標(biāo)記來(lái)計(jì)算修改路徑。

經(jīng)過上面的匹配，能得到這樣的幾種結(jié)果：

在P1中的塊在P2中沒有與之匹配的，定義刪除操作Parent. Delete(block name)。

在P2中的塊在P1中沒有與之匹配的，定義插入操作：Parent. Insert(block type/activity name， activity before， activity after)。

在P1中的塊在P2中有與之匹配并且相似度為1的，無(wú)任何操作。

在P1中的塊在P2中有與之匹配但是相似度小于1的，定義修改操作：

Parent. update(child)表示需要對(duì)他的子孫節(jié)點(diǎn)進(jìn)行操作。

除了這些還應(yīng)考慮到在順序塊中，串行塊的執(zhí)行順序是很重要的，對(duì)于一個(gè)順序塊的節(jié)點(diǎn)，還需要檢查它的子節(jié)點(diǎn)的順序是不是一樣，需要定義移動(dòng)操作，Parent. Move(to be moved block， before， after)這里假設(shè)移動(dòng)操作只能在同一個(gè)父節(jié)點(diǎn)下進(jìn)行。在Chen Li等已經(jīng)找出了如何尋找最少的move動(dòng)作的方法[4]，在這使用他們提出的方法來(lái)完成move操作的查找。

有時(shí)并行的功能模塊可能都變成并行的，類似的修改，需要改變節(jié)點(diǎn)的類型，于是定義操作：Self.changetype (block type).

最后對(duì)于選擇塊和循環(huán)塊，有時(shí)選擇分支的條件需要改變，故還需要定義操作：Parent.setCondition(child name， condition)，表示在parent塊下到child分支的條件變?yōu)閏ondition。

五、差別的定義和證明

定義兩個(gè)流程的差別為他們修改路徑中的有效操作步數(shù)。修改路徑中update操作并無(wú)實(shí)際的進(jìn)行，在計(jì)算距離的時(shí)不計(jì)入。由于修改路徑也是一個(gè)樹，且節(jié)點(diǎn)與服務(wù)流程的結(jié)構(gòu)樹有相同的層次，因此可在不同的顆粒度上對(duì)兩個(gè)服務(wù)流程進(jìn)行比較。當(dāng)從較高層次比較時(shí)，忽略底層的改動(dòng)，這樣他們的差別就比較小，如果更深層次的比較，就可能得到更細(xì)微的差別。

對(duì)于兩個(gè)相同的流程，無(wú)論深度是多少，他們的差別應(yīng)該是0，也就是D(P， P， n)=0。通過上面的查找步驟，對(duì)于兩顆相同的樹來(lái)說(shuō)，他們所有節(jié)點(diǎn)都是匹配的，而且相似度都是1，所以在查找的時(shí)候不需要對(duì)任何一個(gè)節(jié)點(diǎn)采取任何操作。這樣得到的最短路徑的操作步數(shù)是0（無(wú)論比較深度是多少），也就是說(shuō)D(P， P， n)=0成立。

距離的交換性；也就是說(shuō)D(P1， P2， n)=D(P2， P1， n)。插入和刪除是互為你動(dòng)作的，從P1到P2進(jìn)行插入一個(gè)塊的操作（可插入多個(gè)子塊），從P2到P1就執(zhí)行刪除相應(yīng)塊的操作；而如果在P1到P2執(zhí)行了move，那么在P2到P1時(shí)順序也是不同，這時(shí)執(zhí)行相反的move操作，move步數(shù)是相同的；如果在P1到P2執(zhí)行改變類型或者設(shè)置條件的操作，那么在P2到P1的時(shí)就要把類型或條件改變回來(lái)，也執(zhí)行相反的操作，故在從P1到P2、和P2到P1的過程中，所需要執(zhí)行的操作步數(shù)是相同的，因此D(P1， P2， n)=D(P2， P1， n)成立。

D(P1， P2， n)+D(P2， P3， n) ≥ D(P1， P3， n)；在上面的算法中得到的修改操作樹中，每一個(gè)動(dòng)作的執(zhí)行都會(huì)產(chǎn)生一顆新的樹，這些樹是在從P1到P3的過程中必須的。在不等式中，如果P2是P1到P3變換的時(shí)候產(chǎn)生的這些中間樹種的一顆，那么D(P1， P2， n)+D(P2， P3， n)=D(P1， P3， n)，這是顯而易見的。如果P2不是P1到P3的過程中產(chǎn)生的任何一顆中間樹，那么P2必然含有這樣的節(jié)點(diǎn)p，在變化的過程中，從P1到P2的時(shí)候需要插入這個(gè)節(jié)點(diǎn)，然后在P2到P3的時(shí)候需要?jiǎng)h除這個(gè)節(jié)點(diǎn)，顯然是大于直接從P1到P3的變化的，故上面的不等式成立。

六、應(yīng)用與前景

本文提供的算法可實(shí)現(xiàn)服務(wù)流程管理和檢索。

任意兩個(gè)服務(wù)流程進(jìn)行0深度的比較，是無(wú)差別的，所有的服務(wù)流程都可被歸結(jié)成一類，再進(jìn)行更深層次的比較，不同的服務(wù)流程將漸漸被發(fā)現(xiàn)，將在某一個(gè)深度比較沒有區(qū)別的服務(wù)流程歸為一類，這樣越往深層次比較，將會(huì)發(fā)現(xiàn)越來(lái)越多的子樹，當(dāng)把數(shù)據(jù)庫(kù)中的所有服務(wù)流程進(jìn)行了不同層次的分類后，所有流程便構(gòu)成一顆樹，這顆樹只有一個(gè)根節(jié)點(diǎn)(服務(wù)流程)，每一個(gè)非葉子節(jié)點(diǎn)的子節(jié)點(diǎn)間都因在這個(gè)深度所表現(xiàn)出來(lái)的不同而被分到兩個(gè)類別中去，根據(jù)每一類別下流程的共同點(diǎn)，可為此節(jié)點(diǎn)進(jìn)行標(biāo)注，數(shù)據(jù)庫(kù)中的服務(wù)流程就更加有條理得被管理起來(lái)。

基于服務(wù)流程分類，服務(wù)流程的檢索將會(huì)變得更加迅速和精確，根據(jù)用戶的需求，可迅速的定位到某一類流程，再把這一類流程返回給用戶。在整個(gè)檢索過程中僅僅只需進(jìn)行一次樹的查找，提高了用戶體驗(yàn)。

在一個(gè)新的服務(wù)流程被創(chuàng)建并加入到分類樹中的時(shí)，系統(tǒng)可提供被添加的服務(wù)流程通過與他相似的流程修改得到的修改路徑，這樣可清晰的看見用戶對(duì)服務(wù)流程需求的變化，以了解市場(chǎng)和需求的動(dòng)態(tài)。

參考文獻(xiàn)：

[1]. Jussi Vanhatalo， Hagen Volzer and Jana Koehler. The Refined Process Structure Tree.

[2]. Jochen M. Küster， et al.， et al. Detecting and Resolving Process Model Differences in the absence of a change log.

[3]. Boudewijn van Dongen， Remco Dijkman and Jan Mendling. Measuring Similarity between Business Process Models.

[4]. Chen Li， Manfred Reichert and Andreas Wombacher. On Measuring Process Model Similarity based on High-level Change Operations. 2008.

[5]. W.M.P. van der Aalst， A.K. Alves de Medeiros and A.J.M.M. Weijters. Process Equivalence: Comparing Two Process. 2008