ＭＤ４：一種綜合的跨本體實體語義相似度計算方法

摘 要：面向廣域分布環境下信息資源共享與服務的需要，設計了基于本體的元數據模型，并在MD3模型的基礎上給出了一種基于該元數據模型的跨本體的語義相似度計算方法——MD4模型。MD4充分利用本體對實體的描述信息，重點討論了實體名稱、實體屬性、實體語義環境以及實體實例等相似度的計算，把MD3模型擴展到MD4模型，使得信息資源實體間語義相似度的計算更全面、精確。

關鍵詞：元數據模型； 本體； 語義相似度； MD4模型

中圖分類號：TP311.12 文獻標志碼：A 文章編號：1001-3695(2008)08-2335-04

MD4：integrated approach of determining semantic similarity among

entity between different ontologies

HUANG Hong-bin， ZHANG Wei-ming， DENG Su， DONG Fa-hua

(College of Information System Management， National University of Defense Technology， Changsha 410073， China)

Abstract:Oriented the demand of sharing information and service in the distribute network， this paper designed the metadata model based ontology. The MD3 model systematically evaluated semantic similarity across different ontologies dispense with integrating different ontologies into a shared ontology. Based on the MD3 model， focused on the not-hierarchical relations evaluating of concepts from different ontologies， extended the MD3 model to MD4 model to make the semantic similarity of concepts from different ontologies more comprehensive and precise.

Key words：metadata model; ontology; semantic similarity; MD4 model

隨著網絡的發展，在一些大型企事業團體和虛擬組織環境中存在著大量的業務信息系統。組織內的各單位依據業務或專業知識進行分布，并且管理著部分信息資源，不同單位有著不同的工作重心和目標，因此在不同工作領域下對底層的信息資源采用不同的概念實施建模。這些廣域網絡環境下的信息資源具有動態、分布、多元和無序等特點，各部門或組織之間的信息相對封閉，形成了一個個信息孤島，造成信息資源的浪費，同時信息資源的異構性為信息之間的共享與互操作帶來了困難。對用戶而言，訪問并有效利用這些信息資源、實現各節點分布信息資源的共享和交換以及分布信息系統之間的互操作成為一個亟需解決的問題。

本體在人工智能、信息檢索、Web服務發現等領域中扮演著越來越重要的角色，利用本體對信息資源進行建模能夠很好地反映信息資源的語義。基于本體的元數據通過本體來表示元素模型，將有效地促進領域知識的共享和語義表達，能夠為用戶和應用提供語義查詢和信息匯集能力。但是，現有基于本體的信息共享與服務系統中幾乎都假設共享一個集中的全局本體，用來訪問信息資源，這樣的維護開銷比較大。但在廣域網絡環境下，這種假設是不存在的。在網絡環境中每一個節點僅維護本地信息資源的局部領域視圖，通過網絡中節點的協作來發現、理解和使用領域范圍內分布、異構、不斷變化的信息資源，異構問題越來越嚴重，如何解決信息資源的互操作成為一個比較棘手的問題。本體映射和本體集成是解決信息資源語義異構很好的方法，其中一個關鍵步驟就是語義相似度的計算。如何提高語義相似度計算精度也是提高語義信息檢索質量的關鍵之一。語義相似度一般是指計算本體概念間的相似度，多數方法所考慮的概念是基于一個本體的，跨本體概念間的方法比較少，MD3（triple matching-distance model）模型是一種典型的計算跨本體概念間相似度的方法^[1]。

1 常用語義相似度計算方法

1.1 基于特征匹配的模型

Tversky模型是典型的特征匹配模型，提出了基于集合理論，用特征匹配過程來計算相似度的方法^[2]。它指出相似度不僅由兩個概念的相同屬性決定，而且由它們的不同屬性決定。這種模型沒有考慮屬性與概念間的密切程度。由于該模型符合信息領域對相似度的認知，在信息領域有眾多學者在Tversky模型的基礎上建立語義相似度模型，如文獻[3~5]等。

1.2 基于語義距離的模型

