每周学点大数据 | No.75 Spark 实践案例——PageRank

本文为灯塔大数据原创内容,欢迎个人转载至朋友圈,其他机构转载请在文章开头标注

编者按:灯塔大数据将每周持续推出《从零开始学大数据算法》的连载,本书为哈尔滨工业大学著名教授王宏志老师的扛鼎力作,以对话的形式深入浅出的从何为大数据说到大数据算法再到大数据技术的应用,带我们在大数据技术的海洋里徜徉~每周五定期更新

上期回顾&查看方式

在上一期,我们学习了Spark 的核心操作——Transformation 和 Action的相关内容。PS:了解了上期详细内容,请在自定义菜单栏中点击“灯塔数据”—“技术连载”进行查看;或者滑到文末【往期推荐】查看

No.75

Spark 实践案例——PageRank

Mr. 王 :了解了 Spark 的基础使用和两种基本操作之后,我们来尝试实现更加有实际应用意义的案例——PageRank。PageRank 我们前面提到过,是谷歌提出的著名的网页重要度评价算法。其实这个算法并不是很复杂,但我们要用并行平台 Spark 来实现有两个原因。

第一,PageRank 算法虽然简单,但是网络中的网页数目却非常巨大,而且网页页面也是非常复杂的,有着众多的链接,可以想象用来表示一个实际网络的连接关系的数据量将会非常大,这意味着处理它们也会变得有一定的难度。为了让其效率变得更高,我们就需要引入多台计算机来进行处理,也就是进行并行计算。

第二,PageRank 是一个不断研究多级链接关系去更新每个网页重要程度的算法,这意味着它会经历多轮迭代 ;而 Spark 的 in-memory 计算的思想恰恰非常适合迭代运算,所以我们选用 Spark。

小可 :那么具体该怎么做呢?

Mr. 王 :还是先回忆一下这个算法的输入输出格式。

小可 :PageRank 最重要的输入数据就是表示网页之间的链接关系,所以输入只要包括网页的链接关系就好了。用一个文本文件,将每一个链接表示为 :

链接源 链接目的

这样的形式。比如,如果 www.1.com 向 www.2.cn 有一个链接的话,我们就在文本文件中记录下:

www.1.com www.2.cm

嗯,那输出呢?

小可 :输出就是我们期待的结果,将各个网站的重要程度分数输出出来即可。

Mr. 王 :很好,我们先来看看这个程序。

这个程序并不长,我们对其做一个简单的分析。

在程序的一开始,首先定义了两个小函数,让一些重复使用的基本操作不必写到大的程序框架中。computeContribs 用于计算一个网页地址对其他网页地址的贡献 ;parseNeighbors 是一个格式转换函数,用于将我们写在文本文件里的整个地址对转换成连接的组合。

接下来程序中设计了一个防御性编程,执行pagerank 需要两个参数,其中一个是表示网页连接关系的文件 ;另一个是迭代次数。

小可 :为什么需要迭代次数呢?

Mr. 王 :在一些特殊的情况下,网页的连接关系构成了一个相互增益的环形,或者是形成了很长很深的链状,导致程序中的循环会运行很多次,或者由于不断的循环增益,很多网页的连接关系会不断地更新而根本不能停止,所以我们需要设置迭代次数的最大值,以避免程序无休止地运行。

下面这部分想必你已经非常熟悉了,将前面表示各个网页连接关系的文件作为 textFile 输入到 Spark 中去。

注意,这里出现了第一个 map 操作。

它将网页映射成其可以处理的网页地址对,以便进行进一步的处理。后面它使用了 Spark的 distinct() 函数进行数据去重,以防止重复的记录干扰到计算结果 ;groupByKey() 将具有相同键值的网页连接关系聚集起来,并且使用 cache() 将这些结果缓存起来。

接下来我们将管理好的数据记录映射成网页和 1.0 这种形式。后面的 1.0 是对每个网页重要程度的初始化,刚一开始时网页的重要程度都是 1。

现在开始进入 PageRank 的核心部分,整个程序会迭代执行,次数为我们设定的最大迭代次数。

在每一轮迭代的过程中,首先计算每个网页对其他网页的贡献,其中使用了前面定义过的函数进行贡献计算,并将其存储在 contribs 变量中。

