Pagerank算法介绍.ppt

《Pagerank算法介绍.ppt》由会员分享，可在线阅读，更多相关《Pagerank算法介绍.ppt（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、PageRank算法介绍李鹏飞Google服务器Google工作电脑Google爬虫网页Google存储系统搜索引擎示意目录nGoogle的网页排序nPageRank算法求解nPageRank算法的应用n小结Google的网页排序n在Google中搜索“体育新闻”Google的网页排序n在Google中搜索“体育新闻”搜索引擎工作的简要过程如下n针对查询词“体育新闻”进行分词“体育”、“新闻”n根据建立的倒排索引，将同时包含“体育”和“新闻”的文档返回，并根据相关性进行排序这里的相关性主要是基于内容的相关性但是会有一些垃圾网页，虽然也包含大量的查询词，但却并非满足用户需要的文档，如下图，一个网

2、页中虽然出现了四次“体育新闻”但却不是用户所需要的因此，页面本身的重要性在网页排序中也起着很重要的作用查询词和文档的相关性Google的网页排序n在Google中搜索“体育新闻”Google的网页排序n如何度量网页本身的重要性呢？互联网上的每一篇html文档除了包含文本、图片、视频等信息外，还包含了大量的链接关系，利用这些链接关系，能够发现某些重要的网页n直观地看，某网页A链向网页B，则可以认为网页A觉得网页B有链接价值，是比较重要的网页。n某网页被指向的次数越多，则它的重要性越高；越是重要的网页，所链接的网页的重要性也越高。AB网页是节点，网页间的链接关系是边Google的网页排序n如何度量

3、网页本身的重要性呢？比如，新华网体育在其首页中对新浪体育做了链接，人民网体育同样在其首页中对新浪体育做了链接可见，新浪体育被链接的次数较多；同时，人民网体育和新华网体育也都是比较“重要”的网页，因此新浪体育也应该是比较“重要”的网页。新华网体育人民网体育Google的网页排序n一个更加形象的图链向网页E的链接远远大于链向网页C的链接，但是网页C的重要性却大于网页E。这是因为因为网页C被网页B所链接，而网页B有很高的重要性。Pagerank算法简介创始人：拉里佩奇创始人：拉里佩奇(LarryPage)Google创始人之一创始人之一应用：应用：是是Google用来衡量用来衡量一个网站的好坏的一个

4、网站的好坏的唯唯一标准一标准。Google的网页排序nPageRank的提出Google的创始人之一Larry Page于1998年提出了PageRank，并应用在Google搜索引擎的检索结果排序上，该技术也是Google早期的核心技术之一Larry Page是Google的创始首席执行官，2001年4月转任现职产品总裁。他目前仍与Eric Schmidt和Sergey Brin一起共同负责 Google的日常运作。他在斯坦福大学攻读计算机科学博士学位期间，遇到了Sergey Brin，他们于1998年合伙创立Google。Pagerank算法原理：Google的网页排序n网页的PageRa

5、nk值PR值：取值0-10 Google工具栏 9 8 nhttp:/Pagerank算法相关概念PR值：用来值：用来评价网页的重要性评价网页的重要性，PR值越大越重要值越大越重要，其级别从，其级别从0到到10级。级。一般一般PR值值达到达到4，就，就算是一个不错的网站了算是一个不错的网站了。Google把自己的网站把自己的网站的的PR值定到值定到10，这说明，这说明Google这个网站是非常受欢迎的，也可以说这个网站是非常受欢迎的，也可以说这个网站非常重要。这个网站非常重要。阻尼因数：阻尼因数：(dampingfactor)其值为0.85n 阻尼系数d定义为用户不断随机点击链接的概率，所以，

