一种改进的基于结构特征的本体匹配算法.docx

一种改进的基于结构特征的本体匹配算法.docx

《一种改进的基于结构特征的本体匹配算法.docx》由会员分享，可在线阅读，更多相关《一种改进的基于结构特征的本体匹配算法.docx（10页珍藏版）》请在冰点文库上搜索。

一种改进的基于结构特征的本体匹配算法

一种改进的基于结构特征的本体匹配算法

摘要：

设计了一种改进的基于结构特征的相似度计算方法，给出相应的本体匹配算法设计，并验证提出的匹配算法的可行性和有效性。

应用改进的本体匹配算法实现异构本体的匹配，从而有效提高本体匹配的精确度，提高信息搜索的准确率。

关键词：

本体；本体匹配；结构特征；相似度算法

0引言

　　Web应用已深刻影响到人类社会生活的各个方面。

语义Web是当前Web的一种扩展，是很多智能应用实现的基础，并已在电子商务、数字图书馆、信息检索、知识工程和生物医学等领域中发挥重要作用。

　　本体形式化定义了领域内共同认可的知识，是语义Web体系的核心部分。

但由于本体创建和使用的主观性、自治性和分布性，造成了本体异构的问题。

本体异构已成为本体应用的一大瓶颈，本体匹配正是解决这一问题的最有效途径。

它可以实现不同本体的应用程序间的互操作性。

本体匹配对于本体映射与集成、本体的检索和重用、信息集成、语义Web服务的匹配以及基于本体的软件需求工程等是不可缺少的重要环节。

　　解决本体匹配问题对于语义Web、生物医学、WebService、智能Agent通讯、P2P、电子商务、情报科学、软件工程和地理信息系统等领域中的语义信息交互都具有重要的应用价值。

　　国内外许多著名的大学、实验室和研究机构都对本体匹配进行了研究，并且针对进行本体匹配的过程、本体匹配的方法以及本体匹配所采用的技术和工具的研究都取得了一定的成果，为我们今天的研究提供了极有价值的基础。

　　目前的本体匹配工具和方法大都是针对特定领域的本体或本体的某些特征效果比较明显，缺少综合利用本体中各种特征元素进行映射的方法。

而且本体匹配方法主要侧重于本体概念本身，以及概念的实例信息来求取本体元素的语义相似性，并没有充分挖掘本体结构中概念的相邻元素及其语义联系。

　　因此，本文在分析现有基于结构特征的本体匹配方法的基础上，设计一种改进的基于结构特征的相似度计算方法，并给出本体匹配算法设计。

最后，应用改进的本体匹配算法实现异构本体的匹配，并验证该匹配算法的可行性和有效性。

　　1基于结构特征的本体匹配算法分析

　　基于结构特征的本体匹配通过分析实体在模式中的位置比较周围节点的信息来计算相似度，该方法在本体缺乏充分的文本信息时尤为适用。

在结构匹配方法中主要用到了图结构、路径结构、分类结构的匹配模式，这些方法大部分融入了相似度传播的思想。

　　在概念相似度计算过程中，概念的结构特点同样是值得重点考虑的因素。

基于结构特征的本体匹配算法的核心是相似度传播算法，而相似度传播算法中较为典型的是SimilarityFlooding和GMO。

它们的核心思想主要基于：

如果两个概念的父类或者子类相似，那么这两个概念也可能相似，基于此特征把该两个概念的父类或子类的相似度通过相似度传播算法传播到两个待匹配概念中。

它们之间主要区别在于SimilarityFlooding相似度的传播只考虑已匹配的概念对邻居节点的传播，而GMO则是本体全局的相似度传播。

　　1.1SimilarityFlooding算法分析

　　SF是由斯坦福大学（StanfordUniversity）的SergeyMelnik和德国莱比锡大学ErhardRahm于2002年提出的一种匹配多种数据源的通用结构层次算法，算法思想是基于相邻概念节点之间的相似传递性，也就是说如果两个概念节点的邻近节点是相似的，那么它们趋向于相似，即两个元素之间的相似性繁殖到了它们各自的邻居。

　　1.2GMO算法分析

　　GMO中使用RDF二部图模型来表示本体。

其主要思想是：

两个来自不同本体的实体的相似度来源于所有与它们连接的statement节点之间的相似度的累加，而statement节点之间的相似度又来源于与它们相连接的subject，predicate和object之间的相似度的累加。

其存在的缺点：

本体图结构相差太大，本体存在多对多匹配的情况，因此会产生匹配结果相似度很低但却有可能匹配的问题。

尽管有向二部图清晰地表示了本体知识，但是它没有区分概念间的不同关系，而且没有考虑不同邻接概念对于相似度传播的影响不同。

