基于活動(dòng)發(fā)生關(guān)系重要系數(shù)的流程模型相似性度量

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

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

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

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

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

1 預(yù)備知識(shí)

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

1)P是有限庫(kù)所集;

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)是一個(gè)工作流網(wǎng),當(dāng)且僅當(dāng):

1)PN具有一個(gè)源庫(kù)所i:·i=φ;

2)PN具有一個(gè)匯庫(kù)所o:o·=φ;

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

定義3(活動(dòng)發(fā)生關(guān)系)WN=(P,T,F)是一個(gè)工作流網(wǎng),Σ為所有可能發(fā)生序列的集合,t1和t2為活動(dòng),且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ā)生,同時(shí)t2的發(fā)生可使t1發(fā)生,則稱t1和t2之間存在并行關(guān)系,記作t1‖t2或t2‖t1,如圖1b;

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

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

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

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

圖2 兼容性示例

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

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

定義7(活動(dòng)關(guān)系相似性)令WN1=(P1,T1,F1),WN2=(P2,T2,F2)為兩個(gè)工作流網(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)為兩個(gè)工作流網(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 工作流間的相似性計(jì)算

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

算法1工作流間的相似性計(jì)算

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

輸出:WN1與WN2的相似性

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

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

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

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

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

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

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

Step8:算法結(jié)束。

3 實(shí)例分析

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

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

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

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

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

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

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

運(yùn)行Step6,計(jì)算每個(gè)活動(dòng)關(guān)系的相似性:

運(yùn)行Step7,計(jì)算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計(jì)算WN1與WN2的相似性為0.77。表3展示了用其他算法計(jì)算WN1與WN2的相似性。

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

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

4 結(jié)論與討論

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