王倩倩， 邵叱風(fēng)， 王 穎

(安徽科技學(xué)院 信息與網(wǎng)絡(luò)工程學(xué)院，安徽 鳳陽 233100)

對于一個組織或者企業(yè)來說,業(yè)務(wù)流程是其重要組成成分?，F(xiàn)今社會,業(yè)務(wù)流程為適應(yīng)時代的變化,滿足各種需求,也在不斷變化。如果每次變化都從頭開始進(jìn)行構(gòu)建業(yè)務(wù)流程是非常耗時間的。為了重建業(yè)務(wù)流程,一般采用流程聚類、流程查詢等先進(jìn)技術(shù),這些技術(shù)的前提是計算流程相似性。

對于相似性的計算方法，有不少學(xué)者做了相關(guān)的研究。文獻(xiàn)[1]通過計算2個流程之間的距離來度量流程模型相似性，這種距離度量可以用作過程挖掘、流程合并和流程聚類中的定量和定性工具，最終它可以減少或最小化工作流系統(tǒng)的設(shè)計、分析和演化所涉及的成本。但是只能定量的測量，沒有考慮變量約束。文獻(xiàn)[2]考慮可變時間約束，提出時間依賴圖(TDG)的概念，通過計算兩個TDG的距離來表示流程之間的相似性。但此計算方法的前提是節(jié)點標(biāo)簽相同，而現(xiàn)實情況是節(jié)點標(biāo)簽不一定相同。文獻(xiàn)[3]提出一種基于節(jié)點標(biāo)簽的相似性度量。雖然它的計算速度很快，但忽略流程的行為特征會導(dǎo)致結(jié)果不準(zhǔn)確。文獻(xiàn)[4]提出了一種基于變遷鄰接關(guān)系集(TAR)的業(yè)務(wù)流程之間的相似性度量，該度量忽略了變遷鄰接關(guān)系的重要性，使得順序關(guān)系與循環(huán)結(jié)構(gòu)不易區(qū)分。之后，文獻(xiàn)[5]添加了變遷鄰接關(guān)系的重要性，提出了基于變遷鄰接關(guān)系重要性的相似性算法TAR++，可有效區(qū)分順序關(guān)系與循環(huán)結(jié)構(gòu)。文獻(xiàn)[6]對鄰接關(guān)系進(jìn)行擴(kuò)展提出行為輪廓(BP)概念，用BP計算流程一致性，并與跡等價的概念下的一致性對比，凸顯出行為輪廓計算相似性的優(yōu)越性。文獻(xiàn)[7]闡述了一種在不同視角下的應(yīng)急處置流程相似性計算方法。該方法是在應(yīng)急處置活動流程化的基礎(chǔ)上，將各部門之間的聯(lián)動模式分為以下幾種類別：活動同步、活動選擇、訊息傳播，并建立四個試圖，進(jìn)而以四個視圖為基礎(chǔ)，給出了不同視圖表示下應(yīng)急處置流程的相似度計算方法。文獻(xiàn)[8]概述了有關(guān)業(yè)務(wù)流程模型相似性度量的最新技術(shù)，旨在分析存在哪些相似性度量、它們?nèi)绾伪碚饕约巴ǔ?yīng)用哪種計算來確定相似性值。最后，通過對 123 個相似性度量的分析，提出對相似性度量進(jìn)行比較分析,研究人類輸入與相似性度量的整合以及作為未來研究機(jī)會進(jìn)一步分析相似性度量使用場景需求的建議。文獻(xiàn)[9]提出基于LBP的相似性度量算法，但是一旦缺少日志，算法則不可行。

綜合上面的分析，在文獻(xiàn)[6]的啟發(fā)下，提出一種基于活動發(fā)生關(guān)系重要系數(shù)的流程模型相似性度量方法。首先給出活動間的3種發(fā)生關(guān)系，并考慮其重要系數(shù)，給出重要系數(shù)的計算方法，然后基于活動發(fā)生關(guān)系及其重要系數(shù)給出了計算流程模型行為相似性的方法，最后驗證方法的有效性。

1 預(yù)備知識

定義1[4](Petri網(wǎng))Petri網(wǎng)是一個元組(P,T,F)

1)P是有限庫所集;

2)T是有限變遷集,P∪T≠?,P∩T=?;

3)F?(P×T)∪(T×P)為流關(guān)系,將P和T連接。

定義2[4](工作流網(wǎng))Petri網(wǎng)WN=(P,T,F)是一個工作流網(wǎng),當(dāng)且僅當(dāng):

1)PN具有一個源庫所i:·i=φ;

2)PN具有一個匯庫所o:o·=φ;

3)如果添加一個變遷t*到PN,連接庫所i和o,即·t*={i},(t*)·={o},導(dǎo)致Petri網(wǎng)是強(qiáng)連接的。

定義3(活動發(fā)生關(guān)系)WN=(P,T,F)是一個工作流網(wǎng),Σ為所有可能發(fā)生序列的集合,t1和t2為活動,且t1,t2∈T

1)因果關(guān)系:若t1發(fā)生可使t2發(fā)生,則t1和t2之間存在因果關(guān)系,記作t1→t2或t2←t1(即逆序關(guān)系),如圖1a;

2)并行關(guān)系:若t1發(fā)生可使t2發(fā)生,同時t2的發(fā)生可使t1發(fā)生,則稱t1和t2之間存在并行關(guān)系,記作t1‖t2或t2‖t1,如圖1b;

3)互斥關(guān)系:t1和t2不能同時發(fā)生,則稱t1和t2之間存在互斥關(guān)系,記作t1#t2或t2#t1,如圖1c。

