|
使用一款搜索引擎，我们希望搜索结果能够拥有最佳的排序，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四张网页）帮助说明这个矩阵（这个例子来自于这篇文章）：
可以看到矩阵L的几个非零元素的取值：
于是，对于A来说，它的PageRank取值就可以表示为：
但这是在用户百分之百点击网页链接的情况下发生的，实际上，只有p概率的用户会点击网页链接，剩下(1-p)概率的用户会跳到无关的页面上去，而访问的页面恰好是4这个页面中A的概率只有(1-p)/4（p正是前文提到的“阻尼系数”（damping factor），Google取p等于0.85），所以：
推广到一般公式（pi表示第i张网页，L(pj)表示从pi链出网页的数量）：
如果仅仅依赖这个公式，可以看得到每一个页面的PageRank(pi)的值都和其他页面有关系，这样一来，就没有办法直接解出这个PageRank(pi)的值来了。 不过，佩奇和布林想到了一个办法，有了PageRank(pi)的概念以后，PageRank矩阵就可以用一个特征向量来表示：
由上述两个公式，可以得到（其中l(pi,pj)就是前文提到过的pij）：
接着给所有网页一个统一的初始权值，每次都用上面提到的R矩阵去乘以原始的N×N的矩阵，把结果这个新的矩阵继续去乘以那个N×N的原始矩阵，反复进行，相乘行为引起的矩阵变化越来越小，直到收敛到一个给定的值以内，停止。 这时的矩阵就包含了每个网页的PageRank特征向量，对于每个向量来说，它的每一个维度值去乘以该维度下的权值并累加，最终都可以转化为一个具体的PageRank的数字。 这就是PageRank计算最最基本的部分，Google对于这种超大型矩阵相乘有自己的保密技术。截止到2010年，Google索引的网页总数已经超过5000亿，也就是说，Google必须解这个阶数的矩阵相乘问题，这是不是真的就是MapReduce之类的由来呢？ 以上未特殊注明的公式截图来自于维基百科。 原文地址：http://www.raychase.net/1303 |
