基于行為和結構特征的相似語義工作流檢索

孫晉永 古天龍 聞立杰 錢俊彥 孟 瑜

1(西安電子科技大學計算機學院 西安 710071)2(廣西可信軟件重點實驗室(桂林電子科技大學) 廣西桂林 541004)3 (清華大學軟件學院 北京 100084)

基于行為和結構特征的相似語義工作流檢索

孫晉永1,2古天龍2聞立杰3錢俊彥2孟 瑜2

1(西安電子科技大學計算機學院 西安 710071)2(廣西可信軟件重點實驗室(桂林電子科技大學) 廣西桂林 541004)3(清華大學軟件學院 北京 100084)

(sunjy@guet.edu.cn)

相似語義工作流檢索是語義工作流重用的首要任務.現有的相似語義工作流檢索方法僅關注結構特征，忽略了行為特征，影響了檢索到的相似語義工作流的整體質量，提高了語義工作流重用的代價.為此，提出一種結合行為和結構特征的2階段相似語義工作流檢索算法.使用任務緊鄰關系集表達語義工作流的執行行為，結合領域知識構造語義工作流庫的任務緊鄰關系樹索引和數據索引.針對查詢語義工作流，先基于任務緊鄰關系樹索引和數據索引進行過濾得到候選語義工作流集;然后使用圖匹配相似性算法對候選語義工作流集進行驗證，得到排序的候選語義工作流集.實驗結果表明，較主流的語義工作流檢索算法，該方法的檢索性能有較大提升，可以為工作流重用提供更高質量的語義工作流.

工作流重用；語義工作流；相似性檢索；結構特征；行為特征；任務緊鄰關系樹索引

業務過程運行的效率和質量是現代企業和組織在競爭中保持優勢的關鍵因素之一.隨著業務過程管理的廣泛應用，大量業務過程被積累下來.工作流重用是現代企業和組織提高業務過程管理效率的重要方式.近年來，研究者提出了基于知識的工作流管理，將基于事例推理(case-based reasoning, CBR)引入業務工作流管理中，提出了面向過程CBR(process-oriented CBR, POCBR).POCBR使用工作流案例記錄過去的工作流建模和執行活動的經驗知識，進行推理以支持領域專家創建、修正和重用工作流.

基于知識的工作流管理需要以領域知識為背景.語義工作流[1]作為一種基于知識的工作流，為工作流重用提供了更充足的語義和數據或資源信息，可以提高工作流重用的效率.當前語義工作流重用是工作流重用研究的熱點之一.目前語義工作流的應用已經從最初的業務過程領域擴展到電子商務、醫療、軟件開發和科學分析等領域.

從語義工作流庫中檢索出滿足需求的相似語義工作流是語義工作流重用研究的首要任務.然而現有的相似語義工作流檢索方法僅關注結構特征，忽略了行為特征，影響了檢索語義工作流的整體質量，也提高了語義工作流重用的代價.Bergmann等人[1]將基于圖結構匹配的相似性方法用于語義工作流案例檢索.該方法采用遍歷語義工作流庫的方式進行檢索，計算量較大.對于小規模工作流庫，該方法可以得出滿意的檢索性能；對于規模較大的語義工作流庫，實際上是不可行的.索引技術是解決大規模數據庫檢索問題的有效方法.但語義工作流所對應的語義標注有向圖是稀疏圖，其中的頻繁子圖并不多，并且頻繁子圖不能覆蓋所有的工作流模型[2].從而圖索引的檢索技術不能直接用于相似語義工作流檢索.

Forbus等人[3]提出一種用于相似性檢索的MACFAC(many are called, but few are chosen)模型.該模型由2個階段構成：1)MAC階段使用計算量較小的非結構匹配算法從項目池中過濾出候選項目集；2)FAC階段使用結構匹配算法從候選項目集中找出最匹配的項目.Bergmann等人[4]提出基于MACFAC模型的語義工作流檢索方法.MAC階段基于語義工作流的語義特征和語法特征進行過濾，FAC階段使用圖檢索方法選出最匹配的語義工作流.接著，Bergmann等人[5]在MAC階段建立路徑索引：Path-k(k為路徑長度)進行語義工作流過濾.Müller等人[6]使用聚類方法建立索引結構，提出了基于排隊的檢索算法.Müller等人[7]還提出了用于POCBR的相似語義工作流檢索語言POQL，可以表達泛化的檢索項目.Jin等人[8]使用標簽Petri網建模業務過程，提出了基于變遷路徑索引LnP(n為路徑長度，與路徑索引Path-k[5]的本質相同).以上檢索方法僅關注語義工作流或業務過程模型的結構特征，沒有考慮它們的執行行為，因而檢索的準確性有待提高.

Zha等人[9]提出了基于標簽Petri網建模的過程模型的變遷緊鄰關系(transition adjacency relation, TAR)的概念.變遷緊鄰關系集(transition adjacency relations set, TARS)是過程模型的所有TAR的集合.Jin等人[10]構造基于標簽Petri網的過程模型的行為特征索引TARIndex，提出了2階段的過程模型檢索方法.該方法關注了業務模型的執行行為，但不能區分循環和順序結構.Weidlich等人[11]指出在過程模型檢索的一致性檢查中應該考慮業務過程的數據和資源.由于標簽Petri網不含數據流，故針對標簽Petri網的檢索方法不能直接用于相似語義工作流檢索.

