基于链接的分析pagerank排序算法改进的研究

1、湖北工业大学硕士学位论文摘要搜索引擎技术是在当前各领域对计算资源和计算能力不断增长的形势下发展起来的，而基于链接分析的 PageRank 算法的研究更是其至关重要的一个环节，目的是对搜索的网页进行重要性排序，让更符合用户需求的网页在搜索结果中靠前。由于传统排序算法的局限性和客观性，使得对于特定领域搜索的索引不够完善，结果往往偏离用户的需求，很难满足多元化，个性化的搜索需求。而一个完善的索引系统应该对特定领域的搜索进行区分归类，在原有的排序技术上，针对具体的用户需求和资源特征来完善排序算法。探讨了搜索引擎及 PageRank 的基本概念，归纳了不同领域的索引的特征，分析了各种模型，建立一个综合性

2、较高的索引机制。详细介绍了 PageRank 算法的原理，分析了现有链接分析算法的缺陷，在各种领域的搜索中存在的问题，并提出改进的策略。分别描述了针对特定领域搜索，在传统的 PageRank 算法上的改进模型。逐步坦诉了基于主题相关性，信息发布时间反馈性，页面主题分块机制的 PageRank算法改进模型。提出了 PageRank 综合改进模型。通过与原有算法的比较分析，验证出此算法更具时效性，内容相关性。关键词：搜索引擎，PageRank，主题相关性，时间反馈，主题分块机制I湖北工业大学硕士学位论文AbstractSearch Engine technology is developed wi

3、th the situation of growing computingresources and computing ability in all Fields Currently, the algorithm of PageRankwhich based on link analysis is the essential part of it. The purpose of sorting the webpages which have been searched by importance is to make the web pages whichconforms the need

4、of user stand in front of the other web pages. Because of limitationand objectivity of the traditional sorting algorithm, the searching index is not perfectlyin specific field. So the searching result usually deviate from the requirement of theuser and it is difficult to satisfy the need of diversif

5、ication and personalization ofsearching. A perfect index system should be able to discriminate and classify thespecific field of searching, improve the sorting algorithm for specific usersrequirement and resource characteristics in the original sorting technology foundation.This article discusses Se

6、arch Engine and basic concepts of PageRank, summarizesthe characteristics of the index in different fields, analyzes different kinds of models,and establishes a high comprehensive indexing mechanism. It details the principle ofPageRank algorithm, analyzes the shortcomings of existing link analysis a

7、lgorithmsand the searching problems in various fields, and then proposes the improvingstrategies. It describes the searching for a specific area, the improved PageRankalgorithm model based on traditional algorithms. It gradually illustrate improvedPageRank algorithm model that based on Topical Relev

8、ance, feedback ofinformation release time and page themes blocking mechanism.This article propose a comprehensive improvement model of PageRank.Through comparative analysis of the original algorithm, this algorithm is proved to bebetter in timeliness and relevance.Keywords: Search Engine, PageRank,

9、Topical Relevance, Time Feedback, ThemeBlocking MechanismII学位论文原创性声明和使用授权说明原创性声明本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文

10、被查阅和借阅。本人授权湖北工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。学位论文作者签名：指导教师签名：日期：年月日日期：年月日湖北工业大学硕士学位论文第 1 章 绪 论1.1 研究背景及目的与意义众所周知，排序技术作为衡量搜索引擎系统质量的至关重要的环节，是开发搜索引擎者一直很关注的研究课题。高速发展的互联网导致其包含的信息越来越丰富，面对如此海量的网络信息，用户越来越依赖搜索引擎来获取所需资源。文本信息抽取算法是早期搜索引擎的主要算法，但是网页的特性与传统文本并不相同，它有着更新快、变化多、海量、半结构化等鲜明特点，

11、并且传统文本信息抽取算法的索引项仅仅包含网页中的关键字，却忽略了页面间所特有的链接结构，搜索效果并不理想。由 Goolgle 创始人之一拉里、佩奇推出的 PageRank 算法，提供了一种基于链接机制的客观度量网页重要性的排序算法，其隐藏的概念是，每个到页面的链接都作为一次对该页面的投票，投票越多意味着该网页越受欢迎，也就越重要越权威。而这种排序原理独立于文本内容，更独立于网页的人气指数，也就忽略了页面的社会关注程度，从而影响了针对某些特定领域的搜索结果的相关性和准确性。而且一个网页的主题并不是单一的，在不同的版块中主题并非一致。所以需要有一个机制来对其主题相关性进行划分归类，方便用户查找到具

