【十大经典数据挖掘算法】PageRank



转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com

AIQ 机器学习大数据 知乎专栏 点击关注

引言

PageRank 是 Sergey Brin 与 Larry Page 于 1998 年在 WWW7 会议上提出来的,用来解决链接分析中网页排名的问题。在衡量一个网页的排名,直觉告诉我们:

当一个网页被更多网页所链接时,其排名会越靠前;

排名高的网页应具有更大的表决权,即当一个网页被排名高的网页所链接时,其重要性也应对应提高。

对于这两个直觉,PageRank 算法所建立的模型非常简单:一个网页的排名等于所有链接到该网页的网页的加权排名之和:

表示 i 个网页的 PageRank 值,用以衡量每一个网页的排名;若排名越高,则其 PageRank 值越大。网页之间的链接关系可以表示成一个有向图,边代表了网页 j 链接到了网页 i;为网页 j 的出度,也可看作网页 j 的外链数( the number of out-links)。

假定为 n 维 PageRank 值向量,A 为有向图 G 所对应的转移矩阵,

n 个等式(1)改写为矩阵相乘:

但是,为了获得某个网页的排名,而需要知道其他网页的排名,这不就等同于“是先有鸡还是先有蛋”的问题了么?幸运的是,PageRank 采用 power iteration 方法破解了这个问题怪圈。欲知详情,请看下节分解。

求解

为了对上述及以下求解过程有个直观的了解,我们先来看一个例子,网页链接关系图如下图所示:

那么,矩阵 A 即为

所谓 power iteration,是指先给定一个 P 的初始值,然后通过多轮迭代求解:

最后收敛于,即差别小于某个阈值。我们发现式子(2)为一个特征方程(characteristic equation),并且解 P 是当特征值(eigenvalue)为 1 时的特征向量(eigenvector)。为了满足(2)是有解的,则矩阵 AA 应满足如下三个性质:

  • stochastic matrix,则行至少存在一个非零值,即必须存在一个外链接(没有外链接的网页被称为 dangling pages);

  • 不可约(irreducible),即矩阵 A 所对应的有向图 G 必须是强连通的,对于任意两个节点 u,v∈V,存在一个从 u 到 v 的路径;

  • 非周期性(aperiodic),即每个节点存在自回路。

显然,一般情况下矩阵 A 这三个性质均不满足。为了满足性质 stochastic matrix,可以把全为 0 的行替换为 e/ne/n,其中 e 为单位向量;同时为了满足性质不可约、非周期,需要做平滑处理:

其中,d 为 damping factor,常置为 0 与 1 之间的一个常数;E 为单位阵。那么,式子(1)被改写为

参考资料

[1] Bing Liu and Philip S. Yu, "The Top Ten Algorithms in Data Mining" Chapter 6.


更多高质资源 尽在AIQ 机器学习大数据 知乎专栏 点击关注

转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com