基于數(shù)據(jù)場和全局序列比對的大規(guī)模中文關(guān)聯(lián)數(shù)據(jù)模型

王汀，徐天晟，冀付軍

(首都經(jīng)濟(jì)貿(mào)易大學(xué) 信息學(xué)院，北京 100070)

基于數(shù)據(jù)場和全局序列比對的大規(guī)模中文關(guān)聯(lián)數(shù)據(jù)模型

王汀，徐天晟，冀付軍

(首都經(jīng)濟(jì)貿(mào)易大學(xué) 信息學(xué)院，北京 100070)

目前關(guān)聯(lián)數(shù)據(jù)的研究工作主要集中在實(shí)例級別上展開，而在模式級別(Schema-Level)上的關(guān)聯(lián)數(shù)據(jù)構(gòu)建則易被忽視。本體映射是解決本體異構(gòu)問題的重要途徑和手段，同時(shí)，本體映射也可視為模式級別關(guān)聯(lián)數(shù)據(jù)構(gòu)建的典型情景。特別是在中文知識庫方面，中文知識是關(guān)聯(lián)數(shù)據(jù)網(wǎng)中的重要組成部分，但現(xiàn)有的中文本體映射系統(tǒng)在面對大規(guī)模本體映射任務(wù)時(shí)，顯得效率較低且可用性不高，目前仍缺乏針對中文大規(guī)模本體映射的相關(guān)系統(tǒng)。為了解決在模式級別上的中文大規(guī)模關(guān)聯(lián)數(shù)據(jù)構(gòu)建問題，提出了一種新的基于數(shù)據(jù)場和序列比對思想的大規(guī)模中文關(guān)聯(lián)數(shù)據(jù)構(gòu)建模型。首先，基于改進(jìn)的融合概念相似度和相異度的擬核力場勢函數(shù)對大規(guī)模中文本體映射規(guī)模進(jìn)行約簡和壓縮；其次，通過引入序列比對算法，對組合概念進(jìn)行相似度的度量；最后，將本系統(tǒng)與相似度計(jì)算相關(guān)典型算法進(jìn)行比較，表明其具備一定的可用性和較高的總體性能。

語義網(wǎng);關(guān)聯(lián)數(shù)據(jù);本體映射;同義詞詞林;相似度計(jì)算

1 引言

語義Web的愿景是建立“數(shù)據(jù)之網(wǎng)”(Web of Data)，以使機(jī)器能夠理解網(wǎng)絡(luò)上的語義信息[1]。本體作為語義Web的核心元素，是描述特定領(lǐng)域共享概念的形式化、規(guī)范化說明[2]，是實(shí)現(xiàn)網(wǎng)絡(luò)知識共享和語義互操作的基礎(chǔ)。目前關(guān)聯(lián)數(shù)據(jù)(Linked Open Data，LOD)[3]的研究工作主要集中在面向?qū)嵗墑e(Level of Instances)上展開，而面向本體模式(Schema-Level)的關(guān)聯(lián)數(shù)據(jù)構(gòu)建研究亦很重要[4]。同時(shí)，由于不同本體之間存在異構(gòu)性，從而導(dǎo)致本體間的重用和共享變得困難。

本體映射(Ontology Alignment)作為模式級關(guān)聯(lián)數(shù)據(jù)構(gòu)建的典型場景已被廣泛研究，其任務(wù)就是要發(fā)現(xiàn)異構(gòu)本體或數(shù)據(jù)源(LOD Datasets)之間的概念語義關(guān)聯(lián)。隨著語義網(wǎng)的發(fā)展，大規(guī)模中文本體和知識庫也被越來越多地構(gòu)建和發(fā)布到Web上。然而，中文關(guān)聯(lián)數(shù)據(jù)網(wǎng)的構(gòu)建卻尚處于起步階段，目前更缺乏成熟的針對本體模式的中文關(guān)聯(lián)數(shù)據(jù)模型。因此，本文主要探討大規(guī)模中文關(guān)聯(lián)數(shù)據(jù)環(huán)境下的本體映射解決方案。

2 相關(guān)工作

國內(nèi)外研究人員已提出多種映射方法和典型系統(tǒng)。文獻(xiàn)[5]中總結(jié)了基于編輯距離和基于Token的幾種典型元素級相似度計(jì)算算法，并對幾種算法的性能進(jìn)行了評測。Melnik S等提出一種結(jié)構(gòu)級本體映射算法Similarity Flooding，該系統(tǒng)利用本體概念體系構(gòu)造相似度傳播圖，并對概念之間的相似度進(jìn)行傳播和修正[6]。Zhong Qian等提出RiMOM系統(tǒng)，該系統(tǒng)基于本體實(shí)例、概念名稱以及本體結(jié)構(gòu)等特征的多策略映射方式，并通過引入普適的場論思想，使其適用于大規(guī)模本體的映射任務(wù)[7]。Giunchiglia F等基于語言學(xué)方法，引入共享知識詞典(如: WordNet[8])，利用語言關(guān)系進(jìn)行語義關(guān)系發(fā)現(xiàn)[9]。文獻(xiàn)[10]提出一種實(shí)例級本體映射算法，根據(jù)本體概念的公共實(shí)例數(shù)量來度量概念的相似度。