鑒于執行行為等價的語義工作流，其結構可能差異較大；而結構相似度高的語義工作流，其執行行為卻可能差異較大.因而在相似語義工作流檢索時，僅考慮結構特征或行為特征中的1種，得到的檢索語義工作流結果集的整體質量自然不高，進而會提高語義工作流重用的代價.目前，對結合結構和行為特征的語義工作流檢索研究還很少，特別是需要考慮領域知識時.因此本文以考慮領域知識的語義工作流為研究對象，引入任務緊鄰關系樹索引的概念，研究結合結構和行為特征的2階段相似語義工作流檢索方法，以期得到整體質量更高的檢索語義工作流結果集，為語義工作流重用提供更高質量的候選語義工作流.

Fig. 1 The semantic workflow SW1圖1 語義工作流SW1

本文的主要貢獻如下：

1) 提出語義工作流的任務緊鄰關系概念，構造了結合領域知識的任務緊鄰關系樹索引TARTree-Index，用于過濾得到具有指定行為特征的語義工作流；

2) 構造了結合領域知識的數據索引DataIndex，用于過濾得到包含指定數據的語義工作流；

3) 提出了使用TARTreeIndex和DataIndex進行過濾，圖匹配相似性算法進行驗證的2階段相似語義工作流檢索算法；

4) 通過實驗比較得出，本文算法以可接受的代價改善了相似語義工作流的檢索性能.

1 預備知識

語義工作流最初由Bergmann等人[1]提出.為工作流的任務結點及其輸入輸出數據對象增加語義描述，為邊增加語義描述使得工作流同時包含控制流、數據流和語義約束，得到了語義工作流.與傳統工作流相比，語義工作流不但描述了業務過程中的任務及其連接關系，而且描述了任務的語義、數據或資源以及任務間連接關系的語義等重要信息.語義工作流可以表達業務工作流和科學工作流[1].

1.1 語義工作流

定義1. 語義工作流[1,12].語義工作流可以形式化為語義標注有向圖SW=(N,E,S,τ).其中，N=NT∪NC∪ND，NT是任務節點的集合；NC是控制流節點(路由節點)的集合；ND是數據節點集合.E?N×N是邊的集合；S:N∪E→Σ將節點或邊映射為語義描述；Σ是一個與領域相關的語義元數據語言.τ:N∪E→Ω將每個節點或邊映射為1個類型，Ω={task node,data node,control-flow node,control-flow edge,dataflow edge}.

為了表述簡便，本文僅把以控制流為中心的業務工作流作為研究對象，將其表示為語義工作流，探討相似語義工作流的檢索方法.

例1. 圖1是描述意大利面食Baked Spaghetti的烹飪過程的語義工作流SW1[13].

在圖1中，控制流邊的語義描述為Control-flow，為了簡潔，圖1中省略了它們.輸入數據流邊的語義描述為Input.任務節點以其語義描述指示的方式消耗了輸入數據對象，生成了輸出數據對象，這個過程與函數映射類似.由于任務節點及其輸入數據對象的語義描述均基于準確的領域知識，故可以僅使用它和輸入數據對象的語義描述來刻畫它，而省略它的輸出數據對象.如在圖1中省略了任務節點的輸出數據對象.

由定義1，SW1可表示為：SW1=(N1,E1,S1,τ1)，其中，

N1=NT，1∪NC，1∪ND，1,

NT，1={t1,t2,t3,t4,t5,t6,t7,t8,t9};

NC，1={c1,c2,c3,c4,c5,c6};

ND，1={d1,d2,d3,d4,d5,d6,d7,

d8,d9,d10,d11,d12};

E1={(c1,c2),(c2,c3),(c2,t6),(c3,t1),

(c3,t2),(t1,c4),(t2,c4),(c4,t3),(t3,t4),

(t4,t5),(t5,c5),(t6,c5),(c5,t7),(t7,t8),

(t8,t9),(t9,c6),(d1,t1),(d2,t1),(d3,t1),

(d1,t2),(d2,t2),(d3,t2),(d4,t3),(d5,t3),

(d6,t3),(d7,t3),(d8,t5),(d9,t5),(d10,t6),

(d11,t6),(d12,t8)};

S1={(t1,Saute),(t2,Fry),(t3,Add),(t4,Simmer),

(t5,Place),(t6,Mix),(t7,Pour),(t8,Sprinkle),

(t9,Bake),(d1,Onion),(d2,Green_pepper),

(d3,Butter),(d4,Tomatoes),(d5,Mushrooms),

(d6,Olives),(d7,Ground_beef),(d8,Spaghetti),

(d9,Cheddar),(d10,Mushroom_soup),

(d11,Water),(d12,Parmesan),

(c1,Start),(c2,AndSplit),(c3,XORSplit),

(c4,XORJoin),(c5,AndJoin),(c6,End),

((c1,c2),Control-flow),((c2,c3),Control-flow),

((c2,t6),Control-flow),((c3,t1),Control-flow),

((c3,t2),Control-flow),((t1,c4),Control-flow),

((t2,c4),Control-flow),((c4,t3),Control-flow),

((t3,t4),Control-flow),(t4,t5),Control-flow),

((t5,c5),Control-flow),((t6,c5),Control-flow),

((c5,t7),Control-flow),((t7,t8),Control-flow),

((t8,t9),Control-flow),((t9,c6),Control-flow),

((d1,t1),Input),((d2,t1),Input),((d3,t1),Input),

((d1,t2),Input),((d2,t2),Input),((d3,t2),Input),

(d4,t3),Input),((d5,t3),Input),((d6,t3),Input),

((d7,t3),Input),((d8,t5),Input),((d9,t5),Input),

((d10,t6),Input),((d11,t6),Input),

((d12,t8),Input)};

