基于相似度綜合計算的本體映射方法的研究

摘要：語義異構問題已成為目前異構數據集成領域的研究熱點，本體由于其自身的優(yōu)勢而被用于解決語義異構。該文討論了基于相似度的本體映射方法，著重介紹了基于語法距離、基于WordNet語義字典以及基于結構的相似度計算，最后提出了本體映射生成算法，旨在解決語義異構中本體映射問題。

關鍵字：語義異構；本體；相似度計算

中圖分類號：TP311 文獻標識碼：A文章編號：1009-3044(2009)04-0841-03

The Research of Ontology Mapping Method Based on Composite Computing Similarity

LI Jia-qiang，YAN Nan-nan

(Shanghai Maritime University College of Information Engineering，Shanghai 200135，China)

Abstract: Semantics heterogeneity has been a hot research spot in recent data integration field.Ontology has been used for solving semantics owing to its strengths.Firstly，the paper discusses ontology mapping method based on similarity.Secondly，computing similarity based on grammar distance，Wordnet semantics dictionary and structure is mainly introduced.At last，the algorithm of producing ontology mapping is put forward，aimed to solve the problem of ontology mapping in semantics heterogeneity.

Key words:semantics heterogeneity;ontology;computing similarity

1 本體映射概述

本體映射是指本體間存在語義級的概念關聯，通過語義關聯，實現將源本體的實例映射到目標本體的過程[1]。本體映射是語義Web、語義數據搜索、數據集成等研究中的重要方法，也是本體融合、本體集成、本體翻譯等技術的基礎。在基于本體的異構數據集成中，本體映射是解決語義異構問題的關鍵。本體之間的映射主要包括1:1、1:n、n:1、1:1、1:1和n:m共6種映射模型[2]。目前的映射方法能處理的映射類型非常有限，大多數研究都集中于1:1的映射模型。對于1:1的映射，有以下定義：當本體О1中的第i個元素與本體О2中的第j個元素的相似度Sim(e1i，e2j)大于某個設定的閾值時，稱這兩個元素之間符合映射關系map(e1i)=e2j。綜上，可以看出本體映射過程實際上就是找到元素i，j之間所有的元素映射關系并進行映射和轉換的過程。

2 本體映射的研究現狀

目前國內外在本體映射領域已經有了一些具體的映射方法和系統(tǒng)。例如，Karlsruhe大學開發(fā)的MAFRA系統(tǒng)[3]包括了映射的發(fā)現、表達和執(zhí)行的映射框架。由清華大學的唐杰等人基于貝葉斯決策理論提出的RiMOM映射模型[4]，將映射發(fā)現問題轉換成最小風險問題，提供了一個多策略的本體映射方法。

3 本體相似度的計算

在本體之間建立語義關聯，實現本體映射，關鍵在于發(fā)現相同或者相似的元素間的映射關系。相似度計算便成為本體映射中發(fā)現映射關系的重要方法。

3.1 基于語法距離的相似度計算

基于語法的相似度計算方法針對本體的概念、屬性的語法特征進行計算相似度?；谡Z法的相似度計算易于實現，適用范圍廣。由于概念的名稱，屬性名稱等都是字符串在具體實現上，采用基于編輯距離(Edit Distance)的方法[5]。算法實現如下：

算法1：編輯距離的動態(tài)規(guī)劃算法

Function EditDistance(str1，str2);

輸入：字符串str1和str2

輸出：字符串str1和str2之間的編輯距離edit (str1 ，str2)

設字符串str1和str2的長度分別為n，m。

If(n=0) return m and exit;

If(m=0) return n and exit.

構造二維數組d[m+1][n+1]。并令d[0…m][0]=0…m，d[0][0…n]=0…n。

For(str1[i] in str1[]){

For(str2[j] in str2[]){

如果str1[i]=str2[j]，則cost=0.否則cost=1；

d[i，j]=minimum(d[i-1，j]+1，d[j，i-1]+1，d[i-1，j-1]+cost)

}

}

循環(huán)結束，字符串str1和str2的編輯距離即為d[m][n]即edit(str1 ，str2)=d[m][n]。

假設(str1，str2)為編輯距離計算得出的相似度?？啥x語法距離相似度：

■

其中|str1|，|str2|為str1和str2的字符串長度。可以看出該方法適用于差異較小而實際意思相同的字符串，但對字符串差異較大而實際意思相同的字符串就失效了，需采用其他方法。

3.2 基于WordNet語義字典的相似度計算

WordNet是一個典型的語義詞典，它由Princeton大學認知科學實驗室從1985年起開始開發(fā)，目前仍在不斷發(fā)展[6]。為了解決算法1不能解決的問題，采用基于WordNet的本體元素語義相似度計算，算法實現如下：

算法2：基于WordNet的元素相似度算法：

輸入：本體元素名稱word1，word2

輸出：本體元素word1，word2之間的相似度■

