基于復合結構的知識庫分類體系匹配方法

林海倫 賈巖濤 王元卓 靳小龍 程學旗 王偉平

1(中國科學院信息工程研究所 北京 100093)2 (中國科學院網絡數據科學與技術重點實驗室(中國科學院計算技術研究所) 北京 100190)(linhailun@iie.ac.cn)

基于復合結構的知識庫分類體系匹配方法

林海倫1賈巖濤2王元卓2靳小龍2程學旗2王偉平1

1(中國科學院信息工程研究所 北京 100093)2(中國科學院網絡數據科學與技術重點實驗室(中國科學院計算技術研究所) 北京 100190)(linhailun@iie.ac.cn)

近年來，分類體系匹配由于其在知識庫構建和融合等方面的廣泛應用，已成為國內外工業界和學術界的研究熱點.然而，隨著網絡大數據的不斷發展，分類體系變得越來越龐大和復雜，構造一種通用有效的分類體系匹配器以適應大規模、異構分類體系匹配的擴展性仍然面臨很大的挑戰.為此，提出了一種基于復合結構的分類體系匹配方法BiMWM，該方法利用分類體系中分類的復合結構信息：微觀結構和宏觀結構，將分類體系匹配問題轉化為二部圖上的優化問題進行求解.首先，創建賦權的二部圖建模分類體系之間候選的匹配類對關系；然后，通過計算二部圖上的最大權匹配剪枝選擇最優的分類體系的匹配類對.BiMWM方法可以在多項式時間內為2個分類體系產生最優匹配.實驗結果表明:與當前先進的基準方法相比，該方法能夠有效提升大規模、異構分類體系匹配的性能.

知識庫；分類體系匹配；復合結構；二部圖；最大權匹配

知識庫是包含實體、關系和分類等的知識集合，而分類體系作為知識庫的骨架結構，是知識庫中用于語義分類或標注知識項的分類集合.由于不同的知識庫可能會包含重疊或互補的數據，已經有越來越多的工作開始嘗試通過匹配不同知識庫中的公共元素來將它們進行融合.因此，分類體系匹配被認為是知識庫融合所需要的最重要的操作之一，其主要任務就是在不同知識庫中發現對齊分類體系中共同的元素，從而將描述知識的2個分類體系進行集成，完成2個知識庫的融合，實現知識的復用和共享.

特別是近年來，隨著知識庫取得的成功，如Freebase[1]，YAGO[2]，Probase[3]，Knowledge Graph*https:en.wikipedia.orgwikiEdit_distance等，分類體系匹配問題得到廣泛的研究，已有很多研究工作，如RiMOM[4]，PARIS[5]，SiGMa[6]，YAGO+F[7]等.這些研究工作大部分是利用分類自身的信息來計算2個分類體系之間元素的相似度，例如分類的名稱、屬性或與分類相關的實例以及分類在分類體系中的上下位關系等.然而，目前大部分工作還只能在特定領域發揮作用，而且無法有效地處理大規模的分類體系[8].導致這一問題的原因在于：不同的分類體系通常使用不同的詞匯和層級結構來表示自己的分類，而且其對應的可能的匹配空間隨分類體系中分類的規模的增加呈現指數級增長.特別是，隨著網絡大數據[9]的發展，分類體系變得越來越龐大和復雜.基于貪心的方法對處理大規模的分類體系匹配任務可能是一種有效的方法，但由于其貪心的性質，它在匹配決策時難以修正之前的錯誤.因此，該方法無法保證2個分類體系獲得全局最優的匹配.

為了解決上述問題，本文提出了一種基于復合結構的分類體系匹配方法，該方法的設計原理來源于分類體系在結構上具有很多共同點：雖然不同的分類體系具有不同的組織形式，但是分類體系中每一個分類都有標識它的名稱、屬性、上下文描述以及與該分類相關的實例等；除此之外，還有其在分類體系中的父類、子類和兄弟節點等，我們分別稱之為分類的微觀結構和宏觀結構.因此，很容易得出一個結論：2個分類的微觀結構和宏觀結構越相似，它們越有可能是在語義上彼此等價的2個分類.因此，本文提出的基于復合結構的方法則基于分類的微觀結構和宏觀結構特征，將分類體系匹配問題建模為二部圖上的優化問題進行求解，通過在二部圖模型上執行最大權匹配算法剪枝選擇2個分類體系之間可能的候選匹配類對，產生2個分類體系之間的全局最優匹配，從而從整體上提升分類匹配的準確率.創新之處在于：

1) 將異構的分類體系轉化為以分類為中心的結構表示，充分利用分類體系中分類之間的關系結構.這里分類的復合結構包括分類體系中分類的微觀結構和宏觀結構信息.

2) 基于以分類為中心的分類體系結構表示，將分類體系匹配問題建模為二部圖上的優化問題，提出了二部圖最大權匹配(bipartite maximum weight matching, BiMWM)算法，從而獲得2個分類體系之間的全局最優匹配.

1 相關工作

分類體系匹配問題的根源來自于記錄鏈接、重復檢測或共指消解問題[10-11].此外，該問題也與模式匹配問題類似.目前，Shvaiko等人[12]對已有的模式匹配工作進行了研究分析，這些工作可分為3類：基于相似度的方法、基于統計的方法和基于復合的方法.這些工作的目標是試圖為多個數據源建立一個共同的模式或找到不同模式之間內在的關聯方式.

盡管模式匹配問題與分類體系匹配問題類似，但是與模式匹配相比，分類體系匹配有著自己獨特的特點：1)與數據模式相比，分類體系在定義數據時提供更高的靈活性和更明確的語義信息；2)數據模式通常是為特定數據庫定義的，而分類體系本質上是可重用共享的；3)在分類體系中，知識表示的基本元素的數量更大、更復雜，如傳遞性、分類不相交性和類型檢查約束等.因此模式匹配的方法無法直接適用于分類體系匹配問題.

