基于擬行為輪廓的等距離流程變體再區(qū)分

王樂霞 方 歡

（安徽理工大學數(shù)學與大數(shù)據(jù)學院 安徽淮南 232001）

關鍵字：業(yè)務流程模型；變體；編輯距離；擬行為輪廓相似性

隨著信息技術的不斷發(fā)展，商業(yè)界也愈發(fā)動態(tài)多變，這對公司業(yè)務流程的調整提出了更高要求。面對商業(yè)環(huán)境的頻繁且未知的變化，流程-軟件信息系統(tǒng)（PAISs）[1]應運而生。為保證其市場競爭力，組織和企業(yè)不斷重新設計或靈活升級其業(yè)務流程，因此產(chǎn)生了大量源自同一業(yè)務流程的流程變體[2]。這些變體在一定程度上關聯(lián)相似，但在元素層面、結構層面、行為層面[3]又存在著或多或少的差異。這些變體之間的比較研究，對充分利用流程變體的價值具有重要意義。

文獻[4]從變體的結構層面出發(fā)，利用圖編輯距離的概念研究變體之間的差異性。文獻[5]引出了“行為輪廓”的概念，并給出了一致性的判斷標準。但在流程比較方面，行為輪廓一致性忽視了插入或刪除元素帶來的影響。本文引入擬行為輪廓相似性的概念，研究在流程變體距離相等的情況下，原流程與變體在行為關系上的差異性，并合理的區(qū)分處理直接行為關系與間接行為關系。

一、相關概念

定義1（流程模型[6]）定義一個六元組PM=(A,G,F,s,e,t)表示一個業(yè)務流程模型，其中：

1）A表示包含模型中所有活動的有限活動集；

2）G表示包含模型中所有網(wǎng)關的有限網(wǎng)關集，而N=A∪G表示模型中包含活動和網(wǎng)關在內的所有結點；

3）F表示各結點之間的流弧；

4）s表示整個模型的開始結點；

5）e表示整個模型的終止結點；

6）t表示各個網(wǎng)關的類型，包括{and,xor}

定義2（流程變體）定義PM={PM,PM1,PM2,...,PMi,...}表示一個相關的流程模型集，其中，PM是原流程模型，{PM1,PM2,...,PMi,...}是由原模型經(jīng)過系列高級變化操作得到的流程變體。