基于語義距離的模型根據概念在層次節構中的位置來計算語義相似度。層次節構中節點表示概念，邊表示語義關系。在概念層次樹中，任何兩個節點之間有且只有一條最短路徑，把這條路徑的長度作為兩個概念的語義距離的度量。該模型適合很多專業領域，但它過分依賴事先定義好的語義網結構，只考慮了概念間的聚合（is~a）關系，計算出來的有相同父類的子類之間的相似度值很粗糙。

1.3 基于信息內容的方法

基于信息內容的方法^[4]不依賴于層次結構的詞典，只要有概率模型存在，這種方法就可以應用。兩個概念的相似性決定于它們共享信息的程度，共享信息含量越大，兩個概念越相似。兩個概念的共享信息含量用兩個概念在概念樹上的所有共同“超類”所具有的最大信息含量來表示。

1.4 混合模型

MD（matching-distance）模型是一種典型的混合模型^[6]，該模型以Tversky的比率模型^[2]為基礎。其中，特征權重是根據實體之間的語義關系來確定的。MD模型綜合了基于特征匹配和基于語義距離兩種方法，該方法在語言學上有很深的根基，并定義了非對稱的語義相似度計算函數。

2 MD3模型

概念間相似度的計算方法根據要比較的概念是否來自同一個本體分為單本體和跨本體概念相似度計算方法。基于語義距離和基于信息內容的方法分別利用了本體的結構信息（概念術語的位置信息）和信息內容，不同本體的結構和信息內容不能直接進行比較，這兩種方法適合單本體概念相似度的計算?？绫倔w的相似度方法通常使用混合的或基于特征的方法。傳統的跨本體概念間相似度的計算通過手工或半自動方式把不同本體集成為一個共享本體，然后把本地本體中的概念映射到這個共享本體，再利用單本體概念間相似度的計算方法來完成跨本體概念間的比較。在某些情況下，這種集成共享本體的方法是不現實的，或者形成這個共享本體的代價很大，必須考慮直接針對兩個不同本體來比較其概念。其中，MD3模型是一種典型的計算跨本體概念間語義相似度的方法，是MD模型在跨本體應用中的擴展。MD3模型^[1]用一個通用的虛擬的根把兩個本體聯系起來，分別計算概念名稱、特征屬性以及語義鄰居之間的相似度。

MD3模型是一種跨本體概念間相似度計算框架。計算實體類a和b之間的相似度通過計算同義詞集、特征屬性和語義鄰居之間的加權和，公式如下：

sim(a，b)=wSsynelts(a，b)+uSfeatures(a，b)+vSneighborhoods(a，b)（1）

其中：w、u、v表示了各組成部分的重要性。特征屬性細化為組成部分、功能以及其他屬性。概念a和b的語義鄰居及其特征屬性（即概念的部分、功能及其他屬性）也通過同義詞集合描述，每一個相似度的計算都通過Tversky^[4]公式：

S(a，b)=|A∩B|/[|A∩B|+α(a，b)|A-B|+

(1-α(a，b))|B-A|]（2）

其中：A、B分別表示概念a和b的描述集合；A-B表示屬于A但不屬于B的術語集（B-A相反）。參數α(a，b)由概念a和b在各自層次結構中的深度確定，公式如下：

α(a，b)=depth(a)/（depth(a)+depth(b)）; depth(a)≤depth(b)

1-depth(a)/(depth(a)+depth(b)); depth(a)＞dsepth(b)（3）

3 基于本體的元數據模型

本體(ontology)是領域知識的概念化說明，它將特定領域有關的對象、概念及其關系以形式化的說明來嚴格規定。利用本體建立面向語義的元數據模型，可以將元數據中實體類的含義、類間及對象間的關系更加明確地表達出來，從而支持廣域分布環境下的概念建模、信息搜索與交換、信息資源共享與服務系統建設等研究。

