机器学习|PageRank算法原理

01

—

网页排名主要考虑因素

学术界评判学术论文重要性通用方法是看论文的引用次数，原理很多时候都是可以通用的，学术界的思想可以应用到工业界。

google创始人拉里佩奇等将衡量论文重要性的方法应用到了网页的排名上，提出：如果一个网页A被很多其他网页链接到地话，说明网页A比较重要，也就是A的PageRank值会相对较高，意思是有很多其他网页指向这个网页A，也就是说网页A的入度比较大，当然如果链接到网页A的那些网页的PageRank都比较高，那无疑更加表明网页A的PageRank会很高，因为不仅有量，还有质。

02

—

以此为据，建立图模型

假定一共只有4个网页，是的，一共只有4个网页，现在要求它们的PageRank，我们还知道它们之间的引用关系如下所示：

可以看到网页A被网页B和C都引用了，网页B被网页A和D引用了，网页C被网页A和D引用，网页D被网页A和B引用。

如何求出网页A的PageRank呢？以下PageRank简写为PR

网页A的PR值就可以表示为：PR(A) = PR(B)+PR(C)，这个公式是能准确地刻画出网页A的PR吗，假象你现在正在读网页B，文章末尾有两个链接，分别指向网页A和D，此时，你进入网页A的概率是0.5，如果你在网页C，那么此时你点到链接A的概率是1.0，所以PR(A) = 0.5PR(B)+1.0*PR(C)，我们已经往前走了一步，但是这不是终点，为什么？

我们在浏览B网页的时候，读到文章末尾后，虽然给出了两个链接，但是你可能是一个比较另辟蹊径的人，根本不关心给出的链接，直接在地址栏中输入其他网址，直接到C网页了。

这的确是个问题，怎么解决呢？

03

—

意外之喜

当你停留在B网页时，你可能没有点击里面的两个链接，这个的意思是我们要对PR(B)的系数0.5做一个惩罚，比如乘以一个惩罚系数0.85，这样PR(A)=0.85*0.5*PR(B)+0.85*1.0*PR(C)，既然你没有通过两个内部链接找到A，但是在世界的另一个角，一个叔叔直接在地址栏输入了一个网址，直接找到了网页A，这对A来讲，是意外之喜，所以PR(A)还要考虑这个因素，进一步修正PR(A)为，

PR(A)=0.85 * 0.5 * PR(B) + 0.85 *1.0 * PR(C) +（1-0.85) / 4

其中，4是网页的总个数

04

—

将公式抽象

上面这个公式，其实就是最终的求某个网页PR的公式了，只不过总网页的个数为4个，还假定了4个网页的链接关系，为了不失一般性，据此，推理出一般性的公式：

其中，

Mpi描述了指向网页Pi的所有网页集合，L(Pj)是网页Pj的出链数目，N是网页的总数，a是惩罚因子，一般取值为0.85.

根据上面的公式，我们可以计算每个网页的PR值，在不断迭代趋于平稳的时候，即为最终结果，关于算法的Map-Reduce实现代码，请看接下来推送。