6、它取决于点击的次数，被设定为0-1之间。d的值越高，继续点击链接的概率就越大。因此，用户停止点击并随机冲浪至另一页面的概率在式子中用常数(1-d)表示。无论入站链接如何，随机冲浪至一个页面的概率总是(1-d)。(1-d)本身也就是页面本身所具有的PageRank值。Pagerank核心思想PageRank通过通过网络浩瀚的超链接关系网络浩瀚的超链接关系来确定一个来确定一个页面页面的的等级等级。Google把从把从A页面到页面到B页面的链接页面的链接解释为解释为A页面给页面给B页面投票页面投票，Google根据根据投票来源投票来源（甚至来源的来源，即（甚至来源的来源，即链接到链接到A页面的页面）

7、和页面的页面）和投票目标的等级投票目标的等级来决定新的等级。来决定新的等级。这样，这样，PageRank会根据网页会根据网页B所收到的所收到的投票数量来投票数量来评估评估该网页的重要性。此外，该网页的重要性。此外，PageRank还会评估每个投票网还会评估每个投票网页的重要性，因为页的重要性，因为某些重要网页的投票被认为具有较高的某些重要网页的投票被认为具有较高的价值，这样，它所链接的网页就能获得较高的价值价值，这样，它所链接的网页就能获得较高的价值。这就。这就是是PageRank的核心思想，当然的核心思想，当然PageRank算法的实际实算法的实际实现上要复杂很多。现上要复杂很多。PageR

8、ank简单计算：n假设一个由只有假设一个由只有4个页面组成的集合：个页面组成的集合：A，B，C和和D。如果所有页面。如果所有页面都链向都链向A，那么，那么A的的PR（PageRank）值将是）值将是B，C及及D的和。的和。n继续假设继续假设B也有链接到也有链接到C，并且，并且D也有链接到包括也有链接到包括A的的3个页面。一个个页面。一个页面不能投票页面不能投票2次。所以次。所以B给给每个页面每个页面半票。半票。以同样的逻辑，以同样的逻辑，D投出的投出的票只有票只有三分之一三分之一算到了算到了A的的PageRank上。上。n换句话说，换句话说，根据链出总数平分一个页面的根据链出总数平分一个页面的