近年來，分類匹配問題特別是在本體匹配[13]的概念下已被廣泛研究.Shvaiko等人[14-15]對已有的分類匹配工作進行了研究分析，目前已有的分類匹配工作根據使用策略的不同可分為5類：

1) 利用分類在分類體系中的指代形式(詞匯表示)的策略.這種策略主要基于編輯距離①或Jaccard系數*https:en.wikipedia.orgwikiJaccard_index計算分類名稱之間的文本相似度判斷分類之間的等價關系，這種策略計算簡單、直接.然而，這種策略完全取決于分類的詞匯表示，難以區分分類同義和多義表達的情況.

2) 利用語義詞典的策略.這種策略主要利用語義詞典的信息豐富分類體系中分類的背景信息，如Chen等人[16]利用WordNet的Synset信息擴展分類的同義詞信息，提出了一種結合模糊理論與形式概念分析的分類匹配方法FFCA.這種策略受限于詞典的覆蓋率，當詞典中詞語缺失時則無法有效工作.

3) 利用分類在分類體系中的上下位關系的策略.這種策略利用分類在分類體系中的近鄰結構計算2個分類之間的等價關系，如Li等人[4]提出了一種動態組合策略框架RiMOM，該框架基于2個評估因素：詞匯相似度和結構相似度，自動選擇分類匹配使用的策略.RiMOM通過在2個分類體系關系圖上采用Similarity Flooding技術，提高結構信息對分類匹配的影響.這種策略適用于分類結構相似程度高的分類體系之間的匹配.

4) 利用分類下包含的實例信息的策略.這種策略利用分類包含的實例的重疊率計算分類之間的等價關系，如Suchanek等人[5]提出了一種基于實例的概率化的方法PARIS，該方法通過不同的修剪啟發式規則的稀疏表示(特別是在每一步保持分類體系中每個元素的最大分配)來處理維護所有分類匹配的可擴展性問題.Demidova等人[7]采用基于實例的方法將YAGO和Freebase對應的分類體系進行匹配，形成新的YAGO+F知識庫.這種策略適用于分類下實例豐富且重疊率高的分類體系之間的匹配.

5) 利用上述信息組合形式的混合策略.如Ba等人[17]利用詞匯和實例信息計算分類之間的相似度，基于本體服務器設計開發了一個面向生物醫學領域本體匹配的系統ServOMap.Jiménez-Ruiz等人[18]結合詞匯相似度、語義相似度和結構相似度計算分類體系中共同的元素，設計開發了LogMap系統.Lacoste-Julien等人[6]針對大規模分類體系提出了一種基于貪心的分類匹配方法SiGMa，該方法組合詞匯、屬性和結構信息以貪婪的局部搜索的方式發現匹配的分類.基于貪心的方法對處理大規模的分類體系匹配任務來說可能是一種有效的方法.然而，由于其貪心的性質，它在決策時無法修正之前的錯誤.因此，基于貪心的方法不能保證為2個分類體系獲得全局最優的匹配.除上述策略以外，Li等人[19]提出了一種基于用戶反饋的分類體系匹配策略，這種策略雖然通過與用戶的交互可以提高分類體系匹配的準確率，但是這對用戶提出了具備較強的專業知識的能力，難以適用于大規模分類體系的匹配問題.

通過上述分析可以看出，現有的分類體系匹配的工作大部分是通過計算2個分類體系之間的元素相似度來實現的，雖然目前已經構建了很多分類體系匹配器，但是這些匹配器無法有效地處理大規模的分類體系.不僅如此，它們中沒有一個主導性的分類體系匹配器能夠在所有應用領域都表現得很好.特別是，由于網絡大數據的爆炸性增長，分類體系變得越來越龐大和復雜.因此，需要研究新的分類體系匹配方法以便最大程度提升分類體系匹配的有效性.

2 問題定義

本節將詳細介紹基于復合結構的分類體系匹配的方法.為此，我們首先描述分類體系的概念，然后給出2個分類體系之間分類一一映射的問題定義.

Suchanek等人[5]把一個分類體系定義為一組形式化的知識集合，包括分類、關系和實例及斷言等;Gruber[20]將分類體系定義為是一個形式化的、對于共享概念體系的明確而又詳細的說明.由于網絡大數據的爆炸性增長，新的知識每天都在不斷涌現，因此，現有知識庫需要隨時間不斷演化和改變，所以，知識庫的分類體系也不是一成不變的，它應該隨著時間進行演化.而開放知識網絡[21](open knowledge network, OpenKN)是一個異質的具有時空演化特性的網絡，網絡中的點和邊都具有時間跨度和空間約束來定位以跟蹤知識的演化過程.因此，在開放知識網絡的概念下，本文把分類體系定義為演化知識網絡的模式網絡(schema network)，是一個在知識網絡中用于語義分類或標注知識項的分類集合.更準確地說，一個分類體系T由4個部分組成：

T=(VT,ET,θ,ψ)，

其中，VT是頂點集合；ET是標記的邊的集合；θ:VT→A是定義在頂點上的頂點類型映射函數，滿足每個頂點被分配1個唯一的類型θ(v)∈A;ψ:ET→R是定義在頂點對上的關系類型映射函數，滿足每對頂點最多被分配給1個關系.

在1個分類體系中，頂點的類型集合A有4種類型的取值：class，property，alias，context，分別表示在模式網絡中的1個頂點是分類、屬性、別名和上下文.關系的類型集合R有3個類型的取值：hypernymy，hyponymy，meronymy，分別表示上位關系、下位關系和整體-部分關系.特別地，給定關聯2個頂點u和v的一條邊e，如果e被標記為hypernymy，則表示u比v包含的范圍更廣，即u是v的父節點；如果e被標記為hyponymy，則表示u是v的孩子節點，注意，這2個關系類型hypernymy和hyponymy被更多用來描述2個分類頂點的關系，而關系類型meronymy被更多用來描述分類頂點與屬性、別名以及上下文之間的關系.注意的是，分類體系T是1個無環的分類體系.