近年來，大規(guī)模中文本體庫和關(guān)聯(lián)數(shù)據(jù)構(gòu)建的研究工作正逐步展開。李佳等提出一種基于知網(wǎng)(Hownet)[11]的元素層概念相似度算法，并實(shí)現(xiàn)了一個(gè)中文本體映射系統(tǒng)[12]，該系統(tǒng)在面對大規(guī)模本體映射任務(wù)時(shí)，其適用性有待驗(yàn)證。田久樂等提出一種基于同義詞詞林的中文詞語語義相似度計(jì)算算法[13]，但其成果并未在語義網(wǎng)環(huán)境下應(yīng)用。Wang Zhi-chun等學(xué)者[14]提出基于中文百科的分類體系抽取概念間的層次關(guān)系、獲取含有Infobox的詞條Web頁面中的概念屬性及百科詞條實(shí)例，最終建立起基于百度百科和互動百科的兩大中文大規(guī)模本體庫，并根據(jù)簡單的關(guān)鍵字匹配策略，與DBpedia建立起實(shí)例間的共指關(guān)系。Niu Xing等研究人員將百度百科*http://baike.baidu.com/、互動百科*http://www.hudong.com/以及中文維基百科[15]進(jìn)行語義集成，并開發(fā)出基于中文描述的實(shí)例級關(guān)聯(lián)數(shù)據(jù)應(yīng)用系統(tǒng)[16]。王汀等基于同義詞詞林相似度算法和改進(jìn)的擬核力場勢函數(shù)，設(shè)計(jì)并實(shí)現(xiàn)了一種中文大規(guī)模本體映射系統(tǒng)[17]。Yidong Chen等提出利用中文百科Infobox中的屬性-值對信息，自動提取良構(gòu)的訓(xùn)練樣本，進(jìn)而基于統(tǒng)計(jì)學(xué)習(xí)模型從百科的非結(jié)構(gòu)化文本中抽取海量的知識三元組，最終構(gòu)建了一個(gè)面向開放域的中文知識庫[18]。

3 問題定義

簡單詞元與未登錄詞都對應(yīng)于本體概念。本文將簡單詞元稱為原子概念(Atom Concept，AC)，將未登錄詞稱為組合概念(Component Concept，CC)，并約定組合概念由若干個(gè)原子概念的線性排列組合而成。下面給出問題的定義:

定義1 本體映射: 兩個(gè)待映射本體Os、Ot，對于Os中的概念Cs，在Ot中找到與其語義相同或接近的概念Ct，有映射函數(shù)map:Os→Ot:

對于?Cs∈Os，?Ct∈Ot，若sim(Cs，Ct)>t; 則有map(Cs)=Ct

sim(Cs，Ct)為Cs和Ct的相似度，t是閾值，當(dāng)Cs與Ct的語義相似度大于t時(shí)，則將作為等價(jià)概念映射對。

定義2 對于《同義詞詞林》語義知識庫(Semantic Knowledge Base，SKB)，顯然集合SKBTYCCL由原子概念組成，即有SKBTYCCL={AC1，AC2，…，ACN}。N為知識庫中所收錄的詞元總數(shù)。

定義3 組合概念CCi由一系列原子概念的有序排列構(gòu)成。即: 對于?ACi∈SKBTYCCL，引入二維下標(biāo)i和j，則有有序序列CCi=[ACi1，ACi2，…，ACij]，其中j≥1且CCi?SKBTYCCL，j為原子概念A(yù)Ci在有序序列CCi中的排列位置。特別地，對于所有的原子概念A(yù)Ci，可以有ACi=[ACi]。

定義4 對于本體Os和Ot中的概念Cs和Ct，有Cs=CCs=[ACs1，ACs2，…，ACsm]，Ct=CCt=[ACtn，ACt2，…，ACtn]。m和n分別為概念Cs和Ct所對應(yīng)的有序序列CCs和CCt的長度，則有m，n≥1。

4 中文大規(guī)模本體映射系統(tǒng)

主要由以下模塊組成: 概念初始關(guān)聯(lián)度計(jì)算、本體壓縮和確定性映射。

4.1 基于編輯距離和同義詞詞林相融合的概念初始關(guān)聯(lián)度計(jì)算

4.1.1 編輯距離相似度

在面對大規(guī)模本體的映射任務(wù)時(shí)，首先對待映射本體進(jìn)行壓縮。由于在進(jìn)行初始關(guān)聯(lián)度計(jì)算時(shí)優(yōu)先考慮算法的高效性本系統(tǒng)，因此采用編輯距離算法首先進(jìn)行概念集合之間的初始相似度計(jì)算。在獲得待映射本體的初始關(guān)聯(lián)度時(shí)，通過編輯距離算法SIME可以獲取概念之間的字面相似性，而忽略其語義相關(guān)性。對于概念Cs和Ct的編輯距離和相似度值由公式(1)和公式(2)給出。

