机器学习 — 排名算法之PageRank

概述

PageRank 是Google使用的对其搜索引擎搜索结果中的网页进行排名的一种算法,该算法是以Google创始人之一Larry Page的名字来命名的. Google的搜索引擎用它来分析网页的相关性和重要性，在搜索引擎优化中经常被用来作为评估网页优化的成效因素之一.

Google通过PageRank使那些更具“等级/重要性”的网页在搜索结果中另网站排名获得提升,从而提高搜索结果的相关性和质量. PR值(会在下文介绍如何计算)越高说明该网页越受欢迎.目前，PageRank不再是Google给网页进行排名的唯一算法，但它是最早的，也是最著名的算法.

PageRank 是一种链接分析算法,它通过对超链接集合中的元素用数字进行权重赋值,实现“衡量集合范围内某一元素的相关重要性”的目的, 并且PageRank可以运用任何有元素之间互相引用的情况的实体集合.

PageRank概念图

算法

以下介绍以用户点击网页链接的事件作为背景

总的来说, PageRank 通过概率分布来表示用户随机点击某个链接的概率(点击所有链接的概率总和为1), 在开始计算之前,总概率将被平均分布到每个文件上,使得集合中的所有文件被访问的概率相等. 接下来在迭代中,算法会根据数据的实际情况不断调整PR值.

基础算法思想

假设一个由4个网页组成的集合：A，B，C和D。同一页面中多个指向相同的链接视为同一个链接，并且每个页面初始的PageRank值相同，最初的算法将每个网页的初始值设定为0.25(对4个网页进行概率平均分布).

如果所有页面都连接至A, 那么A的PR值变为B,C,D的PR值之和:

如果B链接到A和C，C链接到A，并且D链接到A,B,C。最初一个页面总共只有一票。所以B给A ,C每个页面半票。以此类推，D投出的票只有三分之一加到了A的PR值上：

用数学公式来表示上述情景,可以将每个页面定向到其他网页的总次数 $L(x)$评分该页面的PR值,并加到所指向的页面:

最后，所有这些PR值被换算成百分比形式再乘上一个修正系数 $d$。由于“没有向外链接的网页”传递出去的PR值会是0，而这会递归地导致指向它的页面的PR值的计算结果同样为零，所以赋给每个页面一个最小值(1-d)/N:

最终一个页面的PR值会作为搜索引擎对网页排名的指标.

进阶

为了优化该算法,引入了random surfer的概念,假设某人随机点开了某些页面和链接. 假设用户不停的点击链接直到进入一个没有外部链接的网页, 这个时候他会随机点击其他网页.

没有外部链接的网页会吞噬掉用户继续向下浏览的概率,为了解决这样的问题, 假设该页面会链接到结合中的所有网页(不管是否相关),并使得这样的网页PR值被所有网页均分.这样的概率被称为残差概率(residual probability).

之后,引入阻尼系数 $d$(damping factor), 假设系数为0.85,表示在任意时刻,用户访问到某个页面后还要继续往下访问的概率,对应的,0.15表示用户不再往下继续浏览,而是开始随机浏览一个新的网页的概率.

因此,对于页面i,PR值的计算公式为:

这里，p1,p2,…,pn 是目标页面pi, M(pi) 为页面的集合, L(pj) 是 页面链出的而数量,N是所有页面的数量

缺点

旧的页面的排名往往会比新页面高,因为即使是质量很高的新页面也往往不会有很多外链，除非它是某个已经存在站点的子站点