面向綜合特征提取的流程相似度模型

常關(guān)羽, 楊海成, 莫 蓉, 孫 鵬

(現(xiàn)代設(shè)計(jì)與集成制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(西北工業(yè)大學(xué))， 西安 710072)

面向綜合特征提取的流程相似度模型

常關(guān)羽, 楊海成, 莫 蓉, 孫 鵬

(現(xiàn)代設(shè)計(jì)與集成制造技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(西北工業(yè)大學(xué))， 西安 710072)

針對(duì)流程相似度計(jì)算研究中注重流程結(jié)構(gòu)而缺乏兼顧流程語(yǔ)義的問(wèn)題，以及現(xiàn)有相似度計(jì)算方法在計(jì)算復(fù)雜度上的不足，提出一種基于流程綜合特征提取的相似度計(jì)算模型. 基于流程基本控制結(jié)構(gòu)分析，提出邊權(quán)重標(biāo)注方法以擴(kuò)展現(xiàn)有流程結(jié)構(gòu)，提取流程結(jié)構(gòu)特征；定義流程高層語(yǔ)義模型及其對(duì)應(yīng)特征提取方法； 融合了節(jié)點(diǎn)集、邊集相似度，給出新的流程結(jié)構(gòu)相似度定義，利用集合關(guān)系和向量空間模型計(jì)算流程語(yǔ)義相似度； 通過(guò)加權(quán)實(shí)現(xiàn)綜合流程相似度評(píng)價(jià)，并采用權(quán)重參數(shù)調(diào)節(jié)的方式實(shí)現(xiàn)了同已有相似度計(jì)算方法的自適應(yīng)轉(zhuǎn)化. 將本文模型與典型相似度計(jì)算方法進(jìn)行了實(shí)驗(yàn)對(duì)比，結(jié)果表明,面向綜合特征提取的流程相似度計(jì)算方法更具普適性，同時(shí)具有更高效的計(jì)算能力.

流程模型；業(yè)務(wù)語(yǔ)義；特征提?。涣鞒滔嗨贫?；流程匹配

近年來(lái)，隨著業(yè)務(wù)流程管理技術(shù)和業(yè)務(wù)流程模型表達(dá)重點(diǎn)的轉(zhuǎn)移，相關(guān)領(lǐng)域?qū)＜液脱芯繉W(xué)者從不同視角對(duì)流程相似度分析進(jìn)行了研究[1-2]，定義了多種業(yè)務(wù)流程相似度評(píng)價(jià)模型. 作為一種對(duì)流程的有效表達(dá)方式，流程結(jié)構(gòu)圖及其相似度計(jì)算受到了廣泛關(guān)注. 如最大共享子圖匹配和圖編輯距離計(jì)算都是基于圖的相似度計(jì)算的代表[3]. 基于流程的動(dòng)態(tài)表現(xiàn)可以提取流程的動(dòng)態(tài)模式，并以此模式來(lái)度量相似度. 該類方法主要特點(diǎn)是對(duì)流程活動(dòng)節(jié)點(diǎn)進(jìn)行標(biāo)注，通過(guò)對(duì)標(biāo)注信息的比較,確定流程活動(dòng)相似度,即流程的相似度是基于活動(dòng)的流控結(jié)構(gòu)和動(dòng)態(tài)行為進(jìn)行度量的[4-5]. Wang等[6]使用標(biāo)注PetriNet實(shí)現(xiàn)業(yè)務(wù)流程模型表達(dá)，并以PetriNet的主要變遷序列(稱為流程行為)來(lái)度量流程相似度. 而Kunze[5]等以流程活動(dòng)配對(duì)方式提取流程特征，并基于Jaccard系數(shù)定義流程行為模式完成流程相似度計(jì)算. Li等[7]在服務(wù)組合研究中，為了尋找類似的子流程，采用一種以結(jié)構(gòu)為基礎(chǔ)的流程相似度計(jì)算方法，通過(guò)鄰接矩陣計(jì)算流程相似度. 此類方法聚焦于流程結(jié)構(gòu)中單獨(dú)元素，而較少考慮到流程元素間相互作用對(duì)相似度的影響. 為了提升相似度計(jì)算準(zhǔn)確度，將與流程相關(guān)的各類資源(數(shù)據(jù)、人力、物力)加入到相似度的測(cè)定中. Baumann等[8]考慮了與活動(dòng)相關(guān)聯(lián)的業(yè)務(wù)操作人、業(yè)務(wù)數(shù)據(jù)對(duì)象和活動(dòng)順序，將活動(dòng)1-1的匹配模式改變?yōu)榛顒?dòng)集合間N-M的匹配模式以計(jì)算流程相似度. Chan等[9]采用類似的思路，將與活動(dòng)相關(guān)的鄰居活動(dòng)節(jié)點(diǎn)信息定義為活動(dòng)上下文，通過(guò)上下文比較得出流程相似度. Montani等[10]提出了一種知識(shí)密集性的流程相似度計(jì)算模型，該模型結(jié)合領(lǐng)域知識(shí)擴(kuò)展了圖編輯距離計(jì)算模型，將活動(dòng)類型及其輸入、輸出納入到流程相似度計(jì)算. 基于流程語(yǔ)義相似度計(jì)算主要考慮了流程節(jié)點(diǎn)的執(zhí)行環(huán)境和業(yè)務(wù)關(guān)聯(lián)，考慮更多業(yè)務(wù)背景，但業(yè)務(wù)語(yǔ)義較多體現(xiàn)在業(yè)務(wù)活動(dòng)層次，對(duì)業(yè)務(wù)總體的語(yǔ)義體現(xiàn)還不充分，沒有抽象出完善的業(yè)務(wù)描述體系. 雖然現(xiàn)有研究的成果對(duì)提升業(yè)務(wù)流程管理起到了積極推動(dòng)作用，但是很少有研究能在考慮結(jié)構(gòu)相似性的同時(shí)，兼顧流程較高抽象層次的語(yǔ)義. 另外，對(duì)于相似度度量方法的設(shè)計(jì)和評(píng)價(jià)越來(lái)越多地要求考慮其算法復(fù)雜度，以使得算法能在實(shí)際應(yīng)用中發(fā)揮作用.

