MapReduce框架与实例演示

Map函数以一组（key1 ， value1）值键对作为输入，生成一组（key2 ， value2）组成的列表作为输出。key2通常与key1不相等。

系统将自动地把输入的数据分配给多个mapper node，然后每个节点对它输入的（key1 ， value1）应用Map函数。接下去，系统自动地对输出的（key2 ， value2）按照key2排序，排序的过程也是在多个节点上并行进行的。得到的结果是一组（key2 ， listv）形式的组合，listv是一组与key2相关的值。系统会把排序后的输出结果［即（key2 ， listv）组合］分发给多个reducer node。然后每个节点会对每组（key2， listv）组合执行Reduce函数，得到的结果就是最终结果。

很重要的一点是，在Reduce的过程中，每一次对Reduce函数的调用都只能处理与key2相关的值。也就是说那些与多个key2相关的值不能在Reduce函数里同时处理。这意味着选择正确的key2值（中间结果的键值）非常重要。一旦决定了key2，编写Map和Reduce函数就很直观了。接下去我们用一些例子来说明Map和Reduce函数如何写。

例2.1：第一个例子是一个经典的词频统计问题（图2-2）。输入一组文档，每一篇文档都有很多单词，目标是计算在这些文档中每个词出现的次数（词频）。

图2-2　词频统计示例

我们首先要确定key2。在这个例子中，因为我们要统计的是每个词的频率，key2应该是每个单词w。 Map函数将每篇文档作为输入（key1是每篇文档的名字或ID， value1是文档的内容）。文档中的每个单词会被提取，输出一组（w，1）。 w就是key2 ，1表示单词w出现了一次。（如果w在文档中出现了很多次，则会产生多个输出。）

然后系统会对这些输出进行排序，并应用Reduce函数。Reduce函数接收（w，｛1，…，1｝）作为输入，值是一组“1 ”。函数简单地将这些“ 1”相加，然后输出w和它的词频。

接下去我们再展示一些Map和Reduce函数的例子。

例2.2：假设我们有所有课程所有学生的分数，形式如（学生ID，课程ID，课时，0～4分的成绩）。我们想用MapReduce来计算每个学生的GPA 。

首先确定key2。在这个例子中我们想计算每个学生的GPA，所以学生ID应该作为key2(www.xing528.com)

Map函数输出（学生ID，学时||成绩），||表示拼接，在MapReduce中，值和键都可以通过拼接多个字段形成。然后系统对这些输出进行排序。

Reduce函数接收学生ID和一组值包括学时| |成绩。函数会计算两个数值和，第一个是总学时，第二个是学时乘以成绩的总和。然后我们用后者除以前者得到GPA，并输出（学生ID， GPA ）。

例2.3：假设我们有一组（顾客ID，消费额，消费时间）的销售记录，想要计算每个顾客的月度消费额。

同样我们需要决定key2。不能只选择顾客ID作为键，因为这样我们只能得到每个顾客的消费总额而不是月度消费额，因此key2应该是顾客ID与月份的拼接。

Map函数将月份从消费时间中抽取出来，并输出（顾客ID||月份，消费额），系统对此排序。

Reduce函数将（顾客ID||月份，一系列消费额）作为输入，计算消费额的总和然后输出顾客ID，月份，还有当月的总消费额。

例2.4：最后一个例子展示如何用MapReduce来实现一种常用的聚类算法—k—-means算法^[1]。k-means算法需要进行多轮迭代。图2-3展示了k-means的一次迭代过程。每一轮迭代，输入一组点集和k个种子（或是前一轮计算得到的簇中心）。算法分为两步：将每个点分配给最近的种子（簇中心）；通过计算每一个簇所有点的平均值重新计算簇中心。

图2-3　k-means聚类算法的一次迭代过程

当使用MapReduce实现k-means聚类时，需要多次MapReduce的过程，每一次MapReduce对应k-means中的一次迭代。每一轮过程，Map函数实现算法的第一步（图2-3的1～3行）， Reduce函数实现算法的第二步（4～6行）。

更详细地说，key2应该是簇ID（即Ci）。 Map函数将点xi和当前簇中心集作为输入，计算该点到所有簇中心的距离并选择最近的那一个，并输出，其中是最近的簇的ID，xi是该数据点。Hadoop会对所有（簇ID，数据点）根据簇ID进行排序。Reduce函数将（簇ID，一系列属于该簇的点）作为输入，计算所有该簇内点的平均值作为新的簇中心。新的簇中心会被存下来，在下一轮迭代中作为输入（和每个数据点一起）。