　　2基于结构特征的本体匹配算法改进设计

　　2.1基于结构特征的本体匹配算法思路

　　本体包含概念、属性和实例，这三个元素是本体的实体元素，另外本体还包含连接实体的关系、公理等。

映射基本上在实体元素之间进行的，而且通过简单的推理后都转化为概念—概念映射关系。

因此在本文中，着重讨论的是概念—概念映射的相似度计算问题，并对其进行一些改进。

　　本体实质上就是一个树状层次结构，利用Protégé等工具，可以将本体以树结构显示。

结合对几个基于结构的相似度算法的分析和比较，本文提出了基于概念在结构中深度和密度对相似度传播值的影响。

　　为了说明处于结构中不同深度和密度情况下相似度传播的差异性，我们将Vehicle本体表示成如图1所示的树状层次结构，以此来讨论，该本体默认关系为subclassof。

在图中只有一个入口结点，为根结点，这个结点是最大概念。

第2层结点是对入口结点第1层结点的划分，第3层结点又是在第2层结点的基础上进一步细化，以此类推。

我们可以看到，每一层都是对上一层概念的细化。

越到下层，概念越细化，含义就越具体，反之越上层概念则越抽象。

　　假设通过语言级匹配后，得出源本体中的Vehicle和Car概念和目标本体中的Vehicle和Car概念存在匹配关系，现进行结构级的相似度传播。

我们先讨论Vehicle子类和Car子类的匹配情况，由于Car相对于Vehicle处于结构层次的下层，概念含义更加具体细化，因此Car的子类匹配可能性要比Vehicle大，固概念Vehicle对子类的相似度传播值要小于Car对其子类的相似度传播。

我们再讨论同一层次的Plane子类和MotorVehicle子类的匹配情况，由于MotorVehicle概念的分类更加细化，结点密度相对大一些，因此MotorVehicle子类匹配可能性要比Plane大，固概念Plane对子类的相似度传播值要小于MotorVehicle对其子类的相似度传播。

根据以上分析可知，处于结构中不同位置的概念，它们的相似度传播是有差异的，相似度传播计算应该和概念在层次结构中的深度和密度有关。

　　2.2基于概念结点深度和密度的相似度传播算法

　　针对以往相似度传播算法中存在的不足，本文提出了基于结构中概念结点深度和密度的相似度传播算法，并制定相似度传播公式，从概念所在结构中的深度和密度综合考虑对相似度传播值的影响。

（1）抽取本体中的概念，将概念结点近似构成一棵本体树（设Root为根结点概念，D（Root）=1），则任一非根概念结点x在本体树中的深度值D（x）为：

D（x）=D（parents（x））+1

（1）式中，D（x）为概念结点x的深度值，parents（x）为x的双亲结点。

D（x）的值为[1，+∞]。

　　由于从根结点到一个概念结点可能存在多条不同的路径，因此有通过不同路径计算得到不同深度值的情况，在此，D（x）取深度值最大的一个，而此深度值对应的父结点即为parents（x）。

（2）结点x的深度系数：

Dd（x）=12+…+12D（x）-2+12D（x）-1+12D（x）=

　　∑D（x）n=112n

（2）当只有根结点时，深度系数为0.5，对于非根结点x的深度系数的值在大于0.5而无限接近于1之间，即为（0.5，1）之间，结点深度值越大，深度系数值也越大。

　　（3）结点x的密度系数：

Dc（x）=indegree（x）+outdegree（x）indegree（O）+outdegree（O）（3）式中x为概念结点，O为本体，以概念结点x所连接边的出度、入度之和与本体的出度、入度之和相比来计算结点x的密度，Dc（x）的值在大于0而小于等于1之间，当本体的出度、入度之和一定时，结点x的出度、入度之和越大，即结点密度越大时，则Dc（x）的值越大。

　　（4）综合概念结点的深度和密度系数，定义相似度传播因子W，W的值应在[0，1]之间W=α（Dd（x）+β（Dc（x）

　　α+β=1（4）其中，Dd（x）为结点的深度系数、Dc（x）为结点的密度系数。

α、β的取值应该来自于领域经验值。

但是，目前己有的研究成果中，尚没有足够的数据帮助我们求得基于本体的数据集成领域的这一经验值，在实际应用中，可以先取一组样本，变换α、β的取值求得多组实验结果，然后进行分析，从中选出合适的W值。

　　可见，W值随着结点深度和密度的增加而增加，以W值来影响相似度传播值的大小，则W值越大，相似度传播值越大。

　　（5）相似度传播公式：

