一種新的本體相似度計算方法

收稿日期：2007-12-21；修回日期：2008-03-12

基金項目：國家自然科學基金資助項目(60773100);國家教育部科學技術研究重點資助項目(205014);河北省教育廳科研計劃項目(2006143)

作者簡介：張忠平(1972-)，男，吉林人，CCF會員，副教授，碩導，博士，主要研究方向為網格技術、語義網、本體論、XML數據庫、數據挖掘(xiaoyue8712@163.com);田淑霞(1981-)，女，山東濟寧人，碩士研究生，主要研究方向為語義網、本體論;劉洪強(1981-)，男，山東東營人，碩士研究生，主要研究方向為人工智能、語義網.*

(1.燕山大學 信息科學與工程學院， 河北 秦皇島 066004; 2.南京郵電大學 計算機學院，南京 210003)

摘 要：針對目前本體映射過程中相似度計算存在的問題，提出了一種綜合的相似度計算方法。首先判斷不同本體之間是否存在相關性，若相關，則充分考慮各種相關因素，從語義和概念兩個層面來進行比較；然后給出本體的綜合相似度計算方法；最后采用兩組測試數據對該方法進行實驗，并與GLUE系統的概率統計方法進行了實驗對比。實驗結果表明，該方法能夠有效確保相似度計算的準確性。

關鍵詞：本體;本體映射; 相關度; 本體相似度; 概念相似度

中圖分類號：TP391

文獻標志碼：A

文章編號：1001-3695(2008)10-2939-04

New approach for ontology similarity computation

ZHANG Zhong-ping¹， TIAN Shu-xia¹， LIU Hong-qiang²

(1.College of Information Science Engineering， Yanshan University， Qinhuangdao Hebei 066004， China;2. College of Computer， Nanjing University of Posts Telecommunications， Nanjing 210003， China)

Abstract:Aimmed at the current problems，this paper put forward a compositive approach of similarity computation. It judged the relativity among different domain ontologies first. And then in this subsumption，based on semantic level and concept level， proposed a comprehensive similarity measuring method， after took a full consideration about relative factors. Lastly this app-roach tested with two datasets and compared it with probability statistical method of GLUE system. Experiment results show that this approach can significantly improve the precision.

Key words：ontology; ontology mapping; relativity; ontology similarity; concept similarity

0 引言

近年來，本體已經成為知識工程、語義Web、人工智能、數據集成、信息檢索等研究領域的熱門課題。隨著本體的廣泛應用，為實現資源共享，各領域紛紛定義了相應的本體標準。然而本體的建立一直沒有一個統一的規范來進行約束，由此引發了諸如系統異構、結構異構、語義異構等許多問題。本體映射的研究則正是為了解決這些異構問題。本體映射是本體集成(integration)、本體串聯( alignment)、本體合并(merging)等技術的基礎，是解決知識共享與重用的有效途徑。而本體相似度計算是本體映射的關鍵環節。已有的相似度計算方法通常是通過概念的相似度得到的。然而在復雜應用環境中，僅僅考慮概念的相似度是遠遠不夠的，本體的實例、關系、屬性、結構等信息也是相似度計算需要考慮的重要因素。

本文針對目前本體映射過程中相似度計算所存在的問題，引入了相關度，提出了一種綜合的相似度計算方法。首先判斷不同本體之間的相關性，若兩本體相關，則充分考慮本體結構、本體組成元素(概念、屬性、實例等)以及元素語義等相關因素，分別給出本體語義相似度以及基于名稱、實例、屬性、結構等相關信息的概念相似度計算方法；然后將兩種相似度合并得到本體的綜合相似度。

1 相關術語

11本體

本體最初起源于哲學領域，稱為本體論、存在論，反映的是事物本質的科學內涵。20世紀80年代，科研人員把本體引入人工智能(artificial intelligence)領域，并賦予其新的含義。應用本體的主要目的是為了實現知識共享和重用。在計算機領域，本體是一個對共享概念形式化的、顯性的規范說明[1]。關于本體的形式化定義很多，本文采用文獻[2]中的本體表示形式。文中采用OWL(Web ontology language)的子語言OWL Lite表示。本體主要包括概念、關系、實例以及公理，可表示為O:=(C，HC， RC， HR， I， RI， A)其具體含義如下：概念C包含于層次結構HC中；兩個獨立的概念之間存在關系RC；關系(屬性)處于層次結構HR中；實例I是特殊化概念，由屬性實例RI關聯；另外，公理A用邏輯語言表示，可從已有的知識推導出新的知識。公理在本體映射推理過程中應用較多。