基于T的定義，根據頂點類型函數θ:VT→A和關系類型函數ψ:ET→R，我們能夠獲得分類的復合結構.假設C=(c1,c2,…,cm)表示T中分類頂點集合，它用來組織和標注演化知識網絡的所有知識項.每個分類c∈C可以表示為微觀結構信息：名稱name、別名A、上下文描述X、屬性P以及它的宏觀結構信息：關聯的分類集合Nc(表示T中與c關聯的所有分類).因此，c可以被表示成1個通過組合微觀結構和宏觀結構信息的五元組，也被稱為c的復合結構：

c=(name,A,X,P,Nc)，

其中，每個屬性p∈P通過1個二元組表示：p=(name,aliases)，其中name是屬性的名稱，aliases是表示屬性p的別名集合.

我們注意到，在1個分類體系中，分類集合C是全局的，這意味著一些分類可能在不同分類體系中是一致的.不僅如此，2個分類c和c′之間除了可能存在等價關系之外，c和c′的關系還可能是包含關系，例如c?c′或者c′?c.由于包含關系可以通過分類之間的等價關系推演出來，因此，本文的目標是判定一個分類體系的分類c是否等價于另一個分類體系的分類c′.由于分類集合C是1個分類體系的全局參數，本文我們只考慮2個分類體系中一對一的分類匹配.下面給出分類體系匹配問題的形式化定義.

基于定義1，重點介紹基于復合結構的分類體系匹配方法,其具體處理流程如圖1所示：

Fig. 1 Pipeline model of composite structure based taxonomy matching method圖1 基于復合結構的分類體系匹配方法的管道模型

基于復合結構的分類體系匹配方法主要分為3個步驟：

1) 將每個分類體系T=(VT,ET,θ,ψ)，根據頂點類型函數θ:VT→A和關系類型函數ψ:ET→R轉化為以分類為中心的結構表示，這樣做的目的是將異構的分類體系轉化為相同的結構表示，以此清晰地表達分類體系中分類之間的關系結構.

圖2展示了來源于OntoFarm項目*http:nb.vse.cz～svatekontofarm.html構建的2個學術會議本體的部分分類體系.

Fig. 2 Two simple taxonomies圖2 2個簡單的分類體系

基于頂點類型函數θ:VT→A和關系類型函數ψ:ET→R對圖2所示的分類體系進行結構轉換，轉換之后的以分類為中心的結構表示如圖3所示：

Fig. 3 Class-centered taxonomies圖3 以分類為中心的分類體系

2) 基于轉換的以分類為中心的分類體系結構，構建二部圖模型，建模2個分類體系之間候選的匹配類對之間的關系.

3) 基于步驟2創建的二部圖模型，執行最大權匹配剪枝選擇2個分類體系之間可能的候選匹配類對，產生分類體系最終的類對匹配結果.

下面介紹基于復合結構的匹配方法BiMWM的原理.

3 BiMWM方法

BiMWM方法將分類體系匹配問題建模為優化問題，即二部圖最大權匹配問題進行求解，該方法主要包含2個部分：二部圖模型構建算法、分類最大權匹配算法.

3.1 二部圖模型構建算法

給定2個分類體系：T=(VT,ET,θ,ψ)和T′=(VT′,ET′,θ,ψ)，為了以統一的方式表示分類所有可用的信息，我們需要一種能夠對分類體系T的所有分類C和分類體系T′的所有分類C′之間的所有復雜的關系進行有效編碼的表示方式.為了實現這個目標，我們選擇二部圖作為表示方式，這是因為二部圖能夠把來自不同分類體系的分類編碼成圖上的1個頂點，并且可以明確表示頂點之間的候選匹配關系.

在本節，我們基于修改后的以分類為中心的分類體系結構，計算分類的復合結構并構造二部圖G=(V,E,W)，以此建模分類體系T和T′之間候選匹配的類對之間的關系.G是1個無向加權圖，其中，V是由T中包含的|C|個分類和T′中包含的|C′|個分類組成的頂點集合；E是C和C′之間所有候選匹配類對之間邊的集合；W:E→(是實數)是對E中每條邊進行權重賦值的函數.

具體來講，圖G=(V,E,W)的構造方式如下：首先，對于分類體系T中的每個分類c∈C，建立其與分類體系T′中可能與其匹配的分類c′∈C′之間的映射(c,c′,w)，其中權重w是基于分類的復合結構信息計算；然后，對每個三元組(c,c′,w)，將c和c′添加到G的頂點集合V中并且將邊(c,c′)添加到E中，設置權值函數W(c,c′)=w.

給定1個分類對c和c′，我們基于Sigmoid函數定義它們之間匹配度的權值函數：

(1)

其中，S=(str(c,c′),prop(c,c′),sem(c,c′),struct(c,c′))T是分類c和c′之間不同結構信息的相似度向量：str(c,c′)，prop(c,c′)和sem(c,c′)是c和c′之間的微觀結構的相似度，struct(c,c′)是c和c′之間的宏觀結構的相似度.具體地，str(c,c′)表示分類c和c′的名稱或別名的相似度；prop(c,c′)表示分類c和c′的屬性的相似度；sem(c,c′)表示分類c和c′的語義相似度，而struct(c,c′)則表示分類c和c′之間周圍鄰居的相似度.Θ=(θ1,θ2,θ3,θ4)T是一個參數向量，用于在進行分類匹配時平衡分類對之間的微觀結構信息和宏觀結構信息的重要度.

下面將詳細介紹2個分類之間微觀和宏觀結構的相似度度量方法.

1) 微觀結構相似度