stk+l=stk+∑i∈M（t）Wi*sik（5）其中t=l，2…n；k=l，2…n；stk+l表示概念对t第k+l次迭代的相似度值；stk为概念对t第k次迭代的相似度值；M（t）表示概念对t的邻居中已匹配概念对的集合；sik表示t的邻居概念对i在k次迭代时的相似度值。

最后进行标准化，将概念对之间的相似度除以相似度最大值，保证其值在[0，1]之间。

经多次迭代，直到达到收敛要求为止。

　　2.3相似度传播算法设计

（1）基于结构中深度和密度的相似度算法描述如下：

　　输入：

本体O1和O2

　　输出：

本体匹配表

　　步骤1：

为了正确地引导匹配，减少不必要的候选匹配对，提供相关的匹配信息，在匹配前做好以下预处理工作：

使用Wordnet或字符串匹配方法算出节点间的初始化相似度值，并选取相似度值较高的相似对作为初始相似对，利用Protégé等工具将本体分解成概念树的形式；

　　步骤2：

根据初始相似对中概念结点的深度和密度，计算概念结点对邻接概念结点的相似度传播因子。

　　步骤3：

利用相似度传播公式，多次迭代计算待匹配概念结点的相似度值。

　　步骤4：

利用稳定婚姻算法确定映射概念对。

（2）传播算法设计。

针对以上分析，本文给出相似度传播的改进算法主要过程。

caculate_w（），是相似度传播因子计算函数，其实现方法在2.2节中介绍。

similarityPropagate（），是相似度传播函数，其实现内容采用了2.2节中公式3～5。

相似度传播是一个迭代过程，迭代至达到收敛要求。

　　输入：

O1，O2

　　输出：

finalmappingbetweenO1andO2

　　StructSimilarity（）{

　　Preprocess（）；//WordNet初始化

　　ExtractSimilaritySeeds（）；//提取相似对

　　Do{FindSimilarPair（）；

　　Caculate_W（）；

　　Do{

　　SimilarityPropagate（）；}//计算相似度

　　While（IsConverge（SimilarityPropagate（）））}

　　While（！

AddSimilaritySeeds（））

　　S=GetSimilarity（）；}

　　ExactMapping（）

　　3改进的基于结构特征的本体匹配算法实验验证3.1开发环境和平台

　　本文采用的开发语言是Java。

使用的Jena开发包是使用Java语言开发的，使用Java更容易实现代码重用和移植。

本文选择Eclipse作为开发环境，Eclipse是开放源码的Java集成开发环境（IDE），适用于各种客户机和Web应用。

　　3.2实验设计

　　本文采用OAEI国际组织提供的测试用例集作为实验测试数据集，再通过利用信息领域的查全率、查准率或F-Measure的计算公式，计算得到相应的数值，实验结果与利用其它结构特征匹配方法生成的结果相比较，借此以分析该算法的优劣性。

　　OAEI2007提供的benchmark数据集为本文的测试数据集。

此数据集中，共包含51个本体，其中本体#101为参考本体，其它的本体均为该本体某种特征的变化或缺失后的变体。

该测试集共可分为5类：

基本测试（#101-104）、标签和注释测试（#201-210）、结构测试（#221-247）、综合测试（#248-266）和现实本体（#301-304）。

本文采用信息检索领域的查全率（r）、查准率（p）和F-Measure作为评价映射算法的主要准则，并定义如下：

（1）本体映射查全率（recall）：

　　r=发现的正确匹配对/所有存在的匹配对

（2）本体映射查准率（precision）：

　　p=发现的正确匹配对/发现的所有匹配对

　　（3）F-Measure值由查准率和查全率计算得到，综合反映了映射算法的效果：

　　F-Measure=（p（r

（2）/（p+r）

　　3.3实验结果与分析

　　为了验证改进的相似度传播算法的匹配效果，本文将使用Benchmarks测试用例集对其进行测试，并分析不同测试用例的匹配效果。

本实验单独运行基于图结构的匹配算法，将Wordnet匹配器或字符串匹配器的输出作为图结构匹配器的输入。

为取得较好的匹配效果，在挑选初始相似对时规定相似度大于某一阈值的相似对被设为种子，实验表明种子的质量会影响匹配效果，经验证阈值设为0.8时效果较好。

实验结果将与采用传统SF算法和Falcon系统的GMO模块的计算结果做比较，来分析改进的SF算法的优劣性。

由于测试用例102中的两个本体的是两个完全不同领域的本体，因此得不到结果。

　　表1改进算法与其它算法的F-Measure值比较

　　测试用例改进的SF算法SF算法Falcon系统GMO101～1040.960.950.92201～2100.930.890.93221～2470.620.690.56248～2660.500.520.53301～3040.090.130.11针对实验结果，本文进行如下分析：