τ1={(t1,TN),(t2,TN),(t3,TN),(t4,TN),

(t5,TN),(t6,TN),(t7,TN),(t8,TN),(t9,TN),

(d1,DN),(d2,DN),(d3,DN),(d4,DN),(d5,DN),

(d6,DN),(d7,DN),(d8,DN),(d9,DN),(d10,DN),

(d11,DN),(d12,DN),(c1,CN),(c2,CN),

(c3,CN),(c4,CN),(c5,CN),(c6,CN),

((c1,c2),CE),((c2,c3),CE),((c2,t6),CE),

((c3,t1),CE),((c3,t2),CE),((t1,c4),CE),

((t2,c4),CE),((c4,t3),CE),((t3,t4),CE),

(t4,t5),CE),((t5,c5),CE),((t6,c5),CE),

((c5,t7),CE),((t7,t8),CE),((t8,t9),CE),

((t9,c6),CE),((d1,t1),DE),((d2,t1),DE),

((d3,t1),DE),((d1,t2),DE),((d2,t2),DE),

((d3,t2),DE),((d4,t3),DE),((d5,t3),DE),

((d6,t3),DE),((d7,t3),DE),((d8,t5),DE),

((d9,t5),DE),((d10,t6),DE),

((d11,t6),DE),((d12,t8),DE)}.

τ1中的TN指代task node類型，CN指代control-flow node類型，DN指代data node類型，CE指代control-flow edge類型,DE指代dataflow edge類型.

為了限定問題的范圍，本文假定所研究的語義工作流是塊結構化的(block-structured).當一個語義工作流中的順序結構、選擇結構和循環結構都具有明確的開始和結束的塊表示時，稱該語義工作流是塊結構化的[14].在下文中，如不特別指出，所提到的語義工作流均指的是塊結構化的語義工作流.

1.2 任務緊鄰關系

借鑒標簽Petri網的變遷緊鄰關系[9]，本文提出語義工作流的任務緊鄰關系(TAR)和任務緊鄰關系集(TARS)概念.

定義2. 任務緊鄰關系.假定TrS是塊結構化的語義工作流SW=(N,E,S,τ)的所有可能軌跡的集合，a,b為SW的1個任務緊鄰關系，其中a,b∈NT，NT是任務節點的集合，當且僅當存在1個軌跡trace=t1,t2,…,tn滿足trace∈TrS，ti=a并且ti+1=b(i∈{1,2,…,n-1}).SW的所有TAR的集合記為SW的任務緊鄰關系集TARS.

與標簽Petri網的變遷緊鄰關系相似，任務緊鄰關系不能區分循環和順序結構.但與路徑索引中的路徑集合[5]相比，任務緊鄰關系集TARS較好地刻畫了語義工作流的執行行為，更能反映語義工作流的本質，因而適合用于構造基于行為特征的索引.由于語義工作流中存在路由節點，對于較復雜的語義工作流，直接根據其結構獲取TARS一般是很困難的.Mcmillan等人[15]最先提出使用完全有限前綴來展開Petri網系統.該算法有著較高的效率和比較小的展開規模，在解決Petri網狀態空間爆炸問題方面有比較出色的表現.Esparza等人[16]對此進行了改進，提出了一種規模更小的展開方法，即完全前綴展開.更多相關概念和示例詳見文獻[15-18].

例2. 圖2為圖1所示的語義工作流SW1的完全前綴展開.

Fig. 2 The complete prefix unfolding of the semantic workflow SW1圖2 語義工作流SW1的完全前綴展開

易得，SW1的TARStarS1={t1,t3,t2,t3,t3,t4,t4,t5,t1,t6,t6,t1,t2,t6,t6,t2,t3,t6,t6,t3,t4,t6,t6,t4,t5,t6,t6,t5,t5,t7,t6,t7,t7,t8,t8,t9}.

2 2階段的相似語義工作流檢索方法

在進行相似語義工作流檢索時，一般需要檢索出包含指定數據對象或滿足指定行為和結構特征的相似語義工作流.例如可能有如下的需求或者這些需求的組合.

R1：找出包含某個任務節點的相似語義工作流；

R2：找出包含某個任務緊鄰關系的相似語義工作流；

R3：找出包含某些輸入數據對象或者不含另一些輸入數據對象的相似語義工作流；

R4：找出包含某個語義工作流片段的相似語義工作流.

易得，需求R1～R3是需求R4的子問題,從而本文以需求R4為主要檢索需求.針對R4，提出了基于MACFAC模型的2階段相似語義工作流檢索方法.第1階段，即MAC階段包含2步過濾操作：1)針對具體語義工作流庫，結合領域任務本體構造任務緊鄰關系樹索引TARTreeIndex，結合領域數據本體構造數據索引DataIndex.2)計算查詢語義工作流的TARS，基于TARTreeIndex對語義工作流庫進行過濾獲取包含此TARS的粗選語義工作流集合；接著基于DataIndex對粗選語義工作流集合進行過濾，獲取包含查詢語義工作流的輸入數據的精選語義工作流集合，稱之為候選語義工作流集合.第2階段，即FAC階段利用基于圖編輯距離的圖匹配[20]相似性方法對候選語義工作流集合進行驗證，根據相似性對候選語義工作流進行排序.

2.1 任務緊鄰關系樹索引TARTreeIndex

在相似語義工作流檢索中，大多數情況下檢索不到執行行為完全一致的語義工作流,這時檢索到執行行為足夠相似的語義工作流往往是最佳選擇.在基于知識的語義工作流環境中，任務緊鄰關系之間不再僅僅是相同或者不同這2種情況，而是還可能有包含或被包含關系、既不包含或也不被包含關系.