12 本體映射

本體映射是指兩個本體之間存在語義級的概念關聯，通過語義關聯，實現將源本體的實體映射到目標本體的過程[3]。其實質就是概念層上語義相關的兩個本體的實體根據語義關系進行轉換的過程，以便用戶能使用通用的接口，對同一事物形成共同的理解。Ehrig與Staab[4]歸納出本體映射六個過程。這一過程表明，本體相似度的計算是本體映射的關鍵環節。

13 相似度

所謂相似度就是指兩個對象相似的程度。形式化定義為sim(ei1， ei2)=α/（d+α）其中:sim(ei1，ei2)表示元素ei1(ei1∈O1)和ei2(ei2∈O2)的相似度，取值是[0，1]（如果兩個元素是完全相似的，則相似度為1；如果兩個元素無任何共有特征，則相似度為0）；α為可調節的參數；d是一個整數。關于取值采用如下策略[5]：

a)若ei1=ei2，則令d=0，α≠0，即sim(ei1，ei2)=1。

b)若ei1≠ei2，則令α=0，d≠0，即sim(ei1，ei2)=0。

c)sim(ei1，ei2)=sim(ei2，ei1)，具有對稱關系。

d)若Ei1、Ei2分別表示元素ei1、ei2的特征集合，(Ei1∩Ei2)≠，則令d=1，其相似度值為α/(1+α)，且計算方法如下：simset(ei1，ei2)=|Ei1∩Ei2|/(|Ei1∩Ei2|+

λ|Ei1/Ei2|+(1-λ)|Ei2/Ei1|)；λ∈[0，1]其中：Ei1/Ei2表示集合Ei1中除去集合Ei2具有的特征;Ei2/Ei1反之類似；λ是非公共特征的相對重要程度，可以調節。

e)若sim1(ei1，ei2)，…，simn(ei1，ei2)表示度量得到的多個不同方面的相似度值，則相似度迭代的計算方法如下：simagg(ei1，ei2)=w1×sim1(ei1，ei2)+w2×sim2(ei1，ei2)+…+

wn×simn(ei1，ei2)/(w1+w2+…+wn)

(wi＞0)， w1+w2+…+wn=1其中：wi為可調參數，其取值由相似度值的重要性決定。

2 綜合的本體相似度計算

為了比較兩個本體并計算它們之間的相似度，本文首先引入相關度，通過相關度來判斷兩本體的相關性；然后在相關的基礎上依據 Maedche等人[6]從不同層面上進行相似度計算的基本思想，從語義和概念兩個層面來進行比較，即分別計算語義相似度和概念相似度。

21 相關度

相關性指概念之間相關的程度。相關性是一個比相似性更普遍的概念，相似意味著詞匯所表達的概念在某些特征方面有重合，而相關性表明概念間具有相似性，但概念所表達的一些特征不直接重合。因此，相似只是相關的一個特殊方面。例如汽車與汽油緊密相關但不相似，而汽車與自行車在功能上相似但不是緊密相關。相似的實體通常都可以因為它們的相似性而被認為是相關的，如固定電話—無線電話。但不相似的實體仍然可能具有很強的語義相關性，如企鵝—南極洲。本文統一用一個在[0，1]取值的實數來表示度量的結果，該實數的取值0(1)表示兩個實體完全不相關。具體方法采用Hirst-St-Onge語義相關度算法[7，8]。其基本思想是：當兩個詞在WordNet同義詞集(synset)中有一條較短的路徑相連時，在語義上就具有較大的相關度；當此路徑不存在時，RelHS(w1，w2)=0。具體公式如下：RelHS(w1，w2)=c-len(w1，w2)-k×turns(w1，w2)(1)其中：c和k是兩個常參數；turns(w1，w2)代表在synset 中的路徑轉向次數;len(w1，w2)是路徑長度。