本文立足于建立一種較為全面的相似度計(jì)算方法，兼顧考慮流程的高層業(yè)務(wù)語(yǔ)義及流控結(jié)構(gòu)，并通過(guò)權(quán)重分配計(jì)算綜合相似度. 考慮到流程表示對(duì)流程復(fù)雜度的影響，采用特征提取的方式對(duì)流程結(jié)構(gòu)進(jìn)行形式化表述，在保持流程相似度計(jì)算有效性的前提下，降低計(jì)算復(fù)雜度.

1 高層語(yǔ)義流程模型

在業(yè)務(wù)流程系統(tǒng)中，業(yè)務(wù)流程是實(shí)際業(yè)務(wù)過(guò)程的體現(xiàn)，流程中的各個(gè)活動(dòng)節(jié)點(diǎn)是企業(yè)內(nèi)部各業(yè)務(wù)功能的表示，活動(dòng)節(jié)點(diǎn)間通過(guò)順序關(guān)系表達(dá)了相應(yīng)的信息流向，因此流程模型主要以流程圖的結(jié)構(gòu)表現(xiàn)出來(lái)，如PetriNet、BPMN和EPC等[8]，流程的圖模型表達(dá)也成為流程建模不可或缺的一部分. 通常業(yè)務(wù)流程建模中，流程節(jié)點(diǎn)被分為活動(dòng)節(jié)點(diǎn)和網(wǎng)關(guān)節(jié)點(diǎn). 網(wǎng)關(guān)節(jié)點(diǎn)表達(dá)節(jié)點(diǎn)的分合流控制. 主要有Sequence/AND-Join/AND-Split/XOR-Join/XOR-Split等5種. 流程圖中這5類結(jié)構(gòu)建模成圖節(jié)點(diǎn)時(shí)，由于其沒有活動(dòng)節(jié)點(diǎn)對(duì)應(yīng)的現(xiàn)實(shí)意義，無(wú)法進(jìn)行可識(shí)別性標(biāo)注,計(jì)算相似度時(shí)造成了識(shí)別難度. 因此采用將這5類經(jīng)典的流控類型通過(guò)對(duì)相關(guān)節(jié)點(diǎn)和邊的權(quán)重標(biāo)注的方式進(jìn)行表達(dá).

定義1 邊權(quán)重向量. 令e(x→y)∈E為一條流程圖的有向邊，x、y分別為邊e的兩個(gè)端點(diǎn). x為起始節(jié)點(diǎn)，y為終止節(jié)點(diǎn). 則稱wx為邊e針對(duì)x的權(quán)重標(biāo)注. wy為邊e針對(duì)y的權(quán)重標(biāo)注. w=(wx,wy) 為邊e的權(quán)重向量.

根據(jù)定義1，除Sequence外的4類典型流控的邊權(quán)重向量標(biāo)注見圖1.