定義3（編輯距離[4]）定義d(PM,PMi)表示由原模型PM到變體PMi所經(jīng)歷的高級變化操作的最小數(shù)目，即min{|PM[PMi}。其中，包括從原位置移動一個活動結點到新位置、插入一個新活動結點以及刪除一個原有的活動結點。

二、相似性分析

為了在變體與原流程模型距離相等的情況下，在流程行為關系上進一步區(qū)別變體之間的差異性，這一部分給出了擬行為輪廓相似性及其度量，并提出了基于距離的擬行為輪廓相似性度量的方法。

（一）定義。

定義4（擬行為輪廓相似性[7]）已知PM為原業(yè)務流程模型，其中n?N是模型中的結點元素，擬行為輪廓將結點元素之間的行為關系分為直接行為關系與間接行為關系，包括嚴格序關系、擬嚴格序關系、交叉序關系、擬交叉序關系、排他序關系、擬排他序關系、嚴格逆序關系以及擬嚴格逆序關系，8種行為關系劃分了所有結點元素的笛卡爾積。假設PMi為一個流程變體，由此形成的關于兩個模型之間的8種行為關系相似性度表示為：

然后將其按不同權重加和就得到了擬行為輪廓相似性Sim(PM,PMi)=w1sim→+w2sim←+w3sim||+w4sim++w5sim?+w6sim?+w7sim?+w8simχ定義5（擬行為輪廓距離度量）已知原模型PM與一個相應的流程變體，兩者的編輯距離為d(PM,PMi)，擬行為輪廓相似性度為Sim(PM,PMi)，則擬行為輪廓距離度量為。

（二）變體差異[8]分析。

下面給出對距離相等的變體進一步進行行為差異分析的流程步驟：

步驟一：輸入原流程模型與對應的多個流程變體。

步驟二：計算原流程模型到變體的高級變化操作數(shù)目，即編輯距離d(PM,PMi)。

步驟三：分析出各個流程模型的擬行為輪廓，并區(qū)分直接行為關系與間接行為關系。

步驟四：計算各個變體與原流程模型的嚴格序相似性度、擬嚴格序相似性度、排他序相似性度、擬排他序相似性度、交叉序相似性度、擬交叉序相似性度、嚴格逆序相似性度、擬嚴格逆序相似性度，并依據(jù)不同權重進行組合得到擬行為輪廓相似性度。

步驟五：根據(jù)公式計算得到基于距離的擬行為輪廓相似性度。

三、案例分析

在下面的案例[9]中給定了1個原業(yè)務流程模型與6個流程變體，其中，每個變體都是由原模型經(jīng)過4個高級變化操作（移動某元素或插入新元素）得到，所以，它們到原模型的編輯距離d(PM,PMi)=4。例如，變體PM1是由原模型經(jīng)過這樣的四個高級變化操作得到。例如其中的move(PM,H,I,D)操作則表示將PM模型里的H元素從原位置移動到新位置（I元素與D元素之間）。

圖1 原業(yè)務流程模型

圖2 6個流程變體

下面以PM與PMi為例，分析得出兩者的擬行為輪廓矩陣，如表1、2所示。

表1 PM原流程模型擬行為輪廓矩陣

表2 PM1變體擬行為輪廓矩陣

在變體到原模型編輯距離相等的情況下，要深入了解這6個變體之間的差異，需要增加一個新度量維度，即擬行為輪廓相似性。以原模型PM與變體PM1為例，依據(jù)兩者的擬行為輪廓，計算出相應的8個擬行為輪廓相似性，

由于具有直接行為關系的變遷更能影響模型的行為相似性度，因此令w1=w2=w3=w4=0.15,w5=w6=w7=w8=0.1，得出PM與PMi的行為相似性度為0.341。

同理計算得到6個變體與原模型的擬行為輪廓相似性度，如下表3所示。

表3 變體擬行為輪廓相似性度

上述分析結果表明，在多個變體到原模型編輯距離相等是情況下，通過擬行為輪廓相似性度，6個變體進一步得到差異性的區(qū)分，這說明在使用編輯距離無法區(qū)分多個變體時，擬行為輪廓相似性度是行之有效的差異度量方法。

最后，為了更全面的區(qū)分與度量6個變體育原模型之間的差異性，將上述6個變體與原模型的擬行為輪廓相似性和編輯距離結合起來，根據(jù)公式，得到6個變體到原模型的擬行為輪廓距離度量值，如下表4所示。

表4 變體擬行為輪廓距離度量值

通過擬行為輪廓距離度量值計算結果分析，得知到原模型PM編輯距離相等的情況下，變體PM5與原模型差異最小，相似性最高；而變體PM2與原模型差異最大，相似性最低，6個變體按照與原模型差異性由大到小排序得到：PM5-〉PM4-〉PM6-〉PM3-〉PM1-〉PM2。

四、結語

本文通過將編輯距離與擬行為輪廓相似性度兩個度量標準結合起來，解決了單一變量——編輯距離無法進一步區(qū)分多個流程變體與原模型之間差異性的問題，彌補了單一度量方法片面性的缺點。同時，擬行為輪廓相似性不同于簡單的行為輪廓相似性，其合理的區(qū)分了每個結點元素的直接行為關系與間接行為關系。

本文的研究結果對未來流程變體的管理與維護將是具有一定意義的。然而，行為輪廓無論在模型相似性還是一致性上，都具有舉足輕重的意義，進一步充分挖掘模型行為輪廓的研究背景、多元化研究模型之間的相似性都將是下一步研究工作的重點。