22 語義相似度

語義相似度是指概念間自身語義的相似程度，也就是考慮概念的意思來計算相似度。語義相關度與語義相似度成正比關系。本文采用WordNet語義詞典來計算概念的語義相似度。

WordNet是由Princeton大學開發的一個龐大的語言知識庫系統，是一部樹狀的英語語義字典。其中每個節點s表示一個詞義。節點中保存了多個同義詞或短語。每個單詞或短語又可以存在于多個語義節點中(即表明該單詞有多個詞義)。基于語義詞典的語義相似度的基本思想是：兩個單詞通過上位關系(hypernym)連接的距離越近，它們的相似度越大；反之，它們的相似度越小。如果它們在有限上位層次中沒有共同的父節點，則simd(w1，w2)=0。Pantel等人[9]在WordNet中定義了兩個詞義的相似度。simd(s1，s2)=2×log p(s)/[log p(s1)+log p(s2)](2)其中：p(s)=count(s)/total表示在WordNet中詞義節點s及其子節點所包含的單詞個數在整個詞典中所占的比例；total是WordNet的單詞總數。另外w1∈s1，w2∈s2，表示單詞w1和w2分別位于節點s1和s2中，節點s是s1和s2的公共祖先節點。

令s(w1)={s1i|i=1，2，…，m}和s(w2)={s2j| j=1，2，…，n}分別表示單詞w1和w2的所有詞義，則兩個單詞的相似度定義為它們之間詞義相似度的最大值：simd(w1，w2)=max(simd(s1i， s2j))

s1i∈s(w1)， s2i∈s(w2)(3)23 概念相似度

為了準確計算概念之間的相似度，本文充分考慮概念的名稱、實例、屬性、結構等因素，并在充分考慮現有技術的基礎上，多方面、多角度地給出概念相似度的綜合計算。

2. 3. 1 基于概念名稱

使用概念名稱來計算相似度是映射過程中最直接也是最基本的方法。這種方法主要是指不考慮概念的語義，僅僅考慮兩個概念在語言文字上的相似度。通常可將概念看做是不同的字符串，進行字符串之間的比較。常用的方法有edit distance、N-gram、Humming distance等方法。

本文采用編輯距離(edit distance)方法來計算概念名稱之間的相似度。Edit distance[10]又稱Levenshtein distance，是由Levenshtein提出的，用來比較兩個字符串(后擴展到語句)的相似度。它測量從一個字符串轉換到另一個字符串所需的插入、刪除、替換等的最小操作數目。計算公式如下：simstr(ci，cj)=max{0，[min(|ci|，|cj|)-ed(ci，cj)]/

min(|ci|，|cj|)}(4)其中：C1、C2分別為本體O1、O2中的概念集合，ci∈C1，cj∈C2。可以定義兩本體之間的名稱相似度為sim(C1，C2)=1/|C1|∑nci∈C1maxcj∈C2 sim(ci，cj)(5)sim(C1，C2)是對稱計算，顯然sim(C2，C1)可能與sim(C1，C2)完全不同。比如，如果C2不僅包含C1中的所有概念，而且還包含其他一些概念，則sim(C1，C2)=1，而sim(C2，C1)可能趨近于0。因此需要定義一個相關系數(relative number of hits)[2]：

SetHit(C1，C2)=|C1∩C2|/|C1|

為了使sim(C1，C2)在任何情況下都能運算正確，定義SetHit(C1，C2)≤1。

2. 3. 2 基于概念實例

在需要映射的兩個本體中，可以用概念的具體實例計算概念相似度。一個概念的實例也是其祖先概念的實例。基于實例計算相似度的理論依據是，如果概念所具有的實例全部都相同，那么這兩個概念是相同的；如果兩個概念具有相同實例的比重是相同的，那么這兩個概念是相似的。對于概念A、B的具體實例，可利用Jaccard系數[11]來計算相似度：Jaccard_sim(A，B)=P(A∩B)/P(A∪B)=

P(A，B)/[P(A，B)+P(A，B)+P(A，B)](6)