在權(quán)重標(biāo)注的流程結(jié)構(gòu)中，a、b、c為活動(dòng)節(jié)點(diǎn)，g為網(wǎng)關(guān)節(jié)點(diǎn). 可以通過(guò)對(duì)g節(jié)點(diǎn)入度和出度差異判斷節(jié)點(diǎn)的分合(Split/Join)特性. 邊的權(quán)重向量則表達(dá)了其分合的細(xì)致特性(AND/OR). 因此通過(guò)邊的權(quán)重標(biāo)注可充分體現(xiàn)流程結(jié)構(gòu)特性.

圖1 典型控制結(jié)構(gòu)的權(quán)限標(biāo)注

定義2 控制結(jié)構(gòu). 令N代表一個(gè)流程的活動(dòng)節(jié)點(diǎn)集合，一個(gè)控制結(jié)構(gòu)類型可以表達(dá)為一個(gè)三元組c=(x,Ex,μ).

式中:x∈N為一個(gè)活動(dòng)節(jié)點(diǎn)；Ex?N×N為與該節(jié)點(diǎn)相關(guān)的所有邊，?e∈Ex，x必為e的端點(diǎn)之一;μ:Ex→{(w1,w2)|?w1,w2∈(0,1]} 為一個(gè)控制結(jié)構(gòu)類型相關(guān)的邊權(quán)重賦值映射.

定義3 業(yè)務(wù)流程高層語(yǔ)義元數(shù)據(jù). 業(yè)務(wù)語(yǔ)義的高層語(yǔ)義元數(shù)據(jù)可以表示為H=(O,A,R,G).

式中O為與業(yè)務(wù)流程相關(guān)的業(yè)務(wù)領(lǐng)域知識(shí)，定義了描述流程高層業(yè)務(wù)語(yǔ)義的必要領(lǐng)域概念；A為流程的業(yè)務(wù)主角Actor，可以是具體人，也可以是人物角色;R為流程過(guò)程中涉及到的資源Resource;G=(q1,q2,…，qi), i=1,2,3…?qi∈Q， 代表了業(yè)務(wù)流程的業(yè)務(wù)目標(biāo)Goal,通常以業(yè)務(wù)相關(guān)的各類業(yè)務(wù)指標(biāo)qi來(lái)衡量,Q為業(yè)務(wù)指標(biāo)集合.

定義4 業(yè)務(wù)流程模型. 一個(gè)業(yè)務(wù)流程模型可以被形式化為元組P=(N, E, L, C, H, λ, ω, φ). 其中：N為活動(dòng)節(jié)點(diǎn)集合；E=N×N為連接兩個(gè)節(jié)點(diǎn)的邊集合；C為節(jié)點(diǎn)關(guān)聯(lián)的控制結(jié)構(gòu)集合；H為業(yè)務(wù)流程的高層語(yǔ)義描述元數(shù)據(jù)；λ∶N→L為從節(jié)點(diǎn)到節(jié)點(diǎn)標(biāo)簽的映射；ω∶E→{(w1,w2)|?w1,w2∈(0,1]} 節(jié)點(diǎn)的控制結(jié)構(gòu)權(quán)重賦值的映射；φ∶N→C為將節(jié)點(diǎn)映射到節(jié)點(diǎn)關(guān)聯(lián)控制結(jié)構(gòu)的映射函數(shù).

在業(yè)務(wù)流程模型中，若存在有向邊(n1,n2)，則稱節(jié)點(diǎn)n1為節(jié)點(diǎn)n2的輸入，節(jié)點(diǎn)n2為節(jié)點(diǎn)n1的輸出. 沒有任何輸入的節(jié)點(diǎn)稱為開始節(jié)點(diǎn)，沒有任何輸出的節(jié)點(diǎn)稱為結(jié)束節(jié)點(diǎn).

2 流程模型特征提取及相似度計(jì)算

流程相似度較多地應(yīng)用在流程資源庫(kù)的檢索中[11-12]，因此需要控制相似度算法的復(fù)雜度，以提升響應(yīng)速度. 降低復(fù)雜度要求,簡(jiǎn)化相似度計(jì)算相關(guān)變量，應(yīng)用特征提取的方法可有效簡(jiǎn)化相似度的計(jì)算變量.

2.1 結(jié)構(gòu)特征提取及其相似度

