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

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

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

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

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

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

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

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

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

1 高層語義流程模型

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

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

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

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

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

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

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

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

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

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

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

2 流程模型特征提取及相似度計算

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

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、ω 具備流程定義中一致的表達意義. 容易驗證這3個結(jié)構(gòu)表述對象中能夠確定唯一一個流程的結(jié)構(gòu). 對流程結(jié)構(gòu)而言，典型的相似度有基于節(jié)點集的相似度和基于邊集的相似度.

對于流程模型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é)點集相似度和邊集合相似度計算如下：

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

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

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

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

SHf=wASA+wRSR+wGSG,

wA+wR+wG=1,

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

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

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

2.3 流程綜合相似度

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

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

α+β=1，

α,β∈[0,1].

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

3 分析討論

3.1 相似度計算過程分析

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

圖2 相似度計算過程

3.2 相似度計算實例分析

1)模型獲取. 為了清楚地闡述計算過程，對實際流程細節(jié)進行簡化，圖3為兩個不同的采購流程實例.

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

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

圖3 簡化采購流程業(yè)務(wù)模型

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

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

不失一般性，語義相似度計算參數(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)性分析

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

4 實驗分析

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

4.1 相似度計算有效性驗證

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

圖5 不同相似度算法準確度比較

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

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

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

圖6 相似度算法平均匹配耗時比較

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

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

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

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

5 結(jié) 論

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

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

3) 通過加權(quán)融合結(jié)構(gòu)和語義兩方面的綜合特征度量流程總體相似度. 并根據(jù)場景配置不同參數(shù),提升了流程相似度計算方法的適應(yīng)性. 通過實驗對模型進行了多方位的性能對比，結(jié)果表明:面向綜合特征的相似度計算方法效率高，具備很好的應(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]. 計算機學(xué)報, 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]. 計算機集成制造系統(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

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

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

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

TP315

A

0367-6234(2017)07-0183-06