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

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

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

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

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

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

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

2 問(wèn)題定義

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

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

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

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

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

基于T的定義，根據(jù)頂點(diǎn)類型函數(shù)θ:VT→A和關(guān)系類型函數(shù)ψ:ET→R，我們能夠獲得分類的復(fù)合結(jié)構(gòu).假設(shè)C=(c1,c2,…,cm)表示T中分類頂點(diǎn)集合，它用來(lái)組織和標(biāo)注演化知識(shí)網(wǎng)絡(luò)的所有知識(shí)項(xiàng).每個(gè)分類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個(gè)通過(guò)組合微觀結(jié)構(gòu)和宏觀結(jié)構(gòu)信息的五元組，也被稱為c的復(fù)合結(jié)構(gòu)：

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

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

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

基于定義1，重點(diǎn)介紹基于復(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個(gè)步驟：

1) 將每個(gè)分類體系T=(VT,ET,θ,ψ)，根據(jù)頂點(diǎn)類型函數(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展示了來(lái)源于OntoFarm項(xiàng)目*http:nb.vse.cz～svatekontofarm.html構(gòu)建的2個(gè)學(xué)術(shù)會(huì)議本體的部分分類體系.

Fig. 2 Two simple taxonomies圖2 2個(gè)簡(jiǎn)單的分類體系

基于頂點(diǎn)類型函數(shù)θ:VT→A和關(guān)系類型函數(shù)ψ:ET→R對(duì)圖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個(gè)分類體系之間候選的匹配類對(duì)之間的關(guān)系.

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

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

3 BiMWM方法

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

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

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

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

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

給定1個(gè)分類對(duì)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′的語(yǔ)義相似度，而struct(c,c′)則表示分類c和c′之間周圍鄰居的相似度.Θ=(θ1,θ2,θ3,θ4)T是一個(gè)參數(shù)向量，用于在進(jìn)行分類匹配時(shí)平衡分類對(duì)之間的微觀結(jié)構(gòu)信息和宏觀結(jié)構(gòu)信息的重要度.

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

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

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

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

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

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

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

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

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

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

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

基于上述分類之間相似度計(jì)算方式的定義，給定分類體系T=(VT,ET,θ,ψ)和T′=(VT′,ET′,θ,ψ)，為了構(gòu)造表示這2個(gè)分類體系中分類匹配關(guān)系的二部圖模型，我們首先將T中包含的所有分類作為二部圖的左部頂點(diǎn)，T′中包含的分類作為二部圖的右部頂點(diǎn)，然后在這些頂點(diǎn)之間利用式(1)計(jì)算左部頂點(diǎn)與右部頂點(diǎn)之間匹配的可能性；接下來(lái)為左部頂點(diǎn)和右部頂點(diǎn)之間分配連邊信息并為連邊分配權(quán)重，從而生成T和T′之間的無(wú)向加權(quán)二部圖G=(V,E,W).其中，在二部圖G=(V,E,W)構(gòu)造過(guò)程中，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)計(jì)算分類c和c′等價(jià)匹配的可能性w；

⑤ IFw>0 THEN

⑥ 將分類c和c′添加到頂點(diǎn)集合V中；

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

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

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

⑩ END IF

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

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

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

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

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

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

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

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

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

(2)

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

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

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

(3)

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

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

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

⑩ 擴(kuò)展匹配M:M=M⊕AP；

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

1) 初始化對(duì)偶變量.使用對(duì)偶變量增廣值δ的初始值δ0初始化對(duì)偶變量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中每一個(gè)左部未匹配的頂點(diǎn)LF和右部未匹配的頂點(diǎn)RF之間添加LF→RF方向的連邊；對(duì)最大權(quán)匹配M中屬于右部的匹配頂點(diǎn)MR=VRRF和屬于左部的匹配頂點(diǎn)ML=VLLF之間添加MR→ML的連邊.

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

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

Fig. 5 Extended bipartite graph圖5 擴(kuò)展的二部圖模型

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

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

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

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

輸出：增廣路徑AP.

① IFLF=? ORRF=? THEN

②AP=?；

③ ELSE

④ 在未匹配的頂點(diǎn)對(duì)之間添加從VL→VR的有向邊，在匹配的頂點(diǎn)對(duì)之間添加從VR→VL的有向邊；

⑤ 添加源頂點(diǎn)s和匯聚頂點(diǎn)t，并分別在它們與每一個(gè)左部自由頂點(diǎn)vL∈LF和右部自由頂點(diǎn)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更新自由頂點(diǎn)集合LF=LFAP，RF=RFAP；