12、有某主题相关版块的网页。对于即时性搜索需求而言，传统的 PageRank 算法无疑是偏重于旧网页的，因为旧网页出现的时间长，被其他网页链接的就多一些，那么 PR 值就很低，而用户要求搜索到最热门最新的博客新闻信息时，这种算法就成了劣势。所以如果能引入时间反馈算法，将会更加完善索引机制。尤其在设计面向热门话题的搜索引擎系统时，针对其主要的来源(新闻博客论坛等网站)的特性，在原来的 PageRank 排序算法中引入了主题相关和时效性，将网页的权威性与其受社会关注程度综合起来分析，使搜索结果得到更为合理的排序。1.2 国内外研究现状1.2.1 搜索引擎的国内外研究现状互联网搜索引擎的深入研究已经成了

13、国内外信息检索的焦点，伴随着技术的不断成熟，历经了由关键字匹配发展到独立型搜索引擎，再由独立性索引系统进化1湖北工业大学硕士学位论文到集成式索引系统，元索引机制，甚至现在的理论上的分布式搜索机制。搜索引擎作为搜索者的法宝，为网络经济的繁荣增加了更多的发展空间，随之而来的SEO，搜索优化机制(为商业目的而开发的索引技术)成为新型的网络经济热潮。而在我国对于索引系统的改进和研发也很关注。美国网络公司在搜索引擎的基础研究上每年投入的经费高达几亿美元。据新闻媒体报道，面临越来越激烈的搜索引擎行业之间的竞争，Google 力求创新突破，通过不断完善索引服务，寻求高质量的索引机制来与时俱进，在同行业中力求

14、保持领先地位。最近，google 又推出了下一代搜索引擎技术，其研究编号为“Caffeine”，尚处于测试阶段。“Caffeine”在上市之前将会由开发人员参与其测试过程，对于其性能进行规范性，完整性的测试，预计在上市以后会另搜索用户索引到更为满意的结果。表面上它的客户端界面跟老版本差不多，可以让用户容易接受。然而其后台索引技术是有相当大的改观的，它可以加速信息发布到被蜘蛛程序抓取的时间，让新的信息及时的反馈给用户。Google 的两名研究者马特与西塔啊拉姆在官方博客上发表申明，用户的参与检测以及反馈信息将会对此项技术做更多贡献。最近这段时间，Google 工作者正潜心研究一个新的技术，根据草

15、拟的设想方案做具体的实践，即 Google 网页索引技术的新结构。运用这个机制的索引系统，将在索引规模、索引效率、智能化、查准性、查全率等方面有不俗的表现。”由于新的索引系统没有改变客户端的程序，用交互界面不变的情况下，用户很难发觉索引结果跟以前的相比有任何提高，但是开发人员和专业人士具备此分析能力，所以其测试阶段少不了开发真的参与。很多业内人士对“Caffeine”发表了专业性看法，新的“Caffeine”技术对索引机制将会有很大的改善，首先表现在它的速度上，其索引速度是传统索引的两倍，但其查准率并为见到很大的改善。然而对于即时性信息查询以及突发新闻的索引更为受用，将会让用户及时获取到某些特

16、殊信息。微软最近推出的被业界称之为“谷歌杀手”的 Wolfram Alpha，改进了原 Live 索引机制，并打着“必应”的旗号隆重上市。微软宣称该索引技术能给用户提供更加简洁，直观的服务。我国最具代表性的搜索引擎研究机构当属百度。目前百度是全世界首屈一指的中文信息检索与传递技术供应商。中国超过 75%的提供搜索引擎的所有门户网站中，都由百度提供搜索引擎技术支持。百度索引系统由四个部分组成：1 蜘蛛程序、2 监控程序、3 索引数据库、42湖北工业大学硕士学位论文检索程序。百度索引系统使用了高效率的“网络蜘蛛”软件自动的在互联网中抓取信息，其精湛的调度算法使得搜索器能在极为有限的时间里汇聚到最大

17、数量的网络数据信息。百度在世界各地都安置有服务器，其搜索范围相当庞大。百度索引系统拥有当前世界最大的中文数据库，总量高达 1.2 亿多，并且每天还在以加速度增长。1.2.2 PageRank 研究现状及展望众所周知，排序技术作为衡量搜索引擎系统质量的至关重要的环节，是开发搜索引擎者一直很关注的研究课题。Google 在同行业中最显著的方面在于潜心研制“完善的搜素机制”，开发创始人佩奇以“解析用户之意图，返回用户之需求”为理念来改善此系统。 为了实现此索引机制，Google 不断钻研，力求突破，并且积极摆脱现有模式的束缚。 所以，Google 别出心裁的研制出自己的搜索引擎，突破式的推出了 Pa