(1)

其中，|Do(Cs，Ct)|為Cs和Ct的編輯操作次數(shù)，L(Cs)和L(Ct)為概念的字符長度。

(2)

4.1.2 同義詞詞林相似度

同義詞詞林(Tongyici Cilin，TYCCL)是一個(gè)中文同義詞典，它將每個(gè)詞匯進(jìn)行編碼并以層次關(guān)系組織在一個(gè)樹狀結(jié)構(gòu)中，自頂向下共有五層。每個(gè)層次都有相應(yīng)的編碼標(biāo)識，五層的編碼從左至右依次排列起來，構(gòu)成詞元的詞林編碼。樹中的每個(gè)結(jié)點(diǎn)代表一個(gè)概念，詞語與詞語之間隱含的語義相關(guān)

度也隨著層次的增加而提高。中文的概念共指關(guān)系識別實(shí)際上可以抽象為中文同義詞的識別問題。本系統(tǒng)采用哈爾賓工業(yè)大學(xué)同義詞詞林(擴(kuò)展版)*http://ir.hit.edu.cn/demo/ltp/Sharing_Plan.htm作為本體映射的常識知識庫:SKBTYCCL。

以詞元“物質(zhì)”為例(詞林編碼為: Ba01A02=)，對詞林編碼格式進(jìn)行解釋，如表1所示。

根據(jù)詞林的結(jié)構(gòu)特點(diǎn)，首先對概念的詞林編碼進(jìn)行解析，抽取出第一至第五層子編碼，再從第一層子編碼開始比較。若出現(xiàn)子編碼不同，則根據(jù)出現(xiàn)的層次來賦予該映射對相應(yīng)的相似度權(quán)重。子編碼不同出現(xiàn)在越深的層次，則相似度權(quán)重越高，反之則越低。同時(shí)，每層的分支節(jié)點(diǎn)數(shù)的多少也對相似度有影響。在文獻(xiàn)[13]的基礎(chǔ)上，我們提出改進(jìn)的本體概念相似度計(jì)算公式，如式(3)所示。

(3)

由于本體映射更關(guān)注概念之間的語義相似性，因此引入調(diào)節(jié)參數(shù)語義相關(guān)度因子λ，通過λ來調(diào)節(jié)不同層級概念間語義相關(guān)性和語義相似性的關(guān)系，以及控制處于不同層次分支的詞元之間可能相似的程度，顯然λ∈(0，1)。λ的值越大，表示不同層次之間的詞元相似或等價(jià)的可能性越大，且不同層次的語義相關(guān)性對于最終概念相似度的影響越大，反之則越小。

由于中文本體映射更關(guān)注概念的語義相似度，因此λ的取值不宜過高。

其中，L={1，2，3，4，5}，對于?Li∈L，Li為第i層所代表的層數(shù)，|L|為集合L中的元素個(gè)數(shù)，在本系統(tǒng)中恒等于5。概念相似度權(quán)重系數(shù)為λ×(Li/|L|)。NT為詞元Cs和Ct在第i層分支上的節(jié)點(diǎn)總數(shù)，D為詞元Cs和Ct的編碼距離。

特別是當(dāng)待映射概念對的五層編碼均相等，且詞林編碼最后一位為“=”號，則相似度值為1.0。顯然，SIMT的值域?yàn)?0，1]。本系統(tǒng)將語義相關(guān)度因子設(shè)定為λ=0.9。

4.1.3 多策略融合關(guān)聯(lián)度算法

由于SIME算法與SIMT算法具有語義互補(bǔ)性，因此本系統(tǒng)將兩種算法的相似度結(jié)果進(jìn)行互補(bǔ)融合，取兩種算法結(jié)果的最大值。

算法一同時(shí)考慮兩個(gè)概念Cs和Ct之間的相似度和相異度，并將其疊加進(jìn)入每個(gè)概念Cs、Ct的最終關(guān)聯(lián)度。定義兩種相似度算法得到的最大值為ρ，ρ∈(0，1]，則有公式(4)。

(4)

概念Cs和Ct之間的語義相關(guān)系數(shù)為λst，式(5)中的1-ρst用來度量兩個(gè)概念Cs和Ct之間的相異度。-log(1-ρst)是以10為底的對數(shù)。本系統(tǒng)將其定義為嚴(yán)格單調(diào)遞增函數(shù)，這樣可以使相異度對相似度的變化趨勢能夠平穩(wěn)地反映二者之間的因果關(guān)系。相似度ρst的值越大，相異度越小，則調(diào)節(jié)函數(shù)-ρst×log(1-ρst)的值越大。初始關(guān)聯(lián)度ms綜合考慮了源本體和目標(biāo)本體概念之間的相似度和相異