（1）首先由实验结果计算Benchmarks测试用例集中各类测试用例的平均匹配结果，其中测试集中101～104包括相同的、语言泛化和约束特定的语言本体对；201～210保留了本体结构，但自然语言的信息被大大消弱，如用随机字符串替换实体名字等；221～247给出了本体结构变化的情况，如层次被扩展或去除；248～266中语言和结构信息同时被消减；301～304是实际的本体。

三种匹配方法在本体信息完整的情况下，均能取得较好的效果，而对于结构信息变化或是缺失的情况，总体匹配效果都不理想。

　　图3实验结果比较

（2）从结果中可以看出，在本体自然语言描述不足的情况下，GMO能取得较好的结果，而对于结构差异较大的两组本体，GMO匹配结果稍差。

SF相似度的计算是简单地利用繁殖系数进行迭代，因此元素的相似度只由与它同边的相似对决定，而初始相似对是由字符串等预处理方法确定，因此在前三组测试集中的效果要比GMO略好。

改进的SF，前两组的测试集实验结果的查准率和查全率方面比SF要好，但在后三组中效果相对较差，可见算法对语言和结构信息均发生变化的本体匹配效果还不佳，还需要其他匹配方法的辅助以提高精度。

　　4结语

　　本体匹配为不同个人或团体对同一客体创建的本体异质性，为数据与服务集成障碍解决了问题。

本文设计改进SF的相似度计算方法，根据结点在结构中的深度和密度情况，通过计算传播因子的方式，改进SF中繁殖系数计算相似度的方法，并给出本体匹配算法设计。

通过实验数据验证本文提出的匹配算法的可行性和有效性，从而有效提高本体匹配的精确度。

在后续研究中，还将对算法作如下改进和完善：

进一步改进和完善相似度算法，以更好地计算本体间相似度，从而提高发现映射关系的准确率。

结合多种策略，研究更深入、丰富的相似度计算问题。

　　参考文献：

　　[1]TIMBERNERS-LEE，JAMESHENDLER，ORALASSILA.Thesemanticweb[J].ScientificAmerican，2001（5）.

　　[2]JHONHEBELER，MATTHEWFISHER，RYANBLACE，etal.Web3.0与SemanticWeb编程[M].北京：

清华大学出版社，2010.

　　[3]RUDISTUDER，RICHARDBENJAMINS，DIETERFENSEL.Knowledgeengineering：

principlesandmethods[J].DataandKnowledgeEngineeing，1998（122）.

　　[4]THOMASRGRUBER.Atranslationapproachtoportableontologyspecifications[J].KnowledgeAcquisition，1993（5）.

　　[5]FRANKVANHARMELEN.Ontologymapping：

awayoutofthemedicaltowerofbabel[C].Proceedingsofthe10thConferenceonArtificialIntelligenceinMedicine（AIME05）.Aberdeen，Scotland，2005.

　　[6]陆建江，张亚非，苗壮，等.语义网原理与技术[M].北京：

科学出版社，2007.

　　[7]张悦等.基于改进相似度传播算法的本体匹配[J].计算机应用，2011（31）.

　　[8]杨小影.本体映射过程中的结构相似度改进算法[J].计算机工程与应用，2011（16）.

　　[9]吴军庆.本体映射中名称策略与结构策略改进算法研究[D].长沙：

中南大学，2009.

　　[10]汪鹏.本体映射关键问题研究[D].南京：

东南大学，2009.

　　[11]李光达.ontology映射研究[D].北京：

中国农业科学院，2009.

　　[12]吕刚，郑诚.基于加权的本体相似度计算方法[J].计算机工程与设计，2010（5）.

　　[13]BRUCEECKEL.Java编程思想[M].北京：

机械工业出版社，2005.

　　[14]NetBeans[EB/OL].http：

//zh-beans.org/，2009.

　　[15]10ntologyAlignmentEvaluationInitiative[EB/OL].http：

//oaei.inrialpes.fr.2007.

　　[16]靳涛.面向语义Web的多策略本体映射研究[D].苏州：

苏州大学，2008.

　　TheImprovingOntologyMatchingAlgorithm

　　basedonStructuralFeatures

　　Abstract：

ThetextdesignstoimprovesimilaralgorithmmethodsbasedonthestructuralfeaturesandrespondtoOntologymatchingdesignandprovethefeasibilityandeffectivenessofmatchingalgorithminthetext.UsingtheOntologymatchingalgorithmtorealizethematchofheterogeneousontologies，whichcanimprovethematchingaccuracyandraisetheaccuraterateofinformationsearching.

　　KeyWords：

Ontology；OntologyMatching；StructuralFeatures；SimilarityAlgorithm