Google 的秘密- PageRank 彻底解说

作者:佚名       来源于:中国营销策划网

固定分布。PageRank 用马尔可夫过程来说就是,PageRank就是以一定时间内用户随机地沿着(网页)链接前进时对各个页面访问的固定分布。

假想模型和现实世界的不同

那么,让我们将概率过程(即图表原理)的考虑方法和实际的网页链接构造合起来看一看。

对于刚才举例的假想网页群来说,只要相互顺着链接前进则在彼此页面间必定有相互链接的关系。即,有向图表是强联结的行列既是回归又是最简。像上面举的很多的概率过程的教科书一样,许多证明都是把回归和最简作为前提来证明的,如果是最简的话,各种各样的性质就变得容易说了。

但是现实的网页并不是强联结。也就是说邻接行列不是最简的。具体来说,顺着链接前进的话,有时会走到完全没有向外链接的网页。通常这样的情况,只有利用 web 浏览器的「返回」功能了。如果人们只是浏览而已的话,一切就到此结束了,然而 PageRank 的计算却不能到此结束。因为PageRank 一旦被引入以后是不能返回的。Pagerank 称这种页面为为「dangling page」。同样道理,只有向外的链接而没有反向链接的页面也是存在的。但 Pagerank 并不考虑这样的页面,因为没有流入的 PageRank 而只流出的 PageRank,从对称性来考虑的话必定是很奇怪的。

同时,有时候也有链接只在一个集合内部旋转而不向外界链接的现象。这是非周期性的回归类多重存在时可能出现的问题。(请读者考虑一下陷入上图中一个 R 中而不能移动到别的 R 和 T 的情况)。 Pagerank 称之为「rank sink」。在现实中的页面,无论怎样顺着链接前进,仅仅顺着链接是绝对不能进入的页面群总归存在,也就是说,这些页面群是从互相没有关联的多数的同值类(回归类)形成的。

总之,由现实的 Web 页组成的推移概率行列大部分都不是最简的。当不是最简时,最大特性值(即1)是重复的,并且不能避免优固有矢量多数存在的问题。换句话说,PageRank 并不是从一个意义上来决定的。

在此,Pagerank 为了解决这样的问题,考虑了一种「用户虽然在许多场合都顺着当前页面中的链接前进,但时常会跳跃到完全无关的页面里」,这样的浏览模型。再者,将「时常」固定为 15% 来计算。用户在 85% 的情况下沿着链接前进,但在 15% 的情况下会突然跳跃到无关的页面中去。(注:Pagerank 的原始手法是各自87%(=1/1.15 )和13%(=0.15/1.15)。)

将此用算式来表示的话得到以下公式。

M'= c*M +(1-c)*[1/N]

其中,[1/N]是所有要素为 1/N 的 N次正方行列,c =0.85(=1-0.15)。M'当然也同样是推移概率行列了。也就是说,根据 Pagerank 的变形,原先求行列 M 的特性值问题变成了求行列 M'的优固有矢量特性值问题。M 是固定无记忆信息源(i.i.d.)时,M'被称为「混合信息源」,这也就是固定但非ellGoth信息源的典型例子。

如果从数学角度看,「把非最简的推移行列最简化」操作的另外一种说法就是「把不是强联结的图表变成强联结」的变换操作。所谓对全部的要素都考虑0.15的迁移概率,就是意味着将原本非最简的推移概率行列转换为最简并回归的(当然非负的情况也存在)推移概率行列。针对原本的推移概率行列,进行这样的变换操作的话,就能从一个意义上定义 PageRank、也就是说能保证最大特性值的重复度为1。如果考虑了这样的变换操作的话,因为推移概率行列的回归类的数目变成 1 的同时也最简化,根据前面的定理,优固有矢量(即 PageRank)就被从一个意义上定义了。

数值计算上的问题点(其1)

在此,只要大概明白 PageRank 的概念就可以了,不需要很深的陷入数值计算上的技术的问题中(其实,笔者自己即使有自信也说不清楚)。但是,因为特性值分析和联立一次方程式分析一样,是利用在各种的统计分析中重要的数值计算手法的一中,所以这里我们简单的触及一些分析方法。

|<< << < 1 2 3 4 5 6 7 8 9 10 > >> >>|


 8/12   首页 上一页 6 7 8 9 10 11 下一页 尾页

上一篇登录搜索引擎的准备工作

下一篇搜索引擎垃圾

 【相关文章




版权声明:文章观点仅代表作者观点,作为参考,不代表本站观点。部分文章来源于网络,如果网站中图片和文字侵犯了您的版权,请联系我们及时删除处理!转载本站内容,请注明转载网址、作者和出处,避免无谓的侵权纠纷。