算法一 InterlinkingValue(Os ，Ot)

度，從而使結(jié)果更加合理。為使式(5)收斂，規(guī)定ρ值屬于區(qū)間(0.9，1]時(shí)，Cs和Ct之間的語義相關(guān)因子λst為1。

(5)

最終得到源本體概念Cs與目標(biāo)本體Ot的初始關(guān)聯(lián)度ms，見公式(6)。目標(biāo)本體Ot的概念總數(shù)為n。

(6)

由關(guān)聯(lián)度計(jì)算的對稱性，目標(biāo)本體的概念Ct的初始關(guān)聯(lián)度mt同理可得。為使關(guān)聯(lián)度的轉(zhuǎn)移具有連續(xù)性，規(guī)定: 當(dāng)某概念最終的初始關(guān)聯(lián)度值為0時(shí)，則賦予其固定值為0.04。

4.2 大規(guī)模本體壓縮算法

在面對大規(guī)模的本體映射任務(wù)時(shí)，傳統(tǒng)的算法無論在時(shí)間還是空間復(fù)雜度方面都難以適應(yīng)，因此需要相應(yīng)的策略來對原本的待映射的本體進(jìn)行壓縮。

數(shù)據(jù)場理論[19]的提出是基于物理學(xué)中的場論思想，將數(shù)域空間中數(shù)據(jù)之間的相互關(guān)系抽象為物質(zhì)粒子之間的相互作用問題，最終形式化為場論的描述方法。該理論通過勢函數(shù)來表達(dá)不同數(shù)據(jù)間的相互作用關(guān)系，從而體現(xiàn)出數(shù)據(jù)的分布特征，并根據(jù)數(shù)據(jù)場中的等勢線結(jié)構(gòu)來對數(shù)據(jù)集進(jìn)行聚類劃分。但是，經(jīng)典數(shù)據(jù)場所采用的短程場勢函數(shù)往往只考慮了數(shù)據(jù)對象之間的路徑距離對最終勢值的影響，在面對本體映射問題時(shí)，就體現(xiàn)為忽視了數(shù)據(jù)對象間普遍存在的語義關(guān)聯(lián)因素，例如，擬核力場勢函數(shù)。擬核力場勢函數(shù)只考慮數(shù)據(jù)場中對象之間的斥力，而忽視了對象間存在引力的現(xiàn)象。

本系統(tǒng)提出一種通過綜合計(jì)算概念間的語義相似度和相異度來衡量數(shù)據(jù)對象勢值的新方法，將Os和Ot中的概念間普遍存在的語義關(guān)聯(lián)視為本體壓縮的基礎(chǔ)和前提，將本體概念視為數(shù)據(jù)場中的數(shù)據(jù)對象，將概念間的初始關(guān)聯(lián)度視為數(shù)據(jù)對象的質(zhì)量。通過引入本體中概念之間普遍存在的語義關(guān)聯(lián)度因子，修正了擬核力場勢函數(shù)在面對本體映射問題時(shí)的不足，使其在宏觀上符合關(guān)聯(lián)數(shù)據(jù)構(gòu)建的特征。

4.2.1 勢函數(shù)的定義

由于短程場能更好地反映出數(shù)據(jù)之間的相互作用情況，因此采用擬核力場勢函數(shù)。其在本體映射問題中的具體定義如下。

待映射本體O中，概念之間的最短路徑長度為||Ci-Cj||，由短程場的特性，定義概念之間的路徑長度不大于2?；跀?shù)據(jù)場理論可得概念Ci與Cj之間相互作用的場強(qiáng)函數(shù)表達(dá)式，如公式(7)所示。

(7)

其中，mi代表每個(gè)數(shù)據(jù)點(diǎn)的質(zhì)量，一般令mi=1，但是這種做法只能反映概念之間的路徑距離對最終勢值的影響，卻使得概念之間的語義關(guān)聯(lián)度完全缺失。本研究提出將概念之間的語義相似性和相異性引入勢值計(jì)算，將mi的值定義為概念之間的初始關(guān)聯(lián)度，mi值已由4.1.3節(jié)的公式(6)給出。通過將概念之間的相似度和相異度進(jìn)行綜合考慮，對公式(7)中的場強(qiáng)函數(shù)進(jìn)行改進(jìn)與完善。公式(6)證明，待映射本體中概念的初始關(guān)聯(lián)度越大，則其在數(shù)據(jù)場中的質(zhì)量越大。

本體概念集C={C1，C2，…，Cn}中，用Ci的初始關(guān)聯(lián)度值mi來刻畫本體中的每個(gè)概念對于其他概念的影響程度，即:M={m1，m2，…，mn}。經(jīng)過修正的場強(qiáng)函數(shù)如公式(8)所示。

(8)

