ＰａｇｅＲａｎｋ算法在网页搜索中的实现 二分搜索算法是利用什么实现的算法
时间：2018-12-29 03:24:09 来源：雅意学习网 本文已影响 人 
摘 要： 本文首先介绍了Web结构挖掘技术在Web中的应用，其次陈述了Web结构挖掘技术中的经典链接分析算法PageRank，最后分析了PageRank在网页搜索中具体实现的方法。
关键词： Web结构挖掘 PageRank算法 网页搜索
1.引言
Web是人们获取信息的重要资源之一，传统的搜索引擎在技术上已经不适应海量的Web资源查询，为解决Web搜索引擎所存在的问题，人们提出了Web数据挖掘概念，并在实践中取得了很好的效果。
Web结构挖掘，简称WSM，指通过分析不同页面之间的超链接结构，网页内部的可以用XML、HTML表示成树形结构，以及文档URL中的目录路径结构等，发现许多蕴涵在Web内容之外的、对我们有潜在价值的模式和知识的过程。
目前WSM主要应用有：
*搜索引擎查询结果的排序；
*查找相关文档；
*计算Web页面Reputation；
*确定某站点的主要内容和特征；
*Web Crawler的URL爬行的优先顺序。
2.WSM的链接分析技术
用户在Web上使用搜索引擎进行信息搜索时，最关心的并不是返回结果的多少，而是检索结果是符合自己的需求。许多研究者发现，Web页面的链接结构是非常丰富和重要的资源，如果能够充分利用，可以极大地提高检索结果的质量。
Web页面有三个重要组成部分：网面内容、网页所含的超文本标记及网页间的超链接。一般说来，Web文档中的超链接包含了两种信息：首先，它为用户提供了浏览Web的导航信息，用来指引访问者在各页面之间跳转；其次，页面中的超链接往往是文档作者对于某一文档的推荐，被推荐的目的文档往往与该文档有相似内容而且被作者所认同。后者构成了链接分析的基础，即某一文档的重要性不由文档的内容决定，而取决于被其他文档链接（或者引用）的次数。这种评价机制类似于科学论文中的参考文献：被引用次数多的论文其重要性比引用次数少的论文要高。在Web检索中，除了被其他文档链接的次数外，链接源文档的质量也是评价被链接文档质量的一个参考因子：被高质量文档链接或者推荐的文档往往具有更高的权威性。这就是Web结构挖掘中基于超链接结构的链接分析技术的理论基础。
3.独立于查询的算法――PageRank
PageRank算法是Web超链接结构分析中最成功的代表之一，是评价网页权威性的一种重要工具。搜索引擎Google就是利用该算法和anchor text标记、词频统计等因素结合的方法对检索出来的大量结果进行基于权威值的排序处理，使最重要的网页出现在结果的最前面。其中，PR值（权威度）越高的网页，在结果中出现的位置越前。
PageRank的理论基础是：忽略掉Web页面上的文本和其它内容，只考虑页面间的超链接，把Web看成一个巨大的有向图。
如果页面u包含一个指向页面v的超链接，即存在link(u，v)。这里页面间的超链接构成了一个有向图G：对于每个页面构成有向图G的一个节点；当且仅当u中包含指向页面v的超链接时，存在着从u到v的有向边（u，v）。有向图G如图1：
对于节点v来说，节点b，c，u对于v的权值大小有贡献，因为这三个节点都存在到v的有向边。指向某一节点的有向边越多，其节点（页面）质量越高。这种简单的算法的主要缺点是仅仅考虑的链接数量――所有的链接都是等价的，而没有考虑源节点自身的质量即权值高低。Web中文档之间超链接的情况往往是高质量的文档中包含高质量的链接，源节点的质量对于被链接文档质量评价的作用往往高于数量上的影响。
为了解决链接数量和源节点的质量问题，Sergey Brin和Lawrence Page提出了PageRank算法：某一Web页面的PageRank值等于所有包含指向该页面的源文档的PageRank值与页面链接总数之比的和，即：
outlink（j）为网页集合j指向所有节点的超链接数目；
PR（v）为节点v的权威度。
PageRank算法的实现过程为：将网页的URL对应成唯一的整数，把每一个超链接用其整数ID存放到索引数据库中，经过预处理（如去除数据库中的悬摆指针）之后，设每一个页面的PR值为1，通过以上的递归算法计算每一个网页的PR值，反复进行迭代，直到结果收敛。
PageRank算法除了对搜索结果进行排序外，还可以应用到其它方面，如估算网络流量，向后链接的预测器，为用户导航等。
Google是结合文本的方法来实现PageRank算法的，所以只返回包含查询项的网页，然后根据网页的PR值对搜索到的结果进行排序，把PR值最高的网页放置到最前面，但是如果最重要的网页不在结果网页集中，PageRank算法就无能为力了。
4.结语
在Web结构挖掘中，对超链接的分析算法是重要的研究方向。“权威性”是链接分析算法的对页面进行自动分析的重点，但目前的算法都是对不同的链接赋予相同的权重，如何根据文本内容的相关性，为相应的超链接赋予不同的权重，即把Web内容挖掘和Web结构挖掘进行合理结合，是一个值得继续深入研究的问题。
参考文献：
［1］王晓宇，周傲英.万维网的链接结构分析及其应用综述［N］.软件学报，2003，14(10)：1768-1780.
［2］宋建康，张礼平.Web结构挖掘算法探讨［N］.华东理工大学学报，2003，28(5)：537-540.
［3］曹军.Google的PageRankWeb技术剖析［N］.情报杂志，2002，10：15-18.
［4］WEB超链分析算法纵览.http：//www.省略/news/20041025214603.htm.
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文