假設T為領域語義詞典（domain semantic dictionary，DSD），是領域中術語詞匯的集合，主要包括類術語、屬性術語、關系術語等。Dbasic是預定義的基本數據類型集合；Denum是預定義的枚舉類型。領域語義詞典用來規范元數據中元素的命名，定義了詞匯間的語義關系，DSD是一個受限的詞匯知識庫，面向的是領域的常用詞匯和專用詞匯。其目標是：a）規范不同信息領域中描述信息資源的詞匯，從而可以有效地限制任意詞匯描述引發的不一致性；b）它是中詞匯語義相似度計算的基礎。DSD采用《知網》的語義描述結構進行組織，主要對實詞進行描述，是一種開放結構，可擴充。

基于信息資源都是信息單元組成這一理解，采用信息單元實體類和實體類之間的關系以及實體對象、相關約束和規范描述信息資源。具體定義如下：

定義1 元數據模型是一個八元組MD:=〈E，A，L，HC，R，I，F，P〉。其中：

a）E是信息單元實體類集合，c∈E，c=(name，Ac)，name(c)表示c的命名詞匯，name(c)∈T。其中，Ac={x|x(x∈A)∩(att(x)=c)}。att是函數集中的屬性映射函數。

b）A是信息單元實體類的屬性集合，屬性又分為基礎屬性和復合屬性。a∈A，a=(name，dt)，name(a)表示a的命名詞匯，name(a)∈T，dt∈Dbasic∪Denum。

c）L取值域集，L=Dbasic∪Denum。

d）HC表示類間的二元層次關系，層次關系是有向傳遞的偏序關系，包括了類間的繼承is-a關系和聚合（組合）part-of關系。

e）R是實體類之間的二元關系集。任何所連接的實體類超過兩個的關系都能夠轉換為一組二元多對關系集合，因此，該模型中的關系設計為二元關系。

f）I為實例集，是信息單元實體類對象集合。

g）F表示函數集，主要包括如下函數：

(a)att:A→E∪R，屬性函數，將屬性分配給某一實體類或關系；

(b)val:V→(E，A)，屬性取值函數；

(c)inst:E→2I，信息單元實例化函數，可以寫為inst(E)=I或E(I)^[8]；

(d)instr:R→2I×I，關系實例化函數，可以寫為instr(R)={I1，I2}或R(I1，I2)^[8]。

(e)dom:R→E，由dom(R):=Π1(rel(R))給出其定義域^[1]；

(f)range:R→E，由range(R):=Π2(rel(R))給出其值域^[1]；

h）P為約束規則集，所有信息單元實體類和關系要滿足的約束的集合。

定義2給定MD:=〈E，A，HC，R，L，I，F〉； 語義解釋為一個三元組， 記為I=〈ΔI，ΔL，·I〉。其中，ΔI是一個非空集合，包含領域中的所有個體；ΔL是一個非空集合，包含領域中的所有數據值；·I是解釋函數，它將E中的每個實體類C都映射為ΔI的一個子集CI(CIΔI)。每個具體域L解釋成一個集合LI(LIΔL)，每個關系R解釋成一個二元關系RI(RIΔI×ΔI)，每個屬性A解釋成一個二元關系AI(AIΔI×ΔL)， 每個個體c解釋成一個元素cI(cI∈ΔI)，每個值l解釋成一個元素lI(lI∈ΔL)。

對于定義1中的實體由三部分組成：實體名、實體屬性以及實體間的語義關系，如圖1所示。實體名由知網描述；實體的屬性細化為功能、部分以及其他屬性；實體的語義關系包含兩部分，即層次語義關系和非層次語義關系。其中最常見的層次語義關系是上下位關系和部分整體關系。這類關系是有向傳遞的非對稱關系，而定義的非層次關系不具有傳遞性。因此計算實體間相似度需對這兩類關系分別討論。

定義3 相似度。兩個實體元素具有某些共同特征時，則定義它們是相似的。相似程度用相似度來表示，形式上相似度計算需滿足：

a）sim(x，y)∈[0…1]，表示相似度的計算值為[0，1]中的一個實數。

b）當且僅當x=y，sim(x，y)=1。

c）如果兩個對象沒有任何公共特征，則sim(x，y)=0。

d）sim(x，y)=sim(y，x)，相似關系是對稱的。

由語義相似度定義和常識知識有以下假設^[7]：

