Google 矩阵

google matrix 使用一款搜索引擎,我们希望搜索结果能够拥有最佳的排序,Google 为它最核心的排序算法 PageRank 申请了专利。在 PageRank 以前,排序大多依靠对搜索关键字和目标页的匹配度来进行的,这种排序方式弊端明显,尤其对于善于堆砌关键字舞弊的页面,很容易就跳到了搜索结果的首页。Larry Page 和 Sergey Brin 开始着手解决这个问题,Google 排序的继承来自于互联网上网页之间的链接关系。一张网页被其它网页引用的次数越多,可以简单地认为这样的网页越受欢迎,当然在结果列表中应该越靠前。

前面提到了目标网页被引用网页的“ 数量”,另一条重要的判定 PageRank 级别的依据则是“ 质量”。换言之,质量高的网页所引用的网页,质量往往也比较高,所以质量高的网页投票所占权重理应更高。

在用户访问某一张网页时,假设他有 q 的概率去点击网页上的链接,并且点击该网页每条链接的概率都是相等的。如果该网页有 n 条链接的话,那么点击每条链接的概率就是 1/n。

在表现网页之间链接关系时,Google 使用了矩阵。假设互联网上共有 N 个页面,那么我们可以写出一个 N×N 的矩阵,其中的元素 pij,如果存在从页 i 被页 j 指向的链接(为什么使用“ 被指向” 而非“ 指向”,前文已经解释了),那么 pij 就大于 0,反之就等于 0。同时,每一列元素的取值都除以链接数 n(前文提到了),使得各列矢量总和成为 1,行矢量则表示了各个状态之间的迁移概率,这个最大特征值为 1 的矩阵就成为了 PageRank 矩阵。

现在给出 N 为 4 的一个例子(共有 A、B、C、D 四张网页)帮助说明这个矩阵(这个例子来自于 这篇文章):

 small-web

可以看到矩阵 L 的几个非零元素的取值:

  • p31=1; 表示被 A 指向的只有 C
  • p12=1; 表示被 B 指向的只有 A
  • p13=p43=1/2; 表示被 C 指向的有 A 和 D
  • p14=p24=p34=1/3; 表示被 D 指向的有 A、B、C

于是,对于 A 来说,它的 PageRank 取值就可以表示为:

PR(A) = PR(B)/1 + PR(C)/2 + PR(D)/3

但这是在用户百分之百点击网页链接的情况下发生的,实际上,只有 p 概率的用户会点击网页链接,剩下 (1-p) 概率的用户会跳到无关的页面上去,而访问的页面恰好是 4 这个页面中 A 的概率只有 (1-p)/4(p 正是前文提到的“ 阻尼系数”(damping factor),Google 取 p 等于 0.85),所以:

PR(A) = (1-p)/4 + p(PR(B)/1 + PR(C)/2 + PR(D)/3)

推广到一般公式(pi 表示第 i 张网页,L(pj) 表示从 pi 链出网页的数量):

image

如果仅仅依赖这个公式,可以看得到每一个页面的 PageRank(pi) 的值都和其他页面有关系,这样一来,就没有办法直接解出这个 PageRank(pi) 的值来了。

不过,佩奇和布林想到了一个办法,有了 PageRank(pi) 的概念以后,PageRank 矩阵就可以用一个特征向量来表示:

image

由上述两个公式,可以得到(其中 l(pi,pj) 就是前文提到过的 pij):

image

接着给所有网页一个统一的初始权值,每次都用上面提到的 R 矩阵去乘以原始的 N×N 的矩阵,把结果这个新的矩阵继续去乘以那个 N×N 的原始矩阵,反复进行,相乘行为引起的矩阵变化越来越小,直到收敛到一个给定的值以内,停止。

这时的矩阵就包含了每个网页的 PageRank 特征向量,对于每个向量来说,它的每一个维度值去乘以该维度下的权值并累加,最终都可以转化为一个具体的 PageRank 的数字。

这就是 PageRank 计算最最基本的部分,Google 对于这种超大型矩阵相乘有自己的保密技术。截止到 2010 年,Google 索引的网页总数已经超过 5000 亿,也就是说,Google 必须解这个阶数的矩阵相乘问题,这是不是真的就是 MapReduce 之类的由来呢?

以上未特殊注明的公式截图来自于维基百科。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

19,437 次阅读

10 thoughts on “Google 矩阵

  1. Pingback: 做工程和搞研究
  2. Pingback: Google矩阵 | riaos

发表评论

电子邮件地址不会被公开。

back to top