① 字符串相似度.為了度量字符串之間的相似度，我們基于編輯距離來計算2個分類體系分類之間的相似度.給定2個分類c1和c2，我們定義它們之間的字符串相似度為

其中，Bi={ci.name}∪ci.A是分類ci的名稱和別名的集合(i={1,2})；ed(b,b′)是字符串b和b′之間的編輯距離；|·|是字符串的長度.

② 屬性相似度.對于屬性相似度度量，我們主要基于2個分類包含的相同屬性的個數.值得注意的是，分類的某些屬性可能比其他屬性更具有典型性(typicality),如“人口”一般是國家或地區的屬性.為此，我們借鑒信息檢索中的逆文檔頻率的定義，采用如下方式來度量屬性p的典型度：

其中，tp表示分類屬性p的典型度，#(·)表示數量.基于屬性的典型度，我們采用加權的Jaccard相似系數來定義2個分類之間的屬性相似度：

③ 語義相似度.在語義相似度方面，目前已經有很多工作，例如Resnik[22]和Banerjee等人[23]提出的基于WordNet計算不同字符串之間的語義相關性的方法，本文直接采用Banerjee提出的Lesk算法[23]來計算2個分類之間的語義相似度.給定分類c1和c2，本文把它們之間的語義相似度定義為

其中，如字符串相似度中所述，Bi是分類ci的名稱和別名組成的集合(i={1,2});lesk_sim(b,b′)是基于Lesk算法的語義相似度.

2) 宏觀結構相似度

① 近鄰相似度.近鄰相似度通過利用分類的鄰居信息來度量2個分類的相似度.對于近鄰相似度計算，我們主要基于2個分類周圍公共鄰居分類的個數.因此，我們直接使用Jaccard相似系數來定義分類c1和c2之間的近鄰相似度：

其中，ci.Nc是分類ci的鄰居分類的集合(i={1,2})，|·|表示集合的大小.

基于上述分類之間相似度計算方式的定義，給定分類體系T=(VT,ET,θ,ψ)和T′=(VT′,ET′,θ,ψ)，為了構造表示這2個分類體系中分類匹配關系的二部圖模型，我們首先將T中包含的所有分類作為二部圖的左部頂點，T′中包含的分類作為二部圖的右部頂點，然后在這些頂點之間利用式(1)計算左部頂點與右部頂點之間匹配的可能性；接下來為左部頂點和右部頂點之間分配連邊信息并為連邊分配權重，從而生成T和T′之間的無向加權二部圖G=(V,E,W).其中，在二部圖G=(V,E,W)構造過程中，V，E，W被初始化為空集.二部圖構造算法如算法1所示：

算法1. 二部圖構造算法.

輸入：T=(VT,ET,θ,ψ)，T′=(VT′,ET′,θ,ψ)；

輸出：二部圖G=(V,E,W).

① 初始化G=(V,E,W)：V=?,E=?,W=?；

② FOR ALLc∈VTinTDO

③ FOR ALLc′∈VT′inT′ DO

④ 基于分類的復合結構信息利用式(1)計算分類c和c′等價匹配的可能性w；

⑤ IFw>0 THEN

⑥ 將分類c和c′添加到頂點集合V中；

⑦ 將權值函數W(c,c′)=w添加到W中；

⑧ 將邊e=(c,c′)添加到邊集合E中；

⑨ 為邊e=(c,c′)賦權值w；

⑩ END IF

具體地，算法1主要包含2個步驟：

1) 候選匹配分類選取.在這一步中，對來自分類體系T的每一個分類c，我們把它和T′的每個分類c′進行配對，根據式(1)計算c和c′之間的匹配度w=W(c,c′)，從T′選擇所有可能與c匹配的分類c′(行②～⑥).

利用上述二部圖模型構建方法，對圖3中的2個分類體系構造二部圖，以此建模2個分類體系之間候選匹配的類對之間的關系.對這2個分類體系構造的二部圖模型如圖4所示：

Fig. 4 An example of the bipartite graph between two taxonomies圖4 二部圖模型示例

在圖4中，該二部圖由T中分類組成的二部圖的左部頂點和T′中分類組成的右部頂點，以及這些頂點之間可能的候選連邊組成.

3.2 分類最大權匹配算法

在本節，我們將給出在二部圖上通過最大權匹配算法找到2個分類體系最優等價映射的過程.下面，我們首先介紹如何將分類體系匹配問題形式化表示為二部圖上的最大權匹配問題，然后給出求解該問題的最大權匹配算法.

如上所述，分類體系匹配問題是一個最優化問題，其目標是找到具有最高置信度的最優等價分類之間一對一的映射；而最大權匹配的目標是找到一組權值最大的頂點不相交的邊集合，而該集合與分類體系之間的最優匹配M是等價的.因此，很容易將分類體系匹配問題轉換成最大權匹配問題.

具體來說，給定1個二部圖G=(V,E,W)，分類體系匹配問題可以被建模成圖G上的整數線性規劃問題，問題的形式化定義如式(2)所示：

(2)

其中，x表示頂點之間是否匹配，w表示頂點之間匹配的可能性.

該整數線性規劃問題可以轉化為其對偶問題進行求解：頂點覆蓋問題，即在圖G=(V,E,W)中找出具有最小規模的頂點覆蓋V′?V，滿足如果(v,v′)∈E，則v∈V′或v′∈V′.這個對偶問題已被證明是一個NP完全問題，問題定義如式(3)所示：

s.t. y(e)≥w(e),?e∈E,

(3)

y(v)≥0,?v∈V，

獲得最大權匹配的核心思想是在二部圖中通過1個初始匹配，不斷地查找增廣路徑，直到找不到增廣路徑為止.最經典的求解最大權匹配的算法是匈牙利算法[24].由于我們構建的二部圖的權值是實數，因此我們擴展匈牙利算法，給出針對分類體系匹配問題的二部圖最大權匹配算法，下面詳細介紹該算法.

