PageRank算法简介及Map-Reduce实现

PageRank对网页排名的算法,曾是Google发家致富的法宝。以前虽然有实验过,但理解还是不透彻,这几天又看了一下,这里总结一下PageRank算法的基本原理。

一、什么是pagerank

PageRank的Page可是认为是网页,表示网页排名,也可以认为是Larry Page(google 产品经理),因为他是这个算法的发明者之一,还是google CEO(^_^)。PageRank算法计算每一个网页的PageRank值,然后根据这个值的大小对网页的重要性进行排序。它的思想是模拟一个悠闲的上网者,上网者首先随机选择一个网页打开,然后在这个网页上呆了几分钟后,跳转到该网页所指向的链接,这样无所事事、漫无目的地在网页上跳来跳去,PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。

二、最简单pagerank模型

互联网中的网页可以看出是一个有向图,其中网页是结点,如果网页A有链接到网页B,则存在一条有向边A->B,下面是一个简单的示例:

201959072629566

 

这个例子中只有四个网页,如果当前在A网页,那么悠闲的上网者将会各以1/3的概率跳转到B、C、D,这里的3表示A有3条出链,如果一个网页有k条出链,那么跳转任意一个出链上的概率是1/k,同理D到B、C的概率各为1/2,而B到C的概率为0。一般用转移矩阵表示上网者的跳转概率,如果用n表示网页的数目,则转移矩阵M是一个n*n的方阵;如果网页j有k个出链,那么对每一个出链指向的网页i,有M[i][j]=1/k,而其他网页的M[i][j]=0;上面示例图对应的转移矩阵如下:

202015378717604

 

初试时,假设上网者在每一个网页的概率都是相等的,即1/n,于是初试的概率分布就是一个所有值都为1/n的n维列向量V0,用V0去右乘转移矩阵M,就得到了第一步之后上网者的概率分布向量MV0,(nXn)*(nX1)依然得到一个nX1的矩阵。下面是V1的计算过程:

202114099185287

 

注意矩阵M中M[i][j]不为0表示用一个链接从j指向i,M的第一行乘以V0,表示累加所有网页到网页A的概率即得到9/24。得到了V1后,再用V1去右乘M得到V2,一直下去,最终V会收敛,即Vn=MV(n-1),上面的图示例,不断的迭代,最终V=[3/9,2/9,2/9,2/9]’:

261719185728644

三、终止点问题

上述上网者的行为是一个马尔科夫过程的实例,要满足收敛性,需要具备一个条件:

  • 图是强连通的,即从任意网页可以到达其他任意网页:

互联网上的网页不满足强连通的特性,因为有一些网页不指向任何网页,如果按照上面的计算,上网者到达这样的网页后便走投无路、四顾茫然,导致前面累计得到的转移概率被清零,这样下去,最终的得到的概率分布向量所有元素几乎都为0。假设我们把上面图中C到A的链接丢掉,C变成了一个终止点,得到下面这个图:

fclkjfljaljfldkjglksajglasgj1

对应的转移矩阵为:

fclajsdfkdjsaglkjsdglsajg2

连续迭代下去,最终所有元素都为0:

fclakjsgflkgjlsajgsajg3

四、陷阱问题

另外一个问题就是陷阱问题,即有些网页不存在指向其他网页的链接,但存在指向自己的链接。比如下面这个图:

ljlajkjasglkjsdgkjsgla1

上网者跑到C网页后,就像跳进了陷阱,陷入了漩涡,再也不能从C中出来,将最终导致概率分布值全部转移到C上来,这使得其他网页的概率分布值为0,从而整个网页排名就失去了意义。如果按照上面图对应的转移矩阵为:

fclajsdfkdjsaglkjsdglsajg2

不断的迭代下去,就变成了这样:

202136578712805

 

五、解决终止点问题和陷阱问题

上面过程,我们忽略了一个问题,那就是上网者是一个悠闲的上网者,而不是一个愚蠢的上网者,我们的上网者是聪明而悠闲,他悠闲,漫无目的,总是随机的选择网页,他聪明,在走到一个终结网页或者一个陷阱网页(比如两个示例中的C),不会傻傻的干着急,他会在浏览器的地址随机输入一个地址,当然这个地址可能又是原来的网页,但这里给了他一个逃离的机会,让他离开这万丈深渊。模拟聪明而又悠闲的上网者,对算法进行改进,每一步,上网者可能都不想看当前网页了,不看当前网页也就不会点击上面的连接,而上悄悄地在地址栏输入另外一个地址,而在地址栏输入而跳转到各个网页的概率是1/n。假设上网者每一步查看当前网页的概率为a,那么他从浏览器地址栏跳转的概率为(1-a),于是原来的迭代公式转化为:

202158112317322

现在我们来计算带陷阱的网页图的概率分布:

202205000122441

重复迭代下去,得到:

261719185728644

六、用Map-reduce计算Page Rank

  上面的演算过程,采用矩阵相乘,不断迭代,直到迭代前后概率分布向量的值变化不大,一般迭代到30次以上就收敛了。真的的web结构的转移矩阵非常大,目前的网页数量已经超过100亿,转移矩阵是100亿*100亿的矩阵,直接按矩阵乘法的计算方法不可行,需要借助Map-Reduce的计算方式来解决。实际上,google发明Map-Reduce最初就是为了分布式计算大规模网页的pagerank,Map-Reduce的pagerank有很多实现方式,我这里计算一种简单的。

考虑转移矩阵是一个很多的稀疏矩阵,我们可以用稀疏矩阵的形式表示,我们把web图中的每一个网页及其链出的网页作为一行,这样第四节中的web图结构用如下方式表示:

A有三条出链,分布指向A、B、C,实际上,我们爬取的网页结构数据就是这样的。

1、Map阶段

Map操作的每一行,对所有出链发射当前网页概率值的1/k,k是当前网页的出链数,比如对第一行输出<B,1/3*1/4>,<C,1/3*1/4>,<D,1/3*1/4>;

2、Reduce阶段

Reduce操作收集网页id相同的值,累加并按权重计算,pj=a*(p1+p2+…Pm)+(1-a)*1/n,其中m是指向网页j的网页j数,n所有网页数。

思路就是这么简单,但是实践的时候,怎样在Map阶段知道当前行网页的概率值,需要一个单独的文件专门保存上一轮的概率分布值,先进行一次排序,让出链行与概率值按网页id出现在同一Mapper里面,整个流程如下:

211557326376640

 

这样进行一次迭代相当于需要两次MapReduce,但第一次的MapReduce只是简单的排序,不需要任何操作,用python调用Hadoop的Streaming.

SortMappert.py代码如下:

SortReducer.py也是一样

PageRankMapper.py代码:

PageRankReducer.py代码:

在linux下模仿Map-Reduce的过程:

这个代码不用改动就可以直接在hadoop上跑起来。调用hadoop命令:

关于使用python操作hadoop可以查看参考文献。python代码写得浓浓的C味,望海涵!

第四步中带环的陷阱图,迭代40次,权值a取0.8,计算结果如下:

可以看到pagerank值已经基本趋于稳定,并与第四步的分数表示一致。

PageRank的简介就介绍到这里了,如果想深入可以参考原论文或者下面的参考文献

参考文献

1.《Mining of Massive Datasets》

2.《An introduction to information retrival》

3.使用python操作Hadoop

4.js可视化展示PageRank计算过程(可能需要梯子),可访问作者博客.

3 15 收藏 9 评论

相关文章

可能感兴趣的话题



直接登录
最新评论
跳到底部
返回顶部