定義5 流程結(jié)構(gòu)特征(Sf). P=(N,E,L,C,H,λ,ω,φ)為業(yè)務(wù)流程，則其流程結(jié)構(gòu)特征定義為Sf=(N、E、ω). 該結(jié)構(gòu)特征中N、E、ω 具備流程定義中一致的表達(dá)意義. 容易驗(yàn)證這3個(gè)結(jié)構(gòu)表述對(duì)象中能夠確定唯一一個(gè)流程的結(jié)構(gòu). 對(duì)流程結(jié)構(gòu)而言，典型的相似度有基于節(jié)點(diǎn)集的相似度和基于邊集的相似度.

對(duì)于流程模型P1=(N1,E1,L1,C1,H1,λ1,ω1,φ1)和P2=(N2,E2,L2,C2,H2,λ2,ω2,φ2)可得流程特征分別為Sf1=(N1,E1,ω1) 和Sf2=(N2,E2,ω2). 典型的節(jié)點(diǎn)集相似度和邊集合相似度計(jì)算如下：

針對(duì)提取出的結(jié)構(gòu)特征，對(duì)以上兩種相似度計(jì)算方式進(jìn)行融合，可得基于特征提取的相似度計(jì)算方法:

2.2 流程的高層語(yǔ)義特征提取及其相似度

定義6 高層語(yǔ)義特征(Hf).P=(N,E,L,C,H,λ,ω,φ)為業(yè)務(wù)流程，具備語(yǔ)義H=(O,A,R,G)，則其高層語(yǔ)義特征定義為Hf=(A,R,G)根據(jù)流程的高層語(yǔ)義元數(shù)據(jù)定義，其中G為G的向量表示.

假定Hf1=(A1,R1,G1)和Hf2=(A2,R2,G2)為兩個(gè)不同流程的高層語(yǔ)義特征. 則流程語(yǔ)義的相似度定義為

SHf=wASA+wRSR+wGSG,

wA+wR+wG=1,

wA,wR,wG∈[0,1].

式中：SA、SR、SG分別為業(yè)務(wù)主角相似度、流程資源相似度和流程目標(biāo)相似度，且

fEqualActor為求取相同Actor的函數(shù).

2.3 流程綜合相似度

定義7 流程綜合相似度. 對(duì)前文的不同流程模型P1和P2,其綜合相似度為

SP(P1,P2)=αSSf(Sf1,Sf2)+βSHf(Hf1,Hf2)，

α+β=1，

α,β∈[0,1].

即流程的綜合相似度等于結(jié)構(gòu)特征相似度和語(yǔ)義特征相似度的加權(quán)求和. 其中α、β為調(diào)整參數(shù)，通過(guò)調(diào)整參數(shù)的配比，相似度計(jì)算方法可適用于不同的計(jì)算場(chǎng)景需求，增強(qiáng)了其靈活性.

3 分析討論

3.1 相似度計(jì)算過(guò)程分析

流程綜合相似度的計(jì)算主要分為3個(gè)步驟: 特征提取、場(chǎng)景參數(shù)化和相似度融合. 特征提取是對(duì)流程模型進(jìn)行特征抽取，完成從流程模型到流程特征的轉(zhuǎn)化. 場(chǎng)景參數(shù)化主要涉及到相似度計(jì)算中各類參數(shù)的確定, 主要是語(yǔ)義相似度的參數(shù)wA、wR、wG和綜合相似度的調(diào)節(jié)參數(shù)α、β. 具體流程見圖2.

圖2 相似度計(jì)算過(guò)程

3.2 相似度計(jì)算實(shí)例分析

1)模型獲取. 為了清楚地闡述計(jì)算過(guò)程，對(duì)實(shí)際流程細(xì)節(jié)進(jìn)行簡(jiǎn)化，圖3為兩個(gè)不同的采購(gòu)流程實(shí)例.

2)形式化及特征提取. 根據(jù)對(duì)圖 3中的活動(dòng)標(biāo)識(shí)，先對(duì)流程進(jìn)行結(jié)構(gòu)提取. 由定義1得到帶權(quán)流程結(jié)構(gòu)，圖4展示了流程的結(jié)構(gòu)特征.

語(yǔ)義特征則從圖3的業(yè)務(wù)信息中提取. 為了簡(jiǎn)化演示過(guò)程，設(shè)定流程語(yǔ)義特征中G部分采用3維布爾向量表達(dá)(F,T,C),分別表示流程對(duì)Finance/Time/Collaboration這3類指標(biāo)的要求，對(duì)相應(yīng)指標(biāo)有要求則為1，沒有要求則為0. 根據(jù)語(yǔ)義特征的定義，對(duì)流程P1，其涉及到對(duì)訂單金額的管理，對(duì)交付時(shí)間具備要求，由于其完成過(guò)程涉及到的相關(guān)交互主體很多，因此G1=(1,1,1)，A1=采購(gòu)單位主體，以典型的表單表達(dá)，R1= {采購(gòu)申請(qǐng)單，采購(gòu)標(biāo)書，委托交付合同，交貨清單}. 同理，流程P2主要是采購(gòu)特殊處理，對(duì)資金管理和時(shí)間交付沒有固定限制，因此:G2=(0,0,1)，A2=采購(gòu)個(gè)人主體，R2={采購(gòu)申請(qǐng)單，交貨清單}.