定義3. 任務緊鄰關系的包含關系.對于語義工作流SW1=(N1,E1,S1,τ1),SW2=(N2,E2,S2,τ2)，任務節點a,b∈NT,1?N1,任務節點c,d∈NT,2?N2,tar1=a,b,tar2=c,d分別是SW1,SW2的任務緊鄰關系，C1,C2,C3,C4分別是a,b,c,d的語義描述所對應的領域任務本體概念.如果C1C3且C2C4，則稱任務緊鄰關系c,d包含a,b，記為a,bc,d或tar1tar2,稱tar2為父TAR，稱tar1為子TAR.

任務緊鄰關系的包含關系也可以稱為任務緊鄰關系的泛化關系.如果tar1tar2，則稱tar2是tar1的泛化，tar1是tar2的特化.在相似語義工作流檢索中，如果包含指定TAR的語義工作流不存在，則可以根據TAR的包含關系選擇檢索包含該TAR的父TAR或子TAR的語義工作流.為了簡化，本文優先選擇父TAR.當父TAR不存在時，選擇1個子TAR來執行檢索.

定義4. 任務緊鄰關系的相似性.對于語義工作流SW1=(N1,E1,S1,τ1),SW2=(N2,E2,S2,τ2)，任務節點a,b∈NT,1?N1,任務節點c,d∈NT,2?N2,tar1=a,b,tar2=c,d分別是SW1,SW2的任務緊鄰關系，C1,C2,C3,C4分別是a,b,c,d的語義描述所對應的領域任務本體概念.如果tar1tar2，則sim(tar1,tar2)=1;否則

sim(tar1,tar2)=(sim(C1,C3)+

sim(C2,C4))

(1)

其中，sim(Ci,Cj)的計算方法可參考文獻[21]，Ci,Cj(i,j∈{1,2})為領域任務本體概念.

定義4用于計算當前TAR與父TAR或子TAR的相似性.只有相似性超過給定閾值的父TAR或子TAR才會被選擇替換當前TAR.

定義5. 任務緊鄰關系樹.語義工作流的任務緊鄰關系樹TARTree是基于任務緊鄰關系的包含關系建立的一棵多叉樹.它的每個節點為形如(tar,tar.list)的項，建立了從tar到語義工作流集合的映射.其中tar為任務緊鄰關系，tar.list為含有tar的語義工作流集合.

一棵任務緊鄰關系樹TARTree的片段如圖3所示.TARTree中TAR之間的包含關系對語義工作流重用中可重用組件的選取具有參考價值.

Fig. 3 A segment of TARTree圖3 任務緊鄰關系樹的片段

定義6. 任務緊鄰關系樹索引.語義工作流的任務緊鄰關系樹索引TARTreeIndex是任務緊鄰關系樹TARTree的集合.TARTreeIndex用于獲取包含指定任務緊鄰關系集合的語義工作流的集合.

任務緊鄰關系樹索引TARTreeIndex構造算法的偽代碼如算法1所示：

算法1. 任務緊鄰關系樹索引TARTreeIndex構造算法.

輸入：語義工作流庫SWB、領域任務本體TaskOnto；

輸出：任務緊鄰關系樹索引tarTreeIndex.

①tarTreeIndex=?;

② ifSWB==? then

③ returntarTreeIndex;

④ end if

⑤ foreachSW∈SWBdo

⑥tarS=computeTARS(SW);

⑦ foreachtar∈tarSdo

⑧ iftarTreeIndex==? then

⑨tree1.root=newnode(tar),tree1.root.list.add(SW),tarTreeIndex=tarTreeIndex∪{tree1};

⑩ elsen1=newnode(tar),n1.list.add(SW),insertTARTreeIndex(SW,n1);

函數1.insertTARTreeIndex(SW,tarNode)的偽代碼.

輸入：語義工作流SW、任務緊鄰關系樹節點tarNode；

輸出：任務緊鄰關系樹索引tarTreeIndex.

① foreachtree∈tarTreeIndexdo

② iftarNode.tartree.root.tarortree.root.tartarNode.tarthen

③tree2.root=tarNode,tarTreeIndex=tarTreeIndex∪{tree2};

④ else iftarNode.tar==tree.root.tarthen

⑤tree.root.list.add(tarNode.list);

⑥ else iftarNode.tartree.root.tarthen

⑦insertTARTree(tree.root,SW,tarNode);

⑧ else iftree.root.tartarNode.tarthen

⑨tarNode.childList.add(tree.root.list);

⑩ end if

函數2.insertTARTree(treeRoot,SW,tarNode)的偽代碼.

輸入：任務緊鄰關系樹的根節點treeRoot、語義工作流SW、任務緊鄰關系樹節點tarNode；

輸出：任務緊鄰關系樹索引tarTreeIndex.

① iftreeRoot.childList==? then

②treeRoot.childList.add(tarNode);

③ else foreachchild∈treeRoot.childListdo

④ ifchild.tartarNode.tarthen

⑤tarNode.childList.add(child),treeRoot.childList.add(tarNode),treeRoot.childList.delete(child);

⑥ else iftarNode.tarchild.tarthen

⑦insertTARTree(child,SW,tarNode);

⑧ elsetreeRoot.childList.add(tarNode);

⑨ end if

⑩ end if

算法1中，函數computeTARS(SW)用于計算語義工作流SW的TARStarS，函數insertTARTree-Index(SW,tarNode)用于將SW的TAR節點tarNode插入索引tarTreeIndex中，函數insertTARTree(treeRoot,SW,tarNode)用于將SW的TAR節點tarNode插入以treeRoot為根節點的任務緊鄰關系樹TARTree中.在構造tarTreeIndex的過程中，tarS中的每個TAR被插入到1個TARTree中或者成為1個新TARTree的根節點.