基于實例計算概念相似度涉及到三個概率：P(A，B)、P(A，B)、P(A，B)。其中：P(A，B)表示一個實例在某本體中既屬于概念A又屬于概念B的概率；P（A，B）表示一個實例在某本體中屬于概念A但不屬于概念B的概率；同理，P(A，B)表示實例在某本體中不屬于概念A但屬于概念B的概率。在計算P(A，B)、P(A，B)、P(A，B)時要用到概念A和B在各自本體中的實例個數。用Ui表示本體Oi中的實例集，N(Ui)表示實例集中的實例個數，用N(UiA，B)表示在Ui中既屬于A又屬于B的實例個數，其他類似。以計算P(A，B)為例，具體過程如下[12]：

a)對于本體O1 的實例集U1，把它分成屬于A的實例集U1A和不屬于概念A的實例集UA1。

b)把這兩個實例集中的實例分別作為正反樣本用機器學習方法來訓練對于概念A的學習器L。

c)對于本體O2的實例集U2，把它分成屬于概念B的實例集U2B和不屬于概念B的實例集UB2。

d)使用學習器L對實例集U2B中的實例進行分類，分成兩個實例集U2A，B和UA，B2；同樣用L把實例集UB2分成UA，B2、UA，B2。

e)將本體O1和O2的位置調換，重復以上各步，這樣最終可以獲得實例集U2A，B、UA，B2、UA，B2和UA，B2。

f)從各步計算中求得N(U1)、N(U2)、N(U1A，B)和N(U2A，B)，并利用(7)來計算：P(A，B)=[N(U1A，B)+N(U2A，B)]/[N(U1)+N(U2)](7)

采用同樣的步驟方法來計算P(A，B)、P(A，B)，計算公式分別為P(A，B)=[N(U1A，B)+N(U2A，B)]/[N(U1)+N(U2)](8)

P(A，B)=[N(U1A，B)+N(U2A，B)]/[N(U1)+N(U2)](9)然后利用式(5)計算概念A和B基于實例的相似度。

2. 3. 3 基于概念屬性

本體中概念的屬性對概念的描述具有十分重要的作用。基于屬性計算概念相似度的理論依據是，如果兩個概念的屬性是相同(相似)的，那么這兩個概念是相同(相似)的；如果兩個屬性的域和范圍是相同的，那么這兩個屬性也是相同的。在本體中屬性有兩種類型，即對象屬性和數據類型屬性。通常對象屬性是由個體關聯到個體，而數據類型屬性是個體關聯到數據類型的值。屬性有屬性名稱、屬性數據類型、屬性實例數據等要素，因此判斷兩個屬性是否相似主要從這三個要素來考慮。

屬性名稱、屬性類型本身是文本類型，是字符串，因此可以采用字符串相似度計算方法進行判定。例如用Humming distance[13]來比較兩字符串。設兩字符串s和t，則它們之間的相似度可由式(10)給出：sim(s，t)=1-[(∑min(|s|，|t|)i=1f(i))+

|s|-|t|]/max(|s|，|t|)(10)其中：若s[i]=t[i]，則f(i)=0；否則f(i)=1。

字符串相似度的計算也可以采用其他方法，前面已有說明。由于每個概念的實例對該概念的每一個屬性都分配了一個相應的值，對于其他類型的數據，可以采用基于實例的方法進行計算。

設概念A的屬性為ai，概念B的屬性為bj，兩個屬性之間的相似度記為A sim(ai，bj)，則屬性ai、bj的相似度計算公式為A sim(ai，bj)=w1×sim(ainame，bjname)+w2×

sim(aidatatype，bidatatype)+w3×sim(aivalue， bjvalue)(11)其中：w1、w2、w3是權重，代表屬性名稱、數據類型、屬性實例數據對屬性相似度計算的重要程度，且w1+w2+w3=1。

設概念A、B之間共計算出m個A sim(ai，bj)，并設置相應的權值wkattribute，則概念A與B之間基于屬性的相似度為simattribute(A，B)=∑mk=1wkattributeA sim(ai，bj)/∑mk=1wkattribute(12)

另外，由于一個概念可能有多個屬性，每個屬性對概念的描述程度和作用也各不相同。若每個都考慮則計算量相當大。所以在計算屬性相似度時，可先依據機器學習方法給出屬性的信息增益[14，15]，并以此為依據來確定各個屬性的優先級；最后只選取幾個信息增益較大的屬性進行計算。

