谷歌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转置（交换行和列），得到M^T。M^T的每一行的全部元素之和不就正好是公式(3)中的 吗？例如图3可以得到这样的矩阵：

M^T={ 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 M^T R (4)

在公式(4)中，R可以看作M^T的特征向量，其对应的特征值为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，得到：

(5)

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

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

R = C M^T R + CE = C( M^T R + E )

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

将上式重写为

R = C( M^T + E * 1 ) R (6)

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

在公式(6)中，只要将R看作(M^T + 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/