δ∈(0，+∞)反映概念之間影響的粒度，也稱為縮放因子，不妨取δ=1，k=2。可得本體O中Ci的勢值函數(shù)，如公式(9)所示。

(9)

最終得到本體O中全部概念的勢值集合potentialMap_Os和potentialMap_Ot，記為:potentialMap_O

4.2.2 候選概念的抽取

將O中的概念集劃分為候選區(qū)間和淘汰區(qū)間。具體地，對于算法一的輸出數(shù)據(jù)結(jié)構(gòu)Map_Ot和Map_Os，根據(jù)每個(gè)概念元素的關(guān)聯(lián)度值統(tǒng)計(jì)出Map_Ot和Map_Os中關(guān)聯(lián)度值等于0.04的概念總數(shù)，記為Range_Out，該變量為淘汰區(qū)間長度。而將Map_Ot和Map_Os中關(guān)聯(lián)度值大于0.04的概念總數(shù)記為Range_Candidate，該變量為候選區(qū)間長度。

將potentialMap_Ot和potentialMap_Os中的概念以鍵值降序排序，對于?Ci∈potentialMap_O，其排名記為Ranki。若Ranki∈ [1，Range_Candidate]，則保留Ci作為候選待映射概念。若Ranki∈ [Range_Candidate+1，Range_Candidate+Range_Out]，則Ci被淘汰。

4.3 基于Needleman-Wunsch算法的概念確定性映射

對于Os和Ot中的任意兩個(gè)概念Cs和Ct，在進(jìn)行語義相似度計(jì)算時(shí)有三種情況:

①Cs和Ct均為原子概念，即:Cs∈SKBTYCCL且Ct∈SKBTYCCL；

②Cs和Ct的其中之一為原子概念，而另一個(gè)為組合概念，即:Cs?SKBTYCCL或Ct?SKBTYCCL；

③Cs和Ct均為組合概念，即:Cs?SKBTYCCL且Ct?SKBTYCCL；

對于情況①，采用4.1.2節(jié)給出的公式(3)計(jì)算語義相似度。下面討論情況②和情況③的相似度計(jì)算方法。

對于中文組合概念的相似度計(jì)算，許多學(xué)者給出了處理方案。例如，李佳等采用公式(10)對未登錄詞進(jìn)行相似度計(jì)算。

(10)

其中，Bxy表示分別以兩個(gè)詞匯拆分后得到的簡單詞匯為行列組成的相似度矩陣的元素，maxi(Bxy)表示矩陣中數(shù)值排列為第i位的相似度。但是，該方法忽視了中文自然語言中普遍存在的語序敏感現(xiàn)象和“前輕后重”的特點(diǎn)，因此其必然帶來語義相似度計(jì)算的誤差。

例1 兩個(gè)組合概念: “歷史理論”和“思想史”，經(jīng)過分詞處理后得到兩個(gè)由原子概念構(gòu)成的有序排列: [歷史，理論]和[思想，史]。采用前人普遍的處理未登錄詞方法則會得到如圖1(a)所示的原子概念錯(cuò)誤映射結(jié)果。

圖 1

因此，本文提出一種新的基于全局雙序列比對算法的概念語義相似度計(jì)算方法。

4.3.1 序列比對(alignment)算法概述

生物信息學(xué)中的雙序列比對一般是指將兩條DNA序列排列在一起并標(biāo)明其相似處，序列中可以插入空位符，相同或相似的符號排在同一列上。通過比較兩個(gè)序列的相似片斷和保守性位點(diǎn)，尋找其可能存在的分子進(jìn)化關(guān)系。

Needleman-Wunsch(NW)算法是典型的全局比對算法，其適用于比較全局宏觀上相似程度較高的兩個(gè)序列[20]。它是一種比對兩條序列之間相似性的動態(tài)規(guī)劃算法(Dynamic Programming，DP)。

4.3.2 構(gòu)造動態(tài)規(guī)劃打分矩陣

所謂序列是指由一系列字母標(biāo)識，根據(jù)一定的排列規(guī)則所組成的字符串。本文將組合概念視為詞串序列，序列中的各個(gè)元素即為原子概念。首先將組合概念進(jìn)行分詞處理，得到其對應(yīng)的詞串序列；本系統(tǒng)中采用中國科學(xué)院計(jì)算技術(shù)研究所研發(fā)的ICTCLAS 50* http://ictclas.org/作為分詞工具。然后將本體映射的概念相似度計(jì)算抽象為兩個(gè)詞串序列的比對過程: 通過空位罰分函數(shù)，確定在詞串序列中的相應(yīng)位置插入空位符，使得兩個(gè)序列長度相同，進(jìn)而得到待比對序列的原子概念之間或原子概念與空位符的對應(yīng)關(guān)系。

本文將待比對的兩個(gè)詞串序列以打分矩陣(scoring matrix)的形式表示，兩條序列分別作為動態(tài)規(guī)劃矩陣的兩維。對于Cs和Ct，打分矩陣M的第i行對應(yīng)詞串序列CCs中的原子概念A(yù)Csi，第j列對應(yīng)詞串序列CCt中的原子概念A(yù)Ctj，其中i≤m，j≤n。動態(tài)規(guī)劃矩陣M中第i行第j列元素稱為Mij。