當有新語義工作流加入語義工作流庫時，tarTreeIndex的更新過程與其建立過程基本一致，也是基于TAR的包含關系將新語義工作流的TARS插入到tarTreeIndex中.當某一語義工作流從庫中刪除時，需要進行TARTree相應節點的刪除，這可以立刻執行或當需要刪除的語義工作流達到一定數量時，一次性刪除所有相應的節點.

基于TARTreeIndex檢索與某個查詢語義工作流相似的語義工作流，實質上可轉化為在語義工作流庫中檢索與查詢語義工作流執行行為相似的語義工作流.算法的偽代碼如算法2所示：

算法2. 檢索與某個查詢語義工作流相似的語義工作流.

輸入：語義工作流庫SWB、任務緊鄰關系樹索引tarTreeIndex、查詢語義工作流SWq、任務緊鄰關系的相似性閾值θ1；

輸出：與SWq的執行行為相似的語義工作流集WFS.

①WFS=?;

②tarSq=computeTARS(SWq);

③ foreachtar∈tarSqdo

④tarNode=newnode(tar),tarNode.list.add(SW),insertTARTreeIndex(null,tarNode);

⑤ if ?treeNode∈tarTreeIndexsuch thattreeNode.tar=tarNode.tarthen

⑥WFS=WFS∪treeNode.list;

⑦ else iftarNode.parent.list≠? then

⑧WFS=WFS∪tarNode.parent.list;

⑨ else iftarNode.childList≠? then

⑩ selectchildsuch thatchild.list≠? andsim(tarNode.tar,child.tar)≥θ1,WFS=WFS∪child.list;

算法2的檢索過程與將新語義工作流入庫相似，只是在向TARTree插入相應節點時，將TAR所屬的語義工作流置為null，如算法2的行④.這樣檢索得到的語義工作流集即為所求的集合，而不包含查詢語義工作流本身.在檢索后對TARTreeIndex進行的恢復操作是刪除剛插入的TARNode節點，這點沒有體現在算法2中.算法2首先檢索至少包含tarSq中1個TAR的語義工作流集，然后對這些集合取并集.選擇并集的目的是為了獲取與SWq執行行為相似的語義工作流.在第⑤行，如果已經存在1個TAR節點treeNode，則treeNode.list即為所求的語義工作流集合；如果不存在這樣1個TAR節點，則優先選擇父TAR節點的語義工作流集合，次之選擇某個子TAR節點的語義工作流集合.

2.2 數據索引DataIndex

定義7. 數據索引.語義工作流庫的數據索引DataIndex，結構形如(data,data.list).其中data表示輸入數據對象，data.list表示包含data的語義工作流集.

建立該索引的算法的偽代碼如算法3所示：

算法3. 數據索引DataIndex構造算法.

輸入：語義工作流庫SWB；

輸出：數據索引dataIndex.

①dataIndex=?；

② ifSWB==? then

③ returndataIndex;

④ end if

⑤ foreachSW∈SWBdo

⑥dataS=computeDS(SW);

⑦ foreachdata∈dataSdo

⑧ ifdata?dataIndexthen

⑨data.list.add(SW),dataIndex.add(data);

⑩ elsedata.list.add(SW);

算法3中，函數computeDS(SW)用于獲取語義工作流SW的輸入數據對象集dataS.數據索引dataIndex采用Map結構實現，其更新較簡單.當檢索包含某一數據對象data的相似語義工作流集合時，可以使用data作為key在dataIndex中檢索，返回value為data.list；若不存在該data，則先在領域數據本體DataOnto中查找與它相似的父數據對象或子數據對象data′，然后查找包含data′的相似語義工作流集合.算法偽代碼如算法4所示：

算法4. 檢索包含某個查詢語義工作流的輸入數據對象的相似語義工作流.

輸入：數據索引dataIndex、查詢語義工作流SWq、領域數據本體DataOnto、數據對象的相似性閾值θ2；

輸出：包含SWq的數據對象集的相似語義工作流集合WFS.

①WFS=?;

②dataSq=computeDS(SWq);

③ foreachdata∈dataSqdo

④ ifdata∈dataIndexanddata.list≠? then

⑤WFS=WFS∪data.list;

⑥ else searchdata’sparentinDataOnto；

⑦ ifparent.list≠? then

⑧WFS=WFS∪parent.list;

⑨ else searchdata’schildListinDataOnto;

⑩ foreachchild∈childListdo

算法4中，對包含每個數據對象的語義工作流集合求并集操作是為了獲取與SWq的輸入數據對象相似的語義工作流.

2.3 2階段的相似語義工作流檢索方法

2.3.1 語義工作流過濾

對于查詢語義工作流SWq，過濾操作可以由算法2和算法4實現.首先使用任務緊鄰關系樹索引TARTreeIndex進行粗選過濾操作，由算法2完成，得到語義工作流集WFS1;接著使用數據對象索引DataIndex對WFS1進行精選過濾操作，由算法4完成，得到語義工作流集WFS2,稱WFS2為候選語義工作流集.

2.3.2 候選語義工作流集驗證

在驗證階段，針對查詢語義工作流SWq，使用語義工作流的圖匹配相似性方法對候選語義工作流集WFS2進行驗證，并按與SWq的相似程度進行排序.語義工作流的圖匹配相似性基于圖編輯距離得到，而圖編輯距離反映了語義工作流間的結構特征差別.

定義8. 語義工作流的圖編輯距離.對于語義工作流SW1=(N1,E1,S1,τ1),SW2=(N2,E2,S2,τ2)，SW1與SW2的圖編輯距離是將SW1轉換成SW2所需的最小編輯操作數.編輯操作包括節點和邊的替換、插入和刪除操作.

