基于活動(dòng)發(fā)生關(guān)系的流程相似性度量方法

李東月,方 歡

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

1 引言

隨著業(yè)務(wù)流程管理(business process management,BPM)在企業(yè)中的影響力越來(lái)越大,流程模型在企業(yè)管理中得到了廣泛的應(yīng)用.業(yè)務(wù)流程是對(duì)企業(yè)業(yè)務(wù)執(zhí)行的一種描述,對(duì)企業(yè)的運(yùn)營(yíng)具有重要的指導(dǎo)意義.因此,業(yè)務(wù)流程模型已經(jīng)成為每個(gè)組織寶貴的智力資產(chǎn),企業(yè)不可缺少的一部分.值得注意的是,累積的流程模型已經(jīng)達(dá)到了一個(gè)驚人的數(shù)字[1],管理動(dòng)輒數(shù)以萬(wàn)計(jì)的流程模型已經(jīng)成為人們面臨的一個(gè)挑戰(zhàn).流程模型的相似性度量已經(jīng)被證實(shí)是管理這些寶貴資產(chǎn)高效的解決方案[2].然而,在處理現(xiàn)有業(yè)務(wù)流程的多樣性時(shí),應(yīng)根據(jù)用戶需求,選擇一種適當(dāng)?shù)姆椒▉?lái)分析業(yè)務(wù)流程的相似性.相似性度量有3種觀點(diǎn):1)元素匹配相似度,比較附加到流程模型上的節(jié)點(diǎn)和邊的對(duì)應(yīng)關(guān)系;2)比較元素標(biāo)簽與流程模型拓?fù)浣Y(jié)構(gòu)的結(jié)構(gòu)相似性;3)比較過(guò)程模型中元素標(biāo)簽及其因果關(guān)系的行為相似性[3].其中,流程模型的行為(執(zhí)行語(yǔ)義)最能體現(xiàn)一個(gè)模型的本質(zhì).

基于標(biāo)簽(元素匹配)的相似性方面往往以模式匹配和本體論為基礎(chǔ),例如基于標(biāo)簽對(duì)齊的相似性度量算法[4]和基于標(biāo)簽語(yǔ)義的相似性度量方法[1].

現(xiàn)今對(duì)流程模型的相似性分析主要從行為相似性和結(jié)構(gòu)相似性兩個(gè)方面來(lái)展開(kāi).首先,在模型的行為相似性方面,基于行為的流程相似性度量方法主要包含以下兩種:

1) 基于流程模型中活動(dòng)間的時(shí)序關(guān)系,如執(zhí)行順序等:文獻(xiàn)[5]提出了一種基于兩個(gè)流程變遷緊鄰關(guān)系(transition adjacency relation,TAR)集的相似性定義,對(duì)流程的相似性進(jìn)行度量,該方法沒(méi)有考慮活動(dòng)緊鄰關(guān)系的重要性,因此對(duì)順序結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的區(qū)分不敏感;文獻(xiàn)[6]提出行為輪廓的概念,對(duì)比基于跡等價(jià)一致性與行為輪廓一致性的計(jì)算結(jié)果,突出行為輪廓相似性算法的優(yōu)越性.文獻(xiàn)[7]在文獻(xiàn)[5]的基礎(chǔ)上,將緊鄰關(guān)系的重要性加以區(qū)分,提出一種基于變遷緊鄰關(guān)系重要性的相似性算法TAR++.文獻(xiàn)[8]提出一種基于任務(wù)之間的時(shí)間關(guān)系查詢流程模型的方法,通過(guò)將截?cái)嗍录B接到延續(xù)事件來(lái)擴(kuò)展完全有限前綴,提取任務(wù)之間的所有時(shí)間關(guān)系,進(jìn)而查詢流程模型;文獻(xiàn)[9]拓展變遷的緊鄰關(guān)系,利用完全有限前綴,提出基于任務(wù)最短距離矩陣的流程模型行為相似性算法,但該算法需要計(jì)算兩個(gè)流程模型的同維化矩陣,不能直接用于模型索引.文獻(xiàn)[10]提供了一個(gè)基于跡語(yǔ)義和抽象的行為包含概念,根據(jù)網(wǎng)系統(tǒng)能否重放查詢行為進(jìn)行模型匹配,衡量模型的相似性,該方法只匹配了活動(dòng)間的行為關(guān)系,沒(méi)有考慮模型結(jié)構(gòu);文獻(xiàn)[11]提出了一種基于業(yè)務(wù)流程內(nèi)部結(jié)構(gòu)的相似性度量方法,給出映射函數(shù),通過(guò)計(jì)算單個(gè)節(jié)點(diǎn)(變遷和庫(kù)所)的相似性,將所有變遷或庫(kù)所的相似性加權(quán)求和,進(jìn)而求得流程的相似性.文獻(xiàn)[12]提出了基于Petri網(wǎng)的映射變遷關(guān)系相似性度量方法,給出5種變遷關(guān)系定義,利用變遷的行為關(guān)系,度量相同變遷節(jié)點(diǎn)在不同流程中結(jié)構(gòu)上的相似性,計(jì)算流程相似性;文獻(xiàn)[13]通過(guò)將模型的行為關(guān)系用變遷標(biāo)簽圖來(lái)表征,結(jié)合圖理論,提出一種基于可覆蓋圖編輯距離的行為相似性度量算法(transition-labeled graph edit distance,TAGER);文獻(xiàn)[14]提出了一種基于包含領(lǐng)域知識(shí)的語(yǔ)義任務(wù)重要性緊鄰關(guān)系(semantic task adjacency relations with importance,ISTARs)的語(yǔ)義工作流行為相似度度量方法.文獻(xiàn)[15]利用Petri網(wǎng)的完全前綴展開(kāi)理論和任務(wù)的發(fā)生關(guān)系,提出一種基于任務(wù)發(fā)生關(guān)系的流程模型相似性度量(task occurrence relation,TOR);文獻(xiàn)[16]將行為輪廓中的交叉關(guān)系細(xì)化為6種類型,提出了細(xì)化的基于行為輪廓矩陣的相似性度量方法.