18、geRank 算法。在最开始，Google 的研究人员就强调，如果要提供最迅捷，最满意的搜索服务就需要引入新的索引机制。 之前的搜索引擎系统非常依赖关键词在网页中出现的次数。 Google 则采用了新的 PR 技术分析每个网页的受关注程度。在此基础上，再利用字符匹配寻找到与主题相关的网页。综合判断了网页的重要性以及内容相关性使用户搜索到更为满意的内容。PageRank 机制： PageRank 构造了一个包含大概 6 亿的变量和 10 亿左右的条件的函数，对网页的质量以及主题相关性进行了全面综合的分析。这种搜索引擎在网络高峰期容易速度减退，效率降低；谷歌运用分布在网络上的各个 PC 机来迅速查

19、询相关内容。通过引入新的技术解决了反应时间较长，成本较高的缺陷。 谷歌在推出的新技术令同行业的其他公司赞不绝口并纷纷效仿。谷歌搜索引擎的后台机制可以在瞬间进行大批量同步运算。 区别与传统的搜索引擎，页面 C 指向页面 D 的一个链入可视为页面 C 对页面 D 的一次加分，并非统计直接的链接数目。因此，Pagerank 是根据页面的累积总分来判断此网页的重要程度。PageRank 也会考虑反向链接的因素，比如某个页面的加分越多，那么链如此页面的网页也会具有相对较高的 PR 值。 受关注越多，PageRank 值越高的网页则会在搜索结果中靠前一些。 谷歌机制是综合分析了很多因素来判断网页的重要性。

20、由于不会添加人为的因素，让结果会更加客观准确些，所以谷歌被誉为最清廉最值得信任的搜索系统(不会因为付费操作人为地影响排名)谷歌的搜索机制同样也会考虑文本内容相关性。然而，不会只是单纯的进行字符匹配统计关键词频率，谷歌机制会解析全部的文本内容，并对其主题进行归类分析，还可以统计出关键词出现的精确位置。谷歌也会抓取到其他相邻的页面，3湖北工业大学硕士学位论文并对页面进行全面的内容分析，返回用户最满意的搜索结果。然而 PageRank 独立于网页的人气指数，也就忽略了页面的社会关注程度，从而影响了针对某些特定领域的搜索结果的相关性和准确性。在设计面向热门话题的搜索引擎系统时，针对其主要的来源(新闻博

21、客论坛等网站)的特性，在原来的PageRank 排序算法中引入了评论机制和点击率，将网页的权威性与其受社会关注程度综合起来分析，使搜索结果得到更为合理的排序。所以对于某些特定领域的索引服务，搜索引擎应该提供更加针对性的索引机制。本文就是针对各种不同领域的搜索特性，来研究 PageRank 应用于各个特定搜索领域的改善。对搜索引擎的有待展望：能更加准确表达用户查询需求的方式(客户端的改进)；更好的管理索引数据库，让数据库中文件更新速度更快，层次结构跟鲜明；信息过滤更加强化；查准率和查全率更加提高；多元化的个性服务；客户反馈服务系统；自然语言分析；智能化。1.3 研究内容及组织结构首先，介绍了 P

22、ageRank 的基本思想及其概念，分析搜索引擎中对于某些领域的搜索存在的问题，阐述了在传统的 PageRank 算法中引入主题相关性，信息发布时间反馈性，页面主题分块等机制的重要性，然后介绍了几种不同的算法改善模型，其次，探讨了基于新闻博客系统的特殊领域的搜索引擎需求，比较并分析了几种改善的 PageRank 模型，介绍了基于链接分析的综合性算法改进模型。最后，深入分析了各种信息源的特性，对其提出了改进的方案并将其应用到对特定领域的索引中，设计并实现了基于 PageRank 改进的算法的综合模型，研究了算法的合理性和有效性，通过比较分析，不仅降低了系统负荷，还满足了用户的个性需求，实现了索引

23、系统的查全率和查准率。全文共有六章，各章内容如下：第一章：介绍了课题的研究方向与背景、研究意义、国内外研究现状，改技术的发展及展望，及论文主要研究工作；第二章：介绍了 PageRank 排序技术的基本思想及其体系结构；第三章：根据用户搜索需求提出了经典 PageRank 算法在相关性及关注度方面缺陷，针对不同的问题提出几种新的模型，将这几种模型与传统的排序算法做比较，经分析做出结论。第四章：分析现有排序机制所存在的问题，提出了综合性模型的改进策略，4湖北工业大学硕士学位论文建立了一个查全率查准率更高的模型，实现了基于此模型的算法，不仅保证了信息的及时性和完整性，同时提高了索引速度；第五章：结束