例2 組合概念“第二次工業(yè)革命”和“第二次世界大戰(zhàn)戰(zhàn)犯”經(jīng)過分詞處理后，得到兩個(gè)待比對詞串序列: [第二，次，工業(yè)革命]和[第二，次，世界大戰(zhàn)，戰(zhàn)犯]。根據(jù)動態(tài)規(guī)劃思想，將兩個(gè)詞串序列以行和列來表示。假設(shè)序列CCs的長度為m，序列CCt的長度為n，則可形成一個(gè)以序列CCs為行，序列CCt為列的(m+1)×(n+1)的二維矩陣，如圖3所示。同理可得例一的打分矩陣，如圖2所示。

圖2 例1的打分矩陣

圖3 例2的打分矩陣

4.2.3 最優(yōu)化的遞歸求解算法

基于NW算法對矩陣M中的最優(yōu)比對路徑進(jìn)行遞歸求解。首先，給出序列比對算法的懲罰因子p=-0.05，并分別對矩陣的第m+1行與第n+1列進(jìn)行初始化；其次，基于計(jì)算函數(shù)SIMT，對矩陣中其余m×n個(gè)元素進(jìn)行遞歸求解。先給出記分函數(shù)f的定義，如公式(11)所示。

(11)

考慮到中文詞匯普遍存在“前輕后重”的特點(diǎn)，因此將遞歸的起點(diǎn)選定為兩個(gè)組合概念的結(jié)尾處，即矩陣中的Mmn元素。最后，從矩陣中的Mmn元素開始，回溯至矩陣中的M11元素結(jié)束，可得最優(yōu)比對路徑。如果得到的最優(yōu)比對路徑不止一條，則任選其一。遞歸規(guī)則如公式(12)所示。

(12)

圖4 例二的序列匹配結(jié)果

(13)

5 實(shí)驗(yàn)結(jié)果及分析

5.1 實(shí)驗(yàn)數(shù)據(jù)

本文采用中文網(wǎng)絡(luò)開放百科知識庫作為實(shí)驗(yàn)數(shù)據(jù)源。除DBpedia(中文版)知識庫以外，本系統(tǒng)基于文獻(xiàn)[14-21]提出的方法，使用爬蟲工具包HTMLParser，分別對百度百科和互動百科的開放分類頁面和詞條頁面所包含的Infobox結(jié)構(gòu)化信息進(jìn)行爬取和解析，并將其以中文三元組(Triple)的形式組織起來，形成待映射的大規(guī)模中文開放域知識庫。如表2所示，百科開放分類體系主要構(gòu)成本體的概念體系。

表2 中文網(wǎng)絡(luò)百科知識庫信息

5.2 評價(jià)指標(biāo)

本文采用對等價(jià)關(guān)系識別的查準(zhǔn)率(Precision)、查全率(Recall)和F-measure作為評價(jià)標(biāo)準(zhǔn)。其中:

Precision(P)=輸出的正確映射對數(shù)/輸出的映射對總數(shù)×100%

Recall(R)=輸出的正確映射對數(shù)/標(biāo)準(zhǔn)結(jié)果中的映射對總數(shù)×100%

F-measure(F1)=2×P×R/(P+R)×100%

選取三大中文網(wǎng)絡(luò)百科本體概念集中的頂層分類: 人物、科學(xué)、社會、地理和藝術(shù)子類中的正確映射對作為評價(jià)算法效率的參考映射，如表3所示。

表3 三大中文百科本體映射任務(wù)參考映射統(tǒng)計(jì)

5.3 實(shí)驗(yàn)結(jié)果5.3.1 實(shí)驗(yàn)一: 大規(guī)模中文本體壓縮

基于提出的綜合計(jì)算概念間的語義相似度和相異度擬核力場勢函數(shù)，首先對大規(guī)模本體進(jìn)行了映射規(guī)模的壓縮。在不同語義環(huán)境下可以獲得的壓縮效果如表4所示。其中，壓縮率(%) = (壓縮前本體規(guī)模 -壓縮后本體規(guī)模) /壓縮前本體規(guī)模。

表4 大規(guī)模本體映射規(guī)模壓縮效果

可以看出，當(dāng)兩個(gè)本體之間的原始規(guī)模相差較大時(shí)，相對較小規(guī)模的本體壓縮率也較小，而較大規(guī)模的本體則更易獲得較高的壓縮率。在這種情況下，待映射本體所獲得的壓縮率相差較大。而當(dāng)本體之間的原始規(guī)模趨近時(shí)，二者所獲得的壓縮率也趨同。由此可見，基于修正的擬核力場勢函數(shù)可以獲得較好的聚類效果，在進(jìn)行確定性映射前，可以有效控制和約簡大規(guī)模本體映射任務(wù)的時(shí)間和空間復(fù)雜度。