2) 基于流程模型的變遷發(fā)生序列集合[11].文獻(xiàn)[17]提出了一種基于主變遷序列的相似度度量方法(principal transition sequences,PTS),利用過(guò)程模型的語(yǔ)義,將主變遷序列分成三類,分別定義每類主變遷序列的相似性計(jì)算方法,進(jìn)而計(jì)算流程的相似性;該方法將完整的發(fā)生序列分開(kāi)考慮,破壞了語(yǔ)義的完整性;文獻(xiàn)[18]對(duì)文獻(xiàn)[17]的方法進(jìn)行研究,針對(duì)PTS方法存在的問(wèn)題,利用完整的發(fā)生序列表征模型的行為,提出一種基于觸發(fā)序列的流程相似分析方法PTS++;文獻(xiàn)[19]提出了一種基于約束跡的過(guò)程相似度量化方法,以約束的最長(zhǎng)公共子序列為基礎(chǔ),利用約束跡對(duì)齊計(jì)算流程的相似性.

其次,在流程模型的結(jié)構(gòu)相似性研究方面,目前大多研究方法基于圖的理論進(jìn)行結(jié)構(gòu)相似度計(jì)算[20–21],而在模型結(jié)構(gòu)轉(zhuǎn)為圖的過(guò)程中會(huì)丟失一些語(yǔ)義信息,導(dǎo)致無(wú)法有效區(qū)分圖中活動(dòng)之間存在的是選擇關(guān)系還是并發(fā)關(guān)系,因此僅僅將結(jié)構(gòu)轉(zhuǎn)為有向圖不能準(zhǔn)確表現(xiàn)原有流程,必須結(jié)合一些流程行為信息,以更全面地表達(dá)原流程.為了彌補(bǔ)上述不足,文獻(xiàn)[22]提出了一種基于Petri網(wǎng)選擇性約簡(jiǎn)模型的業(yè)務(wù)流程結(jié)構(gòu)相似性分析方法,以識(shí)別不同業(yè)務(wù)流程之間的相似活動(dòng),分析流程的結(jié)構(gòu)相似性;文獻(xiàn)[23]綜合考慮模型結(jié)構(gòu)與日志行為,提出一種基于模型結(jié)構(gòu)與日志行為的流程相似度計(jì)算方法,根據(jù)模型中行為在日志中的發(fā)生概率為業(yè)務(wù)流程圖加權(quán),并根據(jù)加權(quán)業(yè)務(wù)流程圖編輯距離的定義計(jì)算流程的相似性.文獻(xiàn)[24]提出了一種基于累積分布函數(shù)的相似度計(jì)算方法.該方法通過(guò)隱馬爾可夫模型(hidden Markov model,HMM)建模和狀態(tài)序列引用從拓?fù)浣Y(jié)構(gòu)中挖掘底層拓?fù)湔Z(yǔ)義,并根據(jù)累積分布函數(shù)計(jì)算兩種拓?fù)浣Y(jié)構(gòu)之間的相似度.文獻(xiàn)[25]以現(xiàn)有流程行為相似度度量方法的不足為出發(fā)點(diǎn),提出了一種基于擴(kuò)展轉(zhuǎn)移關(guān)系集(etri集)的業(yè)務(wù)流程行為相似度綜合度量方法.通過(guò)構(gòu)造一個(gè)并發(fā)可達(dá)圖獲得etri集,定義一種新的流程行為相似度度量方法,進(jìn)行流程相似性度量.