給定一個二部圖G=(V,E,W)，我們使用M表示具有最大權的頂點不相交的邊集合，初始時M被初始化為空集；VL和VR分別表示G中左部頂點集合和右部頂點集合；LF和RF分別表示G中左邊自由的頂點集合和右邊自由的頂點集合(當前還未被選擇放入M的頂點的集合)，初始時LF=VL，RF=VR；y(v)表示頂點v∈V的對偶變量值；δ表示對偶變量的增廣值，初始數值為δ0=max{W(e)|e∈E}.

最大權匹配算法的執行流程如算法2所示：

算法2. 最大權匹配算法BiMWM.

輸入：G=(V,E,W)，M，VL，VR，LF，RF，δ0;

輸出：最大權匹配M={(v,v′)|v∈VL,v′∈VR}.

① FOR ALLv∈VinGDO

② IFv∈VLTHEN

③y(v)=δ0；

④ ELSE

⑤y(v)=0；

⑥ END IF

⑦ END FOR

⑧ REPEAT

⑨ 根據VL,VR,LF,RF利用算法3查找增廣路徑AP；

⑩ 擴展匹配M:M=M⊕AP；

具體地，BiMWM算法主要包含4個步驟：

1) 初始化對偶變量.使用對偶變量增廣值δ的初始值δ0初始化對偶變量y(v)(行①～⑦).

2) 查找增廣路徑并根據增廣路徑修改當前找到的最大權匹配.執行算法3查找一條增廣路徑(行⑨)，基于增廣路徑修正最大權匹配結果(行⑩).

重復執行步驟2～4，直至G中找不到增廣路徑，算法終止.至此，我們獲得二部圖G=(V,E,W)上的最大權匹配M.

在BiMWM算法中，增廣路徑查找流程如下：

1) 修改二部圖G，將其轉換為有向圖以便查找增廣路徑.具體修改方式如下：

① 為圖G中的邊添加方向：在G中每一個左部未匹配的頂點LF和右部未匹配的頂點RF之間添加LF→RF方向的連邊；對最大權匹配M中屬于右部的匹配頂點MR=VRRF和屬于左部的匹配頂點ML=VLLF之間添加MR→ML的連邊.

② 在修改的有向圖上添加源頂點s和匯聚頂點t，并在頂點s和每一個屬于左部的自由頂點vL∈LF之間添加s→vL方向的連邊；在每一個屬于右部的自由頂點vR∈RF和匯聚頂點t之間添加vR→t方向的連邊.

基于上述方式，即可將二部圖G轉換為1個有向圖.圖5展示了根據匹配結果將圖4中所示的二部圖G=(V,E,W)轉換為有向圖之后的1個結果.

Fig. 5 Extended bipartite graph圖5 擴展的二部圖模型

2) 在修改之后的有向圖上執行廣度優先算法(breadth first search, BFS)，便可遍歷圖中所有頂點，得到1個頂點訪問的序列，從而找到由該頂點序列組成的1條增廣路徑.

增廣路徑查找算法的執行流程如算法3所示：

算法3. 增廣路徑查找算法.

輸入：G=(V,E,W)，M，{y(v)|v∈V}，VL，VR，LF，RF；

輸出：增廣路徑AP.

① IFLF=? ORRF=? THEN

②AP=?；

③ ELSE

④ 在未匹配的頂點對之間添加從VL→VR的有向邊，在匹配的頂點對之間添加從VR→VL的有向邊；

⑤ 添加源頂點s和匯聚頂點t，并分別在它們與每一個左部自由頂點vL∈LF和右部自由頂點vR∈RF之間添加有向邊：s→vL,vR→t；

⑥ 在修改的圖G上執行BFS算法查找增廣路徑AP={(v,v′)|v∈LF,v′∈RF}，其中AP中所有的邊滿足以下約束條件：y(v)+y(v′)=W(v,v′)；

⑦ END IF

⑧ 根據增廣路徑AP更新自由頂點集合LF=LFAP，RF=RFAP；

⑨AP=AP{s,t}；

⑩ RETURNAP.

算法復雜度分析：給定2個分類體系T=(VT,ET,θ,ψ)和T′=(VT′,ET′,θ,ψ)，記T中包含的分類的個數為n，T′中包含的分類個數為n′.如算法1所示，我們的方法需要n×n′步計算T和T′中所有分類對之間匹配的可能性.因此，我們的方法將會花費O(nn′)的時間創建二部圖G=(V,E,W).

設m=|E|表示圖G中邊的個數，根據算法3，基于圖的廣度優先搜索我們可以在O(m)時間內找到1條增廣路徑.設l=min{n,n′}表示2個分類體系至多可能匹配的分類對個數，如算法2所示，BiMWM則需要花費O(lm)的時間來完成圖G中最大權匹配的查找.因此，我們的方法可以在多項式時間內O(nn′+lm)獲得2個分類體系匹配的類對，找到2個分類體系包含的語義相同的公共分類.

眾所周知，二部圖最大權匹配的目標是在二部圖中查找一組頂點不相交的邊，使得這組邊的權值和最大.所以，最大權匹配的解決方案是一個全局最優的頂點不相交的邊集.在本文中，我們提出將分類體系匹配問題建模成最大權匹配問題.因此，對于2個分類體系，我們的方法可以保證獲得一個全局的具有最高置信度的最優匹配.

4 實驗與分析

在本節中，我們在2個標準數據集上評估我們提出的基于復合結構的知識庫分類體系匹配方法BiMWM的效果.我們將：1)在準確率、召回率和F值3個指標上比較BiMWM方法和基準方法的效果；2)分析BiMWM方法在分類體系規模變化時的性能變化；3)分析BiMWM方法在不同領域分類體系上的有效性.本節所有實驗是在2臺配置相同的服務器上完成的，服務器具體配置如下：64-bit Linux OS，16 core 2 GHz AMD OpteronTM6128處理器，32 GB RAM.

