机器学习之PageRank

image-20210621160912259

基础

问题

  • 如何给众多网页排名?

解决

  • 一个解决办法:
  • 当很多网页都链接到同一个网页时,那这个网页应该排名靠前
  • 链接这个网页的众多网页中,排名越靠前的网页,其重要性应该更高

PageRank

  • $PR_i$表示第$i$个网页的PageRank值,代表其网页排名依据
  • $V$是所有网页集合
  • $O_j$是第$j$个网页所存在的外链数,越多外链,它给$i$网页投票对应重要性越低

使用图构建PageRank

  • 网页对应图的节点node

  • 网页$i$的外链有网页$j$代表$(i,j)$,即图的有向边edge

  • 如下图所示:

    图片来源参考链接

  • 表示为$G(V,E)$,上图的邻接矩阵表示为:

  • 用矩阵表示式(1):$P=A^TP$

  • 其中$P=[PR_1, PR_2, …, PR_n]^T$

如何求解

  • 先给每个网页给定一个初始$PR$值,一般都是$1/n$

  • 然后使用$P=A^TP$进行迭代,直到$||P^k - P^{k-1}||< \epsilon$,这是一个马尔可夫收敛过程

  • 但是需要邻接矩阵$A$满足下面3个条件上式才有解:

    1. 转移概率矩阵(stochastic matrix):即每行至少有一个非零值
    2. 不可约性:矩阵A对应的有向图必须是强连通的,即任意两个节点,存在一条路径可达
    3. 非周期性:即存在一个最小正整数$k$,使得从某节点$i$出发又回到状态$i$的所有路径长度是$k$的整数倍,这就需要阻尼系数d
  • 一般情况下矩阵$A$不满足上述三个条件,故需要对求解式作平滑处理,最终等式如下:

  • 其中:$d \in [0,1],I\text{是单位阵}$

最终求解式

优缺点

  • 缺点:旧的页面的排名往往会比新页面高
    • 因为即使是质量很高的新页面也往往不会有很多外链,除非它是某个已经存在站点的子站点。这也是PageRank需要多项算法结合以保证其结果的准确性的原因

进阶

实践

疑难

参考


文章作者: Myhaa
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Myhaa !
评论
  目录