綜上所述,現(xiàn)有的流程模型行為相似性算法大都基于變遷發(fā)生序列或存在計(jì)算效率較低的問(wèn)題,因此,本文提出一種基于活動(dòng)發(fā)生關(guān)系的流程相似性度量方法,利用活動(dòng)節(jié)點(diǎn)的左右集及發(fā)生關(guān)系度量流程的相似性.本文的主要貢獻(xiàn)主要有以下幾點(diǎn):

1) 基于標(biāo)簽Petri網(wǎng)進(jìn)行業(yè)務(wù)流程建模,并提出了活動(dòng)發(fā)生關(guān)系的概念和活動(dòng)節(jié)點(diǎn)的左右集概念;

2) 在最佳活動(dòng)映射的前提下,將活動(dòng)在左右集上的結(jié)構(gòu)特征與活動(dòng)間發(fā)生關(guān)系變化與否相結(jié)合,提出了兩個(gè)不同流程之間的活動(dòng)相似性,反映了相同活動(dòng)節(jié)點(diǎn)在不同結(jié)構(gòu)上的相似性,并提出流程相似性度的概念來(lái)計(jì)算整個(gè)流程的相似性.

3) 提出了一種基于活動(dòng)發(fā)生關(guān)系的流程相似性算法,通過(guò)實(shí)驗(yàn)對(duì)該算法進(jìn)行了分析驗(yàn)證,給出了一種流程行為相似性度量的新方法.

2 相關(guān)知識(shí)

本文以Petri網(wǎng)建模語(yǔ)言為工具,采用圖形的方式將不同的業(yè)務(wù)流程展現(xiàn)出來(lái),對(duì)其相似性加以分析和度量.

定義1標(biāo)簽Petri網(wǎng)[13].

滿足下列條件的五元組LN=(P,T;F,Φ,L)稱為一個(gè)標(biāo)簽Petri網(wǎng):

1) P為庫(kù)所的有限集合;

2) T為變遷的有限集合;

3) F ?(P ×T)∪(T ×P)為流關(guān)系,即有向邊的集合;

4) L:T →Φ ∪{ε}是標(biāo)簽映射函數(shù),其中,Φ為活動(dòng)標(biāo)簽的集合;

若滿足前3個(gè)條件,則稱為一個(gè)Petri網(wǎng),記為N=(P,T;F).

P和T統(tǒng)稱為網(wǎng)LN的節(jié)點(diǎn),即P ∪T ∈X,若?y∈X,使得(y,x)∈F,則稱y為x的前集節(jié)點(diǎn),所有前集節(jié)點(diǎn)的集合稱為x的前集,即·x={y ∈X|(y,x)∈F};若?y ∈X,使得(x,y)∈F,則稱y為x的后集節(jié)點(diǎn),所有后集節(jié)點(diǎn)的集合稱為x的后集,即x·={y ∈X|(x,y)∈F}.與節(jié)點(diǎn)相鄰的邊稱為節(jié)點(diǎn)的邊,包含輸入邊和輸出邊.圖1給出了一個(gè)最簡(jiǎn)單的標(biāo)簽Petri網(wǎng)的示例.

圖1 最簡(jiǎn)單的標(biāo)簽Petri網(wǎng)Fig.1 The simplest label Petri net