Dijkman等人[20]給出了尋求過程模型的活動節點間最優匹配的方法，基于此確定節點和邊的編輯操作(替換、插入和刪除)次數，進而確定過程模型間的圖編輯距離.最后根據圖編輯距離計算圖編輯相似性，稱之為圖匹配(graph matching)相似性.然而該方法省略了過程模型中的路由節點，無法真實反映過程模型原有的路由情況，從而得出的圖匹配相似性也不夠準確.在獲取語義工作流的圖匹配時，本文改進使用貪婪策略的圖匹配方法[20]，保留語義工作流中的路由節點，基于上下文相似性優先進行路由節點的匹配.來自2個語義工作流的路由節點的上下文相似性越高，則它們在最優匹配中出現的概率就越高.

定義9. 路由結點的上下文相似性.對于語義工作流SW1=(N1,E1,S1,τ1),SW2=(N2,E2,S2,τ2)，假設路由節點u∈NC,1?N1,v∈NC,2?N2的直接前驅節點集合分別為Pu,Pv，直接后繼節點集合分別為Su,Sv，如果u,v為相同類型的開節點或閉節點，則u,v的上下文相似性

simC(u,v)=k1×sim(Pu,Pv)+

(2)

其中，k1+k2=1，一般取k1=k2=0.5；否則simC(u,v)=0.

式(2)中，sim(Pu,Pv),sim(Su,Sv)由KM算法[22]計算得出.在獲取語義工作流的圖匹配時，優先進行語義工作流的路由節點的匹配，基于此再進行任務節點的匹配，最后得到所有節點間的映射.任務節點的相似性采用其語義描述的語義相似性.由于使用貪婪策略可能生成非最優匹配，但在MAC階段的2步過濾操作后，這種概率大大降低.此處省略語義工作流的圖匹配算法的偽代碼.

第1階段(MAC階段)基于行為特征進行語義工作流過濾，獲得執行行為相似的候選語義工作流集;第2階段(FAC階段)基于結構特征對候選語義工作流集進行驗證，通過選擇適當的圖匹配相似性閾值可以獲得不但執行行為相似而且結構特征也相似的語義工作流集.這樣，在檢索過程中把語義工作流的行為特征和結構特征結合起來，可以得到整體質量更高的檢索語義工作流集，從而為語義工作流重用提供更高質量的備選語義工作流.

3 實驗與結果分析

3.1 實驗建立

本文的所有實驗基于如下環境：Intel CoreTMCPU 2.2 GHz，4.0 GB RAM，Windows7 64位操作系統，JDK1.6環境的筆記本計算機.目前，基于知識的語義工作流的數據集還較少.本文的實驗數據集選自WikiTaaable*http:wikitaaable.loria.fr的Recipe和Recipesource*http:www.recipesource.com，其中共有1 000多個意大利面食(pasta)食譜.實驗中的領域任務本體TaskOnto來自WikiTaaable的Culinary actions ontology，領域數據對象本體DataOnto來自WikiTaaable的Food ontology.該數據集及上述本體是ICCBR會議為計算機烹飪比賽(computer cooking contest, CCC)建立的.

本文從數據集中隨機選取50個意大利面食的食譜，根據定義1將食譜的烹飪說明(cooking instructions)表示成如圖1所示的語義工作流[13]，組成規模為50的語義工作流庫.

3.2 實驗結果對比

3.2.1 檢索的準確率比較

本實驗在語義工作流庫中隨機選取10個語義工作流并對之做一定的改動[21]，組成大小為10的查詢語義工作流集.取任務緊鄰關系的相似性閾值θ1=0.6，數據對象的相似性閾值θ2=0.5，語義工作流的相似性閾值θ3=0.5.針對每個查詢語義工作流分別執行檢索，繪制本文的TARTreeIndex+Data-Index算法和Path-1算法[5]的P-R(precision-recall)曲線.這里取k=1,因為長度為1的路徑索引可以獲得較好的檢索性能[5].將TARIndex算法[10]、基于貪婪策略的圖匹配相似性算法[20]的研究方法應用于相似語義工作流檢索，如采用忽略數據流的語義工作流的TARS、任務節點的語義相似性等.繪制由TARIndex算法和圖匹配算法得到的P-R曲線,如圖4所示：

Fig. 4 P-R curves of four retrieval algorithms圖4 4種檢索算法的P-R曲線

由圖4可以看出，TARTreeIndex+DataIndex算法和TARIndex算法的P-R曲線完全處于Path-1算法和圖匹配算法的P-R曲線的上方，表明引入基于行為特征的索引確實提高了相似語義工作流的檢索性能.TARIndex算法的P-R曲線在R=0.7處高于TARTreeIndex+DataIndex算法，這是由于語義工作流庫中存在了2個執行行為足夠相似而數據集有一定差異的可接受語義工作流.TARIndex算法忽略了數據流使得在排序的檢索結果中這2個語義工作流相隔很近，而在考慮數據流的TARTree-Index+DataIndex算法的排序的檢索結果中它們相隔較遠.這樣使得TARIndex算法在R=0.7處準確率P高于TARTreeIndex+DataIndex算法.但TARTreeIndex+DataIndex算法的P-R曲線的大部分處于TARIndex算法的P-R曲線的上方，表明結合結構特征并引入數據對象索引從整體上提高了相似語義工作流的檢索性能.以上表明TARTree-Index+DataIndex算法的相似語義工作流檢索性能好于其他3種算法.

3.2.2 檢索時間比較

本實驗從查詢語義工作流集中任選5個語義工作流，在語義工作流庫中語義工作流數量從10開始以步長10增加到50時，分別執行檢索.記錄每次的檢索時間，并計算每個語義工作流數量的檢索時間的平均值.將本文TARTreeIndex+DataIndex算法的檢索時間與TARIndex算法、Path-1算法、圖匹配算法的檢索時間作比較，如圖5所示：

