【数据挖掘】PageRank 为什么跻身数据挖掘十大经典算法？

数据人有话说

Google 的 PageRank 曾是主宰 Google 排名算法的一个主要因素，一度我们看一个网站的排名，往往会先去分析它的 PageRank 是多少。不过现在人们逐渐意识到 PageRank 已难再唱主角，麻烦就出在它在概念上太容易理解了——一旦容易被理解，就容易被控制。搜索引擎的价值和魅力，就在于我们无法了解它幕后的排名技术。相反，如果我们了解了一个搜索引擎是如何对搜索结果进行排名的，那么我们完全可以从中做手脚，这样的话这个搜索引擎就没有什么意义了。

然而即使辉煌不再，不可否认的是，PageRank 曾是 Google 早期击败所有竞争对手的关键。毫不夸张地说，正是 PageRank 算法成就了 Google 今天的地位。

作者：风中之炎 编辑：赵玥辉

PageRank——谷歌曾借之以独步天下的“倚天剑”。该算法由Larry Page和Sergey Brin在斯坦福大学读研时发明，这种算法的核心思想有 2 点：

1.如果一个网页被很多其他网页链接到的话说明这个网页比较重要，也就是pagerank值会相对较高；

2.如果一个pagerank值很高的网页链接到一个其他的网页，那么被链接到的网页的pagerank值会相应地因此而提高。

虽然因为太“亲民”而导致致命缺陷，但这个能够被载入互联网发展史册的算法，仍然值得我们近距离观察一下。不过要提醒的是，再“亲民”的算法毕竟也是个算法，基本逼格还是在的。前方高能预警——主要内容适合技术宅、程序猿、数学爱好者，以及想要挑战自己的数字恐惧症患者阅读。

1. 前言

这系列文章主要讲述2006年评出的数据挖掘10大算法（见图1）。文章的重点将偏向于算法的来源以及算法的主要思想，不涉及具体的实现。如果发现文中有错，希望各位指出来，一起讨论。

图1 来自IDMer的文章

在这些算法中，最引人注目的自然是Google的核心技术之一——PageRank。因此本系列就先来探索PageRank的诞生过程。

2. 核心思想

常言道，看一个人怎样，看他有什么朋友就知道了。也就是说，一个人有着越多牛X朋友的人，他是牛X的概率就越大。将这个知识迁移到网页上就是“被越多优质的网页所指的网页，它是优质的概率就越大”。

PageRank的核心思想就是上述简单却有效的观点。由这个思想，可以得到一个直观的公式：

(1)

R(x)表示x的PageRank，B(x)表示所有指向x的网页。

公式(1)的意思是一个网页的重要性等于指向它的所有网页的重要性相加之和。粗看之下，公式(1)将核心思想准确地表达出来了。但仔细观察就会发现，公式(1)有一个缺陷：无论J有多少个超链接，只要J指向I，I都将得到与J一样的重要性。当J有多个超链接时，这个思想就会造成不合理的情况。例如：一个新开的网站N只有两个指向它的超链接，一个来自著名并且历史悠久的门户网站F，另一个来自不为人知的网站U。根据公式(1)，就会得到N比F更优质的结论。这个结论显然不符合人们的常识。

弥补这个缺陷的一个简单方法是当J有多个超链接（假设个数为N），每个链接得到的重要性为R(j)/N。于是公式(1)就变成：

(2)

N(j)表示j页面的超链接数

图2 来自Lawrence Page的文章

从图2可以看出，如果要得到N比F更优质的结论，就要求N得到很多重要网站的超链接或者海量不知名网站的超链接。而这是可接受的。因此可以认为公式(2)将核心思想准确地表达出来了。为了得到标准化的计算结果，在公式(2)的基础上增加一个常数C，得到公式(3)：

（3）

3. 计算

由公式(3)可知，PageRank是递归定义的。换句话就是要得到一个页面的PageRank，就要先知道另一些页面的PageRank。因此需要设置合理的PageRank初始值。不过，如果有办法得到合理的PageRank初始值，还需要这个算法吗？或者说，这个严重依赖于初始值的算法有什么意义吗？