當(dāng)選擇Petri網(wǎng)作為建模工具的時(shí)候,通常會(huì)考慮Petri網(wǎng)的子類–工作流網(wǎng)(work flow net,WF–net).由于其只有一個(gè)源庫(kù)所(起始庫(kù)所)和一個(gè)結(jié)束庫(kù)所,流程開(kāi)始于源庫(kù)所(起始庫(kù)所),完成于結(jié)束庫(kù)所,并且所有節(jié)點(diǎn)都屬于從源庫(kù)所(起始庫(kù)所)到結(jié)束庫(kù)所的路徑上.其簡(jiǎn)潔明了的結(jié)構(gòu)特性便于人們進(jìn)行業(yè)務(wù)流程的分析.此時(shí),變遷表示實(shí)際業(yè)務(wù)流程中的行為活動(dòng),庫(kù)所表示相關(guān)活動(dòng)的執(zhí)行條件或狀態(tài).

定義2工作流網(wǎng)[7].

滿足下列條件的標(biāo)簽Petri網(wǎng)稱為一個(gè)工作流網(wǎng)(WF–net):

1) 只存在一個(gè)輸入庫(kù)所i ∈P,使得·i=?;

2) 只存在一個(gè)輸出庫(kù)所o ∈P,使得o·=?;

3) LN=(P,T;F,Φ,L)為強(qiáng)連通的,即N的所有節(jié)點(diǎn)x ∈P ∪T,都屬于i到o的一條有向路徑上.

六元組WFN=(P,T;F,Φ,L,M0)稱為一個(gè)工作流網(wǎng)系統(tǒng),其中M0為網(wǎng)系統(tǒng)的初始標(biāo)識(shí).

定義3跡.

令六元組WFN=(P,T;F,Φ,L,M0)為一個(gè)工作流網(wǎng),變遷的發(fā)生序列稱為工作流網(wǎng)的跡,記作σ=(t1,t2,···,tn),其中ti∈T(i=1,2,···,n).

在工作流網(wǎng)的基礎(chǔ)上,任意2個(gè)變遷在整個(gè)工作流網(wǎng)的結(jié)構(gòu)上存在著不同的關(guān)系,為了便于表述,在進(jìn)行活動(dòng)發(fā)生關(guān)系相似性度量之前,首先對(duì)活動(dòng)之間的關(guān)系進(jìn)行如下定義(見(jiàn)定義4).

定義4活動(dòng)發(fā)生關(guān)系.

令六元組WFN=(P,T;F,Φ,L,M0)為一個(gè)工作流網(wǎng),Tr為WFN所有可能的執(zhí)行序列集合,并且活動(dòng)a,b ∈T.

1) 強(qiáng)序關(guān)系(strict order):若存在一條跡σ=(···,ti,tj,···)∈Tr,其中j=i+1,使得ti=a,tj=b,則活動(dòng)a和活動(dòng)b稱滿足強(qiáng)序關(guān)系,記作a →b.顯然,強(qiáng)序關(guān)系不具有對(duì)稱性和傳遞性;

2) 并發(fā)關(guān)系(concurrency):至少?σ1,σ2∈Tr,σ1=(···,ti,tj,···),σ2=(···,tj,ti,···),使得ti=a,tj=b,則活動(dòng)a和活動(dòng)b稱滿足并發(fā)關(guān)系,記作a+b.顯然,并發(fā)關(guān)系具有對(duì)稱性,不具有傳遞性;

3) 互斥關(guān)系(mutex):不存在σ=(···,ti,···,tj,···),使得ti=a,tj=b,即活動(dòng)a與活動(dòng)b不會(huì)出現(xiàn)在同一條跡中,則活動(dòng)a和活動(dòng)b稱滿足互斥關(guān)系,記作a×b,顯然,互斥關(guān)系具有對(duì)稱性.

強(qiáng)序關(guān)系、并發(fā)關(guān)系和互斥關(guān)系統(tǒng)稱為活動(dòng)的發(fā)生關(guān)系,記作R.

圖2對(duì)活動(dòng)的強(qiáng)序關(guān)系、并發(fā)關(guān)系和互斥關(guān)系作了一個(gè)直觀的闡釋.

圖2 活動(dòng)的發(fā)生關(guān)系Fig.2 Occurrence relationship between activities

