一種新的基于相似度計算的本體映射算法
2009-01-01 00:00:00吳雅娟陳堯尚福華
計算機應用研究 2009年3期
(大慶石油學院 計算機與信息技術學院， 黑龍江 大慶 163318)
摘 要：領域本體在知識的共享和重用方面起著重要的作用。本體映射是解決本體異構，在不同本體間建立語義關聯的一種有效的方法。針對不同本體間的本體概念映射提出了一種新的概念相似度的綜合計算方法，從本體概念名稱、屬性、結構和實例四個方面討論本體概念的相似度，同時提出在涉及概念名稱和屬性名稱時，使用其同義詞擴展集參加計算，計算綜合相似度時，分別用手工和自動的方法賦予權值。實驗證明改進的算法提高了本體概念映射的查全率。
關鍵詞：本體; 本體映射; 相似度; 算法
中圖分類號：TP311 文獻標志碼：A
文章編號：10013695(2009)03087003
New similaritybased approach for ontology mapping
WU Yajuan， CHEN Yao， SHANG Fuhua
(School of Computer Information， Daqing Petroleum Institute， Daqing Heilongjiang 163318， China)
Abstract:Domain ontology plays a key role in knowledge share and reuse. Ontology mapping is an effective method of solving the heterogeneity of ontology and setting up semantic relevance. Aiming at ontology mapping between different ontology， this paper proposed a new synthesized algorithm of concept similarity. The presented algorithm involved concept name， attribute， structure and instance levels， at the meantime used the extended synonym set in computing concept similaritybased concept name and attribute name. The experiment shows that the improved algorithm outperforms in precision of ontology concept mapping.
Key words：ontology; ontology mapping; similarity; algorithm
0 引言
本體在軟件工程、人工智能、知識工程、信息檢索、Web服務發現等領域中扮演著越來越重要的角色。隨著本體研究的不斷深入，研究者們創建了越來越多的本體，由于構建者出于不同的應用角度和對客觀事物的不同理解，導致同一領域內會有相互獨立的異構本體存在。如何解決不同本體間的知識共享和重用成為一個比較關鍵的問題。本體映射是目前解決本體異構的有效方法。本體映射的一個關鍵步驟就是進行概念或實體間相似度的計算[1，2]。
目前關于本體映射的研究中，相似度計算大部分是基于一個本體的，不同本體間的計算方法不多。本文首先簡介基本的計算方法；然后在基本算法的基礎上改進對概念名稱和概念屬性及概念非層次關系的處理，提出了綜合考慮本體概念名稱、屬性、實例以及概念間的語義關系的相似度計算方法，從而改進現有的本體映射算法。
1 本體及本體映射的基本概念
根據Studder的定義，本體是共享概念模型的明確形式化規范說明，它提供了一種明確的形式化的領域知識描述手段，同時支持對隱含知識進行推理，在信息集成和知識管理等領域發揮著重要的作用。本體的形式化的定義為O={C，R，HC，HR，A，I}。其中：C是領域概念的集合；R為概念間的層次關系；HC為概念間的其他關系，如Same As關系、Part of關系、Contains關系等，它們是概念集笛卡爾積的子集；HR定義了關系之間的層次結構；A是公理的集合，代表永真斷言；I是本體實例的集合。所謂本體映射是指不改變原有的本體并在本體間建立關聯，以便雙方能使用通用的接口對同一事物達成共同的理解。本體映射可以在存在語義級概念關聯的兩個本體中，通過語義的聯系，實現將源本體的實體（概念、實例、屬性等）映射到目標本體實體上。其中概念映射是最常用的方法。對于本體工程中本體映射的研究，已有大量的方法和技術，如ONION系統[3]、MAFRA框架[4]、Ontolearn系統[5]、IFMap系統[6]、SF方法[7]、GLUE系統[8]等。
2 概念相似度計算的基本方法
本體映射的一個關鍵步驟是概念間的相似度計算。概念間的相似度計算可以從多個角度、多種層次上進行考慮。概念間的語義相似度在本體映射中發揮重要的作用。概念間的語義相似度是概念在特征描述上的相似程度，定義為概念在層次結構中的語義距離。不同領域的學者針對語義相似度的計算，建立了多種的模型，主要分為基于特征的模型、基于語義距離的模型、基于信息內容的模型以及混合模型。
基于特征的模型主要是通過屬性的集合考慮概念間的相似度?；谡Z義距離的模型主要利用概念的層次結構信息考慮概念間的相似度，多數用于同一本體中。基于信息內容的方法主要利用概率模型表示概念間的相似度。混合模型綜合利用集合論、層次結構和屬性結構等信息計算實體類型間的語義相似度。
3 改進的概念相似度計算方法
本文針對現有一些相似度計算方法的不足，進行了一些改進，主要針對異構本體間的概念映射綜合考慮概念名稱、屬性、實例、層次結構以及概念間關系的信息，利用同義詞集計算概念名稱和屬性名稱的相似度，通過對概念和屬性名稱的語義擴展，提高相似度計算的準確性。
3.1 概念名稱的相似度計算
根據概念名稱來計算概念間的相似度的基本想法是，如果表示概念的標志符是相同或相近的符號，其意義通常也是相同或相近的。據此，可以從語言級上對概念進行相似判斷，中文本體中常用的做法是結合知網（HowNet）常識知識庫來進行語言級相似度計算[9]。
知網的基本形式是對中文詞語的釋義和描述。詞語（概念）的意義不是通過一些其他的常用詞語來解釋、說明，而是通過義原來描述和定義，即義原是描述概念語義的最小單位。在描述語義方面各個義原的作用不是等同的，而是存在復雜的關系。在HowNet中，詞語不是組織在一個樹狀的層次體系中，而是存在一種網狀關系，如上下位關系、屬性關系、對義關系和反義關系等，其中最主要的還是上下位關系。計算概念間的相似度可以利用上下位關系構成的樹狀層次體系。假設兩個義原在該層次體系中的路徑距離為d，那么，可以得到兩個義原之間的語義相似度如下：
sim(p1，p2)=α/(d+α)
其中α是一個可調節的參數。
當考慮節點的層次深度depth時，義原之間的相似度可以按下式計算：
sim(p1，p2)=[α×min(depthp1，depthp2)]/
[d+α×min(depthp1，depthp2)]
這樣，當路徑距離相同時，節點的層次越深，相似度越高。概念中包含多個義原，每個義原的作用是不一樣的?？紤]其不同的影響，設置不同的權重因子，可以如下計算概念間的語言級相似度：
Lsim(c1，c2)=∑ni=1wi sim(p1i，p2i)(1)
其中：描述兩個概念的義原集合是c1={p11，p12，…，p2m}，c2={p21，p22，…，p2m}。假定n≤m，(p1i，p2i)是通過最大匹配得到的一組元素配對。當一個義原與空元素配對時，取其相似度為0。wi=di/∑ni=1di，di=min(depthp1i，depthp2i)。
概念間的語言級的相似度計算只是涉及到表示概念名稱的標志符。如果異構本體中，命名規則不一致，很有可能同一語義的概念在不同本體中的名稱標志符完全不同。例如概念“計算機”可以使用“電腦”“computer”“PC”和“jisuanji”等標志符命名，此時，各標志符按照式（1）計算的相似度可能為0。因此，本文提出在進行概念的語言級相似度計算之前先按照本體定義中的概念的同義詞集（Same As關系）及HowNet中的中英文注釋進行語義擴展，將計算概念c1和c2的相似度轉換為計算概念c1和c2的同義詞集的相似性。具體算法為，對c1的同義詞集中的每個元素c1i（i=1，2，…，n）和c2的同義詞中的每個元素c2j（j=1，2，…，m）計算相似度，然后取最大值作為c1和c2的語義相似度，即
Langsim(c1，c2)=max1≤i≤n1≤j≤m(Lsim(c1i，c2j))(2)
3.2 概念屬性的相似度計算
基于屬性的相似度計算的基本依據是，如果兩個概念具有完全相同的屬性，則認為兩個概念可能是相同的，根據屬性計算相似度的算法可以歸結為計算兩個概念的屬性集合的相似程度，應該不僅與兩個概念具有的相似屬性有關，而且應該與屬性對概念的影響程度及屬性集合中的元素個數有關。
比較兩個概念的屬性集合的相似度可使用Tversky計算：
ppsim(c1，c2)=｜A∩B｜/（｜A∩B｜+
α｜A-B｜+(1-α)｜B-A｜）(3)
其中：A、B分別表示概念c1、c2的屬性集合；A-B表示屬于A但不屬于B的術語集；B-A表示屬于B但不屬于A的術語集；α根據概念在各自的層次結構中的深度確定。因為同一語義的概念在本體構建中可能按不同的規則命名，例如可能使用漢語、英語或拼音等，所以單純從名稱上比較屬性集合也是不全面的。這樣，還是從考慮屬性名稱的同義詞集進行算法改進，將屬性集合A、B分別按屬性的同義詞集擴展為A′、B′，將式（2）中的A-B替換為A-B′，表示屬于A但不屬于B′的術語集；同理，B-A替換為B-A′，即
Psim(c1，c2)=｜A∩B｜/（｜A∩B｜+
α｜A-B′｜+(1-α)｜B-A′｜）(4)
3.3 概念結構及語義關系的相似度計算
概念間結構的相似度Rsim(c1，c2)計算主要考慮概念的層次關系及非層次關系，層次關系如Partof關系、Kind of關系等，非層次關系指存在一個映射關系：F:C1×C2×…×Cn-1→Cn，即可以由前n-1個決定第n個。
基本想法是將兩個概念對應的關系集合根據HowNet表示成義原的并集，然后根據兩個集合的交集的情況計算兩概念間的關系層的相似度。集合的比較與義原之間的相似度的計算與前面介紹的算法類似。
3.4 概念實例的相似度計算
在需要映射的兩個本體中，可以利用概念的具體實例計算概念相似度。一個概念的實例也是它祖先概念的實例。基于實例計算概念相似度的理論依據是，如果概念所具有的實例全部都相同，那么這兩個概念可能是相同的；如果兩個概念具有相同實例的比重是相同的，那么這兩個概念可能是相似的。用具體實例來計算概念c1和c2的相似度，記為
Isim(c1，c2)=p(c1∩c2)/p(c1∪c2)=
p(c1，c2)/[p(c1，c2)+p(c1，c2)+p(c1，c2)](5)
Isim(c1，c2)∈[0，1]，Isim(c1，c2)=0表示兩個概念完全無關；Isim(c1，c2)=1表示兩個概念完全相同[10]。
基于實例計算概念相似度涉及到三個概率，即p(c1，c2)、p(c1，c2)和p(c1，c2)。其中p(c1，c2)是從一個本體的實例空間中隨機選取的一個實例屬于c1但不屬于c2的概率，也可以理解為所有屬于c1但不屬于c2的實例在實例空間中所占的比重。因此，在計算p(c1，c2)、p(c1，c2)、p(c1，c2)時要用到概念c1和c2在各自本體中的實例個數，用Ui表示本體Oi中的實例集，N(Ui)表示實例集中的實例個數。用N(Uc1，c2i)表示在Ui中既屬于c1又屬于c2的實例個數。在存在足夠樣本的情況下，可以取一些樣本作為正反實例，通過機器學習的方法訓練學習器；然后使用學習器對實例集Ui中的實例進行分類，分成屬于ci和不屬于ci兩類。這樣通過機器學習的方法就可以獲得N（Uc1，c21)、N（Uc1，c22）、N(U1)和N(U2)，則可用式（6）計算概率：
p(c1，c2)=[N(Uc1，c21)+N(Uc1，c22)]/[N(U1)+N(U2)]
（6）
類似地可以計算p(c1，c2)和p(c1，c2)：
p(c1，c2)=[N(Uc1，c21)+N(Uc1，c22)]/[N(U1)+N(U2)]（7）
p(c1，c2)=[N(Uc1，c21)+N(Uc1，c22)]/[N(U1)+N(U2)]（8）
把式（6）~（8）代入式（5）即可求得基于實例的概念的相似度。
3.5 概念的綜合相似度的計算方法
將概念名稱相似度、屬性相似度、結構相似度和實例相似度的計算結果進行加權求和，即可求到概念的綜合相似度：
sim(c1，c2)=w1Langsim(c1，c2)+w2Psim(c1，c2)+
w3Rsim(c1，c2)+w4Isim(c1，c2)
其中：wi為權重系數，滿足w1+w2+w3+w4=1。各權重系數可以手工確定，也可以自動獲得。手工確定時需由領域專家根據不同的環境適當選擇，依賴于專家的經驗。本文確定的依據很簡單，就是給高的相似度值一個大比例的權重，而相似度值低的實際上可以被舍棄。實驗采用的方法是將計算出的四種單項相似度值按由大到小的順序排列，然后分別賦予0.5、0.3、0.1、0.1的權重系數。各權重系數也可以自動獲得，方法是使用sigmoid函數。此算法不僅對各相似度算法加權，同時對每一個相似度進行函數計算。在給定的情況下，常用的函數為sigmoid函數，它需要轉換為適合[0，1]的輸入。
sim(c1，c2)=∑4k=1wksigk(simk(c1，c2)-0.5)
其中：sig(x)=1/（1+e-αx），α為可調節參數。
4 實驗結果
4.1 實驗評價準則
本文采用信息檢索領域查全率和查準率作為評價映射算法的主要準則，并定義如下：
a)概念映射查全率（recall）
r=正確發現的概念映射/可能存在的概念映射
b）概念映射召回率（precision）
p=發現的正確概念映射/所有發現的概念映射
4.2 實驗結果
選取了油田地質領域的兩個不同的本體集，分別包括300多個概念和關系，上千個實例，手工定義了28個概念映射，按照本文的算法，平均查全率為75.3%，召回率為68.6%。實驗結果比較令人滿意，結果如圖1所示。圖中meth2表示使用同義詞集擴展的算法的平均值；而meth1是沒有使用同義詞集擴展的結果。
5 結束語
領域本體在知識的共享和重用中起到了關鍵的作用。然而由于各自建立適合自身的本體，使不同本體之間存在個體差異性，本體間也就不可避免地存在著語義沖突，研究者使用本體映射解決不同本體的概念間的語義沖突，使本體映射成為本體研究領域的重要課題。本文針對目前本體映射中概念相似度計算所存在的問題，提出了一種新的綜合的相似度計算方法。從概念名稱、屬性、結構和實例四個不同層次分別計算概念的相似度，然后加權平均求出綜合的概念相似度，并對概念名稱和屬性名稱進行同義詞擴展，在擴展集上計算概念的相似度，提高了概念映射的查全率。但是，計算過程中各個權值的設定還只是根據經驗來給定，有一定的誤差。下一步的工作計劃針對權值的設定作進一步的研究。另外，同義詞擴展的計算在一定程度上增加了計算量，以及在計算屬性的相似度時，沒有考慮屬性的優先級，而不同屬性對概念的影響因素是不同的，還需作深入的研究。
參考文獻：
[1]程勇，黃河，邱莉榕，等.一個基于相似度計算的動態多維概念映射算法[J].小型微型計算機系統， 2006，27(6)：975979.
[2]聶朝暉，王英林. 相似本體間屬性映射方法的研究[J]. 計算機仿真， 2006，23(9):133135， 148.
[3]WILLIAMS A B， TSATSOULIS C. An instancebased approach for identifying can didate ontology relations with in a multiagent system[C]//Proc of the 1st ECAI Workshop on Ontology Learning.2000.
[4]MAEDCHE A， MOTIK B， SILVA N，et al. MAFRA: a mapping framework for distributed ontologies[C]//Proc of the 13th EKAW 2002.London:SpringerVerlag， 2002.
[5]NAVIGLI R， VELARD P， GANGEMI A. Ontology learning and its application to automated terminology translation[J]. IEEE Intelligent Systems， 2003，18(1):2231.
[6]KALFOGLOU Y， SCHORLEMMER M. IFMap: an ontologymapping method based on information flow theory[J]. Journal of Data Semantics， 2003，1(1):98127.
[7]MELNIK S， GARCIAMOLINA H， RAHM E. Similarity flooding: a versatile graph matching algorithm and its application to schema matching[C]//Proc of the 18th ICDE’02.Washington DC:IEEE Computer Society， 2002.
[8]DOAN， MADHAVAN J， DOMINGOS P，et al. Ontology matching: a machine learning approach[C]//STAAB S， STUDER R. Handbook on Ontologies in Information Systems.[S.l.]:SpringerVerlag， 2003:101131.
[9]李峰，李芳. 中文詞語語義相似度計算——基于 《知網》 2000[J].中文信息學報， 2007， 21(3):99105.
[10]曹澤文，錢杰，張維明，等.一種綜合的概念相似度計算方法[J].計算機科學，2007，34(3):174175.
[11]余霞，劉強，葉丹.基于規則的關系數據庫到本體的轉換方法[J].計算機應用研究， 2008，25(3):767770.
[12]潘玉娥，梁鵬，何克清.基于分類的本體映射方法及映射工具實現[J].計算機應用研究，2007，24
(10):213215.
