（计算机软件与理论专业论文）基于多元界的近似信息检索技术研究.pdf

摘要 摘要 基于本体的信息系统可以提供精确而高效的w e b 信息检索服务，但面临着本体异 构问题。近似查询技术通过将关于一个本体的查询改写为关于另一个本体的近似查询来 解决异构问题，其核心是求本体中概念在另一本体中的近似。它找到概念的最小上界和 最大下界，用最小上界的合取作为概念的上近似，最大下界的析取作为概念的下近似。 此方法只考虑异构本体概念间一对一的蕴涵关系，概念的上下界中只包含独立的概念， 因此无法得到概念的最佳近似。概念近似的质量常常难以接受，时常遇到返回全集或空 集的最坏情况。 本文的创新之处是考虑概念合取和析取之间的蕴涵关系来得到概念的最佳近似。定 义了最小上近似和最大下近似两种概念的最佳近似。将概念的最小上界和最大下界扩展 为多元界：引入概念的析取定义概念的多元最小上界，引入概念的合取定义概念的多元 最大下界。证明通过概念的多元最小上界可以得到概念的最小上近似，通过概念的多元 最大下界可以得到概念的最大下近似。通常多元界中可能包含大量冗余，增加了概念近 似表达的复杂度，降低了查询效率。本文又定义了概念的最简多元最小上界和最简多元 最大下界去除这些冗余，并提供两个有效的算法寻找概念的最简多元界，算法被证明是 正确和完备的。 关键词： 信息检索；本体；上近似；下近似；多元；最小上界；最大下界 东南大学硕士学位论文 a b s t r a c t o n t o l o g y - b a s e di n f o r m a t i o ns y s t e m sc a l lo f f e rp r e m s ea n de f f e c t i v el n f o r m a t i o nr e t r i e v a l o nt h ew e bb u ts u f f e rf r o mt h ep r o b l e mo fo n t o l o g yh e t e r o g e n e i t y t h e a p p r o x i m a t e i n f o r m a t i o nf i l t e r i n ga p p r o a c hr e w r i t e saq u e r yw i t hr e s p e c tt oo n eo n t o l o g yi n t oa n a p p r o x i m a t eq u e r yw i t hr e s p e c tt oa n o t h e ro n t o l o g yt os o l v et h eh e t e r o g e n e i t yp r o b l e m t h e c o r eo fa p p r o x i m a t ei n f o r m a t i o nf i l t e r i n gi s f i n d i n ga p p r o x i m a t i o n so fc o n c e p t s i nt h e o n t o l o g y i tf i n d st h el e a s tu p p e rb o u n d sa n dt h eg r e a t e s tl o w e rb o u n d so fac o n c e p t ，t h e nu s e s t h ec o n j u n c t i o no ft h el e a s tu p p e rb o u n d sa st h eu p p e ra p p r o x i m a t i o no ft h ec o n c e p t ，a n du s e s t h ed i s j u n c t i o no ft h eg r e a t e s tl o w e rb o u n d sa st h el o w e ra p p r o x i m a t i o n h o w e v e r , w i t ht h e b o u n d s c o n t a i n i n gs e p a r a t ec o n c e p t s ，i to n l yc o n s i d e r so n e t o o n ec o n c e p ts u b s u m p t i o n r e l a t i o n s ，s oc a n n o ty i e l dt h eb e s ta p p r o x i m a t i o n so fac o n c e p t t h eq u a l i t yo ft h e a p p r o x i m a t i o n si so f t e nn o ta c c e p t a b l e t h ea p p r o x i m a t i o n se i t h e rr e t u r na ne m p t ys e to ra m 1 1s e ti nt h ew o r s tc a s e s t h ei n n o v a t i o ni nt h i sp a p e ri sc o n s i d e r i n gt h es u b s u m p t i o nr e l a t i o n sb e t w e e nc o n c e p t s a n dd i s j u n c t i o no rc o n j u n c t i o no fc o n c e p t st og e tt h eb e s ta p p r o x i m a t i o n so fac o n c e p t t w o b e s ta p p r o x i m a t i o n s ，l e a s tu p p e ra p p r o x i m a t i o na n dg r e a t e s tl o w e ra p p r o x i m a t i o n ，o fa c o n c e p ta r ed e i n e d t h el e a s tu p p e rb o u n d sa n dt h eg r e a t e s tl o w e rb o u n d so fac o n c e p ta r e e x t e n d e dt ot h em u l t i e l e m e n tb o u n d s ：d i s j u n c t i o no ft h ec o n c e p t si si n t r o d u c e dt od e f i n e m u l t i e l e m e n tl e a s t u p p e rb o u n d s ，a n dc o n j u n c t i o no fc o n c e p t si s i n t r o d u c e dt od e f i n e m u l t i e l e m e n tg r e a t e s t1 0 w e rb o u n d s i tp r o v e st h a tt h em u l t i e l e m e n t1 e a s tu p p e rb o u n d so fa c o n c e p ty i e l dt h el e a s tu p p e ra p p r o x i m a t i o no ft h ec o n c e p ta n dt h em u l t i e l e m e n tg r e a t e s t l o w e rb o u n d so fa c o n c e p ty i e l dt h eg r e a t e s tl o w e ra p p r o x i m a t i o no ft h ec o n c e p t i ng e n e r a l ， t h em u l t i e l e m e n tb o u n d sm a yc o n t a i nm u c hr e d u n d a n c y , w h i c hw i l li n c r e a s et h ee x p r e s s i o n c o m p l e x i t yo ft h ea p p r o x i m a t i o n sa n dd e c r e a s et h ee f f i c i e n c y t h es i m p l i f i e dm u l t i e l e m e n t l e a s tu p p e rb o u n d sa n dt h es i m p l i f i e dm u l t i e l e m e n tg r e a t e s t1 0 w e rb o u n d sa r ed e f i n e dt o r e m o v es u c hr e d u n d a n c y t w oe f f e c t i v e a l g o r i t h m s a r ea l s o p r o v i d e d f o rf i n d i n gt h e s i m p l i f i e dm u l t i e l e m e n tb o u n d s t h ea l g o r i t h m sa r ep r o v e dc o r r e c ta n dc o m p l e t e k e y w o r d s ：i n f o r m a t i o nr e t r i e v a l ；o n t o l o g i e s ；u p p e ra p p r o x i m a t i o n ；l o w e ra p p r o x i m a t i o n ； m u l t i e l e m e n t ；l e a s tu p p e rb o u n d s ；g r e a t e s tl o w e rb o u n d s i i 第一章引言 第一章 引言 1 1 选越依据 随着计算机和w e b 的不断普及，它们日益成为人们获取信息的重要来源。信息检索是w e b 上晟 重要的基本服务之一i t , 2 】。但现在常用的基于关键词搜索的信息检索技术不能利用文档中的语义知 识，难以给出查询的精确回答。随着w e b 上信息的爆炸性增长，现有查询技术的查准率和查全率越 来越不能满足用户的要求，常常会遗漏一些重要的结果，同时却返同大量的无关结果。因此人们迫 切需要能处理语义的具有精确查询能力的信息检索技术”j 。 新一代的语义w e b 是现有w e b 的扩展，对w e b 上的信息赋予机器可理解的语义，实现基于语 义的搜索【4 j 。本体是语义w e b 中的关键技术1 5 j ，它形式化地定义概念、关系、公理和实例来描述w e b 知识，是语义w e b 上知识共享和重用的基础【6 】。在基于本体的信息系统中，系统预先将网页和文件 等作为本体中的实例进行标注或分类，用户的查询使用本体中的概念术语写成，从而可以通过精确 的语义而不是有歧义的关键词来查找信息，提高查准率和查全率【7j 。基于语义w e b 和本体的查询技 术有重要的实用价值，是当前研究的热点。 不同的信息系统可能使用不同的本体，不同的本体中有不同的概念、关系、公理和实例，它们 的名字构成了不同的术语集或称词汇集，这就会产生本体异构问题j 。异构问题给信息系统之间的 查询带来很大困难：一个查询由用户本体中的概念术语表达，但系统可能使用另一个本体，其中并 没有这些概念术语，因而无法回答这个查询。w e b 的分布特性决定了即使是同一个领域，也可能存 在多个异构本体，而无论是用户还是系统都不可能也不应该掌握所有的异构本体。因此如何在异构 本体间进行查询是语义w e b 和本体研究中的关键问题，其中最基本的问题是一对用户和系统各使用 不同本体时如何进行查询。晟直接的思路是将这两个本体合并为一个或者通过一系列规则连接起来 ( 称为本体集成和映射) ，消除异构。解决这个问题的另一个重要方法是查询重写技术。本文即关注 基于概念间蕴涵关系的近似查询技术j 。 1 2 国内外研究现状 1 2 1 本体集成和映射 解决本体异构的通用方法是本体 集成和映射”川，”】。本体集成和映射 研究异构本体间存在的语义关系，找 到它们之间的映射规则，或将其合并 为一个本体，从而达到异构本体间的 互操作。图1 是本体映射和本体集成 的框架图，图中o n t o l o g y l 和 o n t o l o g y 2 是两个异构本体，它们分别 对应信息源d a t a l 和d a t a 2 。本体映射 图1 本体映射和本体集成 在两个异构本体之间建立映射规则，从而实现两个系统问的互操作；而本体集成将两个本体合并为 一个统一的本体o n t o l o g y l + 2 ，解决异构问题。但现有的研究表明本体集成和映射是非常困难的，很 多方法都难以得到准确的结果或者无法发现复杂的本体间关系，目前还没有一个本体映射或者本体 集成方法能够较好的解决本体异构问题。 基于本体的查询只是本体的众多应用之一，和本体推理应用相比，查询应用比较简单。在异构 本体间进行查询并不需要发现异构本体问的所有映射规则或者集成异构本体，只需找到异构本体中 用来查询的术语间关系，采用查询重写技术，将基于一个本体的查询重写为基于另一个本体的查询。 1 2 2 查询重写技术 早期使用查询重写解决异构问题通常采用等价查询重写方法，把一个用户本体中词汇表达的查 询重写为系统本体中词汇表达的等价查询，从而适合特定的本体信息系统 1 ”。查询等价意味着重写 前的查询结果和重写后的查询结果完全一致。 在上世纪9 0 年代，就有基于中间件系统的查询重写的研究【l ”。中间件是为多个信息源提供的统 一的查询界面：它接受用户的查询( 用的是中间件本身提供的词汇集) ，然后把它们翻译成针对各个 信息源的查询( 使用信息源的词汇集) 让信息源进行查询，并把信息源返回的查询结果组合起来返 变堕查兰婴圭兰堡丝苎 回给用户】。这样构成了一个全局局部的信息检索模型，用户只需要掌握中间件的词汇集就可以在 多个使用不同本体的信息源中进行查询。这些系统的查询重写要求找到原查询对应的等价查询。但 实际上，由于异构本体间概念和概念层次不同。原查询常常不存在对应的等价查询，或发现它所需 的代价是无法接受的，因此需要将原查询重写为近似的查询m 】。 1 2 3 近似查询技术 1 9 9 9 年的k r a f t 系统【l ”和2 0 0 0 年的o b s e r v e r 系统f l9 】初步探索了本体间概念的近似查询技术， 并在应用中取得了较好的成果。以o b s e r v e r 系统为例，它定义了概念间的同义、广义和狭义关系， 并利用这些关系重写查询。重写后的查询不一定和原查询完全等价，而是原查询的一个近似。但这 些系统中考虑的概念间关系缺乏形式化语义，难以保证近似查询结果的正确性和完各性要求。 针对原有系统形式化不足的弱点，c a l v a n e s e 和d eg i a c o m o 在2 0 0 1 年利用形式化的描述逻辑语 言定义了全局本体和局部本体的框架，并提出在此框架内的全局视图和局部视图两种查询重写方法 2 0 o 描述逻辑有严格的语义和推理方法，是大多数w e b 本体语言的逻辑基础，它保证了近似查询结 果的正确性和完备性。2 0 0 4 年，他们进一步提出p e e r - t o - p e e r 环境下的本体查询重写的框架”“。但 这些方法都假定异构本体间的逻辑映射关系是己知的，没有给出如何找到这些关系的方法。 在数据库领域，k c h a n g 等人提出了基于异构数据库模式词汇间近似的查询重写理论【l ”，并详 细分析了在每个词汇最佳近似的前提下，如何度量和保证近似查询重写后整个近似查询的质量口。 这些思想和方法可以应用到本体查询中，其中数据库模式词汇就对应着本体中的概念。但该方法并 没有涉及如何求得每个词汇的最佳近似。 在此基础上，文献 2 3 ，2 4 提出了基于概念蕴涵的近似信息查询技术。它预先找到用户本体中每 个概念在系统本体中对应的近似查询( 包括上近似和下近似，原概念所有的实例一定都在上近似的 查询结果中，下近似的查询结果一定是原概念的实例) ：首先找到概念在系统本体中的超类和子类， 分别放入概念的上界和下界；然后将上界的合取作为概念的上近似，下界的析取作为概念的下近似。 在重写查询时只需根据对答案正确性和完备性的不同要求将查询表达式中的概念替换为对应的上近 似或下近似得到系统可回答的近似查询。这种方法将在下一章详细介绍。 还有通过实例学习来进行近似查询的研究i 6 j ，即根据每个查询结果中的实例来进行查询重写： 对每一个应该是原查询结果的实例，找到能返回该实例的另一个本体中的最小查询，最后把这些小 查询组合起来得到原查询的一个近似。要得到好的近似需要考虑大量的实例，而且得到的近似查询 是由很多小查询构成，比较冗长。这种方法仅给出了查询上近似和下近似的定义，没有提供有效的 算法来生成或化简近似查询。 目前国外在异构本体近似查询的研究成果主要集中于研究在概念和关系的近似己知的前提下的 近似查询重写过程和系统框架，对如何求概念的近似研究较少，还没有有效的求概念最佳近似的算 法。文献 2 3 2 4 年u 用概念的上界和下界求概念近似的方法无法得到概念的最佳近似，近似的质量有 时是不可接受的【，j 。如果概念远小于它的超类，那么它的上近似可能过大；最坏情况是找不到概念 的超类，那么上近似的查询结果就会返回全集。如果概念远大于它的子类，那么它的下近似可能过 小：最坏情况是找不到概念的子类，那么下近似的查询结果就会返回空集。异构本体常常有全异的 概念集合和概念层次，因此最坏的情况也时常会出现。由于无法得到概念的最佳近似，也可能影响 到重写得到的近似查询的查准率和查全率。这种现象出现的主要原因是现有方法只注意概念的超类 和子类，也就是一对一的概念蕴涵关系。本文针对此问题进行研究，考虑利用异构本体复杂概念间 的蕴涵关系来求概念的最佳近似。 1 2 4 国内研究现状 国内近年也开展了本体相关工作的研究，文献 2 5 2 7 对本体的映射方法和本体的信息共享全局 视图构建方法等作了一般性介绍。文献 2 8 1 利用本体为w e b 服务按领域建立统一的、抽象的概念模型， 为解决基于语义的服务查找和服务合成的异构问题提供了新方法。文献 2 9 】提出了一种基于本体的 w e b 内容二阶段半自动提取方法，该方法同时考虑当前提取系统的通用性和提取准确性，并且通过 有监督的学习来逐步提高包装程序生成的自动化。文献 3 0 1 建立了基于本体论的民族知识获取和分析 方法。文献 3 1 】以文本知识为背景，提出了基于本体的概念联通。 值得一提的是基于本体的信息检索研究工作。文献 3 2 1 提出了一种基于本体的半结构化数据的柔 性查询方法，用户发出的查询通过了解数据库本体语义信息而不必遵循严格的数据库模式也能得出 结果。文献 3 3 提出了一种利用多智能主体和本体理论设计的信息检索服务器，该系统能够比较及时 地反映网络中信息的动态变化，并具有较好的信息导引能力。文献 3 4 1 1 用x m l 米表示本体，并分 2 第一章引言 析了如何利用x i v i l 上的查询语言来实现本体中概念的检索。文献 3 5 利用描述逻辑建立本体的形式 化模型，并提出了本体术语包含关系的检验算法，最后根据所建的本体模型研究了信息检索机制。 文献 3 6 提供了基于本体论的信息处理方法，构造了数字图书馆启发式检索模式的思路。但目前还没 有见到关于异构本体间近似查询重写方面的研究成果。 1 3 研究过程 在本科毕业设计时初步探讨了语义w e b 和本体的应用价值和相关技术，在硕士阶段的学习中进 一步展开更深入的研究工作，主要关注基于多本体的知识表示和信息查询技术。 最初探索本体的建模和表示方法。为了有效利用现有的建模工具构建本体，提出- - e e 基于u m l 的本体表示方法，并通过复杂度分析技术度量本体模型的质量。 语义w e b 是一个多本体环境，有效地管理多本体是实现语义w e b 信息共享的一个重要研究内容。 为此提出了基于桥本体的多本体管理系统。桥本体形式化的描述了多本体之间的关系，具有创建与 维护方便，提高本体重用以及避免不必要的本体扩充与集成的优点。主要的研究内容包括桥本体及 本体间关系的形式化定义，自动生成方法，以及语义冗余和冲突的化简算法。 接着将桥本体应用到多本体系统的具体功能中。本体标注是将现有的知识转化为本体知识的重 要过程，基于桥本体的多本体标注方法可以完成单本体和分布式描述逻辑无法完成的复杂标注任务。 大型本体难以维护和使用，具体应用往往只需其中的部分知识，为此提出了一种基于桥本体的子本 体抽取方法，从大型本体中抽取满足用户需求的较小子本体。 异构本体问的查询是多本体系统要完成的最基本任务。为解决异构本体间的查询问题，开始采 用基于关系矩阵的异构本体间的查询方法。利用关系矩阵描述本体概念间的关系，给出本体间关系 矩阵的定义和计算方法，并通过查询向量和关系矩阵的计算来重写查询。该方法易于实现而且速度 快，但因为仅考虑了简单的概念蕴含关系，查询精度还有待进一步提高。 从以往的研究认识到本体中复杂概念间蕴涵关系对提高异构本体间查询质量的重要作用。于是 考虑采用基于实例的方法寻找本体中复杂概念间蕴涵关系。为此先研究语义w e b 上实例间的等价关 系，解决实例层上的异构问题。接着探讨基于异构本体间共有实例的复杂概念间蕴含关系检查技术， 分析其中存在的问题，提出对应的解决方案。最后将这些工作扩展到模糊本体中，提出了一整套适 用于一般和模糊本体的实例标注、选择和蕴含关系检查算法。 本文的研究是这些工作的直接延续和扩展。 1 4 主要研究内容 探索将异构本体中复杂概念间蕴涵关系应用到近似查询技术中，定义概念的最佳近似，提高近 似查询的质量。引入概念的多元界来求概念的最佳近似，定义晟简多元界提高效率，并给出高效的 求概念最简多元界的算法。完成高质量的异构本体问近似查询。 论文将通过下面几个步骤展开研究。 1 ) 近似查询技术的相关概念、现有方法及其分析 研究当前近似查询技术的基本概念、理论和方法，分析这些理论、方法存在的问题及其原因， 提出解决问题的思路。主要指出目前还没有有效的求概念最佳近似的算法，现有的求概念近似方法 是基于概念的最小上界和最大下界，只考虑了异构本体概念间一对一的蕴涵关系，无法得到概念的 最佳近似，近似的质量有时是不可接受的。因此本文考虑利用异构本体复杂概念间的蕴涵关系来求 概念的最佳近似。 2 ) 概念的最佳近似和多元界 考虑异构本体复杂概念间的蕴涵关系，给出概念的两种最佳近似，最小上近似和最大下近似， 的定义。但是仅从定义难以求得任意概念的最佳近似。为此引入概念的多元界，包括多元最小上界 和多元最大下界。证明由多元最小上界可得概念的最小上近似，由多元最大下界可得最大下近似。 3 ) 概念的最简多元界 为了提高效率，在不影响准确性的基础上去除多元界中的冗余，定义最简多元最小上界和最简 多元最大下界。于是把求概念的晟佳近似问题转化为求概念的最简多元界。 。 4 ) 给出最简多元最小上界生成算法 最简多元最小上界消除了冗余成员，提高了查询效率。但由于最简多元晟小上界的搜索空间是 概念数的指数级，全局搜索不切实际。重点研究求最简多元最小上界的算法及其优化方法。主要采 用迭代递增的过程寻找最简多元最小上界，在每一步迭代利用本体中的概念层次关系缩减搜索空间。 说明算法的详细过程及其理论依据，并给出算法的完备性和正确性证明，分析其有效性。 东南大学硕士学位论文 5 1 给出最简多元最大下界生成算法 求概念的最简多元最大下界的算法也面临着巨大的搜索空间，需要采用迭代递增的过程寻找最 简多元最大下界并在每步减小搜索空间。在求最简多元最大下界算法优化时，由于搜索目标和方向 的不同，部分细节和上界算法并不一样。 1 5 论文主要成果 论文的主要研究成果表现在以下几个方面： 引入异构本体复杂概念问的蕴涵关系定义概念的最小上近似和最大下近似，提高近似查询的 查准率和查全率； 引入概念的多元最小上界和多元最大下界的定义，证明了由多元最小上界和多元最大下界求 得的上近似和下近似分别是概念的最小上近似和最大下近似； 引入概念的最简多元最小上界和最简多元最大下界的定义，去除多元界中的冗余，提高查询 效率，将求概念的最小上近似和最大下近似的问题转化为求概念的最简多元最小上界和最简 多元最大f 界问题； 给出求最简多元最小上界和最简多元最大下界的高效算法，并证明算法的正确性和完备性。 1 6 论文结构 论文主要分为三个部分。第一部分是第一幸和第二章，综述全文，介绍近似查询技术的相关概 念，指出目前存在问题和解决思路，明确本文的目标是求概念的最佳近似。第二部分包括第三章， 是本文方法的理论基础。引入新的多元界定义改善近似查询的质量，将求概念最佳近似的问题转化 为求概念最简多元界，第三部分是本文的重点，包括第四章和第五章。分别给出了求概念最简多元 最小上界和晟简多元最大下界的算法，详细给出算法步骤，并证明算法的正确性和完各性。 论文主要各章节摘要如下： 第一章是论文的绪论。从选题背景开始，简述近似查询技术的研究现状，提出课题研究思路和 论文的主要内容，概要枚举论文的研究成果，描述论文结构。 第二章简介语义网和本体技术，介绍基于本体的查询以及近似查询的基本概念，简述现有的基 于概念晟小上界和最大下界的近似查询方法，分析其中存在的问题，提出本文的目的和思路。 第三章定义概念的晟佳近似，引入概念的多元最小上界和多元最大下界，并证明通过概念的多 元界可以求得概念的最佳近似。定义概念的最简多元最小上界和最简多元最大下界，去除多元界中 的冗余，提高查询效率，将求概念的最小上近似和最大下近似的问题转化为求概念的最简多元最小 上界和最简多元最大下界的问题。 第四章给出求概念的晟简多元最小上界的算法。算法采用迭代递增的过程寻找最简多元摄小上 界，在每一步迭代中利用本体的概念层次关系缩减搜索空间。说明算法的详细过程及其理论依据， 并给出算法的完备性和正确性证明。分析算法的复杂度和有效性。 第五章给出并分析求概念的最简多元最小上界的算法。 第六章对论文进行总结，探讨相关问题，展望今后工作。综述本文在近似查询技术方面所作的 工作及取得的成果，指出现有工作的局限性和需要改进的方面，简述正在或将要进行的研究工作。 4 第二章近似查询技术的相关概念 第二章近似查询技术的相关概念 简单介绍语义网和和本体，综述基于本体的近似查询技术的相关概念、方法及其发展，简述现 有的基于概念最小上界和最大下界的近似查询方法，分析其中存在的问题及引发问题的原因，提出 解决思路。 2 a 语义网简介 w w w 的全球化和快速发展使得w 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 的形式，为w e b 信息附加计算机可 理解的内容，称为w e b 信息的语义，便于计算机更好地处理。前者需要机器具有较高的智能，而后 者则更容易实现。 基于为w e b 信息附加计算机可理解语义的思想，w w w 的发明者t i mb e m e r s l e e 在1 9 9 9 年提 出了作为下一代w w w 雏形的语义网【4 j 。语义网扩展了当前w v n ，的功能，提供了形式化的知识和 数据表示，使得网络中尽可能多的信息都具有计算机可理解处理的语义，从而极大便利人和计算机 之间的交互与合作。有一个专门的组织w o r l dw i d ew e bc o n s o r t i u m ( w 3 c ) 进行改进、扩展和标准化 语义网的工作。很多不同学科和行业的研究机构和企业也都参与到语义网及其相关技术和标准的研 究、开发和制定中来。当前语义网体系结构从底向上包括以下层次： l u n i c o d e + u r ：u n i c o d e 处理信息的编码，u 对标识信息的位置； 2 l + n s + 订ls c h e m a ：作为表示和交换信息的基本语法； 3r d f + r d fs c h e m a ：描述各种w e b 信息资源及它们之间关系； 4 o n t o l o g y ：描述w e b 信息更复杂的语义； 5 逻辑： 6 证明； 7 信任。 语义网的最底层是使得不同地区和平台的程序可以交换和定位网络信息的两种标准：u n i c o d e 和u r i 。不同的地区和国家使用不同的语言文字，不同的系统也常常采用不同的编码标准，在交换 数据时需要进行翻译和转换。u n i c o d e 是一个字符编码系统标准，支持世界上所有主要语言文本的混 合。不同地区和国家都可以使用u n i c o d e 来对字符编码而不会产生冲突。统一资源标识( u n i v e r s a l r e s o u r c ei d e n t i f i e r , u r j ) 是一个表示网络资源的字符串，它能够确保自身表示的资源和人人都能在 网络上找到的一个唯一定义相联系。任何人只要通过在网络上定义一个u r i ，就定义了一个唯一的 瓷源。 可扩展标记语言( e x t e n s i b l em a r k u pl a n g u a g e ，x m l ) 、资源描述框架( r e s o u r c ed e s c 咖t i o n f r a m e w o r k ，r d f ) 和本体( o n t o l o g y ) 这三层是语义网的核心，语义网中信息的语义由这三层负责 表达。x m l 让每个人都能创建自己的标签来对网页进行注释，也就是允许用户在文档中加入任意的 结构，但无须说明这些结构的含义，这些含义由r d f 来表达。本体用于知识表达、知识共享和重用。 x m l 是一个易用的网络数据的语法，对计算机可理解和处理的一切数据编码，用x m ls c h e m a 来指示数据结构，是语义网的一种基础语言。它可以在不同地区和不同系统之间进行信息交流，完 全可以充当网际语言，是语义网上数据和文档交换的标准机制。 r d f 则是描述w e b 资源的数据模型，r d fs c h e m a 更扩展了这个功能，提供了定义r d f 模型的 东南大学硕士学位论文 方法。r d f 模型类似面向对象模型，它把w e b 资源看作实体描述实体和实体间的二元关系，以及 实体自身的属性，在一定程度上为资源提供语义信息。该模型由统一的( 资源，属性，属性值) 三 元组形式构成，提供了一种在网络上对元数据进行编码、交换和重用的基本结构。r d f 模型支持对 网络信息源和服务以及智能应用的集成和统一的访问，并用标准的机制去交换数据和处理不同的数 据语义。它通常用于表示其他网络资源如x m l 文件的元数据，作为网络数据交换的通用框架。 r d f 和r d fs c h e m a 有一定的语义表达能力，但对表达w e b 知识来说，这些能力是远远不够的。 本体在此基础上为语义网提供了更强的表达能力，可以描述更为丰富的语义信息。 5 7 层在下面四层提供的语义和规则的基础上进行逻辑推理、证明和信任等操作，从而完成各 种智能化的网络服务和应用。逻辑层是利用语义网上分布的断言导出新知识，包括对信息语义的逻 辑推理规则。证明层用一种普遍性的语言来表达逻辑推理过程和交换证明。通过复杂逻辑和交换证 明建立信任关系；利用数字签名等技术，使一个团体在一定范围内可信任。 语义网是一种新兴的网络形式，是未来网络发展的方向之一。它将极大地改善网络的功能，使 网络更易于访问、更便于管理。在信息检索方面，语义网可以极大改善查询的质量，提供智能化的 语义信息查询。 2 2 本体简介 本体晟早是一个哲学上的概念，指的是对客观存在的一个系统的解释或说明。它关心的是客观 现实的抽象本质。后来本体被引入到人工智能和计算机领域以及语义网的研究中，成为描述w e b 信 息语义的重要工具。这里的本体有多种定义：“本体是给出构成相关领域词汇的基本术语和关系，以 及利用这些术语和关系构成的规定这些词汇外延的规则的定义”；“本体是概念模型的明确的规范说 明”；“本体是共享概念模型的形式化规范说明”等等。当前语义网研究人员广泛接受的本体定义认 为本体是共享概念模型的明确形式化规范说明9 j 。这包含四种含义： 1 概念模型( c o n c e p t u a l i z a t i o n ) ：是指通过抽象客观世界中的现象的相关概念而得到的模型， 概念模型表现的含义独立于具体的环境状态； 2 明确( e x p l i c i t ) ：概念和概念的约束都有明确的定义： 3 形式化( f o r m a l ) ：是计算机可读的，可以被计算机处理； 4 共享( s h a r e ) ：本体体现的是共同认可的知识，反映的是相关领域内的公认的概念集。 总的来说，本体的目标是捕获相关领域的共有知识，提供对该领域知识的共同理解，确定该领 域内共同认可的词汇，并从不同层次的形式化模式上给出这些词汇( 术语) 和词汇问相互关系的明 确定义，实现对领域知识的推理。从知识共享的角度来说，本体是通用意义上的概念定义集合，是 在各种知识系统间交换知识的共同语言。 一个本体用于描述一个论域中的概念。拥有共同属性的对象被组织成概念，对共享属性的描述 称为概念定义。概念被组织到一个通过子类父类关系构成的分类层次中，类似于信息检索中的分类 层次和面向对象中的类继承层次。而一类的对象和另一类对象间常常存在一定的关系，这些关系说 明了对象间的结构。因此本体通常包含以下元素 1 论域中概念的正规描述概念( c l a s s 或称c o n c e p t ) ： 2 每一概念不同特征性质以及概念和概念之间存在的关系( s l o t 、r o l e 或p r o p e r t y ) ； 3 每一特征或关系上的约束和限制( f a c e t s 或者r o l er e s t r i c t i o n ) ，也称为公理( a x i o m ) ： 4 一组概念的实例( i n s t a n c e ) ，也称为个体( i n d i v i d u a l ) ，用来描述单独对象的相关事实。 目前w e b 本体大多采用描述逻辑作为逻辑基础。网络本体语言o w l 是目前w 3 c 推荐的描述 网络本体的语言。o w l 通过提供附加的形式语义的词汇集，具有比x m l 、r d f 和r d f s 更多的网 络内容的机器可读性。o w l 可以描述属性和类，类之间的关系，基数和等价约束，丰富的属性类型， 属性的特性，枚举类和数据类型等，提供了强大的信息语义描述能力。 本体通过对概念以及概念和概念之间的关系的严格定义来确定概念的精确含义，表示被共同认 可的、可共享的知识，是解决语义层次上网络信息共享和交换的基础。本体在语义w e b 中的骨架地 位促使本体的研究和开发成为整个语义w e b 研究中的重点。众多的w e b 本体在人类知识的各个领域 实现语义w e b 的知识表示，将为语义w e b 的到来奠定良好的坚实基础。 在信息检索中，特别是在面向网络的基于知识的检索中，因为本体具有良好的概念层次结构和 对逻辑推理的支持，得到了广泛的应用。如t a p 系统应用本体支持基于主题的搜索，帮助实现上下 文相关的查询并把结果置于知识库中，取得了很好的查询效果。搜索引擎可以利用本体进行更精确 更全面的查询，还可以对复杂的语义进行查询，甚至利用推理来验证查询的结果。基于本体的信息 系统是实现语义w e b 智能信息检索的基础。 6 第二章近似查询技术的相关概念 但是在本体的应用中也存在一些问题：本体之间往往是异构的，构造本体的目的不同，本体表 示的方法也不统一。异构本体之间难以进行互操作。本体映射和集成的研究就是想要解决这个问题。 近似查询技术也是为了解决查询中遇到的本体异构问题。 2 3 本体间近似查询的基本概念 查询问题有两个概念：信息过滤和信息检索。前者把和用户需求无关的信息过滤掉；后者则根 据用户的查询，返回符合要求的信息结果。两者的实现技术是一致的。经典的查询通常是通过关键 词匹配，其中很多系统还支持关键词构成的布尔表达式查询。也已经有系统使用背景知识来增加查 询的精度，比如利用词汇间的同义关系，但由于关键词本身不具有语义，查询结果的精度仍不能满 足需要。 基于本体的信息系统可以通过精确的语义而不是模糊的关键词来查找信息从而增加查询的查 准率和查全率【6 j 。在这样的信息系统中，网页和文件根据本体进行标注或分类，查询用本体中的词 汇表达。其中最基本的查询形式是概念查询。根据网页的信息内容，可以指派页面属于本体中的概 念。这个指派提供了对信息含义的解释。这时使用对概念名进行的布尔查询，如果指派是正确的话， 可以得到符合信息语义的精确结果。 定义1 信息源是网页、文档等信息项的集合。如果信息源5 中的信息项都分类到本体d 中的 一个或多个概念，也就是把信息项作为d 中的实例，则称s 为基于本体0 的信息源。令0 中全部概 念的集合为丁，( 严是解释函数：对于丁中每一个概念c ，d 表示被分类到概念c 的s 中信息项的集 合。顶概念f 印和底概念6 0 f 是特殊的概念，对于任意s 有：印卿包含s 中所有信息项，b o c a 为空。 在基于本体0 的信息源中，每个信息项都和一个或多个0 中概念相关联，信息源中的信息便具 有了语义。把信息项分类到各个概念中的过程应由领域专家完成，称为语义标注。在进行查询时， 通过使用概念名可以精确的找到这些标注好的信息项。 本体中概念间存在蕴涵关系，令c ，d 为，中概念，如果d 是c 的超类，则称d 蕴涵c ，记作 c e d 。它表示，任何c 的实例一定也是d 的实例。这样的蕴含关系通常是在本体的概念层次中表 述的一般性知识。本文规定所有的信息源都与概念蕴涵关系兼容，即对于任意信息源s 和概念cd ， 有c e d - - - 一d 心。 现有的信息检索系统普遍采用布尔查询模型【1 】。在基于本体的查询中，概念查询也是概念通过 布尔算子八( a n d ) ，v ( o r ) 和，( n o t ) 连接得到的，简称查询。每个查询的查询结果实一个信息项的 集合，定义为查询的解释。使用概念名代替关键词赋予了查询一个清晰的语义，使得可以对查询结 果进行推理。在概念语义基础上定义的布尔概念查询语义，给出了查询和本体直接的联系，查询结 果可以被系统精确的解释。一个查询的解释总能通过其中概念的解释的集合操作得到。下面形式化 的给出概念查询和查询解释的定义。 定义2 概念查询是本体中概念构成的布尔表达式。对于任意信息源s ，查询q 的解释毋定 义为s 中所有满足表达式q 的信息项的集合。令本体o 中全部概念的集合为t ，s 是任意的信息源 则关于o ( 或者说关于，) 的查询定义为： 1 如果c 是丁中的概念，那么c 是一个查询，它的解释为d ； 2 如果q ，r 是查询，那么q v r ，q a r 也是查询，解释分别为： v 固哟= q 柙u r 哆( q r ) 帼= q 俩 n j 蚴： 3 如果q 是查询，那么、q 也是查询，它的解释为( ，q ) 1 ( s ) = f p 9 一q 胸。 通过定义l ，信息源中的信息项按本体中的概念进行了分类。而定义2 说明查询是概念的布尔 表达式，而查询的解释是概念解释运算的结果。因此给定一个查询，可以用其中包含的概念对应的 信息项集合进行集合运算求得应返回的查询结果。 查询的解释同样对应着实例的集合，可以认为查询是复杂的概念。因此查询之间也存在蕴涵关 系，定义如下 定义3 令q ，r 是查询，如果在任意信息源s 中都有q “o r “毋，则称r 蕴涵q ，记作q e 月； 如果r e q 且q e r ，称q 和r 等价，记作q = - r ；如果q e r 但q s 月不成立，称r 严格蕴涵q ， 记作q r ；如果在任意s 中为空，则有q 6 “。 w e b 查询系统都面临着要在分布式的异构系统间进行查询的需求。过去很长时间里，这个问题得 通过手工编码的变换查询来解决。后来兴起的中间件思想可以帮助用户灵活的定义不同数据模型间的 东南大学硕士学位论文 映射关系。这种定义了不同信息结构间的映射规则的中介系统，用来解决数据库结构集成问题。对异 构数据库模式集成的研究成果可以用于信息结构层次上的集成，如集成不同的x m l 模型。它提供一 个多个异构数据源的统一的标准查询界面，目的就是用户在对多个数据源的查询中不用一个个的考虑 数据源的相互影响和人工结合这些数据源的数据。这需要给用户提供一个中间