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

王樂霞 方 歡

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

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

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

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

一、相關(guān)概念

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

1）A表示包含模型中所有活動(dòng)的有限活動(dòng)集；

2）G表示包含模型中所有網(wǎng)關(guān)的有限網(wǎng)關(guān)集，而N=A∪G表示模型中包含活動(dòng)和網(wǎng)關(guān)在內(nèi)的所有結(jié)點(diǎn)；

3）F表示各結(jié)點(diǎn)之間的流弧；

4）s表示整個(gè)模型的開始結(jié)點(diǎn)；

5）e表示整個(gè)模型的終止結(jié)點(diǎn)；

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

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

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

二、相似性分析

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

（一）定義。

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

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

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

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

步驟一：輸入原流程模型與對(duì)應(yīng)的多個(gè)流程變體。

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

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

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

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

三、案例分析

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

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

圖2 6個(gè)流程變體

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

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

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

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

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

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

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

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

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

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

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

四、結(jié)語

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

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