然后根据每个网页在本轮迭代中获得的其他网页对自己的贡献程度,对每个网页更新其重要程度评分。

接下来程序会执行下一轮,直到不再发生变化,或者已经达到最大迭代次数为止。

最后程序会收集所有的网页获得的重要程度评分,并输出网页的重要程度评分。

我们用下面这个例子作为输入,来试着执行程序 :

小可 :这么长的程序,使用 Python Spark Shell 一句句地输入进去岂不是很麻烦吗?

Mr. 王 :嗯,这是我要说明的另一个问题,就是如何让 Spark 直接执行一个 Python 脚本。这个功能是非常有必要的,当要进行的操作相对复杂一些时,我们不可能让整个程序都一句句地直接输入到 pyspark 中,这样不仅很麻烦,而且也不利于代码的重复使用。Spark 也考虑到了这一点,提供了一个直接执行脚本的方法。

在这里我们就可以使用 :

屏幕上开始滚动着大量的执行过程信息。

小可 :执行结果出来了,果然非常方便啊!各个网页的重要程度都显示出来了 !

Mr. 王 :好了,到此为止,我们已经对 Spark 有了一个初步的认识,了解了 Spark 的两种基本操作,你可以很快地学会用它执行各种不同算法的方法了。接下来你可以去参考 Spark 的官方网站或者网络上的各种教程。Enjoy yourself with Spark !

下期精彩预告

经过学习,我们研究了Spark 实践案例——PageRank涉及到的一些具体问题。在下一期中,我们将进一步了解众包算法实践的相关内容。更多精彩内容,敬请关注灯塔大数据,每周五不见不散呦!

文章作者:王宏志

文章编辑:天天

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2018-02-23

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏FreeBuf

ModSecurity技巧:使用ssdeep检测Webshell

最新版本的ModSecurity增加了ssdeep检测webshell的接口,于是猛地回忆起搞客户端安全(游戏安全)的时候买过一本书《恶意软件分析诀窍与工具箱-...

4018
来自专栏从流域到海域

用JAVA的DEA算法衡量社交媒体页面的流行度

原文作者:Vasilis Vryniotis

2836
来自专栏linux驱动个人学习

GPU与CPU的区别

1683
来自专栏Flutter入门

偶遇FFmpeg(一) —— 初了解

FFmpeg的介绍网上还是很多的。官网的wiki上面也有很多内容。围绕目标,主要是有两套实现的思路。早期,其实是想通过自己编写C代码,来完成整个流程的。但是无奈...

2632
来自专栏SDNLAB

P4编程理论与实践——理论篇

由于对SDN充满着兴趣,在学习了一段时间OpenFlow之后,一次偶然的机会接触到了P4。P4可以实现很多新的Idea,但是无奈于国内的实践资料太少了(有些资料...

6779
来自专栏互联网技术栈

Redis 单key值过大 优化方式

由于redis是单线程运行的,如果一次操作的value很大会对整个redis的响应时间造成负面影响,所以,业务上能拆则拆,下面举几个典型的分拆方案。

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

组合测试从理论到实践——从吃货的角度实现组合测试用例的自动设计

从吃货的角度观察组合 作为一名合格的吃货,小编我每天为了吃的健康着实费了不少心思,每周我都会根据应季蔬果来定制一周的饮食,以下是我这周的定制计划: 蔬菜类: 豆...

3058
来自专栏吉浦迅科技

手把手在亚马逊EC2上搭建Keras GPU

由于需要使用越来越复杂的神经网络,我们还需要更好的硬件。但我们的电脑通常不能承受那么大的网络,不过你可以相对容易地在亚马逊上租用一个功能强大的计算机,比如E2服...

5076
来自专栏大数据和云计算技术

技术专栏丨2018 存储技术热点与趋势总结

类型:技术专栏 作者介绍 张凯(Kyle Zhang),SmartX 联合创始人 & CTO。毕业于清华大学计算机系,研究方向为分布式系统和体系结构。2013...

4668
来自专栏FreeBuf

看我如何基于Python;Facepp打造智能监控系统

由于种种原因,最近想亲自做一个基于python&facepp打造的智能监控系统。 0x00:萌芽 1:暑假在家很无聊 想出去玩,找不到人。玩个lol(已卸载),...

5705

扫码关注云+社区

领取腾讯云代金券