活動(dòng)發(fā)生關(guān)系的變化在流程相似性分析中至關(guān)重要,例如:活動(dòng)a和活動(dòng)b在流程A中為強(qiáng)序關(guān)系,在流程B中為互斥關(guān)系,在流程C中為并發(fā)關(guān)系,假設(shè)流程A對(duì)應(yīng)的模型為原模型,那么活動(dòng)a和活動(dòng)b的行為關(guān)系由強(qiáng)序變到互斥,說(shuō)明這種行為變化將本來(lái)直接跟隨的兩個(gè)活動(dòng)直接變成了不會(huì)同時(shí)出現(xiàn)在一條跡中,嚴(yán)重破壞了流程A與流程B的相似性;如果活動(dòng)a和活動(dòng)b的發(fā)生關(guān)系由強(qiáng)序變到并發(fā),由于并發(fā)關(guān)系保留了活動(dòng)a和活動(dòng)b的強(qiáng)序關(guān)系,所以此種行為關(guān)系變化對(duì)流程A與流程C相似性的破壞相對(duì)較小.下面將這種破壞性程度定義為違背度,并給出形式化定義:

定義5違背度.

兩流程中相同活動(dòng)對(duì)發(fā)生關(guān)系的偏差程度稱為違背度,記作V(R,R′).令流程A中活動(dòng)a和活動(dòng)b的發(fā)生關(guān)系為→,流程B中活動(dòng)a和活動(dòng)b的發(fā)生關(guān)系為×,流程C中活動(dòng)a和活動(dòng)b的發(fā)生關(guān)系為+,則V(→,+)

定義6左集和右集.

令六元組WFN=(P,T;F,Φ,L,M0)為一個(gè)工作流網(wǎng),Tr為WFN所有可能的執(zhí)行序列,并且a,b,c ∈T,若?σ=(···,ti,tj,tk,···)∈Tr,其中:i=j ?1,k=j+1,使得ti=b,tj=a,tk=c,則稱b為a的左集活動(dòng),c為a的右集活動(dòng),a的所有左集活動(dòng)組成的集合稱為a 的左集,記作La,a的所有右集活動(dòng)組成的集合稱為a的右集,記作Ra.

本文所討論的Petri網(wǎng),均是基于安全的工作流網(wǎng).所謂安全的,是指流程在運(yùn)行時(shí),網(wǎng)的任意庫(kù)所中最多只有一個(gè)token.

3 基于活動(dòng)發(fā)生關(guān)系的流程相似性分析方法

在大多數(shù)相似性計(jì)算方法中,建立表示兩個(gè)模型元素之間對(duì)應(yīng)關(guān)系的映射函數(shù)是首要工作,而本文是在良好變遷映射的前提下,通過(guò)計(jì)算不同流程中同一活動(dòng)節(jié)點(diǎn)(相同活動(dòng)節(jié)點(diǎn))在結(jié)構(gòu)上的相似度,進(jìn)而求得整個(gè)流程的相似度.

本文從活動(dòng)節(jié)點(diǎn)的角度考察流程的相似性,認(rèn)為一個(gè)活動(dòng)節(jié)點(diǎn)的左集和右集共同作用,影響流程的相似性,故將活動(dòng)節(jié)點(diǎn)相似性分為兩部分:左集相似性、右集相似性,具體定義如下所示.

定義7活動(dòng)相似性.

經(jīng)過(guò)反復(fù)多次實(shí)驗(yàn)計(jì)算,本文中取α,β ∈{0.4,0.5,0.6},形式化取值法則將在下文第3.1節(jié)“基于活動(dòng)發(fā)生關(guān)系的流程相似性算法(activity occurrence relation,AOR)”中進(jìn)行闡述.

在這里α,β不僅起到權(quán)重的作用,同時(shí)通過(guò)巧妙地選擇左右集權(quán)重的取值,權(quán)衡了不同流程中活動(dòng)的相似性程度,也體現(xiàn)了違背度的具體含義與文章前半部分的中心思想.同時(shí)α,β的具體取值要根據(jù)實(shí)際情況進(jìn)行分析(結(jié)合活動(dòng)發(fā)生關(guān)系的變化情況(違背度)與單個(gè)活動(dòng)的結(jié)構(gòu)相似性特征).

圖3對(duì)權(quán)重α和β選擇(0.4,0.5,0.6)何值作出具體解釋.

圖3 流程A,B,C的Petri網(wǎng)模型Fig.3 Petri net models of process A,B and C

為了符合定義6,為圖3中的流程分別人工添加一個(gè)開(kāi)始庫(kù)所ps和變遷as,一個(gè)結(jié)束庫(kù)所pe和變遷ae,4條邊(ps,as),(as,p0),(p4,ae),(ae,pe),如圖4所示.