⑨AP=AP{s,t}；

⑩ RETURNAP.

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

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

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

4 實(shí)驗(yàn)與分析

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

4.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

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

4.2 實(shí)驗(yàn)結(jié)果

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

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

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

從表1和表2可以看出，不管是在DSsmall數(shù)據(jù)集還是在DSwhole數(shù)據(jù)集，BiMWM在所有匹配問(wèn)題上都能獲得相對(duì)更高的準(zhǔn)確率、召回率和F值；在運(yùn)行效率方面，雖然在DSsmall和DSwhole數(shù)據(jù)集中所有匹配問(wèn)題上BiMWM沒(méi)有SiGMa運(yùn)行效率高，但是除了在DSsmall數(shù)據(jù)集中的FMA-SNOMED和NCI-SNOMED匹配問(wèn)題上BiMWM運(yùn)行效率次于IAMA外，在剩余的匹配問(wèn)題上BiMWM的運(yùn)行效率都優(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ù)集上整體的實(shí)驗(yàn)結(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%的提高.不僅如此，在運(yùn)行效率上，BiMWM花費(fèi)的時(shí)間僅是YAM++花費(fèi)時(shí)間的13，運(yùn)行效率提升近2倍.盡管BiMWM的運(yùn)行時(shí)間比基于貪心策略的SiGMa方法稍高，但是我們可以看到，BiMWM在DSsmall和DSwhole的largebio數(shù)據(jù)集上都獲得了超過(guò)83%的F值，大大超過(guò)基準(zhǔn)方法SiGMa.

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

Table 3 Average Comparison over the DSsmall and DSwhole Datasets

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

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

為了比較所有方法在largebio數(shù)據(jù)集上的綜合效果，我們對(duì)這些方法在largebio數(shù)據(jù)集“局部”和“整體”片段上的結(jié)果求平均，實(shí)驗(yàn)結(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%;同時(shí)，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%.總的來(lái)說(shuō)，與基準(zhǔn)方法相比，BiMWM在largebio數(shù)據(jù)集上分類匹配的準(zhǔn)確率、召回率和F值都最好.因此，該實(shí)驗(yàn)表明BiMWM能夠在largebio數(shù)據(jù)集上比基準(zhǔn)方法具有更好的性能.

下面，我們測(cè)試這些方法在會(huì)議數(shù)據(jù)集DSconf上的效果.由于DSconf數(shù)據(jù)集包含7個(gè)不同的本體，因此我們把這些本體組成的21個(gè)本體匹配映射任務(wù)的結(jié)果作為整體來(lái)評(píng)價(jià)這些方法的效果.在DSconf數(shù)據(jù)集上的實(shí)驗(yàn)結(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%；同時(shí)，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)方法相比，該實(shí)驗(yàn)表明BiMWM在DSconf數(shù)據(jù)集上具有更好的效果.

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

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

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

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

5 總 結(jié)

針對(duì)當(dāng)前單一的分類體系匹配方法不適應(yīng)異構(gòu)、大規(guī)模的分類體系匹配的擴(kuò)展性問(wèn)題，本文從分類的結(jié)構(gòu)特征出發(fā)，提出了一種基于復(fù)合結(jié)構(gòu)的知識(shí)庫(kù)分類體系匹配方法BiMWM.該方法借助分類體系結(jié)構(gòu)上的共同點(diǎn)，基于分類的微觀結(jié)構(gòu)和宏觀結(jié)構(gòu)特征，將分類體系匹配問(wèn)題轉(zhuǎn)化為二部圖上的優(yōu)化問(wèn)題，同時(shí)利用二部圖模型建模2個(gè)分類體系之間候選匹配的類對(duì)之間的關(guān)系，最后通過(guò)執(zhí)行最大權(quán)匹配算法剪枝選擇2個(gè)分類體系之間可能的候選匹配類對(duì)，產(chǎn)生2個(gè)分類體系之間的全局最優(yōu)匹配.實(shí)驗(yàn)結(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)(王元卓, 賈巖濤, 劉大偉, 等. 基于開(kāi)放網(wǎng)絡(luò)知識(shí)的信息檢索與數(shù)據(jù)挖掘[J]. 計(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), 李國(guó)良, 馮建華. 知識(shí)庫(kù)實(shí)體對(duì)齊技術(shù)綜述[J]. 計(jì)算機(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

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

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

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