5.3.2 實(shí)驗(yàn)二: 大規(guī)模中文本體映射結(jié)果評測

三個(gè)映射任務(wù)的評測結(jié)果如表5所示，第一種算法為跨語言可通用的編輯距離相似度算法[22]；第二種為田久樂等提出的基于同義詞詞林的中文詞語相似度算法[13]；第三種方法為本文提出的中文概念綜合相似度算法。

為了保證公平性，將判定概念等價(jià)關(guān)系的相似度閾值統(tǒng)一設(shè)定為t=0.9。

表5 三種典型相似度算法的評測結(jié)果

由表5可知，本系統(tǒng)在Baidu-Hudong映射任務(wù)的查準(zhǔn)率與編輯距離相似度算法基本持平，同時(shí)查準(zhǔn)率也明顯高于文獻(xiàn)[13]中的算法，因?yàn)楸倔w映射更注重概念的共指關(guān)系識別，而文獻(xiàn)[13]過分關(guān)注詞語的語義相關(guān)度，從而導(dǎo)致詞語相似度計(jì)算時(shí)引入較大誤差。而Hudong-DBpedia映射任務(wù)得到的查準(zhǔn)率則與編輯距離算法基本持平，同時(shí)高于文獻(xiàn)[13]平均約9%。

在查全率方面，首先，由于引入同義詞詞林作為語義知識庫，因此查全率方面也會高于基于編輯距離的相似度算法；其次，由三個(gè)映射任務(wù)的評測結(jié)果中也可以看出，在引入數(shù)據(jù)場勢函數(shù)作為本體映射規(guī)模壓縮因子后，我們也可以將其視為概念集合之間的結(jié)構(gòu)級映射。因此，根據(jù)某些不同的百科子分類中概念元素可能存在的結(jié)構(gòu)級特征，其也可以為本系統(tǒng)同時(shí)帶來較強(qiáng)的糾錯(cuò)能力，即可能規(guī)避由于采用單純元素級映射策略可能帶來的誤差。同時(shí)，通過引入基于生物信息學(xué)序列比對的組合概念相似度計(jì)算方法，不僅可以避免面向未登錄詞相似度計(jì)算的傳統(tǒng)算法可能帶來的錯(cuò)誤映射，相比于文獻(xiàn)[13]提出的相似度計(jì)算算法，由于其并未考慮未登錄詞問題，因此根據(jù)不同子分類所蘊(yùn)含的組合概念的特征，更可能提高不同子映射任務(wù)的查全率。

最后，從總體性能上(F1值)看，本文系統(tǒng)在面對Baidu-Hudong映射任務(wù)時(shí)，比編輯距離算法和同義詞詞林相似度算法平均高出約11%和20%。在面對Hudong-DBpedia映射任務(wù)時(shí)，本文方法的總體性能高于文獻(xiàn)[13]中提出的同義詞詞林相似度算法，而與編輯距離算法基本持平。在面對Baidu-DBpedia映射任務(wù)時(shí)，本文方法的總體性能仍分別高于文獻(xiàn)[13]中提出的同義詞詞林相似度算法和文獻(xiàn)[22]中提出的編輯距離算法約20%和8%。

6 結(jié)束語

現(xiàn)階段缺乏成熟的中文大規(guī)模本體映射系統(tǒng)，本文提出一種基于同義詞詞林的中文本體映射原型框架，該系統(tǒng)解決了大規(guī)模本體映射系統(tǒng)的可用性問題。它著眼于現(xiàn)有中文大規(guī)模本體的特征進(jìn)行概念元素級映射。今后將根據(jù)不同中文本體的特征，考慮引入實(shí)例級以及概念定義相似度的映射參數(shù)，以進(jìn)一步提高中文映射系統(tǒng)的健壯性和準(zhǔn)確性。

[1] Berners-Lee，T，Hendler J，et al: The Semantic Web. Scientific American,2001.

[2] Borst W N. Construction of Engineering Ontologies for Knowledge Sharing and Reuse[D]. Enschede: University of Twente，1997.

[3] Bizer C，et al. Linked data on the web[C]//Proceeding of the 17th International Conference on World Wide Web.ACM，New York,2008: 1265-1266.

[4] Jain P，Hitzler P，Sheth A P，et al. Ontology alignment for linked open data[C]//Proceeding of theISWC 2010. Springer Berlin Heidelberg，2010: 402-417.

[5] Cohen W，Ravikumar P，F(xiàn)ienberg S. A comparison of string distance metrics for name-matching tasks[C]//Proceedings of the IJCAI Workshop on Information Integration on the Web(IIWeb). Acapulco，Mexico，2003: 73-78.

[6] Melnik S，Garcia-Molina H，Rahm E. Similarity flooding: A versatile graph matching algorithm and its application to schema Matching[C]//Proceedings of the 18th International Conference of Data Engineering(ICDE). San Jose，California，2002: 117-128.