圖3 簡(jiǎn)化采購(gòu)流程業(yè)務(wù)模型

圖4 采購(gòu)流程的結(jié)構(gòu)形式化

3)相似度計(jì)算. 結(jié)構(gòu)相似度為

不失一般性，語(yǔ)義相似度計(jì)算參數(shù)采用等權(quán)重賦值，即wA=wR=wG=1/3，那么

SHf=wASA+wRSR+wGSG=1/3×0+1/3× 2/4+1/3×0.366=0.287.

令α=β=1/2, 可得綜合相似度

SP(P1,P2)=1/2×0.406+1/2×0.287=0.347.

3.3 適應(yīng)性分析

相似度模型的計(jì)算準(zhǔn)確度是衡量模型好壞的重要參考，但隨著應(yīng)用需求人性化和用戶面的不斷擴(kuò)展，相似度模型的適應(yīng)性也值得引起重視. 本文相似度模型，由于其設(shè)計(jì)時(shí)考慮了對(duì)流程進(jìn)行較為全面的知識(shí)描述，模型信息很全面，適合除了流程建模專業(yè)人員的其他用戶(業(yè)務(wù)分析人員、非IT系統(tǒng)人員等)理解和使用，相比于已有的相似度計(jì)算模型,如圖編輯距離(GED)[13]、字符串編輯距離(SED)[14]、近距離最大子圖優(yōu)先(NMSF)[15]、流程規(guī)整矩陣(PWM)[16]等基于特征提取的相似度計(jì)算方法，其應(yīng)用靈活性和用戶延伸能力更強(qiáng)，適應(yīng)性更廣.

4 實(shí)驗(yàn)分析

實(shí)際應(yīng)用中，流程的相似度主要用于流程資源庫(kù)的匹配上，即用戶以新的流程特征為輸入，希望得到流程庫(kù)中相關(guān)的流程作為輸出. 實(shí)驗(yàn)采用SAPReference系統(tǒng)中提取的600個(gè)流程實(shí)例作為實(shí)驗(yàn)樣本，對(duì)實(shí)驗(yàn)樣本進(jìn)行了統(tǒng)一的形式化和特征提取操作，形成了本文特有的兼顧高層語(yǔ)義的流程資源庫(kù). 實(shí)驗(yàn)主要從計(jì)算有效性、計(jì)算復(fù)雜度、模型參數(shù)調(diào)節(jié)效能3個(gè)方面考察相似度計(jì)算模型的性能. 在計(jì)算有效性方面，采用GED、SED和NMSF相似度算法進(jìn)行比較. 由于該3種匹配算法是基于線下模式抽取和線上匹配相結(jié)合，在時(shí)間有效性上無(wú)法比較. 因此在時(shí)間有效性上采取和NMFS相當(dāng)?shù)腜WM算法進(jìn)行對(duì)比.

4.1 相似度計(jì)算有效性驗(yàn)證

因?yàn)镚ED、SED、NMSF只基于流程結(jié)構(gòu)實(shí)現(xiàn)匹配，不支持對(duì)高層業(yè)務(wù)信息的匹配，所以在試驗(yàn)中采取對(duì)本文相似度模型進(jìn)行純結(jié)構(gòu)匹配場(chǎng)景參數(shù)配置. 即令α=1,β=0. 在推薦結(jié)果上本文采用的方法與已有方法有所不同. 以往方法的推薦結(jié)果是點(diǎn)或者路徑，本文推薦結(jié)果是流程庫(kù)中的流程實(shí)例. 匹配的輸入是通過(guò)對(duì)流程庫(kù)中的流程進(jìn)行特征提取后，將特征進(jìn)行模糊化，并以隨機(jī)化方式實(shí)現(xiàn)特征的部分抽取. 其他參考算法則基于各自參考文獻(xiàn)中的偽算法描述. 實(shí)驗(yàn)考察了在同樣的結(jié)構(gòu)特征下，不同算法的匹配準(zhǔn)確度隨著匹配輸出結(jié)果數(shù)的變化，流程資源庫(kù)的規(guī)模為600個(gè)流程實(shí)例. 實(shí)驗(yàn)結(jié)果如圖5.

