（计算机软件与理论专业论文）主题相关的pagerank算法的改进策略的研究和实现.pdf

主题相关的p a g e r a n k 算法的改进策略的研究和实现 摘要 随着网络技术的迅猛发展，w w w 已成为信息发布、交互及获取的主要工具， 它涉及新闻、广告、消费、金融、教育、电子商务等许多领域。w e b 具有四个 特点：庞大性、动态性、异构性、半结构化的数据结构环境。此外，w e b 还包 含丰富和动态的超链接资源。面对w e b 这些固有特点，人们要从这些海量的数 据中查找数据和信息，使用最多的就是搜索引擎技术。就搜索引擎技术领域来 说，可以通过分析一个网页或整个网站链接和被链接的数量、对象，建立w e b 自 身的链接结构模式，通过分析和研究p a g e r a n k 、h i t s 等基于链接结构的搜索 结果排名算法，可以指导网站链接结构优化，有组织，有规划地提高网页在搜 索结果中的排名，避免盲目处理造成的混乱结果。 本文主要针对目前主流的p a g e r a n k 算法，集中研究了p a g e r a n k 算法的形 成思路、计算方法等。在实现了p a g e r a n k 算法的基础上，针对p a g e r a n k 算法 在基于o n t o l o g y 的海洋文献智能信息检索系统应用中的缺陷，对p a g e r a n k 算 法加以改进，在算法中增加了文本文档可能性的判断和主题相关性的判断，提 出了i p a g e r a n k 算法，并实现该算法。 由于现在网络资源的繁多，为了提高系统的查准率，本文引入了o n t o l o g y 技术( 本体技术) ，设计并实现了基于本体的海洋领域智能文献信息检索系统， 分析了传统网络信息检索方面的在知识检索中准确率不高的缺点，提出了基于 o n t o l o g y 的海洋领域智能文献信息检索系统的实现结构框架，将i p a g e r a n k 算 法应用于基于o n t o l o g y 的海洋文献智能信息检索系统中，并做出验证。 经实验证明，算法i p a g e r a n k 有效提高了该系统检索准确性和有效性，验 证了所提出的i p a g e r a n k 算法理论的合理性，验证了算法在海洋文献智能信息 检索系统的应用中的正确性。 关键词：搜索引擎；p a g e r a n k 算法；主题相关；ip a g e r a n k 算法 r e s e a r c ha n dim pie m e n t a tio rt ot h eim p r o v e m e n t s tr a t e g yo fp a g e r a n kaig o rit h mr eia t e dt h e m e a b s tr a c t a l o n g w i t hr a p i dp r o g r e s so fc o m p u t e rn e t w o r kt e c h n o l o g y , w w wh a sb e c o m e t h em a i nf a c i l i t yt h a tp e o p l eu s e dt or e l e a s e ，i n t e r c h a n g ea n dr e t r i e v ei n f o r m a t i o n i t i si n v o l v e di nm a n yf i e l d ss u c ha sn e w s ，a d ，c o n s u m p t i o n ，f i n a n c e ，e d u c a t i o na n d e - b u s i n e s s f o u rc h a r a c t e r i s t i c so fw e ba r et h ef o l l o w i n g ：b i gs c a l e ，d y n a m i c , i s o m e r o u sa n dh a l f - s t r u c t u r e dd a t ac o n d i t i o n w e ba b o u n d sw i t h h y p e r l i n k r e s o u r c e sa sw e l l d u et ot h e s ec h a r a c t e r s ，w ec a nu s es e a r c he n g i n et e c h n o l o g yt o g e ti n f o r m a t i o na n dd a t af r o mw e b a sf o rs e a r c he n g i n e ，w ec a ne s t a b l i s hal i n k i n g s t r u c t u r ep a t t e r nb ya n a l y z i n gq u a n t i t ya n dt a r g e t so faw e b p a g eo rw e b s i t e si n l i n k s a n do u t l i n k s b ys t u d y i n gs u c ha l g o r i t h m sb a s e do nh y p e r l i n ka sp a g e r a n k , h i t s ， w ec a ng u i d eo u rl i n k i n go p t i m i z a t i o na n dc o n t i n u o u s l yi m p r o v et h ew e b s i t e sr a n k , a v o i db a dr e s u l t so fb l i n d n e s s i nt h i sp a p e rw ei n t r o d u c et ot h ep a g e r a n k a l g o r i t h m ，t h ec h a r a c t e r i s t i ca n d t h e l i m i t a t i o no fp a g e r a n ka l g o r i t h mu s e db yg o o g l ea n do t h e rs e a r c he n g i n e w eh a v e d e v e l o p e das y s t e m ，o c e a ns e a r c hs y s t e m ，w h i c hi sb a s e do no n t o l o g ya n da p p l i e d t h ep a g e r a n ka l g o r i t h mt oi t h o w e v e r , b e c a u s eo fp a g e r a n ka l g o r i t h m s ： i n s u f f i c i e n c i e sa b o u tt h ep r e c i s i o ni nt h i ss y s t e m ，w ep r o p o s ean e wa l g o r i t h m i p a g e r a n ka l g o r i t h m a n di nt h ei p a g e r a n ka l g o r i t h mi tj u d g e st h ep o s s i b i l i t yo f d o c u m e n ta n dt h et h e m e r e l a t i v i t y f i n a l l y , ih a v ec a r r i e do u tt h ea l g o r i t h m b e c a u s et h e r ei ss t 3m u c hi n f o r m a t i o no nt h ew e b ，w ei n t r o d u c et h eo n t o l o g y i no r d e rt os o l v et h ep r o b l e wa b o u tt h ep r e c i s i o n a n dw eh a v ed e v e l o p e dt h eo c e a n s e a r c hs y s t e mb a s e do no n t o l o g y t h ei p a g e r a n ka l g o r i t h mi sa p p l i e df o rt h e o c e a ns e a r c hs y s t e m sc o n s u m m a t i o n ii m p l e m e n tt h ei p a g e r a n ka l g o r i t h ma n d t a k et h ei l l u s t r a t i o na n dt e s tt ot h en e wa l g o r i t h m a c c o r d i n gt ot h ee x p e r i m e n t a lr e s u l t ，i p a g e r a n ka l g o r i t h m ni m p r o v et h e q u a l i t ya n de f f i c i e n c yo ft h ei r a f o r m a t i o nr e t r i e v a l a n di tp r o v e st h ec o i t c c t n e s so f t h er e l a t i v et h e o r i e sp r o p o s e di nt h i sp a p e r i i i k e y w o r d s ：s e a r c he n g ir i o ：p a g e r a n ka l g e r i t h i n ；t h e m e - r e i a t i v i t y ； i p a g e r a n ka i g o ri t h m 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写 过的研究成果，也不包含未获得或其他教育机构的学位或证书使用过 的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论文作者签名。州茏 签字日期：矽书f 阴j 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并向国家有 关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权学校可以将学 位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：石叫 导师签字：占文 签字日期：) 唧劳f 砂月妇签字日期：卯彦年，调j 日 主题相关的p a g e r a n k 算法的改进策略的研究和实现 第1 章绪论 1 1 课题背景 随着网络技术的发展和网络的普及，i n t e r a c t 已经深入到社会生活的各个角 落，成为人们日常信息获取的最主要的信息源。据统计，截至2 0 0 3 年7 月全球 w e b 站点总数约为4 6 0 0 万，w e b 页面总数约为1 0 0 亿，而且还在以每天7 0 0 万 的速度增长【1 l ，面对如此浩瀚的信息海洋，人们如何准确、有效的发现自己所 需的信息呢? 当前，人们从网络中获取信息的主要手段是使用g o o g l e 2 1 ，百度【3 】等通用搜 索引擎【4 1 ，通过向目标搜索引擎提交查询关键字，搜索引擎返回查询结果，人 们再在返回结果中人为过滤出有用信息。 目前的搜索引擎接收到用户的查询请求后，首先对用户提交的关键字进行 分词、截词处理【5 1 ，生成一个中间查询关键字的集合，然后再对该集合内的每 一个词在索引库中进行匹配，根据匹配的布尔值返回结果，如果返回值为真， 则将该项索引对应的结果( u r l 地址和该u r l 的摘要) 作为查询结果返回。 所以，这是一种机械的匹配，其存在的主要缺陷有： ( 1 ) 查全率和查准率不高由于目前的查询主要是关键字的硬性机械匹配，然而 一个词往往有多种表达方式，因此注定查询结果的查全率和查准率得不到保证。 ( 笱只能发现信息，而不是知识。 对于目前的搜索引擎，网页中的内容只不过是一堆二进制代码，这时搜索 引擎和网页的关系就如同一个文盲和一篇课文的关系，由于搜索引擎不会“读 课文 ，所以不能从网页中得到任何知识。 ( 3 ) 不能处理同义词和一词多义问题，我们知道海马别名又称水马、马头鱼， 如在g o o g l e 中输入海马，得到4 , 3 7 0 ，0 0 0 项查询结果，而输入水马，得到4 0 5 。0 0 0 项查询结果，输入马头鱼，得到4 1 ，0 0 0 项查询结果，而且返回结果集中相同的 页面很少；相同的词在不同的语境下会产生不同的意思，单纯的机械匹配显然 无法解决一词多义的现象。 ( 4 ) 无法搜索提供网页中的隐含信息。隐含信息是指那些没有被文字直接表述 出来，但隐含在网页内容中的信息。由于目前搜索引擎的检索策略采用的是关 键字匹配，不存在任何推理机制，因此不能发现网页上的隐含信息。 主题相关的p a g e r a n k 算法的改进策略的研究和实现 产生上述问题的原因主要是网页内容是一种无结构的或者半结构的数据， 只能供人阅读，计算机却不能理解。要解决以上问题，必须赋予网上的资源各 种明确的语义信息f 6 】，让计算机可以分辨和识别这些语义信息。 然而，要想定义一个完整、明确的语义集合，使得计算机通过该语义集合 能够理解由该语义集合定义的网络资源的语义信息，就目前看来是一项十分困 难的工作，其主要困难表现在技术、观念和规模上【7 1 。 因此，本文提出了在某一领域内探索实现计算机对网络资源语义信息的理 解，研究了其所涉及的网络搜索引擎的构建。重点介绍了在g o o g l e 中起到至关重 要作用的p a g e r a n k 算法，并根据p a g e r a n k 算法理论提出并实现了依据主题相关性 来搜索网络中的文档的i p a g e r a n k 算法。最后，对算法进行了验证，提出了个人 对以后改进的一点看法。 1 2 课题来源和研究的目标与内容 本文所研究的课题来源于山东省自然科学基金项目：基于o n t o l o g y 的海 洋科技文献资料共享平台，编号：y 2 0 0 5 g 0 6 。该项目的主要研究内容为：在海 洋信息领域内，建立基于o n t o l o g y 的科技文献资料共享平台，通过该平台检索 海洋科技文献资料。其整个系统架构， 如图卜1 ： 用户查询界面 查询模块 语义标注和 抽取模块 o n t o l o g y 管理模块 图1 1文档检索系统的缩略图 o n t o l o g y 本体构建维护子系统的作用主要是负责领域o n t o l o g y 的建立、存 2 主题相关的p a g e r a n k 算法的改进策略的研究和实现 储和进化【8 】；网络资源收集系统的作用是从w e b 上获取信息文件，交给语义元 数据标注子系统进行标注；语义元数据标注子系统和抽取子系统的作用是将网 络资源收集系统抓取的w e b 文档进行加工处理，把用h t m l 、x m l 描述的无 结构、半结构的数据进行标注，然后抽取其中的元数据并进行语义编码，最后 存放在语义元数据库中【9 】；信息检索和发布系统的作用是接受用户的查询请求， 参照建立的o n t o l o g y ，对用户的查询请求进行语义映射和语义扩展，实现信息 的查询和结果的返回。 通过在w e b 信息中添加机器易于理解的语义信息，实现计算机对信息的自 动分类和处理，而o n t o l o g y 作为能从语义和知识层次上描述信息系统的概念模 型，从语义层次上为w e b 信息的共享和交换提供了基础。 本论文课题的研究目标主要是实现网络资源收集，利用网络蜘蛛从网上获 取海洋信息领域的资源，利用改进的p a g e r a n k 算法即i p a g e r a n k 算法，决定所 查询文档信息排名先后，并提供输出。 1 3 论文的组织结构 本文由五章构成： 第1 章：绪论 第2 章：搜索引擎研究综述 第3 章：基于o n t o l o g y 信息检索分析与研究 第4 章：p a g e r a n k 算法 第5 章：基于本体的p a g e r a n k 算法的改进与实现 第6 章：算法在海洋智能文档检索系统中应用和验证 第7 章：总结与展望。总结全文，展望下一步工作。 3 主题相关的p a g e r a n k 算法的改进策略的研究和实现 第2 章搜索引擎研究综述 2 1 搜索引擎的发展历史和趋势 早在w o r l dw i d ew e d 出现之前，搜索引擎就已经诞生了。最初的搜索引擎， 主要被用来在不同的f t p 站点上查询文件，它提供对各站点文件的检索，从而 方便用户查找所需的文件【1 0 1 。 1 9 9 3 年之后，随着互联网的发展，普通网络用户要想查找所需的资料简直 如同大海捞针，现代意义上的搜索引擎便应运而生了。它以通过机器人程序抓 取网页或者由网站主动提供信息的方式来建立对网页的索引，为用户提供信息 检索服务。此时涌现了大量功能相似的搜索引擎，如：l y c o s 1 1 】，y a h o o 等，他 们属于现代意义上的第一代搜索引擎。特别是y a h o o ，成功地使搜索引擎的概 念深入人心，从而使搜索引擎进入了高速发展时期。 在搜索引擎的发展经历个高潮后，处于商业上的考虑，多数搜索引擎发 展为门户网站，伴随着人们对网络经济的过高预期，人们对门户网站非常热衷。 相比之下，搜索引擎的开发运营成本高，用户面窄，仅为少数几家公司提供检 索服务，搜索引擎的开发受到了冷落。而伴随着互联网规模的进一步扩大，搜 索引擎变得越来越被人们所需要，第二代搜索引擎出现了，其中最具代表性的 当属g o o g l e 。g o o g l e 提供了一系列革命性的新技术，包括完善的文本对应技术 和先进的p a g e r a n k 排序算法【1 2 1 ，保证返回结果和用户搜索要求的高度相关性， 从而使g o o g l e 大受欢迎。 随着第二代搜索引擎的逐步成熟和互联网信息的爆炸式增长，第三代引擎 也进入了研制阶段。第三代搜索引擎的最大特点就是大量智能化信息处理技术 引入，网络搜索服务将步入知识检索和知识服务领域，也即第三代搜索引擎将 朝着知识型搜索引擎的方向发展。 数据、信息、知识是属于三个不同层面的概念。知识是和用户能力及经验 紧密结合的、能够用于解决问题和创造新知识的信息组织。新一代搜索引擎的 发展目标就是要把散落在互联网上的不相关的数据搜集起来，经过筛选、组织 和分析，发现知识并返回给用户。在数据库层面的知识发现k d d ( k n o w l e d g e d i s c o v e r yi nd a t a b a s e ) 早已出现，如何将k d d 的现有技术和理论移植到w e b 知识检索上，是摆在我们面前的一个难题，也是第三代搜索引擎的发展方向【1 3 j 。 4 主题相关的p a g e r a n k 算法的改进策略的研究和实现 w e b 自面世以来短短的1 0 年期间之所以如此蓬勃发展，其中一个巨大的原 因就是它上面蕴含了图像、影像、声音等大量的多媒体资源。多媒体信息较之 普通文本信息量大，对用户的说服力和吸引力也更强。对多媒体信息的w e b 检 索也是新一代搜索引擎的一个重要研究方向。 w e b 信息挖掘的一个新兴方向就是自然语言m ) 处理。现在的n l 技术已 经能够分析良结构( w e 1 1 d e f i n e d ) 的句子，较好的消除多义词歧义，在连续文 本中标记出词性( p a r t o f - s p e e c h ) 信息，并可以写出规范的机器可识别的自然 语言文档和进行自然语言翻译。但由于计算机在非确定性逻辑处理技术上还存 在有待突破的难题，流行的w e b 搜索引擎在这方面进展缓慢，因此这也成为新 一代搜索引擎一个的必然发展趋势。 随着信息社会的进一步发展，人们要求准确的查找某一特定学科领域或特 定专题的i n t e r a c t 信息资源，因此，主题型搜索引擎也成为新一代搜索引擎的一 个发展方向。 2 2 通用型搜索引擎 通用型搜索引擎，又称综合性搜索引擎，信息覆盖范围大，适用用户广泛。 如：g o o g l e 、百度等。它们通常使用一个或多个的w e b 信息提取器( 网络蜘蛛) 从i n t e r a c t 上收集各种数据( 如：w w w ，n e w s ，f t p ) ，然后在自身服务器上 为这些数据创建索引，当用户搜索时根据用户提交的查询条件从索引库中迅速 查找出满足条件的信息返回给用户。 通用搜索引擎按照信息搜集方法和服务提供方式的不同，又可分为： ( 1 ) 全文搜索引擎 全文搜索引擎是指能够对网站的每个网页中的每个单子进行检索，由此可 见它是基于网页级的。如：g o o g l e ，百度。 在信息获取方式上，全文搜索引擎必须有一个网络蜘蛛来获取网页内容， 从而建立此网页的全文索引。 它的特点是查全率高，查准率低，搜索范围较广，提供的信息多而全，缺 乏清晰的层次结构。 ( 2 ) 分类目录搜索引擎 5 主题相关的p a g e r a n k 算法的改进策略的研究和实现 分类目录搜索引擎将网络信息加以归类，利用传统的信息分类方式来组织 信息，用户按照分类查找信息，因此它是基于网站级的。 在信息获取方式上，它们并不主动采集网站的任何信息，而是利用各网站 向“搜索引擎”提交网站信息时填写的关键词和网站描述等资料，经过人工审核 编辑后，如果符合网站登录的条件，则输入数据库以供查询。y a h o o 就是其中 的典型代表，国内的搜狐【堋、新浪【1 5 】等搜索引擎也是从分类目录发展起来的。 因此，从信息获取角度看，这种“搜索引擎 算不上真正的搜索引擎。 它的特点是网页内容丰富，有较高的查准率，但查全率低，搜索范围窄， 层次结构清晰。 ( 3 ) 元搜索引擎 元搜索引擎是一种使用其他独立搜索引擎的引擎【1 6 1 。 元搜索引擎并不像全文搜索引擎那样拥有自己的索引数据库，而是当用户 提交搜索申请时，通过对多个独立搜索引擎的整合和调用，然后按照元搜索引 擎自己设定的规则将搜索结果进行取舍和排序并反馈给用户。因此，从信息获 取角度看，这种“搜索引擎”也算不上真正的搜索引擎。 从用户的角度来看，利用多元搜索引擎的优点在于可以同时获得多个源搜 索引擎( 即被元搜索引擎用来获取搜索结果的搜索引擎) 的结果，但由于元搜 索引擎在信息来源和技术方面都存在一定的限制，因此搜索结果实际上并不理 想，目前尽管有数以百计的多元搜索引擎，但还没有一个能像g o o g l e 等独立搜 索引擎那样受到用户的广泛认可。 2 2 1 关键技术 ( 1 ) 信息获取 网上信息收集和存储一般分为人工和自动两种方式。人工方式采用传统信 息收集、分类、存储、组织和检索的方法。研究人员对网站进行调查筛选、分 类、存储，再由专业人员手工建立关键字索引，再将索引信息存入计算机相应 的数据库中。自动方式通常由搜索程序完成信息的获取，搜索程序( 如：r o b o t 、 s p i d e r 等) 是一种自动运行的软件，其功能是搜索i n t e m e t 上的网站或网页。这 种软件定期在i n t e m e t 上漫游，通过网页之间的超链接搜索新的地址，当遇到新 6 主题相关的p a g e r a n k 算法的改进策略的研究和实现 的网页时，就索引该页并把它j j n - n 搜索引擎的数据库中，因此，搜索引擎的数 据库得以定期更新。一般来说，人工方式收集信息的准确性要优于搜索程序， 但其收集信息的效率和信息覆盖面要低于搜索程序。 当进行自动信息收集时，如何遍历i n t e r a c t ，如何提高i n t e r a c t 的遍历效率， 如何下载资源内容以及资源内容的字符编码处理等都是搜索程序需要解决的问 题。当前，很多站点在传输w e b 页时采用了不同的压缩算法以提高传输速度， 如何将下载的w e b 页内容解压缩也是搜索程序需要解决的。 ( 2 ) 信息索引 信息索引就是创建文档信息的特征记录，以使用户能够快速地检索到所需 信息。一个搜索引擎的有效性很大程度上取决于索引的质量，所以信息索引是 搜索引擎的核心，而建立索引主要涉及到以下几个问题： 信息语词切分和语词词法分析。语词是信息表达的最小单位，对于英文来 讲是英语单词，比较容易提取，因为单词之间有天然的分隔符( 空格) ；而对于 中文等连续书写的语言，则必须进行语词切分，由于语词切分中存在切分歧义， 切分需要参考各种上下文知识。语词词法分析是指识别出各个语词的词干，以 便根据词干建立信息索引。 进行词性标注。词性标注是指利用基于规则和统计( 马尔可夫链) 的数学 方法对语词进行标注。基于马尔可夫链随机过程的n 元语发统计分析在词性标 注中能达到较高的精度，可以利用多种语法规则识别出重要的短语结构。 索引器的索引算法。索引器可以采用集中式索引算法或分布式索引算法， 当数据量很大时，必须实现即时索引( i n s t a n ti n d e x i n g ) ，否则不能够跟上信息 量急剧增加的速度。索引算法对索引器的性能( 如大规模峰值查询时的响应速 度) 有很大影响。 建立检索项索引。使用倒排文件的方式建立检索项索引，一般包括“检索 项 ，“检索项所在文件位置信息 以及“检索项权重 。 另外，如今i n t c r n e t 上发布的信息格式多种多样，这就要求搜索引擎提供格 式转换功能，将d o c ，p p t ，p d f 等非纯文本格式文档进行格式转换，获取文字 内容，从而对文档进行索引。 ( 3 ) 信息检索 7 主题相关的p a g e r a n k 算法的改进策略的研究和实现 信息硷索就是要获得从信息索引库中获得与要求最接近的记录。主要技术 包括对用户提交关键词的基本截词、布尔逻辑组配、词位限制等。 能否将最满足用户需求的结果最先展现给用户，是一个搜索引擎能否在商 业上取得成功的关键，因此，搜索引擎还要对检索结果进行排序。排序主要根 据待选网页与查询条件的匹配度，匹配度越高，相关度就越高，排序就越靠前。 常用的匹配算法有：布尔模型，模糊逻辑模型，向量空间模型，概率检索模型。 2 2 2 组成原理 由于分类目录搜索引擎和元搜索引擎算不上是真正的搜索引擎，本文对它 们二者不做深入探讨，将重点介绍全文检索搜索引擎的组成和实现原理。 图2 2 搜索引擎的组成 搜索引擎位于信息检索系统层次分类的底层，以w e b 信息为处理对象，虽 然各个搜索引擎具体实现不尽相同，但一般包括5 个基本部分【1 7 1 ：r o b o t 、解析 器、索引器、检索器和用户接口。 ( 1 ) r o b o t ( s p i d e r c r a w l e r w a n d e r ) ：采用广度优先( 或者深度优先) 策略对 w e b 进行遍历并下载文档，r o b o t 系统中维护一个超链接队列( 或者堆栈) ，其 中包括一些起始u r l ，r o b o t 从这些u r l 出发，下载相应的页面，并从中抽取 出新的超链接加入到队列( 或者堆栈) 中，r o b o t 不断重复上述过程直到队列( 或 者堆栈) 为空。为了提高网页抓取效率，搜索引擎中一般会有多台服务器并行 的遍历不同的w e b 子空间。目前，大多数的r o b o t 并不能够访问基于框架的w e b 页面和需要访问权限的页面，以及动态生成的页面。 在i n t e m e t 中，信息是使用h t m l 语言描述的，不同的h t m l 页面通过其 中所包含的超链接互相联接，这些超链接是以u r l 的方式被表示出来的。依靠 这些相互指向的u r l ，i n t e r n e t 中的信息形成了一个巨大的信息网络，u r l 是 网络中信息资源的标准通用地址。在i n t e m e t 中，人们用u r l 来定位具体的信 8 主题相关的p a g e r a n k 算法的改进策略的研究和实现 息资源。r o b o t 程序从一个起始的u r l 集合开始，顺着u r l 中的超链接在互 联网中搜集信息。这些起始u r l 的选取通常是一些质量较高、非常流行、含有 很多超链接的站点，如新浪、搜狐、雅虎等这样的门户网站。一个u r l 定义一 个源文件，r o b o t 将其全数抓回并交给解析器进行解析处理。 r o b o t 程序通过h 】_ r p 协议获取指定u r l 的资源，而且其在进行网页搜集 的时候遵循一定的协议，对于那些不愿意被访问的网页会有一定的表明，r o b o t 将不会抓取这样的网页，因此r o b o t 也被称为网络中的君子。 ( 2 解析器：对r o b o t 下载的文档进行分析以用于索引。文档分析技术一般 包括：分词、过滤和转换等。这些技术往往与具体的语言以及系统的索引模型 密切相关。在分词时，大部分搜索引擎的解析器从全文中抽取词条，而有些则 仅从文档的某些部分( 如：t i t l e 、h e a d e r ) 中抽取。词条的类型也有多种，包括： 字、词或者短语等。分词后通常要使用禁用词表( s t o pl i s t ) 来去除出现频率很 高的词条，有些系统还对词条进行单复数转换、词缀去除、同义词转换等工作。 分析程序通过一些特殊算法，从r o b o t 程序抓回的网页源文件中抽取主题 词，并对其赋予不同权值，以表明这些主题词网页内容的相关程度，以判断网 页内容。如一篇文章的题目往往能够概括文章的核心内容，它必然会被赋予一 个较高的权值。 同时，解析程序还将此网页中的超链接提取出来，返回给搜集程序，以便 r o b o t 进一步在w e b 上深入搜集信息。 解析程序的目的是从一个u r l 到相应网页主题词建立一种关联，并通过对 主题词的提取和分析，判断该网页所描述的信息。但是，按照终端用户搜索习 惯通常都是从一个关键词入手查找相应的网页，而在解析器中形成的对应关系 恰恰相反，这个问题将留给索引器完成。 ( 3 ) 索引器：将文档表示为一种便于检索的方式存储在索引数据库中。例 如，在矢量空间索引模型中，每个文档d 被表示为一个范华矢量 v ( d ) = ( t 1 ，w 1 ( d ) ；t i ，w i ( d ) ；t n ，w r n ( d ) ) ，其中t i 为词条项，w i ( d ) 为t i 在d 中的权值， 索引的质量是w e b 信息检索系统成功的关键因素之一一个好的索引模型应该 易于实现和维护，检索速度快，空间需求低。搜索引擎普遍借鉴了传统信息检 索中的索引模型，包括：倒排文档、矢量空间模型、概率模型等。 9 主题相关的p a g e r a n k 算法的改进策略的研究和实现 ( 4 ) 检索器：从索引库中找出和用户查询请求相关的文档。首先采用和解 析、索引文档类似的方法来处理用户查询请求。例如，在矢量空间索引模型中， 用户查询，也被表示为一个范化矢量，然后按照某种方法来计算用户查询与索 引数据库中的每个文档之间的相关度。例如，在矢量空间索引模型中，相关度 可以表示为查询矢量与文档矢量之间的夹角余弦。最后，将相关度大于阀值的 所有文档按照相关度递减的顺序排列，并返回给用户。 ( 5 ) 用户接口：为用户提供可视化的查询输入和结果输出界面。在查询输 入界面中，用户按照搜索引擎的查询语法指定待检索词条及各种简单、高级检 索条件。在输出界面中，搜索引擎将检索结果展现为一个线性的文档列表。由 于检索结果中相关文档和不相关文档相互混杂，用户需要人工浏览以找出所需 文档。 2 3 主题型搜索引擎 主题型搜索引擎【1 0 1 ，又称专业搜索引擎，主要提供某一主题或者学科领域 的w e b 信息，信息覆盖范围小，仅适用于某一特定用户群。如：s o f t s c e k 1 8 1 、 t o r r c m s p y 1 9 】等。 主题型搜索引擎和通用型搜索引擎存在着巨大的差别： ( 1 ) 服务目的不同 通用型搜索引擎面向大众用户，主题型搜索引擎则面向专业用户。 ( 2 ) 搜索方式不同 通用型搜索引擎以遍历整个w e b 为目标，主题型搜索引擎则采用一定的策 略预测对相关网页进行预测，动态调整网络蜘蛛的爬行方向，使系统尽可能围 绕设定主题进行爬行，从而节约网络资源。 ( 3 ) 硬件要求不同 通用型搜索引擎对硬件要求非常高，主题型搜索引擎要求低。 2 3 1 产生背景 通用型搜索引擎的出现很大程度上解决了人们在互联网上查找信息的困 难，但由于其覆盖一切、追求普适的设计目标，已经不能满足人们对个性化信 1 0 主题相关的p a g e r a n k 算法的改进策略的研究和实现 息检索服务日益增长的需要。目前，通用搜索引擎在使用中面临着较多待解决 的问题： ( 1 ) 超大规模的分布式数据源。w e b 信息分布在数以亿计的计算机互联网 上，搜索起来非常困难，搜索引擎很难索引所有w e b 资源。 ( 2 ) w e b 信息的质量问题。互联网上的信息无论从数量和类型都呈现出指数 增长的趋势，这导致搜索引擎的实时性很难保证。 ( 3 ) 搜索要求的精度表达问题。在信息搜索领域，个突出的问题世，用 户很难简单地用关键字来准确表达他所需要的真正信息，表达的困难将导致检 索结果不理想。 ( 4 ) 搜索引擎的硬件要求越来越高，由于w e b 信息的海量性，搜索引擎要 对这么大量的信息进行抓取，索引，同时还要相应大量用户的查询请求，需要 有众多的服务器协作完成信息获取，索引，存储，处理用户查询请求 近些年，科学技术在国民经济中的带动作用越发显著，各产业的科技含量 也在不断提高，如何为科技工作者提供最新的科技信息，对科技和经济发展都 是至关重要的。由此对搜索引擎提出了新的要求： ( 1 ) 搜索引擎能运行在普通的软硬件基础之上； ( 2 ) 只搜集莫一特定学科领域的i n t e r n e t 信息资源； ( 3 ) 能够方便的运行搜索主题和学科的自定义搜索配置。 为满足以上要求，主题型搜索引擎应运而生。 2 3 2 关键技术 主题型搜索引擎的实现存在两个难点； 第一，起始种子站点和词库的设置。因为主题引擎并不遍历整个w e b ，所 以起始站点集合的设置就显得非常重要。词库作为评价网页是否主题相关的标 准关键词的集合，它的合理配置将对检索结果的准确性产生直接影响。 第二，搜索效率的考虑。由于要进行有选择性的w e b 信息提取，那么由此 带来的主题相关性判断会直接影响搜索引擎的工作效率。 此外，主题信息的表示、信息的提取、信息的过滤和主题相关性站点的选 择策略都是系统实现的难点。 主题相关的p a g e r a n k 算法的改进策略的研究和实现 进行面向主题的网络信息检索主要有两种技术： ( 1 ) 基于内容的搜索。 此类检索方式是传统信息检索技术的延伸。他的主要方式就是在搜索引擎 内部建立一个主题对应的关键词表，搜索引擎的爬行器根据其内设的关键词集 合对网上信息进行索引。 ( 2 ) 基于链接结构分析的检索。 一些学者认为互联网上的网页间的链接关系同社会关系网络中的人际关系 存在着很多相似之处。通过对链接结构进行分析，可以找出网页之间的引用关 系。由于引用网页与被引用网页内容上一般都比较相关，所以可以按照引用关 系将大量网页分类。 2 3 3 研究现状 目前，有关主题型搜索引擎的研究正在成为一个热点研究领域，一大批主 题性的搜索引擎像雨后春笋般出现，例如军事医学主题搜索引擎【冽，林业主题 搜索引擎研究，健康主题的搜索引擎等等。对于随着信息多元化的增长，千篇 一律的给所有用户同一个入口显然已经不能满足特定用户更深入的查询需求。 同时，这样的通用搜索引擎在目前的硬件条件下，要及时更新以得到互联网上 较全面的信息是不太可能的。针对这种情况，我们需要一个分类细致精确、数 据全面深入、更新及时的面向主题的搜索引擎。由于主题搜索运用了人工分类 以及特征提取等智能化策略，因此它比上面提到的搜索引擎将更加有效和准确， 知识表示已经被引入到该领域得研究。 基于本体论( o n t o l o g y ) 的搜索引擎【2 1 】开始出现。一个本体强调相关领域的本 质概念，同时也强调概念之间的本质联系，以本体为基础建立主题搜索引擎的 关键词表可以更好地显示一个领域中的各个概念及它们之间的关系，从而更好 得表现一个主题。 一些学者提出了概念空间的理论，用概念空间来描述主题，实现语义索引。 概念空间是某个领域中一组对象概念的集合，并且在这组概念之间，存在着一 定的语义上的关联。 1 2 主题相关的p a g e r a n k 算法的改进策略的研究和实现 2 4 搜索引擎的性能指标 w e b 信息的搜索从本质上说是一个信息检索问题，即在由w e b 网页组成的 文档集中检索出满足用户查询需求的文档。所以我们可以用衡量传统信息检索 系统的性能参数：召回率( r e c a l l ) 和精度( p r e c i s i o n ) 2 2 】。 召回率是检索出的相关文档数和文档库中所有的相关文档数的比率，衡量 的是系统的查全率。 精度是最终满足用户要求的文档数与检索出的文档总数的比率，衡量的是 检索系统的查准率。 对于一个检索系统来讲，查全率和查准率通常是相互矛盾的。对于目前的 搜索引擎系统来讲，很难搜集到所有的w e b 网页，所以召回率很难计算。精度 是各个搜索引擎所最为关心的，以g o o g l e 为例，它通过不断优化自己的文档和 查询的表示方法、关键字相关性的匹配策略和查询结果的排序方法等一系列相 关措施，使g o o g l e 具有较高的查准率，从而得到用户的认可。 2 5 本章小结 本章依据搜索引擎的发展历史和趋势，先后主要介绍了通用型搜索引擎和 主题型搜索引擎的特征，包括其关键技术，组成原理和研究现状等。本章最后 还介绍了衡量传统的搜索引擎的性能指标。 主题相关的p a g e r a n k 算法的改进策略的研究和实现 第3 章o n t o io g y 综述和信息检索分析与研究 3 1 引言 近年来随着互联网的飞速发展，w e b 已经成为一个巨大的信息库，也是人 们获取信息的重要途径。但是要从浩如烟海的信息中获取有用的信息好比大海 捞针，困难重重，因而如何提高w e b 信息检索的效率和质量，成为了当前需要 迫切解决的问题。 传统的信息检索技术【为】主要有两种技术：条件检索和目录式导航检索。条 件检索采用词条切分技术，根据文档中的字词以及字词出现的频率来进行检索 查询操作。g o o g l e 等搜索引擎在传统信息检索技术的基础上，结合w e b 的特点， 在其检索过程中增加了w e b 文档间的超链接分析，取得了一定的效果。但从本 质上来看，其仍然是属于基于关键词的机械匹配技术的范畴，并没有从根本上 解决检索过程的语义缺失问题。对于基于关键词匹配的检索技术，检索对象中 只要出现和检索条件一致的关键词，就可以出现在检索结果中，因而只要系统 更新的速度比较快，可以保证比较高的查全率。但是由于采用的是机械匹配， 而且自然语言中一词多义现象广泛存在，因而查询的结果集往往非常庞大，有 些信息甚至和要求风马牛不相及，最后降低了查准率。而且在自然语言中存在 众多的同义词、近义词，对同一个问题不同的人可能有不同的表达，传统的信 息检索技术过分依赖用户的检索式，缺乏语义扩展和分析的能力，很难同时保 障较高的查全率和查准率。 传统信息检索另一个主要的技术是目录式导航检索。目录式导航检索采用 一种直观的方式，将待检索的信息按照结构和内容进行分类组织，用户在检索 时就不需要显式的输入检索条件，只需要按照信息的组织方式选择感兴趣的主 题，逐步缩小查询的范围，最终就能获取想要的信息。典型的导航检索引擎如 m 0 0 f 2 4 1 的o p e nd i r e c t o r y 。导航检索有很好的查准率，但是用户需要逐级查找 比较耗费时间，检索效率不高。而且由于导航检索对信息的分类组织主要由人 工来完成，因而信息更新的速度比较慢，难以保证较好的查全率。近年来，科 研人员在人工智能和自然语言处理方面作了大量的研究工作，包括基于机器学 习和自然语言的信息检索研究，但是进展缓慢。o n t o l o g y 由于其具有良好的概 念层次和表达能力，并能根据一定的规则进行推理和检索，非常适合基于知识 1 4 主题相关的p a g e r a n k 算法的改进策略的研究和实现 的智能检索信息检索，因而成为当前w e b 信息检索技术的新亮点。本文经过分 析研究，提出了基于o n t o l o g y 的智能检索信息检索系统模型。 3 2o n t o io g y 概述 3 2 10 n t o l o g y 概念 o n t o l o g y 旨在克服计算机系统之间的“语义鸿沟 ，其概念源于哲学。从哲 学的范畴来说，o n t d o g y 是客观存在的一个系统的解释或说明，即“对世界上 客观存在物的系统地描述 嘲，其关心的是客观现实的抽象本质。在人工智能 界，最早给出o n t o l o g y 定义的是n e c h e s 等人，他们将o n t o l o g y 定义为“给出 构成相关领域词汇的基本术语和关系，以及利用这些术语和关系构成的规定这 些词汇外延的规则的定义 1 2 6 1 。1 9 9 3 年，g r u b e r 给出了o n t o l o g y 的一个最为 流行的定义f 2 3 1 ，即“o n t o l o g y 是概念模型的明确的规范说明” 2 7 1 。后来，b o r s t 在此基础上，给出了o n t o l o g y 的另外一种定义【2 7 1 ，即“o n t o l