大数据 | Spark中实现基础的PageRank

吴军博士在《数学之美》中深入浅出地介绍了由Google的佩奇与布林提出的PageRank算法,这是一种民主表决式网页排名技术。书中提到PageRank的核心思想为:

在互联网上,如果一个网页被很多其他网页所链接,说明它受到普遍的承认和信赖,那么它的排名就高。

同时,该算法还要对来自不同网页的链接区别对待,排名越高的网页,则其权重会更高,即所谓网站贡献的链接权更大。

例如网页Y被X1,X2,X3,X4四个网页所链接,且这四个网页的权重分别为0.001,0.01,0.02,0.04,则网页Y的Rank值=0.01+0.02+0.03+0.04=0.071。但问题是,如何获得X1,X2,X3,X4这些网页的权重呢?答案是权重等于这些网页自身的Rank。然而,这些网页的Rank又是通过链接它的网页的权重计算而来,于是就陷入了“鸡与蛋”的怪圈。解决办法是为所有网页设定一个相同的Rank初始值,然后利用迭代的方式来逐步求解。

在《数学之美》第10章的延伸阅读中,有更详细的算法计算,有兴趣的同学可以自行翻阅。下面是PageRank的简单执行步骤:

  • 首先假定所有网页的初始Rank值为1/N,N为所有网页的数量。
  • 开始迭代。每次迭代,则页面p会将r/n的值发送给所有链接了p页面的邻居页面。其中,r为当前页面的rank值,n为链接了当前页面的邻居页面数。该值实则就是当前页面p这次迭代的贡献者(contribution)。
  • 每次迭代结束时,都对最终获得的contributions进行求和。假设每个contribution为c(i),则可以通过公式α/N + (1-α)∑c(i)获得每个页面的rank值。其中,α是一个常数值,可以认为是一个调优参数(tuning parameter),N为所有页面的数量。

究竟应该迭代多少次呢?由于PageRank实则是线性代数中的矩阵计算,佩奇和拉里已经证明了这个算法是收敛的。当两次迭代获得结果差异非常小,接近于0时,就可以停止迭代计算。《数学之美》中提到:“一般来讲,只要10次左右的迭代基本上就收敛了。”

原文发布于微信公众号 - 逸言(YiYan_OneWord)

原文发表时间:2015-02-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

资源 | 这是你要的Keras官方中文版(附文档链接)

Keras 是一个用 Python 编写的高级神经网络 API,它能够以 TensorFlow, CNTK, 或者 Theano 作为后端运行。Keras 的作...

3056
来自专栏fangyangcoder

MaskRCNN-Keypoints

这个月先写一篇吧,后面要复习数学考试了,可能到时候就忘了。今天写一个比较有意思的东西,关于人体的分割与姿态估计。如下图所示:

2403
来自专栏杨熹的专栏

什么是 Q-learning

在这个游戏中,agent 从一个给定的位置开始,即起始状态。 在不穿越迷宫墙壁的前提下,在每个状态时,都可以选择上下左右四个方向走一步,或者原地不动, 上下...

1812
来自专栏应兆康的专栏

19. 总结:基本错误分析

1301
来自专栏腾讯大讲堂的专栏

微信亿级用户异常检测框架的设计与实践

月活用户越高的互联网产品,被黑产盯上的可能性就越大。本文将带你一窥究竟,微信是怎么做异常检测框架的?

1.5K8
来自专栏AI科技评论

开发 | 低配硬件就不能运行深度神经网络了?手把手教你克服“杀牛用鸡刀”难题

如果对深度学习有所了解的小伙伴们想必都知道,深度学习需要使用强大的服务器、加速嵌入式平台(如NVIDIA的Jetson)来运行深度学习算法,然而这也同样意味着不...

3805
来自专栏量子位

那个爆火的“梦中修炼”AI,你也能用Keras搭一个了

上月,量子位报道了Google Brain的David Ha和“LSTM之父”Jürgen Schmidhuber的论文World Models。论文中习得周星...

1073
来自专栏应兆康的专栏

19. 总结:基本错误分析

• 不要一开始就尝试设计和构建完美的系统,而是尽可能快的建立和训练一个基础的系统(几天之内),然后使用错误分析。帮助你找到最优的方向,并迭代改进你的算法。

3229
来自专栏AI研习社

实例讲解:时间序列预测究竟需要多少历史数据?

编者按:本文源自美国机器学习专家 Jason Brownlee 的博客,AI 研习社编译。 时间序列预测,究竟需要多少历史数据? 显然,这个问题并没有一个固定的...

50811
来自专栏量化投资与机器学习

强化学习(Reinforcement Learning)应用于量化投资系列专题(二)——设计一个外汇交易系统基于自适应强化学习

往期文章(点击标题查看) 强化学习(Reinforcement Learning)系列(一) 今天带来机器学习应用于量化投资系列之 强化学习(Reinforce...

29310

扫码关注云+社区