浅入浅出:PageRank算法 使用 TextRank 算法为文本生成关键字和摘要 基于物品的协同过滤 如何使用MapReduce实现基于物品的协同过滤(1) 如何使用MapReduce实现基于物品的协同过滤(2) 浅入浅出:K近邻算法 使用mahout下的朴素贝叶斯分类器对新闻分类 使用Affinity Propagation进行聚类 K-medoids聚类 矩阵分解在推荐系统中的应用:NMF和经典SVD实战 使用特征递归消除筛选特征 如何分配权重 比较NMF、PCA和VQ 方差和协方差 基于SVD的协同过滤 逻辑斯谛回归代码实现 隐语义模型和NMF(非负矩阵分解) 使用PCA处理MNIST数据集 使用GBDT选取特征 基于贝叶斯的文本分类系统的数据库设计 在hadoop1.2.1上安装mahout 0.9 Hadoop 2.4 实现Kmeans聚类算法 在Iris数据集上对比PCA、LDA、NMF 基于贝叶斯的文本分类实战 单层决策树 Logistic regression(逻辑斯蒂回归) 基于用户的协同过滤 词袋模型与文档-词矩阵 如何实现拼音与汉字的互相转换 梯度下降法 如何判定相似度 MovieLens数据集介绍 基于KNN的文本分类实战 Jasper文本分类系列博客阅读摘录 使用 Mean Shift进行聚类 朴素贝叶斯的三个常用模型:高斯、多项式、伯努利 使用决策树处理iris数据集 浅入浅出:从Kmeans到Kmeans++ 如何持久化scikit-learn中训练好的模型 浅入浅出:DBSCAN聚类算法(1) 浅入浅出:DBSCAN聚类算法(2) 2015阿里移动推荐算法比赛第一赛季总结 爬山算法 使用朴素贝叶斯分类器划分邮件 层次聚类 基于MapReduce的频繁项集挖掘 搜狗实体关系提取比赛

浅入浅出: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编程模型实现,不讨论。

相关资料



( 本文完 )