假設1 對于實體C1 和C2，如id (C1)=id (C2)，則C1 和C2 為同一實體。

假設2 如果兩個實體具有相同的超實體，則這兩個實體可能是相似的。

假設3 如果兩個實體具有相同的子實體，則這兩個實體可能是相似的。

假設4 如果兩個實體具有相同的兄弟，則這兩個實體可能是相似的。

假設5 如果兩個實體具有相同的實例，則這兩個實體可能是相同的。

假設6 如果兩個實體具有相同的屬性，則這兩個實體可能是相同的。

同時基于OWL實體類等價關系描述，有如下假設：

假設7 如果兩個實體顯式等價，則兩個實體相似度為1。

以上假設是進行語義相似度計算的基礎。

4 MD4模型

MD3的不足在于其語義鄰居只考慮了層次語義關系沒有考慮語義關系中非層次關系的影響，同時也未考慮對象實例對于相似度的影響。本文在MD3模型的基礎上，參考了其實體名稱相似度，并擴展了實體間非層次關系和實例對實體語義相似度的影響，把MD3模型擴展到MD4（fourfold matching-distance model）模型。

4.1 實體名稱相似度

本文元數據模型中所有實體名稱均是在領域語義詞典中定義的，因此實體名稱相似度計算可以采用基于知網的概念距離。知網^[9]中概念的語義用義原來描述。義原是描述概念語義的最小單位，一共采用了1 500多個義原，這些義原的作用并不是等同的，而存在復雜的關系。為了簡單起見，這里僅考慮義原的上下位關系，根據這種關系，所有義原構成了一個樹狀的層次體系。假如兩個義原在該層次體系中的路徑為d，可得到兩個義原之間的語義相似度，公式如下所示：

sim(p1，p2)=a/(d+a)（4）

式中，a是一個可調節的參數。由于概念的語義是由多個義原來表示的，可以計算每個義原的相似度來考慮其重要性，就可以得到實體之間的名稱相似度，計算方法如下：

Sname(c1，c2)=∑mi=1wimax1≤j≤nsim(pi，pj)（5）

其中：m、n為實體;c1、c2為義原數；wi為第i個義原所占權重。

4.2 實體屬性的相似度

文獻[1]中，特征屬性被細化為組成部分、功能以及其他屬性三類。這樣做的優點是可以依據語言環境的不同，根據屬性對實體語義相似度影響的大小不同分配不同的權值。把三部分屬性相似度的加權和作為實體特征屬性的相似度，公式為

Sattr(ap，bq)=w1S1(ap，bq)+w2S2(ap，bq)+w3S3(ap，bq)（6）

其中：S1、S2、S3分別是組成部分、功能和其他屬性的相似度，其相應的權值為wi，并且滿足wi≥0，∑3i=1wi=1。

一般來說，元數據定義時屬性有屬性名稱、屬性描述及屬性數據類型。為了計算屬性相似度，兩個屬性的所有信息都應該進行比較。計算屬性名稱相似度與計算實體名稱相似度方法一致。屬性的數據類型或者是一個簡單的數據類型或者是一個實體類型（對象數據類型），如果兩個數據的數據類型都是簡單的數據類型，簡單數據類型之間的相似度^[10]如表1所示。對象數據類型和簡單數據類型是不相容的，數據類型之間的相似度為0。若比較兩個對象數據類型，則調用實體名稱相似度進行計算。

表1 簡單數據類型的相似度計算數據類型integerlongfloatdecimalstringinteger10.90.80.70.3long0.910.80.70.3float0.80.810.70.3decimal0.70.70.710.3string0.30.30.30.31

4.3 語義關系的相似度

語義關系包括層次語義關系和非層次語義關系。層次關系為有向傳遞，非層次語義關系不具有傳遞性（如關聯關系）。

1）層次語義關系的計算

計算層次語義關系借鑒文獻[1]中語義鄰居的定義，以實體為中心向周圍輻射，設定一個語義半徑，半徑取值的大小反映與實體之間的親疏關系。劃定語義鄰居的范圍集合進行匹配，取集合中的最大值作為語義鄰居之間的相似度。語義鄰居計算公式如下：