24、语。总结了论文的工作，展望今后的研究内容。1.4 主要贡献本文基于网互联网搜索引擎的排序算法的改进，将理论与实践相结合，并通过分析综合，通过在原有排序算法中引入主题相关性及时效性改善了现有的传统搜索引擎的排序算法，增加了索引技术的查准率和查全率，以及对即时信息的及时搜索效率。5湖北工业大学硕士学位论文第 2 章 PageRank 的基本概念及原理2.1 搜索引擎体系结构搜索引擎(search engine)是指根据一定的策略、运用特定的计算机程序搜集互联网上的信息，在对信息进行组织和处理后，并将处理后的信息显示给用户，是为用户提供检索服务的系统。搜索引擎一般由搜索器、索引器、检索器和用户接口四

25、个部分组成： (1)搜索器：其功能是在互联网中漫游，发现和搜集信息； (2)索引器：其功能是理解搜索器所搜索到的信息，从中抽取出索引项，用于表示文档以及生成文档库的索引表；(3)检索器：其功能是根据用户的查询在索引库中快速检索文档，进行相关度评价，对将要输出的结果排序，并能按用户的查询需求合理反馈信息； (4)用户接口：其作用是接纳用户查询、显示查询结果、提供个性化查询项。其工作原理如下所诉：1、抓取网页每个独立的搜索引擎都有自己的网页抓取程序（spider）。Spider 顺着网页中的超链接，连续地抓取网页。被抓取的网页被称之为网页快照。由于互联网中超链接的应用很普遍，理论上，从一定范围的网

26、页出发，就能搜集到绝大多数的网页。2、处理网页搜索引擎抓到网页后，还要做大量的预处理工作，才能提供检索服务。其中，最重要的就是提取关键词，建立索引文件。其他还包括去除重复网页、分词（中文）、判断网页类型、分析超链接、计算网页的重要度、丰富度等。3、提供检索服务用户输入关键词进行检索，搜索引擎从索引数据库中找到匹配该关键词的网页；为了用户便于判断，除了网页标题和 URL 外，还会提供一段来自网页的摘要以及其他信息。6湖北工业大学硕士学位论文图 2.1 搜索引擎体系结构2.2 PageRank 概述在查询信息时，对于符合关键词的所有相关网页的排序是基于超链接分析的，如果某一网页 T 存在一个指向网

27、页 A 的链接，则表明网页 T 的所有者认为网页 A是比较重要的， 从而把 T 重要性得分值(即网页 T 的 PageRank 值)的一部分赋予 A。A 得到的分值大小由 T 的 PageRank 值 PR(T)和 T 的出链(从 T 链出的链接)数 C(T)决定。 用公式表示为：PR(T)/C(T)。 因而对于页面 A，其 PageRank 值PR(A)就是从所有指向它的页面分得的重要性分值的总和。可用以下公式计算：PR( A) = PR(T1 ) / C(T1 ) + . + PR(Tn ) / C (Tn )(2.1)其中：T1、T2、T3Tn 为含有指向 A 的链接的页面。 由于互联网

28、上也存在一些页面没有入链或出链， 因而无法计算其 PageRank 值。为避免这个问题(即所谓的链缺问题)，一些研究学者对其进行改进，为上式添加一个阻尼系数 d 使其变为：PR( A) = (1 d ) + dPR(T1 ) / C (T1 ) + . + PR(Tn ) / C(Tn )(2.2)d 为阻尼系数，值在 0 到 1 之间，通常为 0.85。阻尼系数得使用，减少了其它页面对当前页面 A 的排序贡献。因为用户不可能无限点击链接，常常因无聊而随机跳入另一个页面。阻尼系数 d 定义为用户不断随机点击链接的概率，所以，它取决于点击次数，被设定为 0-1 之间。d 值越高，继续点击链接得概

29、率就越大。因此，用户停止点击并随机冲浪至另一页面的概率在式子中用常数(1-d)表示。无论入站链接如何，随机冲浪至一个页面概率总是(1-d)。(1-d)本身也就是页面本7湖北工业大学硕士学位论文身所具有的 PageRank 值。 这样在整个网络内的页面经过多次递归迭代计算，直到 PR 值达到收敛，即求得页面的 PageRank 值。2.3 PageRank 相关算法(1)Topic-Sensitive PageRank（主题敏感的 PageRank）基本思想：针对 PageRank 对主题的忽略而提出。核心思想：通过离线计算出一个 PageRank 向量集合，该集合中的每一个向量与某一主题相关，

