浅入浅出：PageRank算法

网络上将pagerank的博文已经很多了，一般的数据挖掘相关的书籍中也会有介绍。本文只是粗略的讲一下笔者对pagerank的理解，以及如何放在真实场景中使用pagerank。

下图显示了某一时刻网页A、B、C的链接情况，网页A中存在到网页B、C中的链接，网页B存在到网页C的链接，网页C存在到网页A的链接。

PageRank的目的就是在已知这种链接方式的情况下判断三个网页的重要性。如果A和B中含有相同的关键字，而A的重要性高于B，那么搜索这个关键字的结果中网页A应该放在网页B之前。

最简单的PageRank

一个网页本身具有一定的重要性，我们认为一个网页的链接会把该网页的重要性传递到链接的网页中，而一个网页的重要性又必须通过链接它的网页来确定。公平起见，一个网页X若链接了m个网页，那么这m个网页的每个网页接收到的来自网页X的重要性是PR(X)/m。设A、B、C的重要性，也就是PageRank值分别是PR(A)、PR(B)、PR(C)。

于是由图01，可得以下方程组：

PR(A) = PR(C)
PR(B) = PR(A)/2
PR(C) = PR(A)/2 + PR(B)

计算可得：

PR(A) = PR(C) = 2*PR(B)

上面的结果已经大致能看出A、B、C各自的重要性。不过有一个问题是，没有把重要程度量化。下面，通过迭代的方式将其量化。

设A、B、C的初始的重要性均为1，通过上面的方程组进行迭代，每次迭代后会更新A、B、C的重要性。为了方面，先把方程组转换为矩阵运算。

PR(A) = 0*PR(A) + 0*PR(B) + PR(C)
PR(B) = 0.5*PR(A) + 0*PR(B) + 0*PR(C)
PR(C) = 0.5*PR(A) + PR(B) + 0*PR(C)

下面是MATLAB版本的代码：

M = [0 0 1 
    0.5 0 0
    0.5 1 0];
PR = [1; 1 ; 1];

for iter = 1:100
    PR = M*PR;
    disp(iter);
    disp(PR);
end

第几次迭代	A的重要性	B的重要性	C的重要性
0	1	1	1
1	1	0.5	1.5
2	1.5	0.5	1.0
3	1	0.75	1.25
4	1.25	0.5	1.25
...	...	...	...
20	1.2002	0.5996	1.2002
27	1.2000	0.6000	1.2000
100	1.2000	0.6000	1.2000

但是，上面的方法是有问题的。先看下图：

从上图，得到的方程组如下：

PR(A) = PR(B) + PR(C)

这种情况下，网页之间的重要性无法比较。

而通过迭代的方法求重要性：

M = [0 1 1 
    0 0 0
    0 0 0];

PR = [1; 1 ; 1];

for iter = 1:100
    PR = M*PR;
    disp(iter);
    disp(PR);
end

最终收敛的结果是：

PR(A) = PR(B) = PR(C) = 0

于是，修正是有必要的。

修正版本的PageRank

第一种修正方式是网页通过链接传递的重要性乘以一个在0和1之间的阻尼系数d：

[latex]
PR(A) = (1-d) + d * \sum_{i=1}^{m} \frac{PR(T_{i})}{C(T_{i})} [/latex]

上式是计算网页A的重要性的式子。[latex]T_{i}[/latex]是存在到A的链接的网页。[latex]C(T_{i})[/latex]是网页[latex]T_{i}[/latex]中的存在的链接的数量。d是阻尼系数，一般定义为用户随机点击链接的概率，常取值0.85。而(1-d)代表着不考虑入站链接的情况下随机进入一个页面的概率。

另一种修正方式和第一种很像，如下：

[latex]
PR(A) = \frac{(1-d)}{N} + d * \sum_{i=1}^m \frac{PR(T_{i})}{C(T_{i})} [/latex]

N是网页的总数。

本文只讨论第一种修正方式。

首先，取阻尼系数为0.85，解决图02中的问题，方程组如下：

A = 0.15 + 0.85*(B+C)
B = 0.15
C = 0.15

解得：

A = 0.4050
B = 0.15
C = 0.15

通过迭代的方法计算：

M = [0 1 1 
    0 0 0
    0 0 0];

PR = [1; 1 ; 1];

for iter = 1:100
    PR = 0.15 + 0.85*M*PR;
    disp(iter);
    disp(PR);
end

最终收敛到：

A = 0.4050
B = 0.15
C = 0.15

与特征值的关系

使用迭代的方法处理图01中的链接关系的时候，使用的矩阵是：

M = [0 0 1 
    0.5 0 0
    0.5 1 0];

这是一个典型的状态转移矩阵（所有元素不小于0，每一列的和为1），也可以叫做随机矩阵（Stochastic matrix），状态转移矩阵的最大特征值为1。在迭代的每一步，进行了下面的运算：

PR = M*PR;

由于图01中的迭代是能够收敛的，所以对于最终的向量PR，肯定会满足上式。这也就意味着PR是矩阵M的特征值1对应的特征向量。

这里只说到这儿，详细可以参考How Google Finds Your Needle in the Web's Haystack。

MapReduce实现

矩阵与向量的乘法很容易用MapReduce编程模型实现，不讨论。

浅入浅出：PageRank算法

最简单的PageRank

修正版本的PageRank

与特征值的关系

MapReduce实现

相关资料