每周学点大数据 | No.75 Spark 实践案例——PageRank
每周学点大数据 | 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涉及到的一些具体问题。在下一期中，我们将进一步了解众包算法实践的相关内容。更多精彩内容，敬请关注灯塔大数据，每周五不见不散呦！
文章作者：王宏志
文章编辑：天天