30、即计算某个页面关于不同主题的得分。主要分为两个阶段：主题相关的 PageRank 向量集合的计算和在线查询时主题的确定。优点：根据用户的查询请求和相关上下文判断用户查询相关的主题（用户的兴趣）返回查询结果准确性高。不足：没有利用主题的相关性来提高链接得分的准确性。(2)Hilltop基本思想：与 PageRank 的不同之处：仅考虑专家页面的链接。主要包括两个步骤：专家页面搜索和目标页面排序。优点：相关性强，结果准确。不足：专家页面的搜索和确定对算法起关键作用，专家页面的质量决定了算法的准确性，而专家页面的质量和公平性难以保证；忽略了大量非专家页面的影响，不能反应整个 Internet 的民意

31、；当没有足够的专家页面存在时，返回空，所以 Hilltop 适合对于查询排序进行求精。2.4 PageRank 算法的作用起初 PageRank 对 google 搜索引擎排名算法的影响很大，后来随着 google 不断更新排名算法 PageRank 影响排名的权重也就不那么高了，google 每个季度最少要更新 100 个排名算法，很多站长就觉得 PageRank 不重要了，但是在竞争激烈的时候很多站长才感觉到 PageRank 的作用，才开始进行 PageRank 建设，很多时候市场给予的时间是很短的。1.PageRank 是网站外部链接数量和质量的体现。能够说明网站的权威性，google

32、 反作弊工程师朱凯华在今年的 SMX 大会上说，同一个内容存在两种以上 URL的，google 会自动选择一种 URL，但是这样很有可能会分散该网页的“声誉”。这个声誉就是外链，所以外链好的网站在 google 的眼里声誉就好，在排名种就得到了相应的分数，而 PageRank 是外链的体现，所以通过 PageRank 能够体现出网站的权威性在搜索引擎的眼里。8湖北工业大学硕士学位论文2.通过 PageRank 传递能够判断出网站的结构性。网站首页 PageRank 是 7，则要通过对结构优化将 PageRank 传递到频道和栏目等其他重要的页面，说明网页的重要性，是通过链接来告诉搜索引擎，但是

33、不知道首页到底链接带来的“声誉”有多高，具体传递给其他页面多少“声誉”也不知道，但是通过 PageRank 就可以基本上清楚了。3.seo 中外部链接优化占据了 30%以上的因素，而外链的好换直接体现在 PageRank，就是说在做外链的时候要参考这个指标。 PageRank 与关键词排名、网站流量等没有直接关系，具有很强的客观性。2.5 本章小结本章主要介绍了搜索引擎的基本框架，重点叙述了 PageRank 的基本原理，并讨论了 PageRank 的作用。由于 PageRank 算法的目的是为了提供给用户的最佳索引，基于搜索引擎的技术概要和体系结构，如何能综合考虑到更多的客观因素，让更符合用

34、户意愿的网页更靠前，构建一个查全率查准率更高的排序算法，将在下一章进行重点阐述。9湖北工业大学硕士学位论文第 3 章 基于传统 PageRank 算法的改善模型分析3.1 经典 PageRank 在相关性及关注度方面缺陷的改进在经典的 PageRank 算法中，某网页的 PageRank 值只与该网页链接的链入和链出数有关，而与搜索的内容无关。这造成在搜索结果中排在前面的网页可能与用户需要的网页不相关，降低的搜索的质量。同时一些重要的有意义的网页被搜索用户大量点击，此类网页应该被排在搜索出的所有网页的前面，而在经典的PageRank 算法中，并没有体现出搜索用户网页点击量对网页 PageRan

35、k 值的影响，因此应该在 PageRank 算法中引入相应的网页受搜索用户关注度这一影响因子。在实际中，门户网站的导航网页以及专业网站的导航目录网页一般有较高的链入数，而大多数内容为具体新闻以及具体技术资料的网页的链入数较低，只被个位数的网站链接。而它们所在的主页的链入数和链出数都较高，因此依照经典的 PageRank 算法，这类导航性质的网页通常会有较高的 PageRank 值。而有具体内容的网页通常 PageRank 值都较低，因此依照经典的 PageRank 算法是不能够较好的给出搜索排序结果。所以，需要对这些网页附加相应的权重值，提高网页的搜索排序质量。同时，目前有些网页为了提高自身的

