大数据方法论之PageRank的Map-Reduce计算

2020-06-01 00:00:00 网页 链接 运算 映射 矩阵

大家可能都熟悉Google的Page Rank算法,那么如何通过Map-Reduce的方式实现这个算法呢?



Page Rank算法遵循的是平时我们浏览网页的时候的随机游走模型:

  •  用户从任意一个网址开始浏览网页

  •  如果某个网页有N个链接,则用户很大的可能是随机选择一个链接继续浏览

  •  当某个网页没有链接,则用户会任意选择一个网页进行浏览

  •  在任何一个网页,用户都存在一定的可能性,任意选择另外一个网页进行浏览 (远程跳转)


对于如图中的网页的相互关系,如何鉴别那个网页更加的好呢?


其实就是让链接来”投票”


一个页面的得票数由所有链向它的页面的重要性來决定,到一个页面的超链接相当于对该页投一票。


如下面的公式所示




这个公式可以通过矩阵运算得到。



然而网页之间的关系是有环的,所以次运算完毕之后,得到的向量会影响第二次的运算,如此下去进行N次运算,可能结果才能稳定下来。



可能你会疑问,能够稳定下来么?


如果做一个实验,用excel画一个图,你会发现,是会越来越取向稳定的。



我们管这种趋于稳定的状态叫做收敛。


为了更好的收敛,我们对于计算PageRank的公司稍作修改



增加一个阻尼系数,通俗的理解阻尼系数,就是说当你现在在B,C,D网页的时候,除了沿着里面的连接到达A之外,还有一种随机的方式,在当前的页面看烦了,之间输入A的网址跳到A。


当有了这个阻尼系数之后,PageRank就是一定能够收敛的了。


因为有定理:有限状态的不可约非周期马尔可夫链必存在平稳分布。


靠,这说的是啥,你不用管,反正存在平稳分布就是了。


还有一个补充定理:正的转移矩阵(即矩阵的每一个元素都是正的)是不可约和非周期的。


在前面的矩阵里面,有为0的元素,所以其实不一定存在平稳分布,但是有了(1-d),则所有的元素都是正的了,则这个矩阵就变成了不可约非周期的,所以一定存在平稳分布。



所以如果写一个Java程序做矩阵运算是这样的,但是如果网页数据量太大了,这样是算不过来的。


于是Map-Reduce就发挥了作用。




首先从爬取的网页里面,输出outlinks的库,在这个库中,保存了From->To的映射关系。


因为PageRank的计算是根据入链来的,因而要通过一个map-reduce程序,输出inlinks库,保存从To->From的映射关系。


然后通过两个库outlinks和inlinks进行合并,生成Node库,每个Node保存每个网页有多少是我链接别人的,有多少是别人链接我的,以及每个网页的score的初始值。


接下来基于初始的score值进行一个循环,不断的迭代。


在每个迭代中,首先Inverter会从outlinks库和nodes库进行合并并翻转,得到To->List<From, Score of From>的一个映射关系。


在每个迭代中,其次Analyzer会基于上面的映射关系和nodes库,计算To的这个网页的score,score(To)=sum(score(from)),也即将from的每个score加起来。


如此循环,直到收敛到一个稳定的score,则停止循环。



相关文章