N(ao，r)={coi}i，d(ao，coi)≤r（7）

則層次語義關系相似度計算：

Sh(a，b)=|A∩B|/|A∪B|（8）

其中：A、B分別代表實體a、b的語義鄰居集合;|·|表示集合的勢。

2）非層次語義關系的計算

定義實體的上位詞為實體所有父類的集合，公式如下：

UC(Ci，H)={Cj∈C|H(Ci，Cj)}（9）

基于實體上位詞的定義，定義實體的匹配公式如下：

CM(C1，O1;C2，O2)=|UC(C1，H1)∩UC(C2，H2)|/

|UC(C1，H1)∪UC(C2，H2)|（10）

如果關系的定義域或值域是實體c，則稱這些關系為與實體c相關的非層次關系，公式如下：

Rc(P)={dom(Rx)=c∪range(Rx)=c|Rx∈P，c∈C}（11）

還可進一步把非層次關系細化為實體的in關系和out關系（可以認為非層次關系的方向是從定義域到值域，以此來定義in和out關系）。in關系是指實體c是非層次關系的值域，定義如下：

Rc-I={range(Rx)=c|Rx∈P，c∈C}（12）

而out關系是指實體c是非層次關系的定義域，定義如下：

Rc-O={dom(Rx)=c|Rx∈P，c∈C}（13）

比較實體的非層次關系，首先應找出兩個本體中與這兩個實體相關的同類非層次關系（無須考慮不同類的非層次關系），進而比較這些同類非層次關系的另外一項之間的相似度（如果要比較的實體是非層次關系的定義域，分別找出這個關系的值域，通過實體匹配公式對其進行比較，反之亦然）。

下面以in關系為例描述比較的過程（out關系類似）：

RI=Rpa-I∩Rqb-I

其中：Rpa-I表示本體p中與實體a相關的in關系;Rqb-I表示本體q中與實體b相關的in關系，所以其交集RI表示本體p、q中與實體a、b相關的公共in關系集合。如果實體a、b沒有公共的in關系，則RI為空，無須下面的計算。對于公共in關系集合，公式如下：

Snon-h-I(a，b)=∑|RI|i=1CM(dom(RIi)，p;dom(RIi)，q)/|RI|（14）

對in關系和out關系進行加權綜合，得到非層次關系相似度的公式如下：

Snon-h(a，b)=iSnon-h-I(a，b)+oSnon-h-o(a，b)（15）

其中：i、o為權值，反映了不同類型關系對實體相似度的影響。對層次關系以及非層次關系計算結果進行綜合，得到實體語義環境的相似度。定義如下：

Sneighborhoods(a，b)=w1Sh(a，b)+w2Snon-h(a，b)（16）

其中：w1、w2分別是層次關系和非層次關系的權重。因為層次關系是本體中最重要的關系，所以其比重理應較大，即w1＞0.5＞w2，且w1+w2=1。

4.4 實例特征相似度

實體a、b的實例特征相似度是通過資源元數據描述中具體實例和實例特征來評估。實體a、b實例特征相似度計算函數為

Sinst(a，b)=P(a∩b)/P(a∪b)=P(a，b)/

[P(a，b)+P(a，b)+P(a，b)]（17）

基于實例特征計算實體相似度牽扯到三個概率：P(a，b)、P(a，b)、P(a，b)。其中，P(a，b)是從一個本體的實例空間中隨機選取一個實例屬于實體a，并且同時屬于實體b的實例在實例空間中所占的比重。

4.5 綜合公式

基于上面的分析，最后綜合四部分的相似度值^[10]得到跨本體實體間語義相似度的綜合公式：

sim(a，b)=wSname(a，b)+uSattr(a，b)+

vSneighborhoods(a，b)+rSinst(a，b)（18）

其中：w、u、v、r分別表示各部分所占的權重，且w+u+v+r=1，權重沒有統一的規定，根據實際應用問題的不同而不同。最簡單的方法是w=u=v=r=0.25。當某一部分相似度計算為0時，可以擴大其他權重值，確定合適的權重也有很多種方法。