Fig. 5 Retrieval time of four retrieval algorithms圖5 4種檢索算法的檢索時間

由圖5看出，圖匹配算法的檢索時間多于其他3種算法，原因是該算法采用遍歷語義工作流庫的方法進行檢索，這也說明了引入索引的必要性.而TARTreeIndex+DataIndex算法的檢索時間多于TARIndex算法和Path-1算法，原因是構造任務緊鄰關系樹索引TARTreeIndex和數據索引DataIndex也增加了檢索時間.因此，將索引TARTreeIndex和DataIndex離線構造并存儲在文件中以及使用一定的緩存技術是必要的.

3.2.3 索引構造時間比較

Fig. 6 Index construction time of three retrieval algorithms圖6 3種算法的索引構造時間

對于本文的TARTreeIndex+DataIndex算法，在語義工作流庫中語義工作流數量從10開始以步長10增加到50時，本實驗分別記錄索引構造時間.將本文TARTreeIndex+DataIndex算法的索引構造時間與TARIndex算法、Path-1算法的索引構造時間作比較，如圖6所示.

由圖6看出，TARTreeIndex+DataIndex算法的索引構造時間多于TARIndex算法和Path-1算法，原因是構造索引TARTreeIndex和索引DataIndex使用的時間比構造索引TARIndex或Path-1要多.但由于索引TARTreeIndex和索引DataIndex都可以增量更新，當有新的語義工作流加入庫中時，索引更新所用時間較少.

從以上實驗可以看出，本文的結合行為和結構特征的2階段相似語義工作流檢索算法在檢索性能上得到了改善，但檢索時間和索引構造時間較長.其索引技術需要進一步完善以減少檢索時間和索引構造時間.由于語義工作流的重用一般是離線完成的，因此也可以接受這種檢索時間.從而本文提出的算法以可接受的代價改善了相似語義工作流的檢索性能.

4 總結與展望

在未來的工作中，將致力于研究更高效的語義工作流行為特征索引，以進一步提高結合結構和行為特征的相似語義工作流檢索算法的效率；設計以語義工作流修正代價最少為導向的相似語義工作流檢索方法，以期為語義工作流重用提供更適于重用的檢索語義工作流集.語義工作流庫的內容及其組織結構對語義工作流的檢索與修正效率有重要影響，因而語義工作流庫維護也是未來的工作之一.

[1]Bergmann R, Gil Y. Similarity assessment and efficient retrieval of semantic workflows[J]. Information Systems, 2014, 40(1): 115-127

[2]Jin Tao, Wang Jianmin, Wen Lijie. Indexing technology for business process models[J]. Computer Integrated Manufacturing Systems, 2011, 17(8): 1580-1586 (in Chinese)(金濤, 王建民, 聞立杰. 業務過程模型庫索引技術[J]. 計算機集成制造系統, 2011, 17(8): 1580-1586)

[3]Forbus K D, Gentner D, Law K. MACFAC: A model of similarity based retrieval[J]. Cognitive Science, 1995, 19(2): 141-205

[4]Bergmann R, Minor M, Islam S, et al. Scaling similarity-based retrieval of semantic workflows[C]Proc of ICCBR-Workshop on Process-oriented Case-Based Reasoning. Berlin: Springer, 2012: 15-24

[5]Kendall-Morwick J, Leake D. A study of two-phase retrieval for process-oriented case-based reasoning[G]Successful Case-Based Reasoning Applications-2. Berlin: Springer, 2014: 7-27

[6]Müller G, Bergmann R. A cluster-based approach to improve similarity-based retrieval for process-oriented case-based reasoning [J]. Frontiers in Artificial Intelligence & Applications, 2014, 263: 639-644

[7]Müller G, Bergmann R. POQL: A new query language for process-oriented case-based reasoning[COL]Proc of LWA 2015 Workshops: KDML, FGWM, IR, and FGDB. [2016-10-24]. http:ceur-ws.orgVol-1458F06_CRC59_Mueller.pdf

[8]Jin Tao, Wang Jianming, Wu Nianhua, et al. Efficient and accurate retrieval of business process models through indexing[G]LNCS 6426: Proc of Conf on the Move to Meaningful Internet Systems (OTM 2010). Berlin: Springer, 2010: 402-409

[9]Zha Haiping, Wang Jianmin, Wen Lijie, et al. A workflow net similarity measure based on transition adjacency relations [J]. Computers in Industry, 2010, 61(5): 463-471

[10]Jin Tao, Wang Jianmin, Wen Lijie. Efficient retrieval of similar workflow models based on behavior[G]Web Technologies and Applications. Berlin: Springer, 2012: 677-684

[11]Weidlich M, Mendling J, Weske M. Efficient consistency measurement based on behavioral profiles of process models [J]. IEEE Trans on Software Engineering, 2011, 37(3): 410-429

[12]Bergmann R, Müller G, Wittkowsky D. Workflow clustering using semantic similarity measures[G]Advances in Artificial Intelligence. Berlin: Springer, 2013: 13-24

[13]Dufour-Lussier V, Leber F, Lieber J, et al. Automatic case acquisition from texts for process-oriented case-based reasoning[J]. Information Systems, 2014, 40(1): 153-167

[14]Kiepuszewski B, Hofstede A H M, Bussler C J. On structured workflow modelling[G]Seminal Contributions to Information Systems Engineering. Berlin: Springer, 1999: 241-256

[15]Mcmillan K L, Probst D K. A technique of state space search based on unfolding[J]. Formal Methods in System Design, 1995, 6(1): 45-65