36、 PageRank 值，利用现有的搜索方法的漏洞，通过添加链接，在网页中添加与本网页无关的内容来达到在搜索结果中排序靠前的效果。对此，经典的 PageRank 算法不能有效的进行区分识别。导致搜索用户需要在查询大量网页之后才能获得自己需要的结果。因此应该在以下三个方面对经典的 PageRank 算法进行改进：(1)利用搜索词语与网页的相关性来对搜索结果进行排序。在早期的搜索引擎中，通常是利用统计搜索用户的搜索关键词在搜索到的网页全文中的出现频率来对搜索结果网页进行排序。用户搜索关键词关键在搜索结果网页中出现频率高的网页被排到前面，反之则排到后面。同时有的搜索引擎还会统计搜索用户的搜索关键词在搜

37、索到的网页全文中的位置的重要性来对搜索结果网页进行排序。用户搜索关键词关键在搜索结果网页中出现在重要位置的搜索结果网页被排到前面，反之则排到后面。最终搜索引擎依照这两个影响因素来对搜索结果进行排序。而现在搜索引擎通常利用搜索用户的搜索关键词与搜索到的网页的相关性来对搜索结果进行排序。这里的相关性是指搜索用户的搜索关键词与搜索到的网页10湖北工业大学硕士学位论文的匹配程度。一般是根据搜索用户的搜索关键词在搜索到的网页中出现的频率、出现的位置，与网页中相近词的匹配程度来对搜索结果进行排序。最终相关性越高的网页在搜索结果中位置越靠前。本文中用 C(P)来表示相关性。在实际中，由于会出现某些常用的词语

38、在完全不同类型的网页中出现的频率相近的情况，如果单纯的按照相关性来对搜索出的网页进行排序，则会出现不同类型网页排序相近的结果。这不满足搜索用户对搜索结果的需求。(2)利用搜索用户对网页的点击率来判断网页的重要性。在经典的 PageRank 算法中没有关于用户对网页点击量对网页 PageRank 值的影响。而在实际中，通常用户点击量较大的网页是用户较为关注的网页，这类网页应该更符合用户的搜索需求。因此，这类网页应该排在搜索结果的前面部分。对于某一网页，一般用户有两种点击方式，一种是点击多个该网页中的链接，另一种是顺序点击新点击网页内的链接。例如当前网页中 P 中有链接 P(1)，P(2)， ，P

39、(n)。第一种点击方式是点击当前网页中的 P(i)，i 取 1，2，3，n；第二种方式是点击当前页面中的 P(i)，i 取 1，2，3，n 中的一个，在网页 P(i)中又有链接 P(i)(1)，P(i)(2)，P(i)(m)。则又点击 P(i)(j)，j 取 1，2，3，m中的一个。本文中用 I(P)来表示重要性。对于搜索用户检索得到的搜索结果网页，如果用户对某些网页点击率较高说明这些网页更符合搜索用户输入搜索关键词需要的搜索网页结果。但是搜索用户主要是依照网页的标题来判断该网页是否符合搜索用户自身的需求。如果该网页的标题和网页的实际内容相关度不大，则搜索用户点击的网页并不能很好的满足搜索用户

40、的需求。因此，单纯的以网页的重要度指标 I(P)来对搜索用户搜索出的网页结果进行排序也不能够得到理想的结果。(3)为搜索用户提供在搜索结果中细化检索的向导机制。一般用户在一次搜索中输入的关键词搜索后会产生大量的搜索结果网页。在这些网页中有一部分与用户所需求的结果相关，有一部分与用户的需求无关。因此很有必要对这些搜索结果进行二次搜索。为了能够提供更好的搜索结果，应该对一次搜索出的结果网页进行分类，并给出分类结果。使用户可以根据分类结果，在一次检索结果中的某一类网页中进行二次检索。综合以上三点可知：(1)经典的 PageRank 算法只涉及了不同网页之间的链入链出数。而没有考虑网页的内容与搜索用户

