一種基于冗余消除的本體映射后處理方法
2012-04-29 00:00:00徐德智黃旭
計(jì)算技術(shù)與自動(dòng)化 2012年3期
摘要：現(xiàn)有的本體映射研究大多只關(guān)注映射方法本身，而缺乏對(duì)映射結(jié)果的具體分析，使得已有的映射結(jié)果供本體重用時(shí)應(yīng)用效率不高。因此，本文提出一種基于冗余消除的本體映射后處理方法來對(duì)已有映射結(jié)果進(jìn)行處理，以獲得最優(yōu)基礎(chǔ)映射集，提高本體映射重用的效率。實(shí)驗(yàn)結(jié)果表明，本文方法在精簡映射規(guī)模和提高映射重用效率上的表現(xiàn)均較優(yōu)。
關(guān)鍵詞：本體映射；冗余映射；最優(yōu)基礎(chǔ)映射；映射后處理
中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A
An Ontology Mapping Debugging Method Based on Redundancy Elimination
HUANG Xu，XU Dezhi
（School of Information Science and Engineering， Central South University ， Changsha410083，China）
Abstract：The existing ontology mapping researches are mostly only concerned with the mapping methods itself， but lack of specific analysis of the mapping results， so the efficiency of ontology reusing by existing mapping results is always not high. Therefore， we propose a new method based on redundancy elimination to debug the ontology mapping results and obtain the set of optimal based mapping elements. Our goal is to improve the efficiency of reuse of ontology mapping. The experimental results show that our mentod can acquire good results.
Key words：ontology mapping； redundant mapping； optimal based mapping； mapping debugging
1引言
本體作為語義Web的核心基礎(chǔ)元素，在語義網(wǎng)及相關(guān)語義處理的研究領(lǐng)域得到了廣泛應(yīng)用。本體映射是分布式環(huán)境下實(shí)現(xiàn)不同本體間共享和交流的基礎(chǔ)性任務(wù)，也是本體重用和本體集成的關(guān)鍵環(huán)節(jié)。隨著本體應(yīng)用的不斷發(fā)展，本體映射已成為當(dāng)前語義Web研究的重點(diǎn)和熱點(diǎn)。
目前，對(duì)于本體映射的研究，大多數(shù)的工作都是專注于本體映射本身的算法，關(guān)注如何通過概念相似度、本體結(jié)構(gòu)等信息來獲得本體映射結(jié)果，而對(duì)已獲得的映射結(jié)果還缺乏有效的后處理過程來提高映射結(jié)果重用的效率，因此，本文針對(duì)映射中存在的問題提出一種基于冗余消除的映射后處理方法來對(duì)映射結(jié)果進(jìn)行精簡獲得一個(gè)最優(yōu)映射集，以提高映射重用的效率。
2相關(guān)研究
解決本體異構(gòu)的關(guān)鍵是本體映射，而本體知識(shí)共享的關(guān)鍵是本體映射結(jié)果的重用，本文的目標(biāo)是對(duì)已有的本體映射結(jié)果進(jìn)行后處理來提高其映射結(jié)果重用的效率。本節(jié)，首先介紹相關(guān)本體映射方法的研究，然后介紹相關(guān)的本體映射后處理方法的研究，接著分析這些方法中存在的不足。
當(dāng)前的本體映射的匹配方法主要分為元素級(jí)匹配和結(jié)構(gòu)級(jí)匹配[1]，元素級(jí)匹配方法主要包括：基于字符串比較的技術(shù)，該方法利用本體實(shí)例的名稱、標(biāo)簽、注釋等信息的字符編輯距離來進(jìn)行匹配；基于語言學(xué)特征的技術(shù)；基于約束的技術(shù)，本體中約束主要用來定義內(nèi)部信息，如概念類型、屬性的基數(shù)、唯一性和可選性等，這些信息都為映射發(fā)現(xiàn)提供了有效的信息；基于外部語言資源的技術(shù)，它主要是利用WordNet、HowNet等語義知識(shí)庫來進(jìn)行映射。結(jié)構(gòu)級(jí)匹配方法主要包括：基于圖結(jié)構(gòu)的技術(shù)，該方法將本體輸入轉(zhuǎn)換成有向圖，然后在圖結(jié)構(gòu)中計(jì)算本體實(shí)例的匹配；基于從屬關(guān)系的技術(shù)，該方法仍然是利用圖理論進(jìn)行匹配，不過只考慮了節(jié)點(diǎn)間的特殊關(guān)系；基于模塊的技術(shù)，它處理基于語義解釋的輸入，運(yùn)用推理技術(shù)進(jìn)行映射。
相對(duì)于大量的本體映射方法的研究，僅有一些少量的工作關(guān)注本體映射結(jié)果的處理，如HeB[2]提出如何將已有的映射結(jié)果作為第三個(gè)本體的訓(xùn)練數(shù)據(jù)或背景知識(shí)來提高映射的準(zhǔn)確性的方法；Zhao等人[3]將映射結(jié)果進(jìn)行迭代映射發(fā)現(xiàn)來尋找丟失的映射；Parsia等人[4]利用描述邏輯推理模塊對(duì)本體進(jìn)行后處理來查找不可滿足的類，并以此為依據(jù)來修改他們的OWL本體。
以上介紹的本體映射方法大多都是基于本體概念的元素級(jí)和結(jié)構(gòu)級(jí)的相似性進(jìn)行匹配的，這種映射關(guān)系沒有將語義上的約束關(guān)系考慮進(jìn)來，因此映射結(jié)果會(huì)存在語義不一致性和映射冗余等不合理的情況。而已存的一些本體映射后處理方法雖然在一定程度上對(duì)映射結(jié)果的上述缺陷做了彌補(bǔ)，但是并不能保證最終的的映射結(jié)果是一個(gè)最優(yōu)的映射集，因此，當(dāng)映射結(jié)果作為本體重用的資源時(shí)會(huì)存在重用效率不高的缺點(diǎn)。
計(jì)算技術(shù)與自動(dòng)化2012年9月
第31卷第3期徐德智等：一種基于冗余消除的本體映射后處理方法
針對(duì)以上不足，為了提高本體重用的效率，本文提出一種基于冗余消除的方法對(duì)本體映射結(jié)果進(jìn)行后處理來優(yōu)化映射結(jié)果，以獲得一個(gè)最優(yōu)基礎(chǔ)映射集。本文第3節(jié)首先對(duì)映射冗余的問題進(jìn)行描述，然后給出最優(yōu)基礎(chǔ)映射集的相關(guān)定義，最后詳細(xì)介紹本文的基于冗余消除的映射后處理方法；第4節(jié)通過實(shí)驗(yàn)驗(yàn)證文中方法的有效性；第5節(jié)總結(jié)本文的工作，同時(shí)對(duì)后續(xù)研究方向作展望。
3基于冗余消除的映射后處理
3.1問題描述
本體映射是要在源、目標(biāo)本體間建立一種實(shí)體間的映射關(guān)系，定義1給出了本體映射的具體描述[5]。
定義1. 本體映射可以描述為一個(gè)三元組
本體映射的目標(biāo)不僅僅是要發(fā)現(xiàn)實(shí)體間的映射關(guān)系，它的最終目的是實(shí)現(xiàn)異構(gòu)本體間的知識(shí)共享，或者是重用映射結(jié)果供第三方使用，因此，我們需要保證已獲得的映射結(jié)果應(yīng)該是一個(gè)精簡的，最優(yōu)的映射集，以提高映射重用的效率。下面給出一個(gè)映射結(jié)果中存在冗余映射的實(shí)例，說明對(duì)映射結(jié)果進(jìn)行后處理，消除冗余的必要性。冗余映射實(shí)例如圖1所示。
圖1冗余映射實(shí)例
在圖1（1）中，存在映射
3.2相關(guān)定義
定義2. 在源、目標(biāo)本體Os，Ot的映射M中，若存在一個(gè)映射對(duì)m’∈M，m’=
1）如果R’是蘊(yùn)含關(guān)系，M中存在AB，且A在C連接根節(jié)點(diǎn)的路徑上，D在B連接根節(jié)點(diǎn)的路徑上。
2）如果R’是蘊(yùn)涵于關(guān)系，M中存在AB，且C在A連接根節(jié)點(diǎn)的路徑上，B在D連接根節(jié)點(diǎn)的路徑上。
3）如果R’是不相交關(guān)系⊥，M中存在A⊥B，且A在C連接根節(jié)點(diǎn)的路徑上，B在D連接根節(jié)點(diǎn)的路徑上。
定義3. 在源、目標(biāo)本體Os，Ot的映射M中，若存在子集m∈M滿足以下兩個(gè)條件，則認(rèn)為m是最優(yōu)基礎(chǔ)映射集：
（1）m中不存在冗余映射m’；
（2）Os，Ot中的映射關(guān)系M都可以由m中的映射對(duì)推導(dǎo)出。
定義2和定義3給出了冗余映射和最優(yōu)基礎(chǔ)映射集的具體描述，在一個(gè)已有映射結(jié)果的基礎(chǔ)上，通過消除冗余映射，并保證保留的映射能推導(dǎo)出其他合理的映射對(duì)，則獲得了一個(gè)最優(yōu)基礎(chǔ)映射集。在兩個(gè)待映射的本體中，它的最優(yōu)基礎(chǔ)映射集是唯一存在的。本文下節(jié)內(nèi)容給出在已有映射結(jié)果的基礎(chǔ)上求解最優(yōu)基礎(chǔ)映射集的映射后處理方法的具體實(shí)現(xiàn)。
3.3冗余消除
在本小節(jié)，本文提出一種基于冗余消除的本體映射后處理方法，本文方法處理的對(duì)象是兩個(gè)組織成樹結(jié)構(gòu)的本體，因此首先需要將本體中的概念按父子關(guān)系組織成樹結(jié)構(gòu)，然后再根據(jù)已有的映射結(jié)果求解最優(yōu)基礎(chǔ)映射集。
本文在本體樹結(jié)構(gòu)及已有映射結(jié)果的基礎(chǔ)上求解最優(yōu)基礎(chǔ)映射集的方法描述為OptimalByTree函數(shù)，含有兩個(gè)節(jié)點(diǎn)參數(shù)n1和n2，它計(jì)算以n1和n2為根節(jié)點(diǎn)的兩個(gè)樹結(jié)構(gòu)的本體的最優(yōu)基礎(chǔ)映射集，OptimalByTree函數(shù)的偽代碼描述如下。
OptimalByTree（node n1， node n2）
1.{
2.if（！NodeSubTo（n1，n2））
3.foreach c1 in n1.childnodes do
4.OptimalByTree（c1，n2）//遞歸調(diào)用
5.else{
6.reachlastnode←1；
7.foreach c2 in n2.childnodes do
8.if（OptimalByTree（n1，c2）） //遞歸調(diào)用
9.reachlastnode←true；
10.if（！reachlastnode）
//添加最優(yōu)基礎(chǔ)映射對(duì)
11.then AddOptMapping（n1，n2）
12.return true；
13.}
14.return 1；
15.}
在OptimalByTree函數(shù)中，調(diào)用了另外兩個(gè)函數(shù)NodeSubTo和AddOptMapping，它們的兩個(gè)輸入?yún)?shù)也都是本體樹中的概念節(jié)點(diǎn)，其中NodeSubTo函數(shù)是根據(jù)已有的映射結(jié)果判斷兩個(gè)輸入概念節(jié)點(diǎn)是否存在蘊(yùn)含關(guān)系，若存在蘊(yùn)含關(guān)系則返回真值，若不存在蘊(yùn)含關(guān)系則返回假值；AddOptMapping函數(shù)是當(dāng)找到了一個(gè)最優(yōu)基礎(chǔ)映射對(duì)后，將其添加到映射集合中，這個(gè)集合的最終結(jié)果即為最優(yōu)基礎(chǔ)映射集。
OptimalByTree函數(shù)求解最優(yōu)基礎(chǔ)映射集的過程是一個(gè)遞歸執(zhí)行的過程，在第2行，它首先利用已有的本體映射結(jié)果判斷兩個(gè)節(jié)點(diǎn)n1，n2是否存在蘊(yùn)含關(guān)系，如果存在蘊(yùn)含關(guān)系，則執(zhí)行第7行遍歷n2的所有子節(jié)點(diǎn)，如果n2沒有子節(jié)點(diǎn)，則執(zhí)行第10行直接添加一個(gè)最優(yōu)基礎(chǔ)映射集，如果n2有子節(jié)點(diǎn)，則執(zhí)行第8行，這一步遞歸調(diào)用OptimalByTree函數(shù)，這一步，OptimalByTree函數(shù)又將n1和n2的子節(jié)點(diǎn)c2看做是兩個(gè)本體子樹的根節(jié)點(diǎn)進(jìn)行最優(yōu)基礎(chǔ)映射集的求解，并根據(jù)子調(diào)用OptimalByTree的返回值給布爾變量reachlastnode賦相應(yīng)的值，然后父調(diào)用OptimalByTree函數(shù)返回true值；如果n1，n2之間不存在蘊(yùn)含關(guān)系，則執(zhí)行第3行，遍歷n1的子節(jié)點(diǎn)，然后在n1的子節(jié)點(diǎn)c1和n2之間遞歸調(diào)用OptimalByTree函數(shù)，并返回1值。
由于OptimalByTree在執(zhí)行過程中只對(duì)蘊(yùn)含關(guān)系進(jìn)行映射進(jìn)行了處理，在實(shí)際的本體映射集中，還存在蘊(yùn)含于的關(guān)系，因此，我們可以對(duì)兩個(gè)本體執(zhí)行兩遍OptimalByTree，一遍是以n1作為左參數(shù)，以n2作為右參數(shù)，另一遍是以n2作為左參數(shù)，以n1作為右參數(shù)。最后，由AddOptMapping添加的映射集即為最后的最優(yōu)基礎(chǔ)映射集，這個(gè)映射集中不再包含冗余映射對(duì)，且原有的映射結(jié)果都可以由該映射集中的映射對(duì)推導(dǎo)而來，因此，當(dāng)利用這個(gè)最優(yōu)基礎(chǔ)映射集做本體映射重用的資源時(shí)，其精簡的規(guī)模及可推導(dǎo)的信息完整性可以提高第三方使用者的效率。
4實(shí)驗(yàn)及分析
基于本文方法的映射后處理系統(tǒng)命名為OptBaseMapp，由于本文方法獲得的最優(yōu)基礎(chǔ)映射集，可以通過推導(dǎo)來獲得所有合理的實(shí)體映射，而已存本體映射系統(tǒng)ASMOV[6]也是基于推理的思想來實(shí)現(xiàn)本體映射， 因此，本文實(shí)驗(yàn)是在ASMOV獲得的已有映射結(jié)果的基礎(chǔ)上進(jìn)行基于OptBaseMapp系統(tǒng)的映射后處理來驗(yàn)證本文方法在精簡映射規(guī)模和提高本體重用效率方面的有效性。表1給出了實(shí)驗(yàn)的測(cè)試數(shù)據(jù)集的信息，這些數(shù)據(jù)信息可以從OAEI的網(wǎng)站上獲得，實(shí)驗(yàn)的運(yùn)行環(huán)境是Windows XP SP3操作系統(tǒng)，Pentium（R） 4，2.9GHz CPU，1G DDR2 內(nèi)存。
表1測(cè)試數(shù)據(jù)集信息
#
DataSet pair
Node count
Max depth
1
Staff Employee
45/49
5/5
2
Tourism Visitor
230/275
11/12
3
Mouse Human
2875/3011
20/22
在表1所示測(cè)試集上，ASMOV獲得的映射對(duì)為總映射數(shù)（Total mapping number），OptBaseMapp的后處理獲得的映射數(shù)目是最優(yōu)映射數(shù)目（Optimal mapping number），實(shí)驗(yàn)結(jié)果如表2所示，Reduction衡量映射結(jié)果的精簡程度及供第三方使用時(shí)的運(yùn)算效率。
表2實(shí)驗(yàn)結(jié)果對(duì)比
#
ASMOV
OptBaseMapp
Reduction
Total
number
Run
time（ms）
Optmapp
number
Run
Time（ms）
Number
（%）
Run
time（%）
1
40
450
12
300
70
33
2
212
825
80
645
62
22
3
2100
1563
760
1054
64
34
表2中本體規(guī)模的數(shù)目都是以個(gè)為單位，運(yùn)行時(shí)間是以毫秒（ms）為單位，由實(shí)驗(yàn)結(jié)果可知，本文方法對(duì)ASMOV獲得的結(jié)果進(jìn)行映射后處理后，消除了原有映射結(jié)果中的冗余映射，獲得最優(yōu)基礎(chǔ)映射集，映射結(jié)果的規(guī)模精簡程度為62%～70%，這為映射結(jié)果的存儲(chǔ)節(jié)約了空間；映射結(jié)果供本體重用耗用的運(yùn)行時(shí)間也得到提高，提高范圍為22%～34%，實(shí)驗(yàn)表明對(duì)已有映射結(jié)果的基于冗余消除的后處理可以精簡映射規(guī)模而不失語義完整性，并提高了本體映射重用的效率。
5總結(jié)
本文針對(duì)當(dāng)前的本體映射研究大多只關(guān)注映射本身，而缺乏對(duì)映射結(jié)果的分析的現(xiàn)狀，提出一種基于冗余消除的本體映射后處理方法，通過定義冗余映射、最優(yōu)基礎(chǔ)映射集等概念，并提出一種在本體樹中遞歸查找最優(yōu)基礎(chǔ)映射的方法對(duì)已有映射結(jié)果進(jìn)行后處理，消除冗余，精簡映射規(guī)模來提高本體映射重用的效率。實(shí)驗(yàn)結(jié)果表明，該方法合理有效。
下一步工作將關(guān)注于對(duì)映射結(jié)果的修正，不只是對(duì)冗余映射的消除，而應(yīng)關(guān)注怎樣修正沖突映射，添加遺漏映射等等工作，研究重點(diǎn)除了精簡映射規(guī)模外，還將包括提高映射的準(zhǔn)確性。
參考文獻(xiàn)
[1]P.Shvaiko， J.Euzenat， T.Heath. Ontology Maching（OM2011）[C].In proc of the ISWC’11 International Workshop， Germany，2011.
[2]A.Heb. An Iternative Algorithm for Ontology Mapping Capable of Using Training Data[C].In proc of the 3rd European Semantic Web Conference， 2006.
[3]Zhao YY，Hu W， Qu YZ. Discovering Missing Mappings based on Neighboring Similarity[C].In proc of China National Computer Conference，2007.
[4]A.Kalyanpur，B.Parsia. Repairing Unsatisfiable Concepts in OWL Ontologies[C].In proc of the 3rd European Semantic Web Conference，2006.
[5]Qiu Ji， Peter Haase. Combination of Similarity Measures in Ontology Matching Using the OWA Operator[J]. Studies in Fuzziness and Soft Computing，2011，（265）：271—295.
[6]Yves R，Jean M，Shironoshita. Ontology matching with semantic verification[J].Web Semantic：Science，Services and Agents on the World Wide Web，2009，7（3）：235—251.
