基于復(fù)合結(jié)構(gòu)的知識庫分類體系匹配方法

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

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

基于復(fù)合結(jié)構(gòu)的知識庫分類體系匹配方法

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

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

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

知識庫；分類體系匹配；復(fù)合結(jié)構(gòu)；二部圖；最大權(quán)匹配

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

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

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

1) 將異構(gòu)的分類體系轉(zhuǎn)化為以分類為中心的結(jié)構(gòu)表示，充分利用分類體系中分類之間的關(guān)系結(jié)構(gòu).這里分類的復(fù)合結(jié)構(gòu)包括分類體系中分類的微觀結(jié)構(gòu)和宏觀結(jié)構(gòu)信息.

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

2 問題定義

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

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

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

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

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

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

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

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

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

基于定義1，重點介紹基于復(fù)合結(jié)構(gòu)的分類體系匹配方法,其具體處理流程如圖1所示：

Fig. 1 Pipeline model of composite structure based taxonomy matching method圖1 基于復(fù)合結(jié)構(gòu)的分類體系匹配方法的管道模型

基于復(fù)合結(jié)構(gòu)的分類體系匹配方法主要分為3個步驟：

1) 將每個分類體系T=(VT,ET,θ,ψ)，根據(jù)頂點類型函數(shù)θ:VT→A和關(guān)系類型函數(shù)ψ:ET→R轉(zhuǎn)化為以分類為中心的結(jié)構(gòu)表示，這樣做的目的是將異構(gòu)的分類體系轉(zhuǎn)化為相同的結(jié)構(gòu)表示，以此清晰地表達(dá)分類體系中分類之間的關(guān)系結(jié)構(gòu).

圖2展示了來源于OntoFarm項目*http:nb.vse.cz～svatekontofarm.html構(gòu)建的2個學(xué)術(shù)會議本體的部分分類體系.

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

基于頂點類型函數(shù)θ:VT→A和關(guān)系類型函數(shù)ψ:ET→R對圖2所示的分類體系進(jìn)行結(jié)構(gòu)轉(zhuǎn)換，轉(zhuǎn)換之后的以分類為中心的結(jié)構(gòu)表示如圖3所示：

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

2) 基于轉(zhuǎn)換的以分類為中心的分類體系結(jié)構(gòu)，構(gòu)建二部圖模型，建模2個分類體系之間候選的匹配類對之間的關(guān)系.

3) 基于步驟2創(chuàng)建的二部圖模型，執(zhí)行最大權(quán)匹配剪枝選擇2個分類體系之間可能的候選匹配類對，產(chǎn)生分類體系最終的類對匹配結(jié)果.

下面介紹基于復(fù)合結(jié)構(gòu)的匹配方法BiMWM的原理.

3 BiMWM方法

BiMWM方法將分類體系匹配問題建模為優(yōu)化問題，即二部圖最大權(quán)匹配問題進(jìn)行求解，該方法主要包含2個部分：二部圖模型構(gòu)建算法、分類最大權(quán)匹配算法.

3.1 二部圖模型構(gòu)建算法

給定2個分類體系：T=(VT,ET,θ,ψ)和T′=(VT′,ET′,θ,ψ)，為了以統(tǒng)一的方式表示分類所有可用的信息，我們需要一種能夠?qū)Ψ诸愺w系T的所有分類C和分類體系T′的所有分類C′之間的所有復(fù)雜的關(guān)系進(jìn)行有效編碼的表示方式.為了實現(xiàn)這個目標(biāo)，我們選擇二部圖作為表示方式，這是因為二部圖能夠把來自不同分類體系的分類編碼成圖上的1個頂點，并且可以明確表示頂點之間的候選匹配關(guān)系.

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

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

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

(1)

其中，S=(str(c,c′),prop(c,c′),sem(c,c′),struct(c,c′))T是分類c和c′之間不同結(jié)構(gòu)信息的相似度向量：str(c,c′)，prop(c,c′)和sem(c,c′)是c和c′之間的微觀結(jié)構(gòu)的相似度，struct(c,c′)是c和c′之間的宏觀結(jié)構(gòu)的相似度.具體地，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是一個參數(shù)向量，用于在進(jìn)行分類匹配時平衡分類對之間的微觀結(jié)構(gòu)信息和宏觀結(jié)構(gòu)信息的重要度.

下面將詳細(xì)介紹2個分類之間微觀和宏觀結(jié)構(gòu)的相似度度量方法.

1) 微觀結(jié)構(gòu)相似度

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

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

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

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

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

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