圖5 不同相似度算法準(zhǔn)確度比較

由圖5可以看出，整體表現(xiàn)上，隨著匹配結(jié)果數(shù)目的增加，匹配準(zhǔn)確度不斷提升，當(dāng)匹配結(jié)果數(shù)目達(dá)到6之后，匹配準(zhǔn)確度基本達(dá)到一個(gè)較高的穩(wěn)定水平. 在匹配結(jié)果相同情況下，NMFS算法的匹配準(zhǔn)確度要高于GED和SED算法，這與文獻(xiàn)中的結(jié)果吻合，證明了本文結(jié)果的可信性. 而CHSS算法的準(zhǔn)確度在大部分情況下都高于其他對(duì)比算法，因此可見CHSS算法在相似度計(jì)算問(wèn)題上的優(yōu)勢(shì).

4.2 相似度計(jì)算復(fù)雜度比較

計(jì)算復(fù)雜度影響算法的處理時(shí)間，間接決定了算法在實(shí)際環(huán)境中的可應(yīng)用性. 在時(shí)間復(fù)雜度比較實(shí)驗(yàn)中，采用的PWM方法和本文算法均是線上時(shí)間衡量. 由于文獻(xiàn)[16]中初步驗(yàn)證了PWM和NMSF算法時(shí)間復(fù)雜度相當(dāng)，因此通過(guò)于PWM進(jìn)行比較具備較高可信度. 實(shí)驗(yàn)主要考察了匹配時(shí)間隨流程資源庫(kù)的規(guī)模擴(kuò)張導(dǎo)致的變化情況. 不失一般性，實(shí)驗(yàn)中CHSS采用多種參數(shù)配比最后求均值的方式進(jìn)行實(shí)驗(yàn)，參數(shù)調(diào)控步長(zhǎng)為0.25. 得到的參數(shù)集合為：(α,β)={(1,0),(0.75,0.25),(0.5,0.5),(0.25,0.75,(1,0)}. 對(duì)不同配比結(jié)果比較發(fā)現(xiàn)，同等數(shù)量的流程規(guī)模下，其耗時(shí)誤差最大不超過(guò)26ms，屬于實(shí)驗(yàn)正常波動(dòng)范圍. 不同配比多次實(shí)驗(yàn)數(shù)據(jù)均值見圖6.

圖6 相似度算法平均匹配耗時(shí)比較

圖6為業(yè)務(wù)流程數(shù)量不斷提升導(dǎo)致流程資源庫(kù)規(guī)模擴(kuò)張時(shí)，平均匹配時(shí)間的變化情況. 由圖6可知，在不同參數(shù)配比下采用CHSS算法匹配的平均耗時(shí)基本同PWM算法相當(dāng)并略有優(yōu)勢(shì). 表明即使在加入語(yǔ)義對(duì)比的情況下，本文模型依然能保持計(jì)算高效性. 整體趨勢(shì)上，資源庫(kù)規(guī)模的擴(kuò)張導(dǎo)致流程匹配的次數(shù)增加，進(jìn)而增加了平均匹配時(shí)間. 從平均耗時(shí)的絕對(duì)大小方面，在一般規(guī)模的流程庫(kù)中應(yīng)用CHSS算法進(jìn)行匹配是能夠滿足應(yīng)用需求的.

4.3 權(quán)重參數(shù)調(diào)節(jié)效能

綜合特征提取相似度計(jì)算方法中的各類參數(shù)的可調(diào)節(jié)特性增強(qiáng)了其適應(yīng)性，使得在結(jié)構(gòu)信息不完全甚至缺乏的情況下，使用業(yè)務(wù)信息作為輔助提升模型的可用性. 在實(shí)驗(yàn)中主要驗(yàn)證在不同的(α,β) 權(quán)重組合下，相似度算法的匹配準(zhǔn)確度表現(xiàn). 實(shí)驗(yàn)選取(1,0)、(0,1)、(1/2,1/2)作為權(quán)重參數(shù)調(diào)節(jié)組合，分別命名為結(jié)構(gòu)配比、語(yǔ)義配比和均分配比，表達(dá)了只考慮結(jié)構(gòu)、只考慮語(yǔ)義及綜合考慮兩類特征對(duì)算法匹配效果的影響. 實(shí)驗(yàn)考察了在3種權(quán)重匹配下，準(zhǔn)確度隨著推薦結(jié)果數(shù)變化，結(jié)果見圖7. 由圖7可以看出，3種權(quán)重配比在不同匹配結(jié)果數(shù)量下對(duì)準(zhǔn)確度均產(chǎn)生影響. 結(jié)構(gòu)配比和語(yǔ)義配比在不同情況下的表現(xiàn)呈現(xiàn)波動(dòng)狀態(tài)，沒有絕對(duì)優(yōu)劣之分. 因?yàn)樵陔S機(jī)提供流程信息進(jìn)行匹配的情況下，語(yǔ)義信息和結(jié)構(gòu)信息的完整性是呈現(xiàn)波動(dòng)的. 因此在不同情況下，這兩種配比方式會(huì)有自身的缺陷. 由權(quán)重配比系數(shù)可知，均分配比的相似度輸出是其余兩者的算術(shù)平均. 但從實(shí)驗(yàn)結(jié)果可知，這種均分配比的準(zhǔn)確度也處于其余兩種配比方式之間，但總是靠近表現(xiàn)更好的一方. 因此可見，均分配比可以實(shí)現(xiàn)彌補(bǔ)其余兩種匹配方式缺陷的前提下，更好地發(fā)揮其優(yōu)勢(shì)，實(shí)際應(yīng)用中將具備更好的適應(yīng)性.

