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

时间:2023-11-28 11:02:50

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

  1. C4.5
  2. K-Means
  3. SVM
  4. Apriori
  5. EM
  6. PageRank
  7. AdaBoost
  8. kNN
  9. Naïve Bayes
  10. CART

我特地把PageRank作为【十大经典数据挖掘算法】系列的收尾篇,是因为本人是Google脑残粉。因了PageRank而Google得以成立,因了Google而这个世界变得好了那么一点点。

1. 引言

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

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

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

\begin{equation}
PR_i = \sum_{(j,i)\in E} \frac{PR_j}{O_j}
\label{eq:pr1}
\end{equation}

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

假定\(P=(PR_1, PR_2, \cdots, PR_n)^T\)为n维PageRank值向量,\(A\)为有向图\(G\)所对应的转移矩阵,

\[
A_{ij}=\left \{
{
\matrix {
\frac{1}{O_i} & if \ (i,j) \in E \cr
0 & otherwise
}
}
\right.
\]

\(n\)个等式\eqref{eq:pr1}可改写为矩阵相乘:

\begin{equation}
P = A^T P
\label{eq:pr2}
\end{equation}

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

2. 求解

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

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

那么,矩阵\(A\)即为

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

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

\[
P^k = A^TP^{k-1}
\]

最后收敛于\(||P^k-P^{k-1}|| < \xi\),即差别小于某个阈值。我们发现式子\eqref{eq:pr2}为一个特征方程(characteristic equation),并且解\(P\)是当特征值(eigenvalue)为\(1\)时的特征向量(eigenvector)。为了满足\eqref{eq:pr2}是有解的,则矩阵\(A\)应满足如下三个性质:

  • stochastic matrix,则行至少存在一个非零值,即必须存在一个外链接(没有外链接的网页被称为dangling pages);
  • 不可约(irreducible),即矩阵\(A\)所对应的有向图\(G\)必须是强连通的,对于任意两个节点\(u,v \in V\),存在一个从\(u\)到\(v\)的路径;
  • 非周期性(aperiodic),即每个节点存在自回路。

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

\[
P=\left( (1-d)\frac{\mathrm{E}}{n} + dA^T\right)
\]

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

\[
PR_i = (1-d) + d\sum_{(j,i)\in E} \frac{PR_j}{O_j}
\]

3. 参考资料

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