2) 宏觀結(jié)構(gòu)相似度

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

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

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

算法1. 二部圖構(gòu)造算法.

輸入：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

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

⑤ IFw>0 THEN

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

⑦ 將權(quán)值函數(shù)W(c,c′)=w添加到W中；

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

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

⑩ END IF

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

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

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

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

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

3.2 分類最大權(quán)匹配算法

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

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

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

(2)

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

該整數(shù)線性規(guī)劃問題可以轉(zhuǎn)化為其對偶問題進(jìn)行求解：頂點覆蓋問題，即在圖G=(V,E,W)中找出具有最小規(guī)模的頂點覆蓋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，

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

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

最大權(quán)匹配算法的執(zhí)行流程如算法2所示：

算法2. 最大權(quán)匹配算法BiMWM.

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

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

① FOR ALLv∈VinGDO

② IFv∈VLTHEN

③y(v)=δ0；

④ ELSE

⑤y(v)=0；

⑥ END IF

⑦ END FOR

⑧ REPEAT

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

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

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

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

2) 查找增廣路徑并根據(jù)增廣路徑修改當(dāng)前找到的最大權(quán)匹配.執(zhí)行算法3查找一條增廣路徑(行⑨)，基于增廣路徑修正最大權(quán)匹配結(jié)果(行⑩).

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

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

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

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

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

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

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

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

增廣路徑查找算法的執(zhí)行流程如算法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上執(zhí)行BFS算法查找增廣路徑AP={(v,v′)|v∈LF,v′∈RF}，其中AP中所有的邊滿足以下約束條件：y(v)+y(v′)=W(v,v′)；

⑦ END IF

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

⑨AP=AP{s,t}；

⑩ RETURNAP.

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

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

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

4 實驗與分析

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

4.1 實驗設(shè)置

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

2) 數(shù)據(jù)集.在實驗中使用本體映射任務(wù)國際評測①(ontology alignment evaluation initiative, OAEI)中發(fā)布的2個標(biāo)準(zhǔn)數(shù)據(jù)集.

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

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

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

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

基于上述實驗設(shè)置，我們進(jìn)行：①測試各個方法在不同規(guī)模數(shù)據(jù)集上的運行效果;②進(jìn)一步測試各個方法在不同領(lǐng)域數(shù)據(jù)集上的有效性;③對實驗結(jié)果進(jìn)行分析.

4.2 實驗結(jié)果

1) 不同規(guī)模數(shù)據(jù)集的測試結(jié)果

為了測試BiMWM和基準(zhǔn)方法在不同規(guī)模數(shù)據(jù)集上分類匹配的有效性，在本節(jié)我們分別在DSsmall和DSwhole數(shù)據(jù)集上對這些方法進(jìn)行了測試.

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

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

Table 1 Comparison over the DSsmall Dataset

Table 2 Comparison over the DSwhole Dataset

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

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

Table 3 Average Comparison over the DSsmall and DSwhole Datasets

2) 不同領(lǐng)域數(shù)據(jù)集的測試結(jié)果

在本節(jié)中，我們將評估BiMWM方法和基準(zhǔn)方法在largebio和會議數(shù)據(jù)集上的分類體系匹配的性能.

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

Table 4 Comparison over the largebio Datasets

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

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

Table 5 Comparison over the DSconf Dataset

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

為了清晰地描述BiMWM和基準(zhǔn)方法在不同領(lǐng)域分類體系下的性能變化，圖6展示了這些方法在largebio數(shù)據(jù)集和會議數(shù)據(jù)集上的實驗結(jié)果.

Fig. 6 Comparison over the datasets from different domains圖6 不同領(lǐng)域數(shù)據(jù)集上方法性能的變化

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

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

5 總 結(jié)

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

[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)(王元卓, 賈巖濤, 劉大偉, 等. 基于開放網(wǎng)絡(luò)知識的信息檢索與數(shù)據(jù)挖掘[J]. 計算機研究與發(fā)展, 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)(莊嚴(yán), 李國良, 馮建華. 知識庫實體對齊技術(shù)綜述[J]. 計算機研究與發(fā)展, 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

國家“九七三”重點基礎(chǔ)研究發(fā)展計劃基金項目(2012CB316303,2013CB329602)；“核高基”國家科技重大專項(2013ZX01039-002-001-001)；國家自然科學(xué)基金項目(61303056,61402464,61402442,61572469,61502478)；北京市自然科學(xué)基金項目(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

??機研究與發(fā)展

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