41、搜索关键词的匹配以及用户对网页的点击率。(2)基于内容相关性的搜索引擎只考虑了关键词在搜索到的网页中出现的频率，出现的位置，与网页中相近词的匹配程度，而没有考虑搜索到的网页质量。11湖北工业大学硕士学位论文(3)基于网页点击量的搜索引擎只考虑用户对网页的点击率，而没有考虑该网页标题是否与网页正文内容相关。因此，对于搜索到的众多网页，综合考虑以上三点后得到以下模型。如果用户是搜索某一类网站，则主要以网页的 PageRank 值作为网页的权重指标。而如果用户不是搜索某一网类站，则应该考虑网页的相关性 C(P)和网页的重要度 I(P)。因此，对于网页搜索，其综合权重值计算公式为：PR = f (PR

42、, C (P), I (P)(3.1)在上式中 PR 为网页的综合权重值，PR 为经典的 PageRank 算法计算值，其计算公式为PR( X ) = (1 d ) + d *(PR(D1 ) PR(D2 )O(D1 ) O(D2 )+)O(Dn ) ，其中 D1 ，D2Dn分别代表链接网页 A 的 n 个网页；PR(Di ) 代表网页 Di 的 PageRank 值；O(Di ) 代表网页 Di 总的链出数量；i 的取值为 1，2， n ；d 为阻尼系数，d 的取值范围为(0，1)；C(P)为以搜索用户搜索关键词与网页的相关性得到的网页权重值；I(P)为以搜索用户对网页的点击率为依据考虑网页

43、的重要度的网页权重值。3.2 基于页面分块的 PageRank 改进模型本节对一个基于页面分块重要性模型的 PageRank 算法进行了改进。考虑到即使同一页面，对于不同分块的出链接重要性并不一样，故对不同分块的出链接赋予适当的权重，从而更加公正、准确、高效地计算页面的 PageRank 值。相较于旧的 PageRank 算法，该算法的核心为基于视觉特征的页面分块算法，更加合理地反映了页面的特性，更加人性化，具有非常好的效果。本小节提出了一个 PageRank 改进算法基于自学习页面分块模型的算法。Google 搜索引擎成功地利用了 PageRank 算法对网页的重要性，利用 PageRank

44、 值对网页进行评估，同时结合其他的一些技术对搜索结果网页进行重要性排序，从而将搜索准确率大为提高。仔细研究 PageRank 算法后，发现在以下几方面并不是很合理：偏重旧网页：由于旧网页更可能被其他网页引用，导致 PageRank 值经常比新网页要高，而新网页才应该是用户更加关心的。偏重门户网站：虽然专业网站的信息通常会更加权威，但由于点击量的原因，搜狐、腾讯等大型门户网站比一般专业网站被引用的次数更多，经常拥有更高的PageRank 值，导致专业网站的关注度不够。12+ +PR(Dn )湖北工业大学硕士学位论文主题漂移：PageRank 算法没有评估页面中的链接和主题的相关性、引用与被引用页

45、面内容上的相关性，可能得分高的页面与搜索主题并不相关，也就是所谓的“主题漂移”。本小节主要研究主题漂移的解决方案。为了对页面的 PageRank 值更合理的分配，大致可以将问题分为基于文本内容和页面分块两类来解决，主要是通过改进传统算法中网页 PageRank 值的分配策略，在链接分析的同时综合考虑页面内容。基于文本内容的方法主要是利用空间向量模型(VSM)，在计算页面文本内容的相似度后得到页面间的相关度，在此基础上调整 PageRank 值的分配策略。是用文本分类方法来计算页面间相关度；在计算页面间的相关度时，有的文献以不同的权值处理不同网页标签中的文本内容；有的文献则给出了计算了文本和查询

46、词之间的相关度的详细方法。基于页面分块的方法则首先评估页面块的信息与页面标题的相关性，在评估结果上调整页面出链接的 PageRank 值分配权值。在提取文本特征时，由于网页的半结构化、噪音信息多等特点，基于文本内容的方法很难取得良好效果，故本文的改进算法基于页面分块，并对页面分块的重要性进行等级划分，从而给不同重要性等级的分块的出链接以合适的分配权值，使得提高新算法对 PageRank 值的分配策略的高效性、准确性。页面分块的方法如下：(1)页面分块算法源于 Web 信息抽取领域，其核心思想是：网页上的信息通常会按一定布局和结构有规律地结合在一起。页面分块主要有以下四种思路：Url 链接的 t

47、ag 有分布性。Url 链接的 tag 常常出现在一起。所以如果能够找到所有网页正文分块边界的 Url 链接的 tag 分布规则，那么就可以按此规则对网页正文进行分块。利用超文本链接的标签间的关系：超文本链接的标签间有某种的层次关系，先找出构造标签的优先级，将页面在结构层面上进行块划分，当页面信息复杂或者不规则时作用不大。(2)利用 TABLE 标签的分布规律：超文本链接的标签中，TABLE 具有良好的布局规律，格式复杂的页面通常都采用 TABLE 标签进行网页格式的排布。因此，可利用“table”标签对页面进行划分，但是网页结构和 TABLE 标签的关联关系都非常复杂，页面信息很可能不在同一

48、层的 TABLE 标签中，在划分时容易漏掉部分信息。(3)利用页面的视觉特征：页面的视觉特点包含字体大小、背景颜色、空白区域等特性。通过收集与整理视觉特征，按照总结出的规律把页面划分成块，可以对复杂页面进行划分，但是由于规则与算法比较复杂而难以理解、运用。本小节采用 VIPS (Vision-based Page Segmentation)算法作为页面分块算法，该算法利用页面的视觉特征，较之前三种方法可以更好的对复杂页面进行划分，13湖北工业大学硕士学位论文因而在页面分块处理中有很强的适用性。页面分块重要性模型如下：新算法所采纳的页面分块重要性模型来源于文献12，该模型的核心思想是：相同页面的

49、不同部分拥有不同的重要性，而人脑可以利用页面上的特征，轻松地分辨出各个部分的重要性。总体上来说首先把页面使用页面分块算法分块，之后用人工标记出分块的重要性并提取块特征来得到训练数据，再让处理软件学习训练数据，这样可以建立一个输入块特征向量、输出其重要性级别的模型。文献12把分块做了四级的重要性划分，本文也采用此等级划分方法，依次是：第一级：无用信息，比如页面背景、授权信息等；第二级：有用但是用户不感兴趣的信息，比如转跳链接、友情网站等；第三级：与主题有关联但是不是特别重要的信息，比如类似的关联标题、标题目录等；第四级：页面中最重要，用户最感兴趣的内容，比如内容标题、热点新闻等。页面分块重要性模

50、型为基础的改进算法如下：改进算法的主要目标是改良以往 PageRank 算法的平均分配策略，先对页面进行分块，给不同分块的出链接配以合适的重要系数，防止“主题漂移”。在方法上，选取了 VIPS 算法对网页进行分块，对页面分块进行重要性等级区别的同时，采用空间向量模型进行处理得到页面不同分块的重要性系数，利用该模型统计出网页集中各页面出链接的重要系数，按照这个系数计算得到更加合适科学的 PageRank值。改进算法步骤如下：(1)找出如何对网页正文进行分块的规则。(2)依据分块规则计算搜索到的网页。(3)算出网页的 PageRank 值。建立页面分块重要性模型的：(1)对网页正文分块规则为 VI

51、PS 算法，这种算法可以用来统计从搜索网页正文获得的数据。(2)网页正文分块规则中的特征向量：在网页正文分块规则中的的特征向量包括空间和内容两类。要规格化这两类特征向量。网页正文分块规则中块中心纵坐标算法为：PR(A)=（1-d）+d(PR(T1)*f(T1, A)+f(T, A)=W(T,A)/(W(T,A)+W(T,A1)+ PR(Tn)*f(Tn,A)+W(T,A n)(3.2)(3)收集实验数据：搜索得到 500 个网页正文，利用 VIPS 算法进行计算，计算14湖北工业大学硕士学位论文后将网页正文进行分块，然后对分块后的各个网页的重要性评估，再考虑特征向量，最终给出了实验结果。(4)

52、将 VSM 作为对搜索到的网页正文的分类依据：在分类时输入特征向量，输出重要性值，利用 Gaussian RBF 函数进行实验，建立分块模型。建立模型以后，在对搜索到的所有网页进行分类时应利用 VIPS 算法。然后根据重要性对搜索到的网页正文进行分块。最终算出重要性权值 W(T,A)：2.0W(T , A) = 1.00.5引用链接处于第四级重要性分块引用链接处于第三级重要性分块引用链接处于第二级重要性分块引用链接处于第一级重要性分块(3.3)最终的 PageRank 计算公式为：PR(A)=（1-d）+d(PR(T1)*f(T1, A)+ PR(Tn)*f(Tn,A)(3.4)上式中 d=0.85，f(T, A)=W(T,A)/(W(T,A)+W(T,A1)+W(T,A n )3.3 用信息过滤改进 PageRank 算法这种方法研究分析了经典信息过滤算法，结合主题的相关性以及网页的重要性，针对专题搜索引擎中的数据过滤模块提出了设计思路及实施策略，并对一些算法进行了改进拓展。当今社会充斥着各种各样的信息，如何找到我们所需的有用的信息成为了一个重要的问题。网页搜索引擎由此而生，并影响着我们的生活。现在很多搜索引擎用的都是基于关键字词查询的数据检索算法及技术，搜索到的页面数量成千上万。一个搜索引擎，搜索一个关键字，返回的匹配值可以达到上