[7] Zhong Q，Li H，Li J，et al. A gauss function based approach for unbalanced ontology matching[C]//Proceedings of the 28th International Conference on Management of Data(SIGMOD). Rhode Island，USA，2009: 669-680.

[8] Stark M M，et al: Wordnet: An electronic lexical database[C]//Proceedings of 11th Eurographics Workshop on Rendering. MIT Press，Cambridge,1998.

[9] Giunchiglia F，et al: Element level semantic matching[D]. Italy: Dept.of Information and Communication Technology University of Trento，2004.

[10] Isaac A，Meij L，Schlobach S，et al. An empirical study of instance-based ontology matching[C]//Proceedings of the 6th International Semantic Web Conference and the 2nd Asian Semantic Web Conference(ISWC/ASWC). Busan，Korea，2007: 253-266.

[11] 董振東，董強(qiáng)，郝長伶. 知網(wǎng)的理論發(fā)現(xiàn)[J]. 中文信息學(xué)報(bào)，2007，21(4): 3-9.

[12] 李佳，祝銘，劉辰，等. 中文本體映射研究與實(shí)現(xiàn)[J]. 中文信息學(xué)報(bào)，2007，21(4): 27-33.

[13] 田久樂，趙蔚. 基于同義詞詞林的詞語相似度計(jì)算方法[J]．吉林大學(xué)學(xué)報(bào)，2010，28(6): 602-608.

[14] Z Wang，et al. Knowledge extraction from chinese wiki encyclopedias[J]. Journal of Zhejiang University-Science C，2012,13(4): 268-280.

[15] Bizer C，Lehmann J，et al: DBpedia-A Crystallization Point for the Web of Data[J]. Journal of Web Semantics,2009,7(3): 154-165.

[16] Niu X，Sun X，Wang H，et al. Zhishi.me-weaving Chinese linking open data[C]// Proceedings of ISWC 2011. Springer Berlin Heidelberg，2011: 205-220.

[17] 王汀，邸瑞華，李維銘. 一種基于同義詞詞林的中文大規(guī)模本體映射方案[J]. 計(jì)算機(jī)科學(xué)，2014，41(5): 120-123.

[18] Chen Yidong，Chen Liwei，Xu Kun. Learning Chinese entity attributes from online encyclopedia[C]//Proceedings of IEKB Workshop in APWeb.2012: 179-186.

[19] 李德毅，杜鹢. 不確定性人工智能[M].北京: 國防工業(yè)出版社，2005.

[20] Needleman S B，Wunsch C D. A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins[J]. Journal of Molecular Biology，1970，48: 443-453.

[21] Wang T，Song J C.，Di R H，et al. A Thesaurus and Online Encyclopedia Merging Method for Large Scale Domain-Ontology Automatic Construction[J].M. Wang(ed.) KSEM 2013. LNCS (LNAI)， Springer，Heidelberg.2013,8041: 132-146.

[22] Diogene Ontology Mapping Prototype，http://diogene.cis.strath.ac.uk/prototype.html

A Schema-Level Ontology Alignment Model for Chinese Linked Open Data

WANG Ting，XU Tiansheng，JI Fujun

(School of Information，Capital University of Economics and Business，Beijing 100070，China)

The current research on the linked open data(LOD) mainly focused on level of instances,while the task on finding schema-level links between LOD datasets is ignored. In order to solve the large-scale Chinese ontology mapping problem occurred in LOD,we propose a data field and sequence alignment-based ontology mapping architecture. Firstly,based on an improved nuclear field potential function,we compress dimension of unaligned large-scale Chinese ontology. Secondly,we use the sequence alignment algorithm to compute similarity between concepts. Compared to other typical similarity computing algorithms,the experimental results show that the proposed method has higher overall performance and usability.

semantic web; linked open data; ontology mapping; Tongyici Cilin; similarity computing

王汀(1985-)，博士，講師，主要研究領(lǐng)域?yàn)檎Z義web技術(shù)、自然語言處理等。E?mail：wangting@cueb．edu．cn徐天晟(1972-)，博士，教授，主要研究領(lǐng)域?yàn)樽匀徽Z言處理、人工智能等。E?mail：xuts@cueb．edu．cn冀付軍(1975-)，博士，副教授，主要研究領(lǐng)域?yàn)橛?jì)算機(jī)軟件系統(tǒng)，IPv6資源平臺。E?mail：jfj@cueb．edu．cn

2014-06-04 定稿日期： 2016-04-25

北京市社會科學(xué)基金(15ZHB011); 首都經(jīng)濟(jì)貿(mào)易大學(xué)科研項(xiàng)目(00791554410264，00791654490223); 國家社會科學(xué)基金(13CXW057); 2016北京市教委科研水平提高經(jīng)費(fèi)資助

1003-0077(2016)03-0204-09

TP391

A