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

常關羽, 楊海成, 莫 蓉, 孫 鵬

(現代設計與集成制造技術教育部重點實驗室(西北工業大學)， 西安 710072)

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

常關羽, 楊海成, 莫 蓉, 孫 鵬

(現代設計與集成制造技術教育部重點實驗室(西北工業大學)， 西安 710072)

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

流程模型；業務語義；特征提取；流程相似度；流程匹配

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

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

1 高層語義流程模型

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

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

根據定義1，除Sequence外的4類典型流控的邊權重向量標注見圖1.

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

圖1 典型控制結構的權限標注

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

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

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

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

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

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

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

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

2.1 結構特征提取及其相似度

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

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

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

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

定義6 高層語義特征(Hf).P=(N,E,L,C,H,λ,ω,φ)為業務流程，具備語義H=(O,A,R,G)，則其高層語義特征定義為Hf=(A,R,G)根據流程的高層語義元數據定義，其中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分別為業務主角相似度、流程資源相似度和流程目標相似度，且

fEqualActor為求取相同Actor的函數.

2.3 流程綜合相似度

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

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

α+β=1，

α,β∈[0,1].

即流程的綜合相似度等于結構特征相似度和語義特征相似度的加權求和. 其中α、β為調整參數，通過調整參數的配比，相似度計算方法可適用于不同的計算場景需求，增強了其靈活性.

3 分析討論

3.1 相似度計算過程分析

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

圖2 相似度計算過程

3.2 相似度計算實例分析

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

2)形式化及特征提取. 根據對圖 3中的活動標識，先對流程進行結構提取. 由定義1得到帶權流程結構，圖4展示了流程的結構特征.

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

圖3 簡化采購流程業務模型

圖4 采購流程的結構形式化

3)相似度計算. 結構相似度為

不失一般性，語義相似度計算參數采用等權重賦值，即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 適應性分析

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

4 實驗分析

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

4.1 相似度計算有效性驗證

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

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

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

4.2 相似度計算復雜度比較

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

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

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

4.3 權重參數調節效能

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

圖7 不同權重配比的準確度比較

5 結 論

1) 提出一種融合高層語義的業務流程模型，在流程結構方面，通過流程控制結構定義和邊權重標注對現有流程結構模型進行了擴展，根據擴展模型對典型結構相似度計算方法進行了改進.

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

3) 通過加權融合結構和語義兩方面的綜合特征度量流程總體相似度. 并根據場景配置不同參數,提升了流程相似度計算方法的適應性. 通過實驗對模型進行了多方位的性能對比，結果表明:面向綜合特征的相似度計算方法效率高，具備很好的應用潛力.

[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]曹斌，尹建偉，鄧水光，等. 一種基于近距離最大子圖優先的業務流程推薦技術[J]. 計算機學報, 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]葉巖明，尹建偉，曹斌. 基于流程規整矩陣的流程推薦技術[J]. 計算機集成制造系統,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

國家自然科學基金(51375395)

常關羽(1985—)，男，博士研究生; 楊海成(1959—)男，教授，博士生導師

常關羽，dengxiao@mail.nwpu.edu.cn

TP315

A

0367-6234(2017)07-0183-06