圖4 人工改造后的A′,B′,C′Petri網(wǎng)模型Fig.4 Manual modified Petri net models of process A′,B′and C′

此時(shí)考察流程A與C中活動(dòng)b和c的相似性:同理可得

發(fā)現(xiàn)有SA,B(b)=SA,C(b),SA,B(c)=SA,C(c),這是因?yàn)榛顒?dòng)b在流程A與B中左右集,與在流程A與C中的左右集相等,活動(dòng)c同理,同時(shí)也說(shuō)明了引入α,β的必要性.這時(shí),因?yàn)閎,c在流程A中的發(fā)生關(guān)系為b →c,在流程B中的發(fā)生關(guān)系為b×c,在流程C的發(fā)生關(guān)系為b+c,又由于V(→,+)0和0<1),分別取α=0.4,β=0.6, α=0.6, β=0.4;計(jì)算A 與C中b,c的相似度時(shí),分別取α=0.5,β=0.5,則

綜上所述,當(dāng)活動(dòng)發(fā)生關(guān)系不變或由強(qiáng)序變?yōu)椴l(fā)時(shí),取α=β=0.5;發(fā)生關(guān)系由強(qiáng)序變?yōu)榛コ鈺r(shí),根據(jù)活動(dòng)左右結(jié)構(gòu)相似性的大小進(jìn)行取值(α,β ∈{0.4,0.6}).

需要說(shuō)明的是,上述討論的是兩個(gè)強(qiáng)序關(guān)系的活動(dòng)變?yōu)榛コ饣虿l(fā)的情況,對(duì)于由弱序變?yōu)榛コ饣虿l(fā)時(shí),此方法同樣適用.

定義8流程相似性.

令WFN1=(P1,T1;F1,Φ1,L1,M0)為流程1的工作流網(wǎng),WFN2=(P2,T2;F2,Φ2,L2,M′0)為流程2的工作流網(wǎng),則流程1與流程2的相似性為

其中分母減去2是為了消除人工初始、結(jié)束變遷的影響.

根據(jù)式(2),圖3中流程A與B的相似性為

流程A與C的相似性為

3.1 基于活動(dòng)發(fā)生關(guān)系的流程相似性算法(AOR)

算法1基于活動(dòng)發(fā)生關(guān)系的流程相似性算法.

輸入:流程模型M1和M2;

輸出:M1和M2的相似性度.

步驟如下:

3.2 算法時(shí)間復(fù)雜度分析

首先分析算法的時(shí)間復(fù)雜度.給定一個(gè)工作流網(wǎng)W,變遷集為T(mén),庫(kù)所集為P,流關(guān)系集為F,AOR算法遍歷W中除輸出庫(kù)所外的所有節(jié)點(diǎn)及流關(guān)系,操作所需時(shí)間為O(|T|+|P|+|F|).條件判斷、計(jì)算權(quán)重、并入操作、賦予顏色、出隊(duì)、入隊(duì)等操作所需時(shí)間均為O(1),總時(shí)間為O(1).因此AOR算法的時(shí)間復(fù)雜度為O(|T|+|P|+|F|),而目前主流算法中,計(jì)算效率較高的基于變遷緊鄰關(guān)系重要性的流程相似性(TAR++)算法的最壞時(shí)間復(fù)雜度為O(V +E+N!),是一個(gè)階乘級(jí)的復(fù)雜度,即使運(yùn)用所給的兩種加速方式,其時(shí)間復(fù)雜度也不可能低于O(|T|+|P|+|F|).

4 案例分析

本節(jié)通過(guò)兩個(gè)具體的業(yè)務(wù)流程來(lái)驗(yàn)證所提出相似性算法的可行性,即利用基于活動(dòng)發(fā)生關(guān)系的流程相似性算法(AOR),度量?jī)蓚€(gè)業(yè)務(wù)流程的相似程度(省略人工改造后的Petri網(wǎng)模型),流程模型如圖5所示.

圖5 流程1和2的Petri網(wǎng)模型Fig.5 Petri net models of process 1 and 2

下面以流程1和流程2的Petri網(wǎng)模型作為輸入,執(zhí)行基于活動(dòng)發(fā)生關(guān)系的流程相似性算法(AOR).

執(zhí)行算法Step1,輸出相同活動(dòng)的左右集:

5 實(shí)驗(yàn)設(shè)計(jì)與仿真分析

實(shí)驗(yàn)機(jī)器環(huán)境為:Intel Core I5–7200U CPU@可加速至3.1 Hz,內(nèi)存為8 GB,Window10 64位操作系統(tǒng).

5.1 實(shí)驗(yàn)設(shè)計(jì)

本節(jié)實(shí)驗(yàn)主要分兩階段進(jìn)行,第1階段為算法的可行性分析,第2階段為算法的性能分析.實(shí)驗(yàn)涉及的數(shù)據(jù)集由兩部分組成:450個(gè)典型的業(yè)務(wù)流程模型來(lái)自SAP模型庫(kù),50個(gè)人工流程模型,為滿足實(shí)驗(yàn)需要由人工編撰.首先將500個(gè)業(yè)務(wù)流程模型運(yùn)用本文提出的相似性算法(AOR),計(jì)算出兩兩模型之間的相似性度,利用實(shí)驗(yàn)結(jié)果分析以及相似性結(jié)果均屬于0～1,初步驗(yàn)證算法的可行性,并對(duì)同樣的模型運(yùn)用主流的相似性算法,與AOR算法結(jié)果作對(duì)比,進(jìn)一步驗(yàn)證算法結(jié)果的正確性.然后,對(duì)不同規(guī)模的數(shù)據(jù)集應(yīng)用本文算法和主流的相似性算法,通過(guò)算法運(yùn)行時(shí)間對(duì)比,驗(yàn)證本算法良好的性能體現(xiàn).

5.2 效果評(píng)估

對(duì)500個(gè)業(yè)務(wù)流程模型應(yīng)用本算法,限于篇幅,本節(jié)僅給出10個(gè)流程模型(其中6個(gè)來(lái)自SAP模型庫(kù),4個(gè)來(lái)自人工模型,具體請(qǐng)參見(jiàn)鏈接https://pan.baidu.com/s/1PmQDvFrEXg-JTzT2UoD-Gw)的實(shí)驗(yàn)結(jié)果,如表1所示.可以看出,本算法得出的實(shí)驗(yàn)結(jié)果均在0 ～1范圍內(nèi),當(dāng)流程完全相同時(shí),實(shí)驗(yàn)結(jié)果為1,當(dāng)流程完全不同時(shí),實(shí)驗(yàn)結(jié)果為0.由此,初步驗(yàn)證了本算法的可行性.

表1 AOR算法得到的10個(gè)流程模型的相似性度Table 1 Similarity of 10 process models derived from AOR algorithm

為進(jìn)一步驗(yàn)證算法的正確性,從500個(gè)流程模型中任意抽出300個(gè)模型運(yùn)用主流的相似性算法與AOR相似性算法,將得到的實(shí)驗(yàn)結(jié)果與本算法做對(duì)比.對(duì)比算法包括基于行為的度量方法:1)行為輪廓相似性算法(behavioral profile,BP)[6,8],細(xì)化了活動(dòng)發(fā)生關(guān)系,給出行為輪廓概念,進(jìn)而度量模型相似性,但該算法對(duì)并發(fā)結(jié)構(gòu)不敏感;2)任務(wù)最短跟隨距離矩陣的相似性算法(shortest sucession distances between tasks,SSDT)[9],用兩兩活動(dòng)間的最短跟隨距離表征模型行為,問(wèn)題在于該算法需要計(jì)算兩個(gè)流程模型的同維化矩陣,降低了算法的運(yùn)算效率.基于變遷緊鄰關(guān)系重要性的流程相似性算法(TAR++)[7],在考慮模型行為的基礎(chǔ)上對(duì)邊加權(quán),有效的改進(jìn)了現(xiàn)有的算法.基于模型內(nèi)部結(jié)構(gòu)的流程相似性度量方法(total-mappingmodel,TMM)[11],該方法采取迭代映射來(lái)映射庫(kù)所和變遷,進(jìn)而識(shí)別兩個(gè)模型的對(duì)應(yīng)關(guān)系.但其忽略活動(dòng)文本標(biāo)簽的語(yǔ)義,使得到的模型不夠準(zhǔn)確.

本節(jié)僅給出人工模型M1和M2(圖6)及其實(shí)驗(yàn)對(duì)比結(jié)果(表2),根據(jù)本文提出的AOR相似性算法,模型M1和M2的行為相似性度為0.23,由表2可以看出,AOR算法的運(yùn)算結(jié)果與主流算法比較接近,進(jìn)一步驗(yàn)證了算法的正確性.

圖6 Petri網(wǎng)模型M1和M2Fig.6 Petri net models M1andM2

表2 與主流算法的實(shí)驗(yàn)結(jié)果比較Table 2 Comparisons with experimental results of mainstream algorithms

5.3 性能評(píng)估

為評(píng)估AOR算法在實(shí)際應(yīng)用中的性能體現(xiàn),將抽取的300個(gè)實(shí)驗(yàn)?zāi)Ｐ头殖刹煌臄?shù)據(jù)集(數(shù)據(jù)集1、數(shù)據(jù)集2、數(shù)據(jù)集3),分別包含70,90和140個(gè)流程模型,表3列出了各數(shù)據(jù)集的基本特征:所含平均變遷數(shù)、最大變遷數(shù)、平均庫(kù)所數(shù)、最大庫(kù)所數(shù)、平均邊數(shù)、最大邊數(shù).目的是利用算法在不同復(fù)雜程度模型上的花費(fèi),驗(yàn)證算法的性能表現(xiàn).

為更加直觀地比較AOR算法與其他主流算法,根據(jù)表3信息,將算法在不同復(fù)雜程度數(shù)據(jù)集上的運(yùn)行時(shí)間制成柱形圖,橫坐標(biāo)為不同的數(shù)據(jù)集,縱坐標(biāo)為運(yùn)行時(shí)間,如圖7所示.由圖7可以看出,對(duì)于任意一種復(fù)雜程度的數(shù)據(jù)集,AOR算法所花費(fèi)的時(shí)間都稍低與其他算法,運(yùn)算效率最高,而行為輪廓相似性算法(BP)的運(yùn)行時(shí)間明顯高于其他算法,運(yùn)算效率最低.

表3 不同規(guī)模下的算法性能體現(xiàn)Table 3 Performance of algorithms at different scales

圖7 不同算法的運(yùn)行時(shí)間對(duì)比Fig.7 Comparisons of runtime for different algorithms

另外,本文方法(AOR)與文獻(xiàn)[11](TMM)不同之處在于不需要定義不同流程中的活動(dòng)節(jié)點(diǎn)映射,本文是在最佳的變遷節(jié)點(diǎn)映射條件下,進(jìn)行流程的相似性度量.并且文獻(xiàn)[13]是從左右集的交叉元素與節(jié)點(diǎn)左右分支的結(jié)構(gòu)考慮節(jié)點(diǎn)的相似性,進(jìn)而度量整個(gè)流程的相似性.而本文是結(jié)合活動(dòng)節(jié)點(diǎn)左右集的重復(fù)元素與活動(dòng)發(fā)生關(guān)系在整個(gè)流程中是否發(fā)生變化,來(lái)度量流程的相似性.

6 結(jié)語(yǔ)與展望

為了一定程度上解決大量流程模型的管理問(wèn)題,提高模型檢索、重用以及流程合并的效率,本文提出了一種基于模型時(shí)序關(guān)系(執(zhí)行順序)的流程行為相似性算法,該算法在標(biāo)簽Petri網(wǎng)和良好的變遷映射基礎(chǔ)上,模型結(jié)構(gòu)與行為相結(jié)合,將活動(dòng)在左右集上的結(jié)構(gòu)相似性與活動(dòng)間發(fā)生關(guān)系在不同流程的變化情況綜合考慮,進(jìn)一步識(shí)別活動(dòng)的相似性,然后,通過(guò)將活動(dòng)的相似性進(jìn)行歸一化處理,給出流程相似性定義,最后,提出基于活動(dòng)發(fā)生關(guān)系的流程相似性算法(AOR)度量不同流程的相似性.實(shí)驗(yàn)結(jié)果表明,該算法能夠正確的計(jì)算不同流程的相似性,與其他相似算法相比,具有更高的時(shí)空復(fù)雜度.

該相似性算法尚存在一些不足,算法適用于當(dāng)相同活動(dòng)節(jié)點(diǎn)的左右集與“原模型”左右集不同時(shí),未考慮左右集相等的情況.另外,如何將AOR方法應(yīng)用于工業(yè)場(chǎng)景,未來(lái)將對(duì)這些工作做進(jìn)一步研究,以使算法具有更強(qiáng)的適應(yīng)能力.