大数据 | 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 条评论
登录 后参与评论

相关文章

来自专栏数据科学与人工智能

【机器学习】Python语言下的机器学习库

Python是最好的编程语言之一,在科学计算中用途广泛:计算机视觉、人工智能、数学、天文等。它同样适用于机器学习也是意料之中的事。 当然,它也有些缺点;其中一个...

23210
来自专栏机器人网

Python最有用的机器学习工具和库

Python是最好的编程语言之一,在科学计算中用途广泛:计算机视觉、人工智能、数学、天文等。它同样适用于机器学习也是意料之中的事。

955
来自专栏AI传送门

斯坦福大学《机器学习》课程-中文版内容(3.6)

1013
来自专栏程序人生 阅读快乐

《并行程序设计 (第二版)》

本书系统介绍并行程序设计原理及应用。除介绍常用的一些算法范例,包括分治、流水、同步计算、主从及工作池,还介绍了一些常用的经典数值和非数值算法,如排序、矩阵相乘、...

482
来自专栏机器学习实践二三事

Caffe中均值文件的问题

关于均值文件 (1) 在Caffe中作classification时经常需要使用均值文件,但是caffe自己提供的脚本只能将图像数据转换为 binarypr...

1959
来自专栏机器学习算法与Python学习

博客 | 对学习/理解 Word2Vec 有帮助的材料

之前面试被面到了,加上一直不是很理解词嵌入的工作方式,所以这段时间找了不少相关的资料想把这玩意儿搞明白。理解还是有限,就不自不量力自己写一篇了(就算写也是把已有...

872
来自专栏新工科课程建设探讨——以能源与动力工程专业为例

5.2 二维导热算例

本节算例使用actionScript编写,与javascript语法相近。主要阅读理解其算法,可以自己试着开发二维程序。

530
来自专栏企鹅号快讯

能在不同的深度学习框架之间转换模型?微软的MMdnn做到了

Microsoft/MMdnn:深度学习框架随心切换 学习深度学习的各位同学都希望自己的模型能在不同的深度学习框架之间随意转换,比如,斯坦福大学CVGL实验室的...

3935
来自专栏腾讯移动品质中心TMQ的专栏

启动耗时可以这样测~

启动耗时作为App一项核心性能指标,腾讯地图现在是基本上每个版本都会进行数据的收集。纵向的对比(与自己)之前我们都依赖于开发埋点,横向的对比(与竞品)就是人工拿...

3687
来自专栏石瞳禅的互联网实验室

【TensorFlow实战——笔记】第2章:TensorFlow和其他深度学习框架的对比

可以看到各大主流框架基本都支持Python,目前Python在科学计算和数据挖掘领域可以说是独领风骚。虽然有来自R、Julia等语言的竞争压力,但是Python...

791

扫码关注云+社区