4.1 實驗設置

1) 評價指標.在實驗中我們使用標準的評價指標：準確率、召回率和F值，度量分類體系中正確匹配的類對的數目.除此之外，我們使用運行時間度量各個方法在不同規模數據集上的運行效率.

2) 數據集.在實驗中使用本體映射任務國際評測①(ontology alignment evaluation initiative, OAEI)中發布的2個標準數據集.

第1個數據集來自于OAEI 2013的生物醫學領域的測試用例②(記為largebio)，該測試用例包含3個生物醫學本體：FMA，SNOMED-CT(以下簡記為SNOMED)，NCI，這些本體都包含數萬的分類.該測試用例的主要目標是尋找這些本體之間的分類匹配映射.由于該測試用例包含3個不同的本體，因此分成不同的匹配問題：FMA-NCI，FMA-SNOMED，NCI-SNOMED，而每一個匹配問題又被分成了“局部”和“整體”片段上的2個測試任務，分別記為DSsmall和DSwhole數據集，以便評測不同方法在不同規模數據集上的性能表現.該測試用例使用一體化醫學語言系統UMLS詞表作為本體匹配的標注數據(ground truth)，該數據集分類的規模約為27萬.

第2個數據集來自OAEI 2013的學術會議領域的測試用例③(記為DSconf)，其目標是要找到學術會議領域的本體集合中所有正確的匹配關系.在該測試用例中，我們采用標記ra1的數據集作為ground truth，其包括7個本體，即21個本體匹配映射問題，這些本體來源于OntoFarm項目④.

3) 基準方法.為了驗證BiMWM方法在分類匹配任務上的有效性，在實驗中我們選擇OAEI 2013評測中[8]在各項評價指標上效果排名靠前的4種方法作為基準方法，它們分別是YAM++，IAMA，LogMap，ServOMap.除此之外，我們還選擇基于貪心的方法SiGMa[6]作為基準方法(見第1節).

4) 參數設置.在實驗中，測量2個分類之間的匹配可能性的權值函數的參數Θ=(θ1,θ2,θ3,θ4)T被設置為Θ=(0.39,0.41,0.10,0.10)T，該參數是我們通過探討BiMWM方法在會議數據集上的有效性找到的合理值.在所有數據集上，我們都固定這些參數進行效果比對.另外，由于SiGMa開始于1個初始的匹配分類對，該分類對可以是任意具有高質量的初始匹配種子[6].由于選用的OAEI標準數據集中所有分類體系的根節點都是名為“Thing”的分類，因此，在實驗中我們選擇標準數據集的根節點之間組成的類對作為SiGMa初始匹配的分類對.

基于上述實驗設置，我們進行：①測試各個方法在不同規模數據集上的運行效果;②進一步測試各個方法在不同領域數據集上的有效性;③對實驗結果進行分析.

4.2 實驗結果

1) 不同規模數據集的測試結果

為了測試BiMWM和基準方法在不同規模數據集上分類匹配的有效性，在本節我們分別在DSsmall和DSwhole數據集上對這些方法進行了測試.

表1和表2分別展示了針對OAEI 2013生物醫學領域測試用例中所有的匹配問題(FMA-NCI，FMA-SNOMED，NCI-SNOMED)上，這些方法在DSsmall和DSwhole數據集上的分類匹配的準確率、召回率和F值以及這些方法的運行時間.在表1和表2中，對于每一項評價指標，效果最好的用粗體表示.

從表1和表2可以看出，不管是在DSsmall數據集還是在DSwhole數據集，BiMWM在所有匹配問題上都能獲得相對更高的準確率、召回率和F值；在運行效率方面，雖然在DSsmall和DSwhole數據集中所有匹配問題上BiMWM沒有SiGMa運行效率高，但是除了在DSsmall數據集中的FMA-SNOMED和NCI-SNOMED匹配問題上BiMWM運行效率次于IAMA外，在剩余的匹配問題上BiMWM的運行效率都優于基準方法.

Table 1 Comparison over the DSsmall Dataset

Table 2 Comparison over the DSwhole Dataset

BiMWM和基準方法在DSsmall和DSwhole數據集上整體的實驗結果如表3所示.從表3中可以發現與基準方法相比，BiMWM在所有規模的largebio數據集上都能獲得最好的準確率、召回率和F值.而且，與表現最好的YAM++方法相比，BiMWM方法分類匹配的F值在DSsmall和DSwhole數據集上分別有2.3%和3.3%的提高.不僅如此，在運行效率上，BiMWM花費的時間僅是YAM++花費時間的13，運行效率提升近2倍.盡管BiMWM的運行時間比基于貪心策略的SiGMa方法稍高，但是我們可以看到，BiMWM在DSsmall和DSwhole的largebio數據集上都獲得了超過83%的F值，大大超過基準方法SiGMa.

除此之外，從表3中我們可以發現，所有方法在“局部”測試集上的效果好于在“整體”測試集上的效果.導致這一現象最可能的原因是對于分類體系中的每一個分類來說，與較大的分類體系中的分類進行匹配時會產生更多可能的候選選擇，在這種情況下更難以在保證召回率的前提下保證較高的準確率，反之亦然.盡管如此，無論在“局部”數據集還是在“整體”數據集上，BiMWM都保持最好的準確率、召回率和F值，并且BiMWM表現相對穩定，這也證明了BiMWM方法可以很好地適應不同規模的分類體系匹配.

Table 3 Average Comparison over the DSsmall and DSwhole Datasets

2) 不同領域數據集的測試結果

在本節中，我們將評估BiMWM方法和基準方法在largebio和會議數據集上的分類體系匹配的性能.

為了比較所有方法在largebio數據集上的綜合效果，我們對這些方法在largebio數據集“局部”和“整體”片段上的結果求平均，實驗結果如表4所示：

Table 4 Comparison over the largebio Datasets

