（计算机软件与理论专业论文）一种本体匹配对修补工具的设计与实现.pdf

东南大学硕士学位论文 摘要 本体对于语义w e b 的发展至关重要。随着语义w e b 的发展，基于本体的应用越来越多。 本体匹配就是一个发现不同本体之间映射关系的过程，如今本体匹配已经发展成语义w e b 研究中的一个核心问题。虽然目前已存在大量自动化或半自动化的本体匹配工具，但它们的 有效性还远不能满足实际应用的需求。 本文提出了一种通用的针对本体匹配对的修补框架，该框架包含剔除错误的匹配对和寻 找缺失的匹配对两个功能模块。面向修补框架中剔除错误匹配对这一功能模块，本文提出了 一种基于聚类分析的剔除错误匹配对的方法，该方法的主要思想是将本体划分成块，通过匹 配对所在的块之间的相似度来判定匹配对是否正确。另外，面向修补框架中寻找缺失匹配对 这一功能模块，本文基于图的相似度传播理论提出了一种利用邻居相似度寻找缺失匹配对的 方法，该方法综合利用实体的自然语言信息和邻居信息来寻找新的匹配对。在这两种方法的 基础上，本文设计并实现了一个本体匹配对的修补工具p o m ，并通过实验数据分析了p o m 的性能。实验表明，p o m 确实能在基本不损失精度的情况下有效地提高本体匹配对的召回 率，使得匹配对的综合评价有所提高。 关键词：本体匹配，语义w e b ，错误匹配对，聚类分析，缺失匹配对，相似度传播 东南大学硕士学位论文 a b s t r a c t o n t o l o g yi sc r u c i a lf o rt h ed e v e l o p m e n to ft h es e m a n t i cw e b w i t ht h ed e v e l o p m e n to ft h e s e m a n t i cw e b ，t h e r ea r em o r ea n dm o r eo n t o l o g y - b a s e da p p l i c a t i o n s o n t o l o g ym a t c h i n gi sa p r o c e s so ff i n d i n gm a p p i n g sb e t w e e nd i f f e r e n to n t o l o g i e s n o wo n t o l o g ym a t c h i n gh a sb e c o m e i n t oa ni m p o r t a n ti s s u ei nt h er e s e a r c ha r e ao ft h es e m a n t i cw e b a l t h o u g ht h e r ea r eag r e a td e a l o f ( s e m i - ) a u t o m a t i co n t o l o g ym a t c h i n gt o o l sp r e s e n t l y , t h e i re f f e c t i v e n e s si ss t i l lf a ra w a yf x o m p r a c t i c a lu s a g e t h i st h e s i sp r e s e n t sag e n e r a lf i a m e w o r kf o rp a t c h i n gg i v e nm a p p i n g sg e n e r a t e db yc e r t a i n e x i s t i n gm a t c h i n gt o o l s i tc o n s i s t so ft w of u n c t i o n a lm o d u l e s ，i e e l i m i n a t i n ge r r o rm a p p i n g sa n d f i n d i n gm i s s i n gm a p p i n g s o no n eh a n d ，an e wa p p r o a c hb a s e do nc l u s t e r i n ga n a l y s i si sp r o p o s e d f o re l i m i n a t i n ge r r o rm a p p i n g s n em a i ni d e ao ft h i sa p p r o a c hi st ou s et h es i m i l a r i t yb e t w e e n b l o c k st od e t e r m i n ew h e t h e ram a p p i n gi sc o r r e c to rn o t o nt h eo t h e rh a n d ，an e wa p p r o a c hb a s e d o nt h et h e o r yo fs i m i l a r i t yp r o p a g a t i o no ng r a p h si sp r o p o s e df o rd i s c o v e r i n gm i s s i n gm a p p i n g s i i ln l i sa p p r o a c hw ec o m b i n el i n g u i s t i cs i m i l a r i t ya n ds t r u c t u r a ls i m i l a r i t yo fe n t i t i e st of i n dn e w m a p p i n g s b a s e do nt h e s et w oa p p r o a c h e s ，a na u t o m a t i ct o o ln a m e dp o m f o rp a t c h i n go n t o l o g y m a p p i n g si sd e s i g n e da n di m p l e m e n t e d f u r t h e r m o r e ，t h ep e r f o r m a n c eo fp o m i sa n a l y z e db y e x p e r i m e n t a lr e s u l t s e x p e r i m e n t a lr e s u l t sd e m o n s t r a t et h a tp o mc a ns t a b l yi m p r o v et h e e f f e c t i v e n e s so fg i v e nm a p p i n g s k e yw o r d s ：o n t o l o g ym a t c h i n g ，s e m a n t i cw e b ，e r r o rm a p p i n g s ，c l u s t e r i n ga n a l y s i s ，m i s s i n g m a p p i n g s ，s i m i l a r i t yp r o p a g a t i o n i i 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 研究生签名：赵燃日期：型鳋：生：主垒 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位 论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人 电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论 文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包 括刊登) 授权东南大学研究生院办理。 研究生签名：炎些旺导师签名：；斜日 期：型出 第一章绪论 1 1 研究背景 第一章绪论 在短短十几年的时间里，万维网( w o r l dw i d ew e b ，简称w e b ) 已经改变了我们的世界， 从购物到订购飞机票，从写博客到听音乐，w e b 已渗透到日常生活的方方面面。w e b 上的 信息非常丰富，几乎涵盖了所有的知识领域。但是由于w e b 内容的极其庞杂和目前网络信 息检索工具的性能限制，使很多人面对w e b 上巨大的信息量不知所措。在目前的w e b 中， 网页仅仅是一个简单的内容显示，计算机目前所起到的作用只是存储数据、传输数据或显示 数据，它们并不能理解存储和传输的数据的内容，如果能将目前w e b 中一个个现存的信息 孤岛，发展成一个巨大的数据库，计算机就能方便地按照用户的要求自动搜寻和检索信息了。 正是基于这个思想，w e b 的创始人t i mb e r n e r s l e e 在1 9 9 8 年提出了语义w e b ( s e m a n t i c w e b ) f 佝概念l l j ，并把语义w e b 看成是下一代w e b 的发展方向。语义w e b 的目标是为w e b 的实际信息内容提供形式化的含义，以实现信息在语义层的互操作，更便于计算机和人的协 同工作。也就是说，语义w e b 的目标是提供一个通用的框架，使得数据可以在不同的应用 程序之间被共享和重用。它主要包含两个方面的内容：( 1 ) 提供一个通用的格式，使得分散 的数据源可以被集成和组合；( 2 ) 提供一种语言，记录数据和现实世界对象之间的关联。语 义w e b 的核心思想是给w e b 上的信息赋予确切定义的含义，从而实现w e b 信息的自动处 理( 如自动搜索、知识获取、逻辑推理等) ，以适应w e b 信息资源的快速增长，更好地为人类 服务。 本锌：( o n t o l o g y ) 是语义w e b 中的一个核心概念，它是共享概念的形式化的显式规范说明， 可以用来描述数据的语义信息。在实现上，本体论是概念化的详细说明，一个本体往往就是 一个正式的词汇表，其核心作用就在于定义某一领域或领域内的专业词汇以及它们之间的关 系。这一系列的基本概念为交流各方提供了一个统一的认识。在这一系列概念的支持下，知 识的搜索、积累和共享的效率将大大提高，真正意义上的知识重用和共享也成为可能。现实 世界中，本体已经无处不在，并在诸如数据库集成、p 2 p 系统、电子商务、w e b 服务、社会 网络等众多应用中扮演着至关重要的角色。 由于w e b 具有分散性( d e c e n t r a l i z a t i o n ) 的特点，所以在相交( 甚至是同一) 领域中，常会 存在多个不同的本体。本体匹配的过程就是发现不同本体之间实体映射关系的过程。对于使 用不同但又相关本体的w e b 应用程序而言，本体匹配为它们之间的交互提供了一种互操作 性( i n t e r o p e r a b i l i t y ) 。这种互操行性使得这些应用程序之间可以实现：信息集成( i n f o r m a t i o n i n t e g r a t i o n ) 、数据仓库( d a t aw a r e h o u s i n g ) 、分布式查询处理( d i s t r i b u t e dq u e r yp r o c e s s i n g ) 等功 能。 随着语义w 曲的发展，目前已存在大量的本体匹配方法和本体匹配工具( 详见综述【2 1 ) ， 对匹配工具进行评估和比较的工作也随之展开。有效性是目前评价本体匹配工具优劣的一个 重要标准，通常使用信息检索领域中的精度( p r e c i s i o n ) ，召回率( r e c a l l ) ，以及综合评价 ( f - m e a s u r e ) 来衡量例。精度又称查准率，是匹配对中正确匹配对数目与匹配对中全部匹配对 数目的比值；召回率也称查全率，是匹配对中正确匹配对数目与实际存在的正确匹配对数目 的比值；而综合评价是两者的综合，常取( 2 精度* j d 回率) “精度+ 召回率) 。 本体匹配测评竞赛( o n t o l o g ya l i g n m e n te v a l u a t i o ni n i t i a t i v e ，简称o a e i ) 1 是检验本体匹 配系统性能的舞台，对本体匹配的发展起到了促进与推动作用。o a e i 每年举办1 次，迄今 为止已经举办了4 次。从最初的2 0 0 4 年只有4 个系统参赛，2 0 0 5 年7 个，2 0 0 6 年1 0 个， 到2 0 0 7 年已有多达1 7 个系统参加，可以看出该竞赛的权威性已经得到普遍认可，并且本体 匹配已经越来越受到人们的关注。 东南大学硕士学位论文 通过对近四年本体匹配测评竞赛( o a e i ) 结果的观察，我们可以发现目前已有的本体匹配 工具，无论是在精度还是在召回率上，都还远未达到实际应用的需求，它们的有效性还有待 进一步的提高，相关研究也表明对本体匹配对进行后期修补可以有效地提高匹配工具的有效 性。 1 2 问题描述 本节将给出本体匹配问题的定义以及本体匹配对修补的定义。 1 2 1 本体匹配的定义 参照文献【2 】，给出如下映射单元以及本体匹配的定义： 定义1 1 ( 映射单元) 一个映射单元是一个5 元组： ，其中： 一耐是给定映射单元的唯一标识符。 一e 和e 分别表示本体0 和本体0 中的两个实体。 一n 表示e 和e 之间的确信度( 或相似度) ，范围通常在 0 ，1 】之间。 一尺表示e 和e 之间的关系，例如等价关系( - ) ，包含关系( ) 等。 定义1 2 ( 本体匹配) 对于给定的一对本体d 和p ，本体匹配是这样一个操作，它得到 一个映射单元的集御，( 如图1 1 所示) ，其中： 一彳是输入的映射单元的集合。 一p 是匹配过程中用到的参数。 一，是匹配过程中用到的外部资源。 o a o r 1 2 2 本体匹配的一般步骤 p 图1 1 本体匹配过程 k 目前，已有大量的研究人员对本体匹配这一研究课题进行了广泛而深入的研究，提出了 很多各具特色的本体匹配方法。通常这些本体匹配方法都遵循图1 2 中的框架。给定一对本 体作为输入，经过以下5 个步骤，输出一组匹配对： 2 第一章绪论 1 本体解析：目前已有不少本体解析工具，如j e n a l 、o w l a p l 2 等； 2 特征选取：针对不同的本体匹配方法，抽取不同的特征，例如本体的语言学特征或 结构特征等； 3 匹配算法：选用不同的算法，进行本体匹配。这里需要注意的是，每个匹配算法可 能会用到多个特征，而一个特征也有可能被多个匹配算法采用。另外，整个匹配过 程还可能组合多种匹配算法，并多次迭代。 4 结果表达：采用标准化的结果表达形式，输出匹配对。 5 评价( 可选步骤) ：对匹配对，进行评价，如计算匹配对的精度、召回率等等。 组合 h 到二羔互二 j 图1 2 本体匹配的一般步骤 1 2 3 本体匹配对的评估标准 对本体匹配对的评估，一般使用信息检索系统中的评估标准来衡量【2 1 ，包括精度 p ( p r e c i s i o n ) 、召回率r ( r e c a l l ) 、和f ( f - m e a s u r e ) 。 给定一个标准匹配结果r ( r e f e r e n c e ) ，某个匹配对a 的精度为： 毗咖訾( 1 1 ) 即a 的精度为，相对于标准匹配结果，a 中正确匹配对的数目占a 中总的匹配对数目的比 例。 匹配对a 的召回率的定义如下： 枇) = 肾 即a 的召回率为，相对于标准匹配结果，a 中正确匹配对的数目占标准匹配结果中总的匹 配对数目的比例。 另外，可以通过f - m e a s u r e 对精度和召回率进行综合。f m e a s u r e 一般使用精度和召回率 的调和平均值( h a r m o n i cm e a n ) 来表示： m 咖篇黼 ( 1 3 ) 1 h t t p ：i e n a s o u r c e f o r g e n e t 2 h t t p ：o w l a p i s o u r c e f o r g e n e t 3 东南大学硕士学位论文 1 2 4 本体匹配测评竞赛( o a e i ) 随着本体匹配工具数量的增多，有必要对这些工具进行评估和比较，使得用户在对本体 进行匹配的时候能够选择较优的工具，并且能够促使本体匹配工具开发者改进他们的工具。 为了评估和比较各本体匹配工具的优劣，2 0 0 4 年举办了两个关于本体匹配工具的比赛： 一个是1 3 c o n l ，另外一个是e o n 2 0 0 4 2 。这两个比赛都提供了若干对测试本体，要求参赛者 运行各自的匹配工具并提交匹配对，通过对匹配对进行评估从而决定各匹配方法和工具的优 劣。其中1 3 c o n 采用的测试用例是8 对不同领域的本体；而e o n 2 0 0 4 的测试用例中的所有 本体都是覆盖一个相同领域的本体，其所有2 5 对的测试用例，都是在一个本体的基础上作 某些变化或修改得到的。从1 3 c o n 比赛结果来看，没有哪个本体匹配工具对所有的测试用 例都有最好的匹配结果；而e o n 2 0 0 4 中，虽然其中两个工具相对另外两个工具匹配对较优， 但它们仍然存在着不足之处( 例如，对本体的自然语言描述信息依赖性强) 。通过这两个比赛， 一方面使得本体匹配工具的开发者能够找到他们工具的不足之处并加以改进；另一方面，则 可以促使更多的人投入到这个领域中来。 在2 0 0 4 年的两个比赛的基础上，2 0 0 5 年1 0 月在加拿大b a n f f , 举行了一个新的本体匹 配工具的比赛o a e l 2 0 0 5 3 ( 一般将e o n 2 0 0 4 作为第一届o a e i 比赛) 。这一次的比赛吸取 了一些2 0 0 4 年经验和教训，并吸引了更多的组织参加。o a e l 2 0 0 5 仍然通过评估本体匹配 对来衡量一个本体匹配工具的优劣，它提供了3 组不同的测试用例集，这三组测试用例集分 别具有不同的特征，其中的两组测试用例集参赛者事先并不知道标准匹配结果，比赛组织者 根据参赛者提供的匹配结果进行评估，这样更具合理性和公平性。 自2 0 0 5 年之后，o a e i 每年举办1 次，迄今为止已经举办了4 次。从最初的2 0 0 4 年只 有4 个系统参赛，2 0 0 5 年7 个，2 0 0 6 年1 0 个，到2 0 0 7 年已有多达1 7 个系统参加，可以看 出该竞赛的权威性已经得到普遍认可，并且本体匹配已经越来越受到人们的关注。o a e i 也 成了检验本体匹配工具性能的舞台，对本体匹配的发展起到了很大的促进与推动作用。 1 2 5o a e i 对匹配工具的评估 o a e i 比赛通常通过几组例子对本体匹配工具的性能进行测试，并采用不同的评估模式。 2 0 0 7 年的o a e i 比赛( o a e l 2 0 0 7 4 ) 共有7 组测试用例( b e n c h m a r k 、a n a t o m y 、d i r e c t o r y 、f o o d 、 e n v i r o n m e n t 、l i b r a r y 和c o n f e r e n c e ) ，这些测试用例分成三组，每一组测试用例采用不同的评 估过程：其中b e n c h m a r k 采用公开测试的方式即在比赛之前b e n c h m a r k 的标准匹配结果已 经给出；a n a t o m y 、d i r e c t o r y 、f o o d 、l i b r a r y 和e n v i r o n m e n t 采用盲测试的方式，即参加者并 不知道标准的匹配结果；c o n f e r e n c e 测试用例事先没有标准的匹配结果，在比赛期间举行一 个c o n s e n s u sw o r k s h o p 来对各个工具的匹配对进行评估。 b e n c h m a r k 测试用例集是4 届本体匹配测评竞赛都使用的测试用例集，每对测试用例都 给出标准匹配结果，与各匹配工具产生的匹配结果进行比较。b e n c h m a r k 测试用例集是在 e o n 2 0 0 4 测试用例集的基础上改进的，它包含5 1 对测试用例共5 1 个不同的本体，所有的 本体都覆盖了一个相同的领域，其中大部分的本体是在一个基本本体的基础上通过人工修改 得剑的。这种修改是有目的的修改，以测试匹配工具在某一方面的性能( 例如，将本体中所 有实体的名字换成随机字符串，以测试本体匹配工具对自然语言的依赖程度) 。另外，其中 测试用例3 0 1 3 0 4 则采用相对比较真实的本体，它们是由四个不同的组织开发的同一领域 的本体。对于b e n c h m a r k 测试用例集，本体匹配工具只需要匹配其中的c l a s s 和p r o p e r t y 即 4笋一 第一章绪论 可，i n d i v i d u a l 之间的匹配关系可以不予考虑。 a n a t o m y 测试用例中包含了一对关于解剖学领域的本体，这两个本体最显著的特点在于 它们都具有一定的规模并且来源于两个不同的组织开发的真实的本体。其中一个本体具有近 2 7 4 4 个c l a s s ，而另一个本体中则包含了3 3 0 4 个c l a s s 。 d i r e c t o r y 测试用例集主要为了测试本体匹配工具对于真实世界中只包含概念层次结构 的本体的匹配能力，它是从g o o g l e 、y a h o o 等的w e b 目录中抽取出来的，并具有以下特点： 1 ) 包含4 0 0 0 多对本体，并且每一个本体规模都比较小；2 ) 本体中只包含了一种 o b j e c t p r o p e r t y ，即r d f s ：s u b c l a s s o f ；3 ) 所有的本体都可以说是真正来源于真实世界的本体。 f o o d 、e n v i r o n m e n t 和l i b r a r y 来自于s k o s l ( s i m p l ek n o w l e d g eo r g a n i s a t i o ns y s t e m s ) ，简 单知识组织系统( s k o s ) 是w 3 c 于2 0 0 4 年发布的新的网络知识组织系统表示语言o - f 0 0 d 和 l i b r a r y 各包含两个本体，而e n v i r o n m e n t 包含三个本体，它的匹配次序为( a - b ，b c ，c a ) 。 这些测试用例的标准匹配结果由领域专家给出。 c o n f e r e n c e 测试用例包含1 4 个关于会议组织情况的本体，这些本体两两进行匹配，这 组测试用例没有标准匹配结果，各个工具的匹配结果通过手工和数据挖掘的方法进行评估， 这个评估除了得出各个工具在这组例子上的精度之外还得到一些统计信息，例如哪些工具在 特定类型的本体上表现较好以及这些工具能产生何种匹配模式( m a p p i n gp a t t e r n ) 等等。在对 结果评估的过程中会发现一些“有趣的”( 不明确的，可疑的等等) 匹配对将在c o n s e n s u s w o r k s h o p 进行讨论，建立一个共识。 由于目前我们只拥有b e n c h m a r k 测试用例集的标准匹配结果，因此在本文中我们所选 的例子都是各匹配工具在b e n c h m a r k 上的结果，而且我们也选择b e n c h m a r k 测试用例集作 为我们实验的测试用例。 1 2 6 本体匹配对修补的定义 对本体匹配工具评估的研究工作表明现有的本体匹配方法通常是在高精度和高召回率 之间取得一个平衡。这些工具产生的匹配对不是有相当多的错误( 高召回率低精度) 就是只涉 及到待匹配本体的一小部分( 高精度低召回率) 【4 】。对本体匹配对修补的目标是通过对本体匹 配对进行后期修补，提高结果的精度和召回率，使得综合评价标准f - m e a s u r e 有所提高。 我们可以将匹配工具产生的匹配对划分为如图1 3 所示的四类： 一匹配工具找到的正确的匹配对( a ) 一 匹配工具找到的不正确的匹配对( b ) 一 匹配工具未找到的正确的匹配对( c ) 一匹配工具未找到的不正确的匹配对( d ) 5 东南大学硕士学位论文 找到 未找到 图1 3 匹配对的划分 匹配工具得到的匹配对彳，包含图1 2 中的a 和b 两部分，而对匹配对修补的目标就是 剔除a 中的b 并找到c 加入到a 中。所以所谓本体匹配对的修补就是如图1 4 所示的过程： 它以本体匹配工具生成的匹配对彳作为输入，利用本体d 以及d 的信息，通过一个修补的 模块，得到新的匹配对彳”，a ”的综合评价( f m e a s u r e ) 要高于彳。 o a o r p 图1 4 本体匹配对修补过程 a ” 从图1 4 中可以看出对本体匹配对的修补就是在本体匹配过程的后期增加一个修补的模 块。通过分析我们发现匹配对有效性评估标准的两个不同角度( 精度和召回率) 也正是对匹配 对进行修补的两个方向：一是提高精度( 剔除结果中错误的匹配对) ，二是提高召回率( 寻找结 果中缺失的匹配对) 。所以对本体匹配对的修补可以从两个方面开展：剔除错误的匹配对和 寻找缺失的匹配对。 1 3 本文工作 本文的研究重点是：( 1 ) 调查和研究本体匹配对的修补问题，全面了解研究现状和方法( 包 括数据库s c h e m a 匹配和本体匹配两个方面) ，理解该问题的本质和研究难点；( 2 ) 提出一个 通用的本体匹配对的修补框架。针对框架中剔除错误匹配对的模块，本文提出了一个基于聚 类分析剔除错误匹配对的方法：针对框架中寻找缺失匹配对的模块，本文提出了一种基于邻 居相似度寻找缺失匹配对的方法。( 3 ) 设计和实现一个本体匹配对的修补工具，并通过实验 对工具进行测试和评估。 本文的以下各章安排如下：第二章介绍相关工作：第三章从修补本体匹配对的通用框架 入手，提出本文中所用的本体匹配对的修补方法，包括剔除错误的匹配对和寻找缺失的匹配 对两个方面：第四章详细介绍本体匹配对修补工具的设计与实现；第五章给出了相关的实验 结果，并对结果进行了详细的分析：最后一章对本文的研究工作做出总结，并展望下一步的 研究工作。 6 第二章相关工作 2 1 本体匹配 第二章相关工作 在传统的数据库领域，人们就数据的集成和转换对数据库s c h e m a 之间的匹配已经进行 了许多研究。近几年，随着语义w e b 的发展，本体的开发及应用越来越多，本体之间的匹配 问题也被众多研究者所关注。虽然数据库s c h e m a 和本体有很大区别，但s c h e m a 的匹配方法 对本体匹配有着很大的借鉴意义。 在s c h e m a 匹配或本体匹配中常用的匹配策略主要有基于模式的匹配和基于实例的匹 配。前者只考虑模式的信息，而不考虑实例数据，后者则综合利用了这两方面的信息。目前， 基于实例的匹配还比较少，典型的有i m a p t 5 】和g l u e 州，而其他大多数的匹配算法重点考虑 的都是基于模式的策略。根据匹配的映射关系表示的不同，数据库模式之间的匹配方法和本 体之间的匹配方法一般可以分为面向相似度的匹配和面向逻辑关联的匹配。面向相似度的匹 配一般使用 0 ，l 】区间上的实数值表示相似度。而面向逻辑关联的匹配则是计算节点概念之间 的语义关系，这种关系一般使用相等、包含、相交等表示。目前大多数的数据库模式匹配工 具和本体匹配工具都是使用面向相似度的匹配方法；而面向逻辑关联的匹配方法则比较少， 其中比较典型的是s m a t c h j 。 目前的匹配工具在匹配过程中一般考虑本体语言学上的相似性以及结构上的相似性，在 有较多( 或者充足) 实例数据的情况下，综合使用基于实例的匹配方法与技术。本节将介绍一 些本体匹配中常用的方法以及目前比较成熟的本体匹配工具。 2 1 1 匹配方法简介 目前使用的本体匹配方法一般分为三类：基于语言学的方法，基于结构的方法以及基于 实例的方法，现有的工具一般都是使用这三类方法中的一种或综合使用这三类方法得到最终 的匹配结果。 基于语言学的方法 基于语言学的本体匹配方法是一种采用自然语言处理技术进行本体匹配的方法，目前几 乎所有的本体匹配工具都会采用基于语言学的方法。使用的比较多的是基于字符串处理的方 法和基于字典的方法。基于字符串处理的方法主要有编辑距离【引、i - s u b 9 】等等。基于词典的 方法主要是使用通用词典( 如：w o r d n e t 1 0 1 ) 或领域相关的词典识别出词汇间是否存在同义、 近义或上下位等关系。下面用几个例子来说明现有的工具是如何使用自然语言信息的： c u p i d e l l 是一种一般的s c h e m a 匹配工具，它结合了字符串和字典两种技术对s c h e m a 进 行语言学上的匹配。首先它对s c h e m a 中元素的名字进行相应的自然语言处理( 包括分词，去 词缀和扩写缩写单词等) 并在处理过程中使用词典作为处理的参考，然后通过字符串的相似 度来度量元素之间的相似度，在计算字符串相似度时使用字典查找词汇间的同义和上下位关 系。 o l a 1 2 】是一种针对o w ll i t e 表示的本体进行匹配的工具，它综合使用了字符串距离和 词汇距离来计算两个实体的相似度。其中词汇距离的计算是基于w o r d n e t 的。给定两个待 比较的词汇，将它们各自的同义词形成两个同义词集，然后计算这两个集合规格化后的 h a m m i n g 距离来代表这两个词汇的距离。 a s c o 1 3 是由法国i n r i a 研究所开发的一个本体匹配工具。在a s c o 中，实体间语言 学上的相似度主要通过它们名字的相似度，标签的相似度以及注释的相似度通过线性组合 得到。计算名字和标签之间的相似度时使用了w o r d n e t 查找近义词，而在计算注释之间相 7 东南大学硕士学位论文 似度时使用了彻f 方法。 s - m a t c h 【7 】主要是面向概念层次结构的本体，它综合使用了多种自然语言处理技术，包 括基于字符串处理的方法( 词缀处理，编辑距离、n g r a m 等) ，基于词义的方法( w o r d n e t 、层 次距离等) 和基于注释的方法( w o r d n e t 注释注释比较等) 等。 基于结构的方法 在数据库s c h e m a 匹配和本体匹配的相关工作中有很多是利用结构信息来进行匹配的， 这些方法的不同之处主要在于它们使用的图模型以及抽取的结构信息有所不同。 s i m i l a r i t yf l o o d i n g ( s f ) 0 4 是一个通用的图匹配算法。该算法是一个迭代的过程，首先计 算两个点之间的初始相似度，然后在每次迭代中都根据相邻的节点之间的相似性的传播来计 算新的相似度。 c u p i d 0 1 1 中的结构匹配是基于树状结构的，给定的s c h e m a 需要转化成一棵概念树。其 主要思想是对树状结构的s c h e m a 作自底向上的结构匹配，两元素之间的相似度取决于他们 自然语言的相似度以及它们叶子节点集的相似度，而叶子节点的相似度取决于自然语言相似 度、数据类型的相似度以及邻接节点的相似度。 o l a 【1 2 j 主要针对用o w ll i t e 语法描述的本体。本体中的实体被分为若干类型，如：类， 对象，属性，关系，数据类型等等。一个本体用一个o l - g r a p h 表示，它是一个有向标记图， 图中的节点对应o w l 实体，边对应各种实体关系。相似度的计算在同一种类的实体间进行， 两个节点的相似度依赖于在各自的o b g r a p h 中与表示相同实体关系的边连接的相邻节点的 相似度。最终的结果通过实体集合的局部匹配以及迭代计算得到。 在a s c o b 3 1 使用的图模型中把本体表示为带有根节点的有向无环图，其中节点表示 c l a s s 和p r o p e r t y ，边表示i s - a 关系或d o m a i n 、r a n g e 关系，所抽取的结构相似特征是实体的 邻接关系和实体层次路径。实体相似度的计算基于以下假设：如果直接的上层实体或直接的 子实体相似则这两个实体相似：或如果从一个实体层次的根到实体a ，与从另一个实体层次 的根到实体b 所经过的路径中包含相似的实体，则实体a 和b 有可能是相似的。 a m c h o r _ p r o m p t 【l 纠是美国s t a n f o r d 大学开发的一个半自动化的本体匹配工具，在它使 用的本体图模型中把c l a s s 作为节点而p r o p e r t y 作为边，输入若干已知的匹配项作为a n c h o r s ， 所抽取的结构特征即a n c h o r s 之间的定长路径，对于路径中同样位置的节点在每次迭代中增 加它们相似度的值。 基于实例的方法 基于实例的本体匹配方法一般使用综合多种学习策略的机器学习方法，寻找两个本体之 间的映射关系。目前，基于实例的匹配方法和工具还比较少，比较有名的有i m a p 【5 j 和 g l u e t 6 1 。 i m a p l 5 是美国i l l i n o i s 大学u r b a n a 分校开发的一个数据库模式匹配工具。它能够半自动 地发现1 ：l 的匹配和复杂的匹配( 例如：r o o m p r i c e = r o o m r a t e * ( 1 + t a x r a t e ) ) 。i m a p 把匹配 看成在一个非常巨大的匹配空间中的搜索。为此，它集成了一系列的搜索器，每种搜索器用 来发现一种特定的复杂匹配。为了提升匹配的准确度，i m a p 对多种领域知识进行挖掘，包 括以前的匹配对、领域完整性约束以及重叠的数据等。 g l u e l 6 是由美国w a s h i n g t o n 大学开发的本体匹配工具。它采用实体之间的联合概率分 布来度晕实体间的相似度，将实体a 和b 之间的相似度表示为s i m ( a ，b ) = p ( a n b ) p ( a u b ) ， 然后通过机器学习的算法计算实例的概率分布，并以实例的概率分布来近似代替实体的概率 分布。g l u e 使用了多种机器学习的策略，每种策略针对特定的实例信息或者本体包含的 分类结构信息。 8 第= 章相关i 作 2 1 2 工具简介 目前已有很多自动化和半自动化的本体匹配工具，比较成熟的工具包括：德国莱比锡大 学开发的工具c o m a h i “、东南人学开发的工具f a l c o n - a ( # ”- 、以及清华大学开发的t 具 r j m o m i s i 。 c o m a _ i - v “是目前最完备的匹配工具之一，是对原型系统c o m a 的一个扩展。它 是一个既能匹配数据库s c h e m ax 能匹配本体的通用匹配工具。c o m a + + 提供了易 于操作的图形用户界面。井支持组合使用多种匹配算法以及重用先前确认过的匹配 对，c o m a + + 的体系结构如图21 所示知识库储存所有与匹配相关的数据模型 以及匹配池管理储存在内存中的所有s c h e m a 、本体以及匹配对，匹配引擎执行匹 配操作。图形用户界面提供对组件的访问，并将模型以可视化的方式显示出来，井 提供对匹配过程及匹配对的管理。匹配引擎在执行过程中，将输入模型f 如本体1 统 一转换为有向无环圈的数据结构，应用不同的匹配算法将再匹配算法产生的临时 匹配对以矩阵的形式存储在知识库中，通过采用不同的组台策略，生成最终匹配对 井输出。 图21c o m a + + 系统结构圈 f a l e o n - a o t t i 是一个表现出色且稳定快速的本体匹配工具，目前是一个开镢的项 目。它的最新版本07 版的体系结构图如图22 所示，它包括5 大模块；本体模型池、 匹配对集、匹配算法库、中央控制器及外部存储数据库。本体模型池处理本体并针 对不同的匹配器构造不同的模型；匹配对集台产生最终的匹配结果并对结果进行评 估：匹配算法库管理一系列单元匹配器；中央控制器可以根据输入本体的特征，自 动有效地选取匹配策略并执行匹配过程：外部存储数据库用来存储匹配过程中用到 的数据。在f a l e o n - a o 的匹配算法库中包括4 个各具特色的单元匹配嚣：p b m ， v - d o c i - s u b 以及g m o 。p e i m 采用了分而治之的思想，先把每个大本体分别划分 为规模较小的块m l o c k ) ，再通过预先找到的锚点，发现块之间的匹配关系，从而使 得已有的本体匹配算法可咀直接作用于这些小的块，实现大本体匹配；v - d o c u w 是一种新的基于语言学的匹配方法它的思想是通过领域实体在本体中的用法来揭 示它们可能的含义，从而计算匹配对。具体的方法是，通过抽取本体中实体吼及它 的邻居实体的描述信息来构建虚拟文档，然后通过空间向量模型方法计算虚拟文档 之间的相似度，从而得到实体之间的相似度；i - s u b 是一个轻量级的匹配器，采用 了希腊雅典理工大学f n a r i e l t h n i c a l u n i v e r s i t y o f a 山e n s ) c l 工s t o i l o s 等人提出的 一种基于字符串比较的方法它不仅考虑字符串中相同的部分，而且考虑字符串 之间的差异ig m o 将基于r d f - - - - 元组的图模型转换为有向一部图来表示，利用相 似性的传递性来计算相似度。两个本体中对应实体的相似度随着与其关联的某些 s t a t e m e n t 的相似度的增加而增加，在这些s t a t i s t 中被比较的两个实体在三元组中 黜攀 自大学两学位论文 是同样的角色( 主语，谓语宾语) = 同时两个s t a t e m e n t 的相似性也和与之关联的在 三元组中是同样角色的实体的相似性相关。在匹配过程中g m on j 将用其他方法 f 如；语言学上的方法等1 预先找到的匹配对作为输入，通过比较两个本体结构上的 相似性得到更多的匹配对。特别地，当两个本体在结构上比较相似时，g m o 可以 获得较好的匹配结果。 图2 2f a l c o n - a o 系统结构图 r i m o m l l 8 1 是基于最小风险本体映射模型开发的本体匹配系统。它采用贝叶斯决策 理论，将映射发现问题转化为风险最小化问题。r i m o m 的匹配过程如图2 3 所示， 它的执行过程包括a 个主要步骤： 1 ) 相似要素评估。对于给定的两个本体r i m o m 评估两个相似要素，它们分别 近似代表着两个本体的结构相似度咀及自然语言描述的相似度。这两个要素将 用于下一步的策略选择。 2 ) 策略选择。策略选择的基本思想是：如果两个本体自然语言描述的相似度较高 那么r i m o m 将更多地依赖于自然语言为基础的策略；相反如果结构相似度较 高那么r i m o m 将采用相似度传播的策略。在目前的版本中r i m o m 共定义了 五种簟略：基于编辑距离的策略，基于统计学习的策略以及三种基于相似度传 播的策略( 包括e a m c e p t - t n e o n c e p t 的传播策略( c o p ) ，p r o p e r t y - t o - p r o p e r t y 的 传播策略口p p ) ，以及c o n c e p t - t o - p r o p e r t y 的传插策略( c p p ) ) 。该系统的另一个 特点是可以发现多对多的匹配结果。 3 ) 策略执行。对于选定的策略r i m o m 独立地采用每一种策略去发现匹配，一 种簟略输出一个匹配结果。 钔多策略匹配结果组合。组合不同的镱略输出的匹配对。 5 ) 相似度传播。如果两个奉体有较高的结构相似度，r i m o m 用一种称为相似度 传播的算 去来对找到的匹配对进行优化并用该算法来寻拽其他簟略不能找到 的匹配对。相似度的传播利用的是本体的结构信息。 旬匹配结果优化。在这个过程中对上一步输出的匹配结果进行优化。在匹配过程 的最后阶段r i m o m 有一个利用启发式规则进行匹配对优化的过程。r i m o m 定义了一系列的启发式规则来去除“不可信”的匹配对。匹配对的优化主要包 括：降低那些预测值根高但“不合理”的匹配对的预测值，同时提高那些预测 值较低但“合理”的匹配对的预测值然后对所有候选匹配对排序，选择最优 的匹配对。 第二章相关工作 本体 映射燕代过程 2 2 匹配对的修补 图2 3r i m o m 的执行过程 通过研究我们发现无论是在数据库s c h e m a 匹配还是在本体匹配方面，对匹配对进行后 期修补都可以有效地提高匹配工具的有效性。除了通过改进匹配算法来提高匹配工具的有效 性之外，人们也逐渐认识到后期修补的重要性，在数据库s c h e m a 匹配方面具有代表性的工 作有美国伊利诺大学提出的一个自动发现错误匹配的解决方案m a v e r i c l 2 0 和加州大学的 工具s p i d e r l 2 ，在本体匹配方面具有代表性的有日本丰桥大学的工具o n t o k d e 2 2 和清华 大学的工具r i m o m 1 引。 在一个数据集成系统中总存在从不同的源数据s c h e m a 到中间数据s c h e m a 的映射， 但源数据s c h e m a 会随着时间而改变，原本正确的映射随着时间的推移会变成错误 的映射，m a v e r i c 2 0 1 就是一种自动的发现错误映射的方法。在同定的时间间隔 m a v