5 初步試驗驗證

5.1 實驗評價準則

為方便與MD3算法進行對照，參考文獻[1]，本文采用信息檢索領域查全率和查準率作為評價相似度計算的主要準則，并重新定義如下：

recall=|A∩B|/|A|（19）

precision=|A∩B|/|B|（20）

其中：A表示實際相似的實體；B表示通過模型計算所得的相似實體；||表示集合的勢。

5.2 實驗結果及分析

文獻[1]中把WordNet本體和SDTS本體進行綜合得到WS本體，并以這三個本體為例進行實驗。筆者對WS本體利用定義1進行重新擴展定義，加入非層次關系以及實例的描述，使其滿足本文中基于本體元數據模型的描述。本文以WS本體和EWS本體為例，分別利用MD3模型和MD4模型進行計算。

針對WS本體和EWS本體集，各部分采用相同的權重，計算結果如表2所示。

表2 計算結果模型名稱/％屬性/％關系/％實例/％recall/%precision/%MD334333304497MD4252525256898從上面的結果可以知道，MD4模型對實體的各個維度進行了綜合的考慮，無論是在查全率還是在查準率上，MD4模型比MD3模型都有所提高。必須指出的是，雖然MD4模型在計算相似度時有一定的優勢，但是，對實體全面的描述只是一個理想，只能在一定程度上的小范圍內才能實現。針對具體的應用，MD4模型需要進行相應的改動。

6 結束語

語義相似度計算方法的評估通常是把計算結果與人的主觀判斷結果進行比較，兩者越接近，說明語義相似度方法就越好。由于知識背景和認知經驗不同，判斷結果主觀性很強，即使取一群人判斷結果的平均值，也只能相對客觀地反映這一群人的認知特性，不能客觀反映實體之間的語義相似性。因此如何客觀地評估語義相似度計算方法還有待于深入研究。

本文提出的MD4模型繼承了MD3模型的優點，對MD3模型進行了完善。在描述豐富的本體中，通過選擇合適的權值，在MD4模型理論上可以確保語義相似度的計算更全面、準確。當然，在語義相似度計算過程中存在大量權值的設定，對性能存在一定的影響。如何方便快捷地選擇合適的權值是未來工作的重點。

參考文獻：

[1]RODRIGUEZ M A， EGENHOFER M J. Determining semantic similarity among entity classes from different ontologies[J]. IEEE Trans on Knowledge and Data Engineering， 2003，15(2):442-456.

[2]TVERSKY A.Features of similarity[J]. Psychological Review，1977， 84(4):327-352.

[3]LEE J， KIM M，LEE Y. Information retrieval based on conceptual distance in is-a hierarchies[J]. Journal of Documentation，1993， 49(2):188-207.

[4]RESNIK P. Semantic similarity in a taxonomy: an information-based measure and its application to problems of ambiguity and natural language[J]. Journal of Artificial Intelligence Research， 1999，11:95-130.

[5] RADA R， MILI H， BICKNELL E， et al. Development and application of a metric on semantic nets[J]. IEEE Trans on System， Man， and Cybernetics， 1989，19(1): 17-30.

[6]RODRIGUEZ M A. Assessing semantic similarity among spatial entity classes[D]. Orone: University of Maine，2000.

[7]程勇，黃河，邱莉榕，等.一個基于相似度計算的動態多維概念映射算法[J].小型微型計算機系統， 2006， 27(6):975-979.

[8]MAEDCHE A， EACHARIAS V. Clustering ontology-based metadata in the semantic Web[C]// Proc of the 6th European Conference on Principles of Data Mining and Knowledge Discovery. London: Sprin-ger-Verlag， 2002: 348-360.

[9]劉群，李素建．基于《知網》的詞匯語義相似度計算[J]. 中文計算語言學， 2002，7(2):59-76.

[10]NGAN L D， HANG T M， GOH A E S. Semantic similarity between concepts from different OWL ontologies[C]// Proc of IEEE International Conference on Industrial Informatic. 2006.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文