從表4中，我們可以發現BiMWM的準確率比基準方法表現最差的ServOMap提高了8%，比基準方法表現最好的YAM++提高了1.3%;同時，BiMWM的召回率比基準方法表現最差的IAMA提高了37%，比基準方法表現最好的YAM++提高了2.8%;在綜合指標F值上，BiMWM比基準方法表現最差的IAMA提高了32.8%，比基準方法表現最好的YAM++提高了2.8%.總的來說，與基準方法相比，BiMWM在largebio數據集上分類匹配的準確率、召回率和F值都最好.因此，該實驗表明BiMWM能夠在largebio數據集上比基準方法具有更好的性能.

下面，我們測試這些方法在會議數據集DSconf上的效果.由于DSconf數據集包含7個不同的本體，因此我們把這些本體組成的21個本體匹配映射任務的結果作為整體來評價這些方法的效果.在DSconf數據集上的實驗結果如表5所示：

Table 5 Comparison over the DSconf Dataset

從表5中可以看出，BiMWM的準確率比基準方法表現最差的SiGMa提高了35.2%，比基準方法表現最好的YAM++提高了3.4%；同時，BiMWM的召回率比基準方法表現最差的SiGMa提高了38.5%，比基準方法表現最好的YAM++提高了0.9%；BiMWM的F值比基準方法表現最差的SiGMa提高了38.1%，比基準方法表現最好的YAM++提高了2.1%.因此，與基準方法相比，該實驗表明BiMWM在DSconf數據集上具有更好的效果.

為了清晰地描述BiMWM和基準方法在不同領域分類體系下的性能變化，圖6展示了這些方法在largebio數據集和會議數據集上的實驗結果.

Fig. 6 Comparison over the datasets from different domains圖6 不同領域數據集上方法性能的變化

從圖6中可以看出，所有方法中除BiMWM和YAM++外，其他方法在largebio數據集和DSconf會議數據集上的性能波動比較大.雖然BiMWM和YAM++在這2個數據集上性能相對穩定，但是與YAM++相比，BiMWM在這2個數據集上都獲得了最好的準確率、召回率和F值.該實驗證明了BiMWM方法可以在不同領域的分類體系上很好地完成分類匹配任務.

基于以上實驗分析可以看出，與基準方法相比，BiMWM不僅可以在不同規模的分類體系上獲得更好的效果，而且在不同領域的分類體系上也能獲得更好的效果，這些都表明BiMWM方法的有效性，這也說明在分類體系匹配過程中采用分類的復合結構是非常有用的技術，這表明了不管分類體系的規模和所屬領域，它們在結構上具有很多共同點.

5 總 結

針對當前單一的分類體系匹配方法不適應異構、大規模的分類體系匹配的擴展性問題，本文從分類的結構特征出發，提出了一種基于復合結構的知識庫分類體系匹配方法BiMWM.該方法借助分類體系結構上的共同點，基于分類的微觀結構和宏觀結構特征，將分類體系匹配問題轉化為二部圖上的優化問題，同時利用二部圖模型建模2個分類體系之間候選匹配的類對之間的關系，最后通過執行最大權匹配算法剪枝選擇2個分類體系之間可能的候選匹配類對，產生2個分類體系之間的全局最優匹配.實驗結果證明該方法能夠有效支持大規模分類體系匹配，不僅如此，該方法在不同的分類領域和不同規模的分類體系中都表現出很好的適應性.

[1]Bollacker K, Evans C, Paritosh P, et al. Freebase: A collaboratively created graph database for structuring human knowledge[C]Proc of 2008 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2008: 1247-1250

[2]Fabian M S, Gjergji K, Gerhard W. YAGO: A core of semantic knowledge unifying WordNet and wikipedia[C]Proc of the 16th Int World Wide Web Conf. New York: ACM, 2007: 697-706

[3]Wu Wentao, Li Hongsong, Wang Haixun, et al. Probase: A probabilistic taxonomy for text understanding[C]Proc of 2012 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2012: 481-492

[4]Li Juanzi, Tang Jie, Li Yi, et al. RiMOM: A dynamic multistrategy ontology alignment framework[J]. IEEE Trans on Knowledge and Data Engineering, 2009, 21(8): 1218-1232

[5]Suchanek F M, Abiteboul S, Senellart P. PARIS: Probabilistic alignment of relations, instances, and schema[J]. The VLDB Endowment, 2011, 5(3): 157-168

[6]Lacoste-Julien S, Palla K, Davies A, et al. SiGMa: Simple greedy matching for aligning large knowledge bases[C]Proc of 2013 ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2013: 572-580

[7]Demidova E, Oelze I, Nejdl W. Aligning freebase with the YAGO ontology[C]Proc of the 22nd ACM Int Conf on Information and Knowledge Management. New York: ACM, 2013: 579-588

[8]Grau B C, Dragisic Z, Eckert K, et al. Results of the ontology alignment evaluation initiative 2013[C]Proc of the 8th ISWC Workshop on Ontology Matching. New York: ACM, 2013: 61-100

[9]Wang Yuanzhuo, Jia Yantao, Liu Dawei, et al. Open Web knowledge aided information search and data mining[J]. Journal of Computer Research and Development, 2015, 52(2): 456-474 (in Chinese)(王元卓, 賈巖濤, 劉大偉, 等. 基于開放網絡知識的信息檢索與數據挖掘[J]. 計算機研究與發展, 2015, 52(2): 456-474)

[10]Lin Hailun, Jia Yantao, Wang Yuanzhuo, et al. Populating knowledge base with collective entity mentions: A graph-based approach[C]Proc of IEEEACM Int Conf on Advances in Social Networks Analysis and Mining. Piscataway, NJ: IEEE, 2014: 604-611