9、PR值值。如图图1 所示的例子来说明PageRank的具体计算过程。PR值计算公式：PR(A)=(1-d)/N+d(PR(t1)/C(t1)+.+PR(tn)/C(tn)N:网络中网页总数d:阻尼因数 PR(x):网页x的PR值C(tn)：网页tn的链出网页数 一个页面的PageRank是由其他页面的PageRank计算得到。Google不断的重复计算每个页面的PageRank。如果给每个页面一个随机PageRank值（非0），那么经过不断的重复计算，这些页面的PR值会趋向于正常和稳定。这就是搜索引擎使用它的原因。PR值的取决因素：n链入网页数n链入网页的质量n链入网页的链出网页数nPageR

10、ank值是一个特殊矩阵中的特征向量。这个特征向量为：PR值的计算（1）PR(A)=(1-d)/n+d(PR(t1)/C(t1)+.+PR(tn)/C(tn)PR值的计算（2）(1-d)/n+d(PR(t1)/C(t1)+.+PR(tn)/C(tn)2.2使用使用幂法求幂法求PageRank 幂法幂法计算过程如下计算过程如下：X设任意一个初始向量设任意一个初始向量,即设置初始每个网页的即设置初始每个网页的PageRank值均。一般为值均。一般为1.R=AX;while(1)(if(lX-RIe)/如果最后两次的结果近似或者相同，返回如果最后两次的结果近似或者相同，返回RreturnR;elseX

11、=R;R=AX;n一、一、P概率转移矩阵的计算过程概率转移矩阵的计算过程:n先建立一个先建立一个网页间的链接关系的模型网页间的链接关系的模型,即我们需要合适的数据结构表示页面间即我们需要合适的数据结构表示页面间的连接关系。的连接关系。n1)首先我们使用图的形式来表述网页之间关系：首先我们使用图的形式来表述网页之间关系：n现在假设只有四张网页集合：现在假设只有四张网页集合：A、B、C，其抽象结构如下图，其抽象结构如下图1：2.3求解步骤：求解步骤：n2）我们用矩阵表示连通图：）我们用矩阵表示连通图：n用邻接矩阵用邻接矩阵P表示这个图中顶点关系表示这个图中顶点关系，如果顶（页面），如果顶（页面）i

12、向顶点（页面）向顶点（页面）j有链接情况有链接情况，则，则pij=1，否则，否则pij=0。如图。如图2所示。如果网页文件总数为所示。如果网页文件总数为N，那么这个网页链接那么这个网页链接矩阵就是一个矩阵就是一个NxN的矩的矩阵阵。n3）网页链接概率矩阵）网页链接概率矩阵n然后将然后将每一行除以该行非零数字之和每一行除以该行非零数字之和，即（每行非，即（每行非0数之和就是链接网个数）则得到新数之和就是链接网个数）则得到新矩阵矩阵P，如图，如图3所示。所示。这个矩阵记录了这个矩阵记录了每个网页跳转到其他网页的概率，即其中每个网页跳转到其他网页的概率，即其中i行行j列列的值表示用户从页面的值表示用

13、户从页面i转到页面转到页面j的概率。图的概率。图1中中A页面链向页面链向B、C，所以一个用户从，所以一个用户从A跳跳转到转到B、C的概率各为的概率各为1/2。n4）概率转移矩阵）概率转移矩阵Pn采用采用P的转置矩的转置矩阵进行计算，阵进行计算，也就是上面提到的概率转移矩阵也就是上面提到的概率转移矩阵P。如图如图4所示：所示：2.3求解步骤：求解步骤：2.4A矩阵计算过程。矩阵计算过程。2.5循环迭代计算循环迭代计算PageRank的过程的过程 2.6改改进进 LarryPage和和SergeyBrin两人从理论上证明了不论初始值如何选取，这种算法都保两人从理论上证明了不论初始值如何选取，这种算

14、法都保证了网页排名的估计值能收敛到他们的真实值。证了网页排名的估计值能收敛到他们的真实值。由于互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方由于互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数目平方之多个元素。如果我们假定有十亿个网页，那么这个矩阵之多个元素。如果我们假定有十亿个网页，那么这个矩阵就有一百亿亿个元素。这样就有一百亿亿个元素。这样大的矩阵相乘，计算量是非常大的。大的矩阵相乘，计算量是非常大的。LarryPage和和SergeyBrin两人利用稀疏矩阵计两人利用稀疏矩阵计算的技巧，大大的简化了计算量。算的技巧，大大的简化了计算量。PageRa

15、nk的计算举例链接源链接源ID链接目标链接目标ID12,3,4,5,72131,242,3,551,3,4,661,5753 PageRank算法的应用n学术论文的重要性排序n学术论文的作者的重要性排序某作者引用了其它作者的文献，则该作者认为其它作者是“重要”的。n网络爬虫(Web Crawler)可以利用PR值，决定某个URL，所需要抓取的网页数量和深度重要性高的网页抓取的页面数量相对多一些，反之，则少一些n关键词与句子的抽取（节点与边）小结n优点：是一个与查询无关的静态算法，所有网页的PageRank值通过离线计算获得；有效减少在线查询时的计算量，极大降低了查询响应时间。nPageRank的缺点过分相信链接关系n一些权威网页往往是相互不链接的，比如新浪、搜狐、网易以及腾讯这些大的门户之间，基本是不相互链接的，学术领域也是这样。n1）人们的查询具有主题特征，PageRank忽略了主题相关性，导致结果的相关性和主题性降低 n 2）旧的页面等级会比新页面高。因为即使是非常好的新页面也不会有很多上游链接，除非它是某个站点的子站点。n排序技术是搜索引擎的绝密Google目前所使用的排序技术，已经不再是简单的PageRank谢谢大家!