圖1 活動發(fā)生關(guān)系圖

比較兩個工作流網(wǎng)之間的相似性的前提是它們是σ-兼容的。如果它們不σ-兼容,那么認(rèn)為它們不相似,不需要繼續(xù)比較它們。

在圖2中,給出了3個工作流網(wǎng)g0,g1和g2,來說明如何比較工作流網(wǎng)間的兼容性。

圖2 兼容性示例

定義5(活動關(guān)系矩陣)令WN=(P,T,F)為一個工作流網(wǎng),WN的活動關(guān)系矩陣M定義如下:

定義6(活動關(guān)系重要系數(shù))給定兩個工作流網(wǎng)WN1=(P1,T1,F1),WN2=(P2,T2,F2),則因果關(guān)系重要系數(shù)、并行關(guān)系重要系數(shù)、互斥關(guān)系重要系數(shù)分別為I1,I2,I3

定義7(活動關(guān)系相似性)令WN1=(P1,T1,F1),WN2=(P2,T2,F2)為兩個工作流網(wǎng),因果關(guān)系、并行關(guān)系,互斥關(guān)系的相似性分別為sim→(WN1,WN2),sim‖(WN1,WN2),sim#(WN1,WN2)

定義8(WN相似性)令WN1=(P1,T1,F1),WN2=(P2,T2,F2)為兩個工作流網(wǎng),因果關(guān)系、并行關(guān)系,互斥關(guān)系的相似性分別為sim→(WN1,WN2),sim‖(WN1,WN2),sim#(WN1,WN2),則WN1與WN2的相似性為

sim(WN1,WN2)=I1×sim→(WN1,WN2)+I2×sim‖(WN1,WN2)+I3×sim#(WN1,WN2)

2 工作流間的相似性計算

本文提出的基于活動發(fā)生關(guān)系重要系數(shù)的流程模型相似性度量方法即算法1工作流間的相似性計算,首先分析兩個工作流網(wǎng)之間是否兼容,兼容則可計算相似性,然后計算因果關(guān)系、并行關(guān)系、互斥關(guān)系的相似性,最后計算完整的兩個工作流網(wǎng)的相似性。

算法1工作流間的相似性計算

輸入:工作流網(wǎng)WN1與WN2

輸出:WN1與WN2的相似性

Step1:輸入兩個工作流網(wǎng)WN1與WN2;

Step3:遍歷WN1與WN2的所有活動,根據(jù)活動發(fā)生關(guān)系的定義,確定所有活動相互之間的關(guān)系,即t1→t2或t2←t1或t1‖t2或t2‖t1或t1#t2或t2#t1;

Step4:根據(jù)定義5列出WN1與WN2的活動關(guān)系矩陣M1,M2;

Step5:計算WN1與WN2的所有活動關(guān)系的重要系數(shù)I1,I2,I3

Step6:利用定義7計算WN1與WN2中因果關(guān)系、并行關(guān)系、互斥關(guān)系的相似性sim→(WN1,WN2),sim‖(WN1,WN2),sim#(WN1,WN2),

Step7:根據(jù)定義8計算WN1與WN2的相似性

sim(WN1,WN2)=I1×sim→(WN1,WN2)+I2×sim‖(WN1,WN2)+I3×sim#(WN1,WN2)

Step8:算法結(jié)束。

3 實例分析

本文引用文獻(xiàn)[10]的兩個工作流網(wǎng)來驗證算法的可行性,即通過算法1來計算兩個工作流網(wǎng)的相似性,工作流網(wǎng)如圖3。

圖3 工作流網(wǎng)WN1和WN2

運(yùn)行Step3～4,輸出WN1與WN2的活動關(guān)系矩陣M1,M2:

表1 活動關(guān)系矩陣M1

表2 活動關(guān)系矩陣M2

運(yùn)行Step5,計算活動關(guān)系的重要系數(shù)I1,I2,I3,由表2～3可知,

(d,d),(e,e),(f,f),(f,g),(g,g),(g,f)}

運(yùn)行Step6,計算每個活動關(guān)系的相似性:

運(yùn)行Step7,計算WN1與WN2的相似性:

sim(WN1,WN2)=I1×sim→(WN1,WN2)+I2×sim‖(WN1,WN2)+I3×sim#(WN1,WN2)=0.66×0.81+0.09×0.67+0.25×0.69≈0.77

根據(jù)算法1計算WN1與WN2的相似性為0.77。表3展示了用其他算法計算WN1與WN2的相似性。

表3 算法結(jié)果比較

由表3結(jié)果對比可知,算法1與其他算法結(jié)果接近,說明算法1的可行性。

4 結(jié)論與討論

計算流程之間的相似性是在涉及業(yè)務(wù)流程管理的廣泛應(yīng)用中執(zhí)行的任務(wù)。相似性度量可在簡化更改、合并流程、促進(jìn)重用、流程檢索等方面應(yīng)用。為了簡化管理并促進(jìn)流程變量的重用,提出了基于活動發(fā)生關(guān)系重要系數(shù)的流程模型相似性度量方法。首先判斷兩個工作流網(wǎng)的兼容性,其次計算兩個工作流的活動關(guān)系矩陣,并計算兩個工作流網(wǎng)的3種活動關(guān)系的相似性,然后將重要系數(shù)分配給對應(yīng)的活動關(guān)系相似性,最后計算完整的兩個工作流的相似性。算法對比結(jié)果也說明此算法的可行性。未來的工作將解決實際流程之間的相似性度量的其他開放問題,例如具有不同標(biāo)簽字母的過程和以及基于距離度量的過程模型聚類等。