2. 3. 4 基于概念結構

OWL中本體概念主要有四種基本關系：kind-of、part-of(或part-whole)、 instance-of和attribute-of。由于本體中的實例都是單獨給出，關系instance-of可以不考慮。關系attribute-of表示一個概念是另一個概念的屬性，其相似度計算也就是概念屬性的相似度計算，在此也不考慮。本體可以依據概念的kind-of和part-of關系刻畫出概念間的層次結構。因此，本文中通過考慮概念的父子關系、兄弟關系，并結合一些啟發規則來給出結構相似度的計算方法。

涉及到的啟發規則主要有以下幾條：a)如果兩個概念相似，那么它們的子概念在一定程度上也相似。b)如果兩個概念的子概念都相似，那么這兩個概念也相似。c)如果兩個概念具有相似的兄弟概念，則這兩個概念也相似。d)如果所有子概念都與某概念X相似，那么它們的父概念也與X相似。e)如果某概念的兄弟概念都與某一概念Y相似，那么該概念與Y也可能相似。f)同一本體中，如果兩個概念屬于同一個父概念，那么這兩個概念是相似的，即兄弟概念是相似的。g)如果概念對中的概念A和B都有多個子概念。其中：A有子概念{A1，A2，…，An}；B有子概念{B1，B2，…，Bn}，并設定一個閾值δ。若A中有大于δ個子概念與B中的子概念相似，則可認為概念A與B是相似的。

計算結構相似度的具體公式如下：simA，B(Ci1，Ci2)=[αsimHfset(Ci1， Ci2)+βsimHbset(Ci1， Ci2)+

γsimHsset(Ci1，Ci2)]/(α+β+γ)(α≥β≥γ＞0)（13）其中：simHfset(Ci1， Ci2)表示度量概念Ci1、Ci2的父概念集HCi1f和HCI2f之間的相似度，其父概念集為其特征因子；simHbset(Ci1， Ci2) (兄弟概念集)和simHsset(Ci1， Ci2)(子概念集)與之類似；α、β、γ為權重因子。由于在概念的層次結構中，父子、兄弟概念對其相似度的影響是不同的，而父概念占有絕對的權重，本文預定為α≥β≥γ。

2. 3. 5 綜合概念相似度

根據相似度定義式(5)，可以將基于名稱的相似度、基于實例的相似度、基于屬性的相似度以及基于結構的相似度進行合并，得到本體的綜合概念相似度，記為simconcept(A，B)。公式表示如下：simconcept(A，B)=w1×simname(A，B)+w2×siminstance(A，B)+

w3×simattribute(A，B)+w4×simstructure(A，B)

(wi＞0， w1+w2+w3+w4=1)(14)24 綜合本體相似度

綜上所述，本體的相似度可由本體的語義相似度與概念相似度兩部分得到，記為sim(O1，O2)，即sim(O1，O2)=w1×simsemantic(O1，O2)+

w2×simconcept(O1，O2)(15)3 實驗與分析

31 實驗數據

本文在兩組測試集上對該方法進行了實驗。第一組測試數據是TestData 1，該數據集中的兩個本體family.swrl和gene-ration分別針對家庭成員信息作了不同的描述，兩個本體的概念和屬性名稱定義比較相似。第二組測試數據是TestData 2，該數據集中的兩個本體travelOntology和travelMessage分別對旅游信息作了不同的描述。表1給出了這兩組測試數據的具體統計信息。

表1 測試集的統計數據數據集本體概念屬性實例

2 實驗結果

本文首先利用人工方法計算各相似度并記錄結果，然后借助WordNet 2.1和Protege 3.3等工具，使用該方法分別對各相似度進行計算，其中各權置的設定存在一定的主觀因素。本文實驗最終所得相似度的部分數據與GLUE系統[11]的概率統計方法以及人工方法的計算結果進行比較，結果如表2所示。

3 實驗分析