圖7 不同權(quán)重配比的準(zhǔn)確度比較

5 結(jié) 論

1) 提出一種融合高層語(yǔ)義的業(yè)務(wù)流程模型，在流程結(jié)構(gòu)方面，通過(guò)流程控制結(jié)構(gòu)定義和邊權(quán)重標(biāo)注對(duì)現(xiàn)有流程結(jié)構(gòu)模型進(jìn)行了擴(kuò)展，根據(jù)擴(kuò)展模型對(duì)典型結(jié)構(gòu)相似度計(jì)算方法進(jìn)行了改進(jìn).

2) 在流程語(yǔ)義方面，提出流程高層語(yǔ)義模型，闡述了其特征提取方法和基于向量空間模型的高層語(yǔ)義特征相似度計(jì)算方法.

3) 通過(guò)加權(quán)融合結(jié)構(gòu)和語(yǔ)義兩方面的綜合特征度量流程總體相似度. 并根據(jù)場(chǎng)景配置不同參數(shù),提升了流程相似度計(jì)算方法的適應(yīng)性. 通過(guò)實(shí)驗(yàn)對(duì)模型進(jìn)行了多方位的性能對(duì)比，結(jié)果表明:面向綜合特征的相似度計(jì)算方法效率高，具備很好的應(yīng)用潛力.

[1] JIN T, WANG J, WEN L. Efficient retrieval of similar business process models based on structure[C]// On the Move to Meaningful Internet Systems. Hersonissos: Springer Berlin Heidelberg, 2011:56-63. DOI: 10.1007/978-3-642-25109-2_5.

[2] BECKER M, LAUE R. Analysing differences between business process similarity measures[C]// BPM 2011 International Workshops. Clermont-Ferrand: Springer Berlin Heidelberg, 2012:39-49.DOI: 10.1007/978-3-642-28115-0_5.

[3] DIJKMAN R, DUMAS M, LUCIANO G. Graph matching algorithms for business process model similarity search[C]//7th International Conference on Business Process Management. Ulm: Springer, 2009:48-63. DOI: 10.1007/978-3-642-03848-8_5.

[4] LIU H, LIU G, WANG Y, et al. A novel behavioral similarity measure for artifact-oriented business processes[C]// International Conference on Technology for Education and Learning. Macau: Springer Berlin Heidelberg,2012:81-88.DOI:10.1007/978-3-642-27711-5_12.

[5] KUNZE M, WEIDLICH M, WESKE M. Behavioral similarity: a proper metric [C]//Business Process Management - 9th International Conference. Clermont-Ferrand: Springer Berlin Heidelberg, 2011:166-181. DOI: 10.1007/978-3-642-23059-2_15.

[6] WANG J, HE T, WEN L, et al. A behavioral similarity measure between labeled petri-nets based on principal transition sequences[C]// On the Move Confederated International Conference. Hersonissos: Springer Berlin Heidelberg, 2010:394-401.DOI: 10.1007/978-3-642-16934-2_27.

[7] LI S, CAO J. A new similarity search approach on process models[C]// First International Workshop, PAS 2014. Shanghai: Sprin-ger Berlin Heidelberg, 2015:11-20. DOI: 10.1007/978-3-662-46170-9_2.