[16]Esparza J, R?mer S, Vogler W. An improvement of McMillan's unfolding algorithm[G]Tools and Algorithms for the Construction and Analysis of Systems. Berlin: Springer, 1996: 87-106

[17]Engelfriet J. Branching processes of Petri nets[J]. Acta Informatica, 1991, 28(6): 575-591

[18]Du Yuyue, Sun Ya’nan, Liu Wei. Petri nets based recognition of model deviation domains and model repair[J]. Journal of Computer Research and Development, 2016, 53(8): 1766-1780 (in Chinese)(杜玉越, 孫亞男, 劉偉. 基于Petri網的模型偏差域識別與模型修正[J]. 計算機研究與發展, 2016, 53(8): 1766-1780)

[19]Song Jinfeng, Wen Lijie, Wang Jianmin. A similarity measure for process models based on the occurrence relations of tasks[J]. Journal of Computer Research and Development, 2017, 54(4): 832-843 (in Chinese) (宋金鳳, 聞立杰, 王建民. 基于任務發生關系的流程模型相似性度量[J]. 計算機研究與發展, 2017, 54(4): 832-843)

[20]Dijkman R, Dumas M, Garcíabauelos L. Graph matching algorithms for business process model similarity search [C]Proc of the 7th Int Conf on Business Process Management. Berlin: Springer, 2009: 48-63

[21]Sun Jinyong，Gu Tianlong，Wen Lijie，et al. Similarity algorithm for semantic workflows used in process-oriented case-based reasoning[J]. Computer Integrated Manufacturing Systems 2016, 22(2): 381-394 (in Chinese)

(孫晉永, 古天龍, 聞立杰, 等. 用于面向過程的基于實例推理的語義工作流相似性算法[J]. 計算機集成制造系統, 2016, 22(2): 381-394)

[22]Munkres J. Algorithms for the assignment and transportation problems[J]. Journal of the Society for Industrial and Applied Mathematics, 1957, 5(1): 32-38

Sun Jinyong, born in 1978. Master. Student member of CCF. His main research interests include business process management and workflow technology, knowledge representation and reasoning, etc.

Gu Tianlong, born in 1964. PhD. Professor, PhD supervisor. His main research interests include formal methods, data and knowledge engineering, software engineer-ing, etc.

Wen Lijie, born in 1977. PhD, associate professor, PhD supervisor. His main research interests include process mining, process data management, workflow for big data analysis (wenlj@tsinghua.edu.cn).

Qian Junyan, born in 1973. PhD. Professor. Senior member of CCF. His main research interests include software engineering, model checking and program verification, etc (qjy2000@gmail.com).

Meng Yu, born in 1976. PhD candidate. Associate professor. Member of CCF. Her main research interests include intelligent planning, knowledge representation and reasoning, and formal method, etc (mengyu@guet.edu.cn).

Retrieval of Similar Semantic Workflows Based on Behavioral and Structural Characteristics

Sun Jinyong1,2, Gu Tianlong2, Wen Lijie3, Qian Junyan2, and Meng Yu2

1(SchoolofComputerScienceandTechnology,XidianUniversity,Xi’an710071)2(GuangxiKeyLaboratoryofTrustedSoftware(GuilinUniversityofElectronicTechnology),Guilin,Guangxi541004)3(SchoolofSoftware,TsinghuaUniversity,Beijing100084)

Workflow reuse is an important method for modern enterprises and organizations to improve the efficiency of business process management (BPM). Semantic workflows are domain knowledge-based workflows. The retrieval of similar semantic workflows is the first step for semantic workflow reuse. Existing retrieval algorithms of similar semantic workflows only focus on semantic workflows’ structural characteristics while ignoring their behavioral characteristics, which affects the overall quality of retrieved similar semantic workflows and increases the cost of semantic workflow reuse. To address this issue, a two-phase retrieval algorithm of similar semantic workflows is put forward based on behavioral and structural characteristics. A task adjacency relations (TARs) set is used to express a semantic workflow’s behavior. A TARs trees index named TARTreeIndex and a data index named DataIndex are constructed combined with domain knowledge for the semantic workflows case base. For a given query semantic workflow, firstly, candidate semantic workflows are obtained by filtering the semantic workflows case base with the TARTreeIndex and DataIndex, then candidate semantic workflows are verified and ranked with the graph matching similarity algorithm. Experiments show that the proposed algorithm improves the retrieval performance of similar semantic workflows compared with the existing popular retrieval algorithms for similar semantic workflows, so it can provide high-quality semantic workflows for semantic workflow reuse.

workflow reuse; semantic workflow; similarity-based retrieval; structural characteristics; behavioral characteristics; task adjacency relations trees index (TARTreeIndex)

2016-10-24；

2017-02-13

國家自然科學基金項目(61562015,61572146,U1501252)；廣西自然科學基金項目(2015GXNSFDA139038,2016GXNSFDA380006)；廣西可信軟件重點實驗室項目(KX201627)；廣西高等學校高水平創新團隊及卓越學者計劃項目；桂林電子科技大學創新團隊項目；廣西精密導航技術與應用重點實驗室項目(DH201508) This work was supported by the National Natural Science Foundation of China (61562015, 61572146, U1501252), the Natural Science Foundation of Guangxi of China (2015GXNSFDA139038, 2016GXNSFDA380006), the Project of Guangxi Key Laboratory of Trusted Software (KX201627), the Project of High Level of Innovation Team of Colleges and Universities in Guangxi and Outstanding Scholars Program, and the Program for Innovative Research Team of Guilin University of Electronic Technology, and the Project of Guangxi Key Laboratory of Precision Navigation Technology and Application (DH201508).

古天龍(cctlgu@guet.edu.cn)

TP315; TP18