與傳統GLUE系統的概率統計方法相比，采用綜合的相似度計算方法所得到的相似度值更加準確。主要原因在于，本文提出的綜合本體相似度計算方法，首先通過判斷相關性，過濾掉了不相關的本體，這樣就大大減少了不必要的計算，降低了復雜度。對于相關本體，從語義與概念兩個層次入手，分別計算本體的語義相似度與概念相似度。對于每一對概念，則充分考慮概念的名稱、實例、屬性、結構等相關因素，與已有的計算方法相比，雖然計算量加大，耗費的時間增多，但其更全面、更準確地反映了概念之間的相似關系。當然這種方法也存在不足，如計算過程中大量權值設定的存在，對系統存在很大的影響。這一點可以在研究過程中通過機器學習(machine lear-ning)或神經網絡(neural networks)技術[16]進行改進。

4 結束語

本體是對領域知識概念的抽象和描述，其目的是為了實現知識的共享與重用。但由于構建標準的不統一，語義異構、結構異構等問題日漸突出，使本體映射越來越成為本體研究的重要課題，作為本體映射基礎的相似度計算也越來越成為該課題研究的難點和焦點。本文針對這一問題提出了一種綜合的本體相似度計算方法，有效確保了計算的全面性、準確性。但在計算過程中，憑經驗設定的各個權值對結果造成了一定的誤差，因此還需要作進一步的研究。后續研究工作中將對這一技術細節作進一步的研究，并將結合本文所提出的相似度計算方法對本體映射技術作更加深入的研究。

參考文獻：

[1]GRUBER T R.A translation approach to portable ontologies[J]. Knowledge Acquisition，1993，5(2):199-220.

[2]WANG Zong-jiang， WANG Ying-lin， ZHANG Shen-sheng， et al. Effective large scale ontology mapping[M]. Berlin: Springer-Verlag， 2006:454-465.

[3]EHRIG M， SURE Y.Ontology mapping: an intergrated approah[C]//Proc of the 1st European Semantic Web Symposium. Heraklion: Springer，2004:76-91.

[4]EHRIG M， STAAB S.QOM-quick ontology mapping[C]//Proc of ISWC 2004. [S.l.]: Springer-Verlag， 2004:683-697.

[5]肖文芳.基于相似度計算的本體映射研究與實現[D].長沙:中南大學，2007.

[6]MAEDCHE A， STAAB S. Measuring similarity between ontologies[C]//Proc of European Conference on Knowledge Acquisition and Management. London:Springer-Verlag， 2002:251-263.

[7]BUDANITSKY A， HIRST G. Evaluating WordNet- based measures of lexical semantic relatedness[J].Computational Linguistics， 2006，32(1):13-47.

[8]張承立，陳劍波，齊開悅.基于語義網的語義相似度算法改進[J].計算機工程與應用，2006， 42(17):165-166，179.

[9]PANTEL P， LIN De-kang. Discovering word senses from text[C]//Proc of ACM SIGKDD Conference on Knowledge Discovery and Data Mining. New York: ACM Press， 2002: 613-619.

[10]BOUQUET P， EUZENAT J， FRANONI E， et al. Specification of a common framework for characterizing alignment， knowledge Web deliverable 2.2.1 v2[D]. Karlsrube: University of Karlsruhe，2004.

[11]DOAN A H， MADHAVAN J， DOMINGOS P， et al. Learning to map between ontologies on the semantic Web[C]//Proc of the 11th International Conference on World Wide Web. New York: ACM Press， 2002: 662-673.

[12]鄭麗萍.本體映射的研究[D].青島:山東科技大學， 2005.

[13]曹澤文，錢杰，張維明，等.一種綜合的概念相似度計算方法[J].計算機科學，2007，34(3):174-175，191.

[14]HAN Jia-wei， KAMBER M. 數據挖掘概念與技術[M].范明，孟曉鋒，譯.北京:機械工業出版社，2007.

[15]鄭麗萍，李光耀，梁永全，等.本體中概念相似度的計算[J].計算機工程與應用，2006，42(30):25-27，61.

[16]LI W S， CLIFTON C. Semantic integration in heterogeneous databa-ses using neural networks[C]//Proc of the 20th International Confe-rence on Very Large Data Bases.San Francisco: Morgan Kaufmann Publishers Inc，1994: 1-12.