依赖于合理初始值的PageRank算法是没意义的，那么不依赖于初始值的PageRank算法就是有意义的了。也就是说，如果存在一种计算方法，使得无论怎样设置初始值，最后都会收敛到同一个值就行了。要做到这样，就要换一个角度看问题，从线性代数的角度看问题。

将页面看作节点，超链接看作有向边，整个互联网就变成一个有向图了。此时，用邻接矩阵M表示整个互联网，若第I个页面有存在到第J个页面的超链接，那么矩阵元素m[i][j]=1，否则m[i][j]=0。对于图3有

矩形M={ 0, 1, 1, 0,

0, 0, 0, 1,

1, 0, 0, 0,

1, 1, 1, 0 }

图3

观察矩阵M可发现，M的第I行表示第I个网页指向的网页，M的第J列表示指向J的网页。如果将M的每个元素都除于所在行的全部元素之和，然后再将M转置（交换行和列），得到MT。MT的每一行的全部元素之和不就正好是公式(3)中的 吗？例如图3可以得到这样的矩阵：

MT={ 0, 0, 1, 1/3,

1/2, 0, 0, 1/3,

1/2, 0, 0, 1/3,

0, 1, 0, 0 }

将R看作是一个N行1列的矩阵，公式(3)变为

R = C MT R (4)

在公式(4)中，R可以看作MT的特征向量，其对应的特征值为1 / C（看不明白这句话，可以回忆下线性代数中对特征向量的定义——对于矩阵A，若存在着列向量X和一个数c，使得AX=cX，则X称为A的特征向量，c称为A的特征值）。幂法(power method）计算主特征向量与初始值无关，因此只要把R看作主特征向量计算，就可以解决初始值的合理设置问题。

幂法得到的结果与初始值无关，是因为最终都会收敛到某个值。因此使用幂法之前，要确保能够收敛。但是，在互联网的超链接结构中，一旦出现封闭的情况，就会使得幂法不能收敛。所谓的封闭是指若干个网页互相指向对方，但不指向别的网页，具体的例子如图4所示：

图4 来自Soumya Sanyal的PPT

上图4个绿色网页就是封闭情况。这种情况会使得这些网页的PageRank在计算的时候不断地累加，从而使得结果不能收敛。仔细研究就会发现红色网页的PageRank给了绿色网页后，绿色网页就将这些PageRank吞掉了。Larry Page将这种情况称为Rank Sink。

如果沿着网页的链接一直点下去，发现老是在同样的几个网页中徘徊，怎么办？没错，把当前页面关掉，再开一个新的网页。上述情况正好与Rank Sink类似，也就意味着可以借鉴这个思想解决Rank Sink。因此，在公式(3)中的基础上加一个逃脱因子E，得到：

（4）

E(i)表示第i个网页的逃脱因子

将(5)变成矩阵形式，可得：

R = C MT R + CE = C( MT R + E )

其中列向量R的1范数(即R的全部矩阵元素相加)为1

将上式重写为

R = C( MT + E * 1 ) R (6)

1是指一行N列的行向量，且每个元素都是1

在公式(6)中，只要将R看作(MT + E * 1)的特征向量，就可以同时解决初始值设置问题和封闭的情况。

4. 资料共享

找资料是简单的事，但要找到好资料就不那么容易了。因此，这一小节是分享我找到的一些比较好的资料。

1. PageRank之父的文章: The PageRank Citation Ranking Bringing Order to the Web

http://ilpubs.stanford.edu:8090/422/

2. 一个对PageRank进行解释的PPT，讲解得很好: The PageRank Citation Ranking – Redone

http://wenku.baidu.com/view/30657568a98271fe910ef975.html?from=related

3. 不错的PageRank科普文: Google 的秘密- PageRank 彻底解说 中文版

http://www.kreny.com/pagerank_cn.htm

4. 本文所用到的线性代数相关知识

http://ceee.rice.edu/Books/LA/eigen/

文章来源：http://www.cnblogs.com/FengYan/archive/2011/11/12/2246461.html