[11]Zhuang Yan, Li Guoliang, Feng Jianhua. A survey on entity alignment of knowledge base[J]. Journal of Computer Research and Development, 2016, 53(1): 165-192 (in Chinese)(莊嚴, 李國良, 馮建華. 知識庫實體對齊技術綜述[J]. 計算機研究與發展, 2016, 53(1): 165-192)

[12]Shvaiko P, Euzenat J. A survey of schema-based matching approaches[J]. Journal on Data Semantics, 2005, 5: 146-171

[13]Kumar S, Singh V. Multi-strategy based matching technique for ontology integration[J]. Computational Intelligence in Data Mining, 2015, 3: 135-148

[14]Shvaiko P, Euzenat J. Ontology matching: State of the art and future challenges[J]. IEEE Trans on Knowledge and Data Engineering, 2013, 25(1): 158-176

[15]Vargas-Vera M, Nagy M. State of the art on ontology alignment[J]. International Journal of Knowledge Society Research, 2015, 6(1): 17-42

[16]Chen R C, Bau C T, Yeh C J. Merging domain ontologies based on the wordnet system and fuzzy formal concept analysis techniques[J]. Applied Soft Computing, 2011, 11(2): 1908-1923

[17]Ba M, Diallo G. Large-scale biomedical ontology matching with ServOMap[J]. IRBM, 2013, 34(1): 56-59

[18]Jiménez-Ruiz E, Grau B C. Logmap: Logic-based and scalable ontology matching[C]Proc of Int Conf on Semantic Web. Berlin: Springer, 2011: 273-288

[19]Li Chunhua, Cui Zhiming, Zhao Pengpeng, et al. Improving ontology matching with propagation strategy and user feedback[C]Proc of the 7th Int Conf on Digital Image Processing. Los Angeles: ISOP, 2015: 963127

[20]Gruber T R. A translation approach to portable ontology specifications[J]. Knowledge Acquisition, 1993, 5(2): 199-220

[21]Jia Yantao, Wang Yuanzhuo, Cheng Xueqi, et al. OpenKN: An open knowledge computational engine for network big data[C]Proc of IEEEACM Int Conf on Advances in Social Networks Analysis and Mining. Piscataway, NJ: IEEE, 2014: 657-664

[22]Resnik P. Using information content to evaluate semantic similarity in a taxonomy[C]Proc of the 14th Int Joint Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 1995: 448-453

[23]Banerjee S, Pedersen T. An adapted Lesk algorithm for word sense disambiguation using WordNet[C]Proc of Computational Linguistics and Intelligent Text Processing. Berlin: Springer, 2002: 136-145

[24]Kuhn H W. The Hungarian method for the assignment problem[J]. Naval Research Logistics Quarterly, 1955, 2(12): 83-97

Lin Hailun, born in 1987. PhD and assistant professor. Her main research interests include open knowledge network, information extraction.

Jia Yantao, born in 1983. PhD and assistant professor. His main research interests include open knowledge network, social computing, combinatorial algorithms.

Wang Yuanzhuo, born in 1978. PhD and associate professor. His main research interests include social computing, open knowledge network, network security analysis, stochastic game model, etc.

Jin Xiaolong, born in 1976. PhD, associate professor and PhD supervisor. His main research interests include social computing, multi agent systems, performance modeling and evaluation, etc.

Cheng Xueqi, born in 1971. PhD, professor and PhD supervisor. His main research interests include network science, Web search, data mining, etc.

Wang Weiping, born in 1975. PhD, professor and PhD supervisor. His main research interests include big data storage and processing.

A Composite Structure Based Method for Knowledge Base Taxonomy Matching

Lin Hailun1, Jia Yantao2, Wang Yuanzhuo2, Jin Xiaolong2, Cheng Xueqi2, and Wang Weiping1

1(InstituteofInformationEngineering,ChineseAcademyofSciences,Beijing100093)2(KeyLaboratoryofNetworkDataScienceandTechnology(InstituteofComputingTechnology,ChineseAcademyofSciences),ChineseAcademyofSciences,Beijing100190)

Taxonomy matching, i.e., an operation of taxonomy merging across different knowledge bases, which aims to align common elements between taxonomies, has been extensively studied in recent years due to its wide applications in knowledge base population and proliferation. However, with the continuous development of network big data, taxonomies are becoming larger and more complex, and covering different domains. Therefore, to pose an effective and general matching strategy covering cross-domain or large-scale taxonomies is still a considerable challenge. In this paper, we presents a composite structure based matching method, named BiMWM, which exploits the composite structure information of class in taxonomy, including not only the micro-structure but also the macro-structure. BiMWM models the taxonomy matching problem as an optimization problem on a bipartite graph. It works in two stages: it firstly creates a weighted bipartite graph to model the candidate matched classes pairs between two taxonomies, then performs a maximum weight matching algorithm to generate an optimal matching for two taxonomies in a global manner. BiMWM runs in polynomial time to generate an optimal matching for two taxonomies. Experimental results show that our method outperforms the state-of-the-art baseline methods, and performs good adaptability in different domains and scales of taxonomies.

knowledge base; taxonomy matching; composite structure; bipartite graph; maximum weight matching

2015-09-22；

2016-05-16

國家“九七三”重點基礎研究發展計劃基金項目(2012CB316303,2013CB329602)；“核高基”國家科技重大專項(2013ZX01039-002-001-001)；國家自然科學基金項目(61303056,61402464,61402442,61572469,61502478)；北京市自然科學基金項目(4154086) This work was supported by the National Basic Research Program of China (973 Program) (2012CB316303, 2013CB329602), the National Science and Technology Major Projects of Hegaoji (2013ZX01039-002-001-001), the National Natural Science Foundation of China (61303056, 61402464, 61402442, 61572469, 61502478), and the Beijing Natural Science Foundation (4154086).

王偉平(wangweiping@iie.ac.cn)

TP391

??機研究與發展

10.7544issn1000-1239.2017.20150796 Journal of Computer Research and Development54(1): 63-70， 2017