初始化■=0

利用WordNet查詢獲得的相應的同義詞集合Syn1[]和Syn2[]

If(Syn1[]包含 ||Syn2[]包含 ) //如果為同義詞{

return ■=1 //直接返回相似度為1

}

Else{

對word1，word2進行預處理分詞，獲得相應的字串數組subword1[m]和subword2[n]，令word1i為subword1中元素，1 ≦i≦m；word2j為subword2中元素，1 ≦j ≦n；

For(w1i in subword1){

For(w2j in subword2){

計算■

取得■的最大值■

}

令■

}

■

return ■

}

3.3 基于結構的相似度計算

基于結構的相似度計算是在以上的相似度計算方法上加入了本體中所包含的類概念的結構化信息，即父類和子類關系信息?？梢哉J為，兩個類概念的父類集合之間相似度越高，則其相似度越高。兩個類概念的子類集合之間的相似度越高，則其相似度越高。因此，可以定義基于結構的相似度計算方法如下[7]：

■

其中，■表示度量概念C1i，C2i的父概念集■，■之間的相似度；■表示度量概念C1i，C2i的子概念集■，■之間的相似度； α，β表示權重因子。綜上可得算法實現如下：

算法3：基于結構的相似度計算算法

輸入：本體概念Ci1，Ci2權重因子α，β

輸出：本體概念Ci1，Ci2之間的相似度■

獲取概念Ci1，Ci2的父類集合■，■

■

計算■

//調用基于語義詞典的方法計算父類之間的相似度

}

}

■

計算■

//調用基于語義詞典的方法計算子類之間的相似度

}

}

計算■，得出結果。

3.4 屬性約束相似度計算

在本體描述中，屬性(Property)的定義域(Domain)和值域(Range)是屬性中蘊含的重要信息。通過比較屬性的定義域和值域可以得到屬性的約束相似度，■[8]。

3.5 相似度綜合與閾值選取

通過上述四種方法計算相似度，得到不同的計算結果。為了平衡各個算法計算結果所帶來的差異需要進行相似度綜合，計算公式如下：

■

■

其中，α，β，γ代表基于領域經驗可調整的計算相似度權重因子；S1，S2代表計算相似度的輸入值。

同時，為了生成本體映射，需要設置一個閾值，當計算結果大于閾值時才認為其元素是相似的。

4 本體映射生成算法

通過對上述算法1、2、3以及屬性約束相似度計算的分析、整合得出如下分別針對本體中的概念和屬性的本體映射生成實現算法。

算法4：本體映射生成算法

Function OMapping(О1，О2)

首先解析本體特征，獲得本體О1，О2的待計算概念集合與屬性集合。

For(concept i in О1){

For(concept j in О2){

//基于語法距離計算相似度

SimDist(concept i，concept j)

//基于語義詞典計算相似度

SimWord(concept i，concept j)

//基于結構計算相似度

SimStruct(concept i，concept j)

//相似度綜合

SimConcept(concept i，concept j)

}

}

ConceptMappingConstruct()//概念映射構建

//構建屬性間映射

For(property i in О1){

For(property j in О2){

//基于語法距離計算相似度

SimDist(property i， property j)

//基于語義詞典計算相似度

SimWord(property i， property j)

//相似度綜合

SimProperty(property i， property j)

}

}

PropertyMappingConstruct()//屬性映射構建

}

5 結束語

鑒于本體映射在基于本體的異構數據集成中解決語義異構問題的重要性，本文在分析本體映射生成過程中若干相似度計算實現算法的基礎之上，提出了基于相似度綜合計算的本體映射生成算法。該算法的具體實現能夠提高本體映射準確度，避免出現因為某種計算方法出現較大誤差而影響映射結果。

參考文獻：

[1] Rahm E，Bernstein P A.A Survey of Approaches to Automatic Schema Matching[J].TheVLDB Journal.2001，10(4):334-350.

[2] 唐杰，梁邦勇.語義Web中的本體自動映射[J].計算機學報，2006，11:5-16.

[3] Noy N，Musen M.The PROMPT Suite:Interactive Tools for Ontology Merging and Mapping[J]. International Journal of Human-Computer Studies，2003:18-45.

[4] Do H H，Rahm E.COMA—A System for Flexible Combination of Schema Matching Approaches[C]. Proc of the 28th Intl.Conf.on Very Large Database，2002:610-621.

[5] Dynamic Programming Algorithm(DPA) for Edit-Distance[EB/OL]. http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/.

[6] 顏偉，荀恩東.基于WordNet的英語詞語相似度計算[C].第二屆全國學生計算語言學研討會論文集，北京，2004.

[7] 肖文芳.基于相似度計算的本體映射研究與實現[D].中南大學碩士論文，2007:21-34.

[8] 郭鑫.基于本體的異構數據集成技術的研究和實現[D].北京信息控制研究所碩士論文，2008:37.