（计算机科学与技术专业论文）一种用于本体排序的内容分析方法的研究.pdf

r e s e a r c ho i lac o n t e n t a n a l y s i sm e t h o du s e df o ro n t o l o g y r a n k i n g s p e c i a l t y ：c o m p u t e rs c i e n c ea n dt e c h n o l o g y m a s t e r d e g r e ec a n d i d a t e ： s u p e r v i s o r ： p r o f x ud e z h i c o l l e g eo fi n f o r m a t i o ns c i e n c e & e n g i n e e r i n g c e n t r a ls o u t hu n i v e r s i t y c h a n g s h ah u n a np r c 50 眦7i9mmmim，1y 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致 谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得中南大学或其他单位的学位或证书而使用过的材 料。与我共同工作的同志对本研究所作的贡献均已在论文中作了明 确的说明。 作者签名：虱性聱日期：型! 里年上月盟日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论 文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或 部分内容，可以采用复印、缩印或其它手段保存学位论文。同时授 权中国科学技术信息研究所将本学位论文收录到中国学位论文全 文数据库，并通过网络向社会公众提供信息服务。 、 作者签名：过盗整导师签名煎龃日期：致年上月丑日 摘要 随着语义w e b 的发展，本体技术受到了越来越广泛的关注。如 何帮助用户有效地获得相关本体，提高本体重用度和开发效率成为 一项重要的研究课题。本文将着重对本体搜索中的核心问题，即用 于本体排序的方法进行研究。 首先，文中介绍了课题的研究背景，对语义w e b 和本体进行了 简介，对万维网中的排序问题进行分类总结，针对不同的类别进行 分析并重点介绍了几种有代表性的方法。 然后，为了帮助用户更加快速有效地理解相关本体，提出了一 种本体概要的提取算法。该算法中，通过对本体结构进行分析得出 了一种本体的概念模型，在此基础上得到本体的主题词集合并为本 体中每个概念分配权值，再通过对本体模型进行分析得到本体的重 要属性集，结合本体主题词集合与重要属性集获得本体的概要信 息。 接着，针对传统的用于本体排序的方法的不足，提出了一种用 于本体排序的内容分析方法，根据关键词与本体加权概念的匹配得 到本体与关键词之间的主题相关度，分析关键词在本体中的上下文 信息得到本体的上下文相关度并结合两种不同相关度值得到本体的 排序值。 最后，根据上述研究，设计并实现了用于本体排序的内容分析 方法，利用本体搜索引擎s w o o g l e 获得相关的测试集，对本文提出 的方法进行测试，同时根据所得结果与主观结果之间的皮尔森相关 系数来评价本方法，实验结果表明，该方法与已有的o n t o r a n k 方法 比较，更加接近于主观排序结果。 关键词语义w e b ，本体排序，本体概要，主题相关度，上下文相关 度 l a b s t r a c t a st h ed e v e l o p m e n to ft h es e m a n t i cw e b ，o n t o l o g i e st e c h n o l o g yi s p a i dm o r ea n dm o r ea t t e n t i o nb yr e s e a r c h e r s i tb e c o m e s av e r yi m p o r t a n t r e s e a r c hs u b j e c tt h a th o wt oh e l pu s e r sg e tt h eu s e f u lo n t o l o g i e sa n dr e u s e t h e me f f e c t i v e l y i nt h i st h e s i s ，i tm a i n l yf o c u s e so no n t o l o g i e sr a n k i n g w h i c hi st h ek e yi s s u ei nt h eo n t o l o g i e ss e a r c ha r e a f i r s t ，i ti n t r o d u c e st h eb a c k g r o u n do ft h es u b j e c ti n c l u d i n gt h e s u m m a r ya b o u tt h es e m a n t i cw e ba n do n t o l o g i e s t h e ni tc l a s s i f i e st h e r a n k i n gp r o b l e mi nt h ew o r l dw i d ew e ba c c o r d i n gt ot h er a n k i n go b j e c t s t oe v e r yc a t e g o r y , i ta n a l y s e st h em a i nm e t h o da n dt a k e ss o m et y p i c a l a l g o r i t h m sf o re x a m p l e s e c o n d ，i no r d e rt oh e l pu s e r st ou n d e r s t a n dr e l a t e do n t o l o g i e s ，i t p r o p o s e s a l l a l g o r i t h mo fe x t r a c t i n gt h eo n t o l o g ys c h e m a i nt h i s a l g o r i t h m ，i tg e t st h eo n t o l o g yc o n c e p tm o d e la c c o r d i n gt ot h es t r u c t u r e o ft h eo n t o l o g i e s b a s e do nt h eo n t o l o g yc o n c e p tm o d e l ，i to b t a i n st h e o n t o l o g yk e yw o r d ss e ta n da s s i g nt h ew e i g h tt oe v e r yc o n c e p t t h e n ，i t g e t st h ei m p o r t a n tp r o p e r t i e ss e ta c c o r d i n gt ot h eo n t o l o g yc o n c e p tm o d e l a n dt h ew e i g h to ft h ec o n c e p t t h eo n t o l o g ys c h e m ai sg o t t e nc o m b i n i n g t h eo n t o l o g yt o p i cs e tw i t ht h ei m p o r t a n tp r o p e r t i e ss e t t h i r d ，a i m i n ga tt h ep r o b l e mt h a tt h eo n t o l o g yr a n k i n gr e s u l ti sn o t p r e c i s ee n o u g hu s i n gt r a d i t i o n a lm e t h o d ，i tp r o p o s e dan e wc o n t e n t a n a l y s i sm e t h o d i tg e t st h et o p i cr e l a t e d n e s sa c c o r d i n gt ot h em a t c h b e t w e e nt h ek e y w o r da n dt h ew e i g h t e dc o n c e p ta n dg e t st h ec o n t e x t r e l a t e d n e s sb ya n a l y z i n gt h ec o n t e x to ft h ek e yw o r d a n dt h e nt h e r a n k i n gs c o r ec a nb ec a l c u l a t e db yc o m b i n i n gt h et o p i cr e l a t e d n e s sa n d c o n t e x tr e l a t e d n e s s f i n a l l y , a c c o r d i n gt ot h er e s e a r c ha b o v e ，i td e s i g n sa n di m p l e m e n t s t h ec o n t e n ta n a l y s i sm e t h o du s e df o ro n t o l o g yr a n k i n g i tg e t st h et e s ts e t b yu s i n gt h eo n t o l o g ys e a r c he n g i n es w o o g l et ot e s tt h ep r e c i s i o no ft h i s m e t h o d t h ee x p e r i m e n t a lr e s u l ti se v a l u a t e db yt h ep e a r s o nc o r r e l a t i o n c o e f f i c i e n tb e t w e e nt h es u b je c t i v er e s u l ta n dt h ee x p e r i m e n t a lr e s u l t t h e l i e x p e r i m e n t a lr e s u l ts h o w s t h a tc o m p a r i n gt ot h eo n t o r a n ka l g o r i t h m ，t h e r e s u l tg e t sf r o mt h i sm e t h o di sm o r es i m i l a rt ot h es u b j e c t i v er a n k i n g r e s u l t k e yw o r d ss e m a n t i cw e b ，o n t o l o g yr a n k i n g ，o n t o l o g ys c h e m a ， t o p i cr e l a t e d n e s s ，c o n t e x tr e l a t e d n e s s 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 课题研究背景一1 1 1 1 语义w e b 简介。1 1 1 2 本体2 1 1 3 本体描述语言5 1 2 主要研究内容一5 1 3 论文组织结构6 第二章万维网中排序问题研究综述8 2 1 传统的用于信息检索系统中的排序技术8 2 1 1 基于链接分析的方法8 2 1 2 基于用户行为的方法10 2 2 用于本体排序的相关技术1 1 2 2 1 基于链接分析的方法1 1 2 2 2 基于结构分析的方法1 3 2 2 3 基于内容分析的方法1 4 2 3 用于本体元素排序的技术1 4 2 3 1t e r m r a n k 算法1 4 2 3 2c a r r a n k 算法一l5 2 3 3t r i p l e r a n k 算法l5 2 4 万维网中其他排序问题16 2 5 小结1 6 第三章本体概要提取算法l7 3 1 本体概念模型的提出l7 3 2 本体主题词提取算法l8 3 2 1 本体概念的处理1 9 3 2 2 本体主题词的提取2 3 3 3 本体概要提取算法2 4 3 4 本体概要提取算法的相关分析一2 7 3 5 小结2 9 第四章用于本体排序的内容分析方法3 0 4 1 本体主题相关度计算3 0 4 1 1 本体主题词对排序结果的影响一3 0 4 1 2 主题相关度计算3 1 4 2 本体上下文相关度计算3 2 4 2 1 概念上下文分析3 2 4 2 2 上下文相关度计算算法3 2 4 3 本体排序值的计算3 5 4 4 刀、结3 5 第五章实验结果及分析3 6 5 1 实验设计3 6 5 1 1 实验数据的获得。3 6 5 1 2 实验过程3 7 5 2 实验结果与分析3 7 5 2 1 实验结果3 7 5 2 2 评价方法及皮尔森相关系数简介3 8 5 2 3 与s w o o g l e 排序结果的比较3 9 5 3 小结4 0 第六章结论与展望4 1 6 1 研究工作及成果总结4 1 6 2 进一步研究方向4 2 参考文献4 3 致谢4 8 攻读学位期间主要研究成果4 9 i i 第一章绪论 第一章绪论 不断发展，网络在人们的生活中起到了越来越重要的作 提供了很大的便利。然而，现今网络上的信息是以机器 表达的，随着网络中信息数据的不断增长，万维网中信 息的表达和检索面临着越来越大的挑战，网络的智能化程度逐渐不能满足用户 的需求。为了使万维网上的信息具有语义，达到更高的自动化和智能化程度以 便用户更好地与万维网进行交互，国际万维网之父t i mb e m e r s l e e 于上世纪九 十年代末期首次提出了语义w e b 1 j 的概念。随后，在2 0 0 0 年的世界x m l 大会 上，他又做了相关的报告，更加深入地描述了语义w e b 的概念，并提出了语义 w e b 的七层模型体系结构1 2 】。在t i mb e r n e r s l e e 对语义w e b 的描述中，语义 w e b 是对当前基础w e b 的一个扩展，但语义w e b 并不是独立的w e b 而是通 过在信息中添加相关的语义信息来达到计算机可以自动地与人进行交互的目 的。即语义w e b 中的信息是相互联系的，信息本身也是存在语义的，使计算机 可以自动地理解信息语义，从而提高万维网的自动化和智能化程度。 1 1 课题研究背景 随着语义w e b 概念的提出，语义w e b 的各项技术也引起了大量研究者的 兴趣。本体技术作为语义w e b 的核心内容更是受到了足够的重视。 1 1 1 语义w e b 简介 语义w | e b p j 是智能化的网络，它在当前w 曲的基础上添加了语义信息，从 而达到一种计算机可以自动地理解信息含义的目的。由于计算机可以智能地理 解信息的语义，因而，可以使计算机更加准确地获得相关信息，并对这些信息 根据用户需求进行选择和处理，返回用户真正感性兴趣的信息，并进行组合， 从而提高了网络的自动化程度。语义w e b 的提出，一方面可以使机器自动放弃 大量的垃圾信息，使返回结果更加满足用户需求，提高检索的查准率，另一方 面，由于计算机的智能性，可以大大地减少用户的工作量，提高检索的效率。 语义w e b 体系结构是t i mb e m e r s l e e 提出的一种层次结构1 2 i ，可以分为七 个层次 4 1 ，它存在于网络o s i 七层模型之上的，如图1 1 所示。 第一层为语义w e b 的基础，u n i c o d e 表示资源的编码格式，使用u n i c o d e 硕士学位论文 第一章绪论 可以对多种字符集进行统一的表示；u r i 可以用来给出一个资源区别于其他资 源的标识，从而有效地区分不同的资源； 第二层使用一种可以由用户来进行定义的标记语言来表示语义w e b 中的数 据； 第三层主要用来描述w e b 中的资源和资源的类型。其中，r d f 为一种资源 描述框架，r d fs c h e m a 是一种可以表达语义的简单的本体词汇集，但是其表 达语义的能力不够强大； 第四层是用来表达资源语义的最重要的一层，也是语义w e b 体系结构中最 为核心的一层，它能够描述语义的实质也就是资源与资源的关系； 第五层用来进行推理，通过对知识库推理，可以得到知识库中存在的隐式 信息，该层同样是语义w e b 七层模型中非常核心的一层，是实现w e b 智能化 和自动化的关键。此外，它在本体的构建和应用领域都起到了非常重要的作 用； 最高两层用来对信息的正确性和信息的可靠性进行相关验证。 图1 一l 语义w e b 的体系结构 目前，在语义w e b 七层模型中，对第一层u n i c o d e 和u r i 的相关技术 研究已经出现了很多，而且比较成熟，相关的应用也有很多，所以下面不再进 行进一步的介绍；而对处于最上面的几个层次p r o o f 、l o g i c 和t r u s t ，相关的 研究还非常地少，基本上还处于构想阶段；如今，语义w r e b 中的热点研究主要 集中在其他几个层次，本文的研究也主要是面向本体层的，因此下面只对本体 的相关知识进行重点的介绍。 1 1 2 本体 本体是语义w e b 中表示概念的重要模型，是语义w e b 中一项关键的技 术。本体层作为语义w e b 体系结构中最核心的一层，是对其下面层次的扩展， 2 硕士学位论文 第一章绪论 用来描述资源与资源的关系并以此反映信息的语义。本节详细介绍了本体的定 义、本体的应用领域、本体的研究方向等内容。 1 本体的定义 本体最初是在哲学中定义并得到广泛使用的概念【5 1 。后来，在计算机科学 中的人工智能领域也给出了相关的定义并得到了相关的应用 6 1 。后来经过各科 研工作者更加深入地研究，给出了本体的定义，即它是对共享概念模型形式化 的、明确的、规范的说明f 7 】，该定义包括了四层涵义：共享、形式化、明确和 概念模型。 1 ) 共享，指本体中的概念集是对该领域中公认知识的一种反映，也就是说 本体中所有的元素都是团体的共识而不是个人的意见。 2 ) 形式化，是指本体是可以被计算机处理的。 3 ) 明确，指对所有的概念及概念与概念间的相互关系都要有明确的定义。 4 ) 概念模型，是对客观世界中的一些现象进行抽象而得到与之相关的概念 并根据这些概念而得到的模型，其含义是与具体环境无关的。 本体的目标是通过分析领域相关知识，得到对该领域的一种公认的理解， 从而获得大家公认的概念，并形式化的给出这些概念的明确定义以及概念与概 念之间的相互关系。 2 本体的应用领域 随着万维网在智能化和自动化方向的不断发展，本体技术在很多领域获得 了普遍的应用，如本体在信息检索领域中的应用，本体在信息抽取领域中的应 用，本体在w e b 服务领域中的应用等，此外，本体在电子商务，电子工程和数 字图书馆等领域也有着非常重要的应用。本节主要对本体的典型应用进行简 介。 1 ) 本体在信息检索领域中的应用 本体作为语义w e b 中一种最为重要的表示概念的模型，具有良好的概念层 次结构、概念之间具有良好的相互关系同时本体具有较好的推理能力。在信息 检索领域【8 9 】中，本体已经获得了相关的应用，主要可以应用于两个方面。第 一，在文档领域中应用相关的本体l i o j ，可以更加精确有效地得出文档所归属的 领域信息；在用户检索条件中使用相关本体i l l l ，可以对用户的检索请求进行规 范化处理，从而更加明确用户的需求。同时，利用本体良好的推理能力，可以 3 硕士学位论文第一章绪论 对用户检索条件进行相关推理，从而提高搜索的查全率和查准率。 2 ) 本体在信息抽取领域中的应用 本体在信息抽取领域中的应用f 1 2 】已经成为了一个热点研究问题，将其用在 信息抽取领域，可以帮助用户获得相关的抽取规则【1 3 】。相对于其他的抽取方 法，通过将本体使用在信息抽取领域，其结果是由领域本体决定且独立于文档 本身的，其关键是对领域本体的选择，只要领域本体选择正确，就可得到较高 的查全率和查准率。 3 ) 本体在w e b 服务领域中的应用 w e b 服务模型是w 3 c 倡导的一种应用，用来弥补传统的分布式所存在的 不足，以更好地适应w e b 环境。其良好的封装性、高度的灵活性、松散的耦合 性、标准协议的规范性等优点使其在很多领域中得到了相关的应用1 1 4 1 。 随着语义w e b 的发展，本体对w e b 服务匹配【1 5 】、w e b 服务发现【1 6 1 及w e b 服务组合技术f 17 】的发展都起到了推动作用。w 3 c 也针对w e b 服务推出了 o w l s t l 8 1 本体，使w e b 服务向着更加智能的方向发展，为机器理解w e b 服务 的特征提供了一种可能。本体在w e b 服务领域中的应用，有效地改善了w e b 服务匹配的查全和查准率以及w e b 服务发现与组合的可行性。 3 本体的研究方向 随着语义w e b 的发展，本体的应用越来越普遍，对本体的研究也逐渐多了 起来，本节主要介绍当今对本体的研究方向。 1 ) 本体映射 随着本体越来越多的得到应用，对于本体的研究也受到了越来越多的研究 者的关注，万维网上大量的本体被创建了出来，然而，由于对本体的构建过程 并没有一种大家都遵守的公认的标准，产生了本体的异构性，给信息集成和共 享造成了一些麻烦。为了解决这一问题，本体映射【1 蛇0 1 是使用最广泛的一种方 法，通过本体映射，可以得到不同本体间元素的对应关系。 为了推动本体映射研究的发展，o a e i 国际组织每年组织一次本体映射系 统的比赛，通过提供一系列的测试数据集对现有的系统进行评估。 2 ) 本体推理 语义w e b 中，为了实现网络的智能性，需要使用本体对语义w e b 中的信 息进行描述。本体推理是以描述逻辑【2 1 】为基础的，通过推理可以检测本体中的 4 硕士学位论文第一章绪论 不一致性，发现本体元素之间的联系。对于本体推理机制的研究和使用能够有 效地提高对万维网中信息检索的查全率和查准率等要素【捌。 1 1 3 本体描述语言 本体描述语言是为形式化表示语义w e b 中的概念模型而提出的用来定义本 体的语言。现今已存在很多种本体描述语言，包括r d f ( r e s o u r c ed e s c r i p t i o n f r a m e w o r k ) 和r d f s 、d a m l 、o i l 、d a m l + o i l 、o w l ( w r e bo n t o l o g y l a n g u a g e ) 等。其中，r d f 为资源描述框架，是最为基础的一种本体描述语 言，o w l 是w 3 c 所推荐的一种本体描述语言，这两种语言是现今使用最多的 本体描述语言，本节重点介绍r d f 和o w l 这两种本体语言。 r d f 是w 3 c 所推荐的一种描述万维网上资源的语言标准【2 3 】，元数据通常 可以使用r d f 来表示。r d f 中，使用u r i r e f ( u 刚引用) 来区分不同的元数 据，每个资源都有其唯一的标识，并且u r i r e f 是机器可以理解的。每个r d f 陈述均由主语、谓语和宾语三种元素组成的三元组来表示。对于任何一个r d f 陈述，都可以选择三元组模型，图模型或者r d f x m l 文档模型中的一种来表 示。但是r d f 只提供了对资源的形式化表示，并没有对任何一个领域知识进行 相关定义，因此在表示语义信息时存在很大的缺陷，为了弥补r d f 模型的这一 不足，r d f s 被提出，用来定义相关的词汇集对其进行扩展和补充。 o w l 是w 3 c 所推荐的一种本体描述语言的标准【2 4 l 。与r d f r d f s 相比， o w l 具有更强的表达语义的能力。为了满足不同层次用户的需求，o w l 定义 了如下三类子语言：o w ll i t e 、o w ld l 和o w lf u l l ，这三类语言表达语义 的能力是逐渐增强的。其中，o w ll i t e 只能用来定义简单的分类层次体系和简 单的约束关系，表达能力最弱但具有良好的计算性；o w ld l 是基于描述逻辑 的，表达能力要优于o w ll i t e 且具有可判定性，但其复杂度要高于o w l l i t e ；o w lf u l l 是表达能力最强的，复杂度也最高，但是不能保证可计算性。 o w l 的三种子语言表达能力不同，计算能力不同，各有优缺点，用户可以根据 自身的需求来选择不同的本体语言。 1 2 主要研究内容 随着万维网技术的发展，网络成了人们日常生活和学习中不可或缺的一部 分。然而，万维网中的数据正以极快的速度增长，网络智能化程度低，使得用 户搜索过程中返回的信息数目大，选择困难，为了使机器能够理解语义，语义 硕士学位论文第一章绪论 w e b 应运而生。本体为语义w - e b 中的重要的表示知识的模型，在语义w e b 中 起到了至关重要的作用。然而，随着语义w e b 的发展，万维网中的本体数目日 益增多，而开发一个合适的本体对研究者来说是一件既费时又费力的工作。为 了减少开发者的工作量，提高开发效率，如何对已有的本体进行重用受到了越 来越多的研究者的关注。为了帮助用户快速的选择已有本体，本体搜索引擎返 回的本体列表排列顺序至关重要，对用于本体排序的问题的研究受到了越来越 多的研究者的重视。 本文研究的核心内容包括：本体的概要提取算法；用于本体排序的内容分 析方法排序值的得出及实验评估。 1 本体的概要提取算法 本体元素中，概念在对用户理解本体方面的帮助要远远大于本体的其他元 素，本文提出了一种本体的概念模型，并在该模型的基础上提出了一种本体主 题词集合提取算法，实现了对本体中主题词概念集合的提取，并通过对本体主 题词集合进行分析得到本体的重要属性信息，再通过结合本体主题词集合中的 元素和本体的重要属性集中的元素生成本体的概要。这部分的研究，一方面作 为后面研究内容的基础，另一方面可以帮助用户快速理解本体信息，从而可以 提高用户搜索并选择本体的效率。 2 用于本体排序的内容分析方法 针对用于本体排序的方法中没有考虑的本体的本身信息，或者没有考虑到 本体中元素之间的差异性而仅从元素数量方面来得到本体排序值，使得本体排 序结果不够准确的问题，本文提出了一种用于本体排序的内容分析方法，不仅 从结构上分析了本体，而且从本体的主题和上下文信息两个方面对本体进行分 析，从而提高本体排序结果的准确性。 1 3 论文组织结构 论文共分六章，其结构如下： 第一章为绪论，首先介绍了本课题的研究背景，包括对语义w e b 及其体系 结构的简介，对本体的基本定义、描述语言及其应用领域的简介等；然后对本 文研究的核心内容进行了介绍； 第二章为万维网中排序问题研究综述，根据排序对象的不同，分三类进行 介绍，包括对传统信息检索系统中排序问题的介绍，对用于本体排序的技术的 6 硕士学位论文 第一章绪论 介绍，对用于本体元素排序的技术的介绍。对每一类排序问题，根据所使用技 术的不同分别进行分析，并对典型的算法进行了相应的描述： 第三章为本体的概要提取算法，首先对本体结构进行分析得到本体的概念 模型，然后在本体概念模型的基础上对本体进行分析，得出本体的主题词集合 并为本体中的概念分配相应的权值。最后根据本体的结构特征对本体的属性进 行分析得到本体的重要概念，并结合本体的主题词集合和重要属性集合得到本 体的概要信息，从而帮助用户快速准确地理解本体； 第四章为用于本体排序的内容分析方法，首先通过关键词与本体的加权概 念匹配得到本体的主题词相关度，然后根据对关键词所处的本体上下文得到本 体的上下文相关度，最后结合本体的主题相关度和上下文相关度得到本体的排 序值，并进行排序，方便用户选择相应本体； 第五章为实验结果与分析，根据前面两章提出的方法设计相应的实验，并 通过常用本体搜索引擎s w o o g l e 得到相应的候选集进行分析得到本文方法的实 验结果，分析该方法的优势与不足； 第六章为总结和展望，对本文中所做的相关工作进行总结，并指出了进一 步的研究方向。 7 硕士学位论文 第二章万维网中排序问题研究综述 第二章万维网中排序问题研究综述 随着信息技术的发展，万维网上的数据快速增长。由于万维网上海量数据 的存在，给用户查找相关信息带来了很多的不便。为了帮助用户准确高效地找 到相应的数据，搜索引擎应运而生。搜索引擎中使用的排序技术作为一种核心 技术，受到了越来越多的研究者的重视，一个合理的排序技术不仅可以帮助用 户节省搜索时间，提高工作效率，而且可以营造一种公平的互联网环境。 2 1 传统的用于信息检索系统中的排序技术 随着万维网的发展，搜索引擎已经成为了使用最多的网络工具之一。自搜 索引擎诞生的那一天起到现在已经历了三个发展阶段1 2 5 1 。 第一代搜索引擎包含的被索引的网页数目少，网页更新速度慢，搜索返回 时间长，效率低；第二代搜索引擎，由于使用了更加先进的技术并且引入了分 布式计算，使得其无论在被索引的网页数目、网页更新速度还是响应时间上均 比第一代搜索引擎有了很大的提高；现今，常用的搜索引擎都属于第三代搜索 引擎，其索引规模更大，甚至已达上亿个网页，并引入了更加先进的技术，如 用户行为反馈技术、超链接分析技术等，网页更新速度、响应时间和检索的用 户满意程度都有了更大程度上的提高。 本节主要对第三代搜索引擎所用的排序技术进行分析，可以分为基于链接 分析的方法和基于用户行为分析的方法两大类。 2 1 1 基于链接分析的方法 万维网中的页面并不是独立存在的，页面之间通过超链接相互联系，用于 页面排序的基于链接分析的方法便是根据页面之间的这种链接关系来计算网页 排名的，代表的算法包括p a g e r a n k 算法、h i t s 算法和s a l s a 算法等。 1 p a g e r a n k 算法 p a g e r a n k 2 6 1 算法是搜索引擎g o o g l e 的创始人，斯坦福大学的l a r r yp a g e 和 s e r g e yb r i n 所提出的，是g o o g l e 中用到的非常重要的一个页面排序算法。 p a g e r a n k 算法是根据具有链接关系的网页的数量和质量来对网页进行评价的， 主要基于如下两个假设。 8 硕士学位论文 第二章万维网中排序问题研究综述 假设l ：页面的重要性可以由链接到该页面的页面数目来决定，链接到该页 面的页面数目越大，则该页面具有越高的重要性值。 假设2 ：页面的重要性也与链接到该页面的其他页面的重要性有关，其他条 件相同时，链接到该页面的其他页面越重要，则该页面越重要。 基于如上所示的两个假设，页面的p a g e r a n k 可以利用公式( 2 1 ) 来进行 迭代计算。 p r ( a ) ：芝善+ d 步笔挲孕 公式( 2 1 ) 智c ( d ) 这里，假设需要计算p a g e r a n k 值的页面是页面彳，彳的p a g e r a n k 值由 p r ( a ) 来表示，表示万维网上的页面总数，d 是阻尼系数，通常情况下可以取 d = 0 8 5 ，撒( a ) 表示页面a 的p a g e r a n k 值，c ( n ) 表示由页面b 链接到其他页 面的链接数目。 p a g e r a n k 算法使用随机冲浪模型1 2 7 1 ，根据页面之间链接关系来进行迭代得 到每个页面的重要性值，并以此值为依据来对页面进行降序排列的。由于该算 法主要是根据客观存在的链接关系来对页面的重要性进行评价的，极少涉及到 人为的干涉因素，因此得到的结果比较客观。但是，由于新网页存在时间短， 被链接到的概率低，因此该算法对新网页具有一定的不公平性。同时，由于该 算法较少考虑页面本身的内容，会造成部分门户网站得到很高的p a g e r a n k 值， 而这些页面并不是用户真正需要的页面，因此形成了所谓的“主题漂移”现 象，造成了某些结果不准确。为了解决p a g e r a n k 算法的缺陷，研究者提出了相 关的改进算法，如h i l l t o p 算法【2 8 l 和主题敏感的p a g e r a n k 算法【2 9 1 等。h i l l t o p 算 法考虑了主题对排序结果的影响，也就是说具有相同或者相关主题的页面之间 的链接作用要远远大于不相关主题页面之间的链接作用，因此，使用该算法， 可以弥补无效链接对页面p a g e r a n k 值的影响。主题敏感的p a g e r a n k 算法则是 根据o d p ( o p e nd i r e c t o r yp r o j e c t ) 的主题，为每个页面分别计算每个主题的 p a g e r a n k 值，避免“主题漂移 的现象发生，弥补了p a g e r a n k 算法由于缺乏 对主题信息的考虑而造成的缺点。p a g e r a n k 算法及其改进版本的提出，为万维 网中的页面排序做出了很大的贡献，大大提高了页面排序的准确度。 2 h i t s 算法 h i t s 算法【3 0 】为康奈尔大学的j o nk l e i n b e r g 所提出的另种用于万维网排 序的基于链接分析的方法，不同于p a g e r a n k 算法中以页面的权威性作为研究重 点，h i t s 算法是从页面的中心性和权威性两个方面来对页面做出评价的，因此 9 硕士学位论文 第二章万维网中排序问题研究综述 页面也可以分为权威性页面和中心性页面两种。权威性页面即包含了用户需求 信息的页面，中心性页面虽不能直接反应用户需求的信息，但是包含可以链接 到权威性页面的链接，对用户获得有用的信息提供了一定的帮助。h i t s 算法中 页面的权威性由链接到该页面的页面中心性决定，中心性则由该页面链接到的 页面的权威性决定，两种性质互相增强。与p a g e r a n k 算法类似的是，传统的 h i t s 算法由于没有考虑页面的主题信息，因此也不能避免主题漂移的现象的发 生。针对这一不足，研究者通过对不同的超链接提供不同的权值的方法来弥补 此缺陷【3 l l 。此外，如果存在部分页面之间的相互链接关系非常紧密，会出现该 部分页面的权威性和中心性反复相互增强，导致该部分页面具有很高的中心性 值和权威性值，从而产生“密织群现象 。目前，h i t s 算法在实际环境中的应 用还存在着很大的困难，因此其仍然处于研究水平【3 引。 3 s a l s a 算法 s a l s a 算法1 3 3 】是对h i t s 算法的一种改进版本，与h i t s 算法相同的是， 该算法依然保留了页面的权威性和中心性两个最基本的性质，但是由于h i t s 算法中权威性与中心性间相互增强的关系会导致密织群现象的发生，为了改进 这一缺陷，s a l s a 算法放弃了这一思想，而是采用了随机冲浪模型并使用了马 尔可夫链的原理，从而有效地解决了密织群现象的发生。 2 1 2 基于用户行为的方法 基于用户行为的方法也是搜索引擎常用的一种方法，与链接分析方法不 同，此类方法所得到的结果一般不考虑页面间的链接，而是通过用户是否浏览 一个网页和用户在不同页面上提留的时间长短来作为依据来对页面进行评价 的，页面的重要性由用户行为来决定。此类用于页面排序方法的代表算法主要 有b r o w s e r a n k 算法和d i r e c th i t 算法等，本节主要对这两种算法进行简介。 1 b r o w n s e r a n k 算法 b r o w n s e r a n k 算法【3 钙5 】是微软亚洲研究院于2 0 0 8 年推出的一种新的用于万 维网页面排序的技术。与传统的以基于链接的技术不同，该算法并没有使用页 面之间的链接关系图，而是提出了一种新的用户浏览图的概念。用户浏览图是 基于用户行为的，在该图中，以页面为节点，而图的有向边则表示用户在浏览 过程中页面的转换情况。该算法中，通过分析用户行为得到马尔科夫过程的一 个框架，并利用用户对页面访问的概率和用户在页面上的停留时间长短作为主 要的标准来对页面的重要性进行相关的评价。 1 0 堡圭堂垡兰奎 通过实验分析b r o w s e r 矗i l l 【 的方法在处理垃圾页面上有很大 第二章万维网中排序问题研究综述 算法所得出的排序结果比使用传统的基于链接 的优势，同时，由于该算法不仅仅考虑了用户 可能的对页面选择的情况，而且考虑了用户在浏览过程中的真实操作情况，因 此得到的结果准确度要高于传统的基于链接分析的方法。 2 d i r e c t h i t 算法 d i r e c th i t 算法【3 6 】也是一种基于用户搜索行为的用于页面排序的方法。其 中，页面的排序结果是通过页面被浏览的次数和用户在页面上浏览时问的长度 来得到的。用户在页面上停留时间越久则说明该用户给出的关键词与该页面的 相关度越大，该页面越能满足用户的需求。该算法由于考虑了用户行为，因此 可以在某种程度上满足用户的需求。但是，由于用户行为的不确定性，因此结 果的准确度也很难得到有效的保证，同时，由于用户总是倾向于浏览页面列表 中前面的页面，因此对排在后面的页面具有一定的不公平性。如今，该算法并 不是独立地存在于搜索引擎中使用的，而是通过与其他搜索引擎合作，对排序 结果进行进一步处理来得到优化了的页面列表的。 2 2 用于本体排序的相关技术 随着语义w e b 的发展，万维网中本体的数目与日俱增，大量表示相同或者 相似概念的本体相继出现，而寻找并重用已有的本体并不是一件容易的事情， 导致本体重用度低并产生了大量的冗余信息【3 7 1 。为了解决这一问题，本体搜索 引擎应运而生，排序问题作为搜索引擎的核心技术，引起了研究者的广泛关 注。目前，用于本体排序的相关技术主要分为三类：基于链接分析的方法，基 于结构分析的方法和基于内容分析的方法。下面对这三类方法分别做下简单的 介绍。 2 2 1 基于链接分析的方法 链接分析方法是万维网搜索中用于解决排序问题的算法中最常用的一种方 法，无论是在网页排序还是本体排序中都有着非常广泛的应用。然而，本体不 同于一般的w e b 页面，本体间不存在显示的链接关系，为了使用基于连接分析 的方法得到用于本体排序的排序值，关键是寻找到本体间隐式的链接关系。基 于链接分析的方法中，最典型的例子是常用本体搜索引擎s w o o g l e t 3 8 - 4 0 】使用的 o m o r a n k 算法和o n t o k h o j 算法。 1 s w o o g l e 和o n t o r a n k 算法 硕士学位论文第二章万维网中排序问题研究综述 s w o o 酉e 是马里兰大学开发的一种语义w 曲搜索引擎，