[8] BAUMANN M H, BAUMANN M, SCH?NIG S, et al. Towards multi-perspective process model similarity matching[C]// 10th International Workshop, EOMAS 2014. Thessaloniki: Springer Berlin Heidelberg, 2014:21-37. DOI: 10.1007/978-3-662-44860-1_2.[9] CHAN N N, GAALOUL W, TATA S. Assisting business process design by activity neighborhood context matching[C]// 10th International Conference, ICSOC 2012.Shanghai: Springer Berlin Heidelberg, 2012:541-549.DOI: 10.1007/978-3-642-34321-6_38.[10]MONTANI S, LEONARDI G, QUAGLINI S, et al. A knowledge-intensive approach to process similarity calculation[J]. Expert Systems with Applications, 2015, 42(9): 4207-4215. DOI: 10.1016/j.eswa.2015.01.027.

[11]LA ROSA M, DUMAS M, EKANAYAKE C C, et al. Detecting approximate clones in business process model repositories[J]. Information Systems, 2015, 49: 102-125. DOI: 10.1016/j.is.2014.11.010.

[12]LINCOLN M, GAL A. Searching business process repositories using operational similarity[C]// On the Move to Meaningful Internet Systems,OTM 2011. Hersonissos: Springer Berlin Heidelberg, 2011: 2-19. DOI: 10.1007/978-3-642-25109-2_2.

[13]CAO B, YIN J, DENG S. Graph-based workflow recommendation: on improving business process modeling[C]//Proceeding of the 21st ACM International Conference on Information and Knowledge Management. New York: ACM, 2012：1527-1531. DOI:10.1145/2396761.2398466.

[14]LI Y, CAO B, XU L, et al. An efficient recommendation method for improving business processmodeling[J]. IEEE Transactions on Industrial Informatics, 2014, 10(1): 502-513. DOI: 10.1109/TII.2013.2258677.

[15]曹斌，尹建偉，鄧水光，等. 一種基于近距離最大子圖優(yōu)先的業(yè)務(wù)流程推薦技術(shù)[J]. 計(jì)算機(jī)學(xué)報(bào), 2013, 36(2): 263-274. DOI: 10.3724/SP.J.1016.2013.00263.

CAO Bin, YIN Jianwei, DENG Shuiguang, et al. A near neighbor and maximal subgraph first based business process recommendation technique[J]. Chinese Journal of Computers, 2013, 36(2): 263-274. DOI: 10.3724/SP.J.1016.2013.00263.

[16]葉巖明，尹建偉，曹斌. 基于流程規(guī)整矩陣的流程推薦技術(shù)[J]. 計(jì)算機(jī)集成制造系統(tǒng),2013,19(8): 1868-1875. DOI：10.13196/j.cims.2013.08.006.

YE Yanming, YIN Jianwei, CAO Bin. Process warping matrix based business process recommendation technique[J]. Computer Integrated Manufacturing Systems, 2013,19(8): 1868-1875. DOI：10.13196/j.cims.2013.08.006.

(編輯 楊 波)

Feature extraction oriented similarity metric of business process

CHANG Guanyu, YANG Haicheng, MO Rong, SUN Peng

(Key Laboratory of Contemporary Design and Integrated Manufacturing Technology, Ministry of Education (Northwestern Polytechnical University), Xi’an 710072， China)

The existing research of process similarity mostly focuses on process structure but neglects the business semantic, and the similarity calculation on process structure is somehow deficient on computation complexity. To solve this problem, this paper proposes a business process representation with synthetical feature extraction, and a corresponding similarity calculation method is given at the same time. Weight notation of edges is used to extend the process structure for structure feature extraction based on the analysis of basic process control patterns, and high level business semantic is also involved for constructing business process semantic model for semantic feature extraction. The classic similarity metrics of node and edge are heuristically adapted to form a new structure similarity metric, and the similarity of business semantic is computed on vector space model and set theory. The total similarity is deduced by the weighted sum of structure and semantic similarity, and the computation model is self-adaptive to other existing methods by the adjustment of weight assignment. Finally, experiments are carried out to verify the performance of similarity computation, and the results show that the model of this paper is more adaptive and higher in computation efficiency when comparing to other methods in the literatures.

business process model; business semantic; feature extraction; process similarity; process matching

2016-04-13

國(guó)家自然科學(xué)基金(51375395)

常關(guān)羽(1985—)，男，博士研究生; 楊海成(1959—)男，教授，博士生導(dǎo)師

常關(guān)羽，dengxiao@mail.nwpu.edu.cn

TP315

A

0367-6234(2017)07-0183-06