李東月,方 歡

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

1 引言

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

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

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

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

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

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

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

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

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

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

2 相關(guān)知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義3跡.

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

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

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

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

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

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

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

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

圖2對活動的強序關(guān)系、并發(fā)關(guān)系和互斥關(guān)系作了一個直觀的闡釋.

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

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

定義5違背度.

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

定義6左集和右集.

令六元組WFN=(P,T;F,Φ,L,M0)為一個工作流網(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的左集活動,c為a的右集活動,a的所有左集活動組成的集合稱為a 的左集,記作La,a的所有右集活動組成的集合稱為a的右集,記作Ra.

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

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

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

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

定義7活動相似性.

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

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

圖3對權(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中的流程分別人工添加一個開始庫所ps和變遷as,一個結(jié)束庫所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′

此時考察流程A與C中活動b和c的相似性:同理可得

發(fā)現(xiàn)有SA,B(b)=SA,C(b),SA,B(c)=SA,C(c),這是因為活動b在流程A與B中左右集,與在流程A與C中的左右集相等,活動c同理,同時也說明了引入α,β的必要性.這時,因為b,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;計算A 與C中b,c的相似度時,分別取α=0.5,β=0.5,則

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

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

定義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 基于活動發(fā)生關(guān)系的流程相似性算法(AOR)

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

輸入:流程模型M1和M2;

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

步驟如下:

3.2 算法時間復雜度分析

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

4 案例分析

本節(jié)通過兩個具體的業(yè)務(wù)流程來驗證所提出相似性算法的可行性,即利用基于活動發(fā)生關(guān)系的流程相似性算法(AOR),度量兩個業(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í)行基于活動發(fā)生關(guān)系的流程相似性算法(AOR).

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

5 實驗設(shè)計與仿真分析

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

5.1 實驗設(shè)計

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

5.2 效果評估

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

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

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

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

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

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

5.3 性能評估

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

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

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

圖7 不同算法的運行時間對比Fig.7 Comparisons of runtime for different algorithms

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

6 結(jié)語與展望

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

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