本篇讲述入门的MapReduce算法，表述不加斟酌，可能非常抽象且思维流，有疑问的朋友请随时提问。
注意，本文提到的Mapper和map是不一样的，Reducer同理，请读者务必加以区分。Mapper是一个类，它包含一个方法叫map，故一个Mapper实例可以多次调用map方法。
1. 排序算法
弄懂排序算法算是搞清MapReduce的第一步。最简单的，为一堆数字排序。map和reduce的配置也是最简单的，默认即可。
为了搞明白为什么这样就能排序，我们得知道，MR框架中sort发生在Reducer上，它在执行reduce前会对到来的数据进行归并排序。要是能让Mapper把所有数据都发给同一个Reducer，那这一步就把所有数据给排序了。再复杂点的，比如对学生成绩排序。Mapper处理输入数据，然后将成绩作为key输出，其它内容都塞到value里。Reducer会自动对这些key排序，reduce函数中重新将数据组合起来并以合适形式输出即可。
最关键的在于如何把所有数据塞到一个Reducer里——或者，塞到有限的几个Reducer里，比如0到99划成一组，100到199划成一组，以此类推。这就用到了TotalOrderPartitioner，它会执行采样，大概了解数据的分布情况，然后从采样数据内定出划分点，这样就能使划分的每一组内有差不多数量的数据。这些不同的分组被发送给不同的Reducer，它们对每一分组内的数据排序，然后写入到各自的输出文件里。
2. 单词同现矩阵算法
统计任两个单词在一定范围内同现的次数。Mapper的输入就是一个窗口内的所有单词，然后其中的单词两两组合作为key输出即可。Reducer的设计自然不需多言。
还可以做一点优化。两两组合输出中间结果比较浪费带宽，不如把它们部分组合一下，就像这样：
3. 可扩展文档倒排索引算法
根据词语，定位它出现在哪个文档中。Mapper的输入是各个词语以及它所在的文档，输出……当然也是词语和它所在的文档。Reducer将它们整合在一起即可。不过在Mapper中，词语所在的文档是通过一个context变量来获取的，这点只要做过实验就知道。实验还是很有用的。
要是希望同时统计单词位置、文档等多种属性，那有必要借助一些map和reduce之外的设施。例如，LineRecordReader可以向Mapper传入行首单词的位置。Mapper将读取到的行断开，对产生的每个词生成一个中间结果，其中每个词所包含的属性都作为value输出出来。
再整个刺激的，将某个单词所有的occurence按照文档名排序。排序这事说着简单，但量一大就不方便直接调用函数进行内存中排序，所以最好利用MapReduce自带的排序机制。这里涉及到一个小trick叫键值转换，排序的关键不就在于key吗，那好，我们要对文档名排序，就直接把文档名塞到key里，并确保把同一个单词的所有中间结果发射到同一个Reducer中。决定发射到哪个Reducer，这件事是Partitioner做的，所以实现上述的目标，需要实现一个自定义的Partitioner。
reduce函数每次只处理一个中间结果，但是不同的中间结果是按照键的顺序排列的，例如第一次对reducer的调用，传入的参数可能是<<word1, 1.txt>, [p1, p2, ...]>，第二次可能是<<word1, 2.txt>, [p1, p2, ...]>，第三次可能是<<word2, 1.txt>, [p1, p2, ...]>，等等。这带来了非常好的性质：同一个word的各个中间结果是连续输入到reduce函数中的，因此我们只需在Reducer类中设定一些用于缓存这些中间结果的数据结构，就可以轻易实现该word各个属性的合并。
4. 专利文献数据分析
现给定专利引用关系，要求统计各专利被引情况。这不就是倒排索引么？Mapper将被引的专利编号作为key输出即可，至于要统计被引次数还是引用者列表，由value的内容决定。
统计了被引次数之后还可以统计被引次数直方图，这和WordCount是一样的，只不过这里是统计被引次数的出现次数罢了，被引次数前面出现的专利名称会被忽略掉。
专利文献的更多问题懒得描述啦，换汤不换药，琢磨透可扩展带属性文档倒排索引就可以应付所有这些简单算法。
5. 多数据源的连接
这玩意很烦，要连接数据源直接用Hive多好？但是本着要学会造轮子的态度，还是认真学习一下。课本上讲的是老版本MapReduce的DataJoin类，这是早就弃用的老版本API，扩展性不大行。不过我们在这说说思路，辅以真实代码，应对考试完全不慌。
首先是Mapper类，要实现3个方法。generateInputTag用于生成数据源标签。设想要连接两个不同的文件，我们要确保Reducer处理的时候知道这些数据分别来自哪些数据源，所以要这样标记一下，例如将包含该数据源的文件名作为tag。generateGroupKey和generateTaggedMapOutput分别用于生成Mapper中间结果的键和值。
看看MapReduce的框架代码，把这三个函数串起来：
从框架代码我们可以知道，输入到Mapper的key不被使用，value是数据表的一条记录，也许是用LineRecordInputFormat完成的。
了解了Mapper的输入输出，接下来看看Reducer的输出。拥有同样GroupKey的数据被发射到同一个Reducer。reduce函数则在一系列处理后最终调用到用户自定义的combine函数，完成连接处理。这是combine的原型：
tags表示数据源的来源标签，和上面generateInputTag说的是一回事。values则顺次存放了来自各数据源的数据。用户可在combine中自行完成连接，并使用context.write完成结果输出。
6. PageRank算法
6.1. 算法分析
PR的基本思想：被多个优质网页链接的网页，多半也是优质网页。我们用指向来表示链接关系，这样各网页就形成了有向图。如何评价一个网页有多优质？可以用这个简单的公式：
说形象点，就是一群人互相投票，nb的人有更多票。每个人都有一些自己认可的人，并把自己的票平分，投给这些人。投票结束后，每个人都算算自己得了多少票，得票越多越nb，然后开始下一轮的投票。这一过程会渐渐收敛，也就可以选出真正nb的人。
然而，每个人投票的行为在每一轮都是相同的，即把自己的选票均分给自己认可的人，这一认可和均分的关系不随票数的改变而改变。用矩阵相乘可以简洁明了地反映投票的过程：
这个问题实际上变成了求解特征值为1的特征向量的问题。不巧的是，H每列元素和为1，所以必有这样的特征向量，证明方法留给读者自行思考（x
但是这种简单的模型存在一些问题，例如：如果有网页不引用其他网页，就相当于拿了票不给别人，但总票数有限，大家迟早都会把票给他。或者有人只给别人投票，自己收不到票，那么自己总有一天要没票了，比较可怜。
加上随机浏览模型后，这一算法鲁棒性就更强。它的意思是，用户不一定严格按照一个网页给出的链接进行浏览，而是有一定概率随机跳到其它页面，像极了你在Google上debug时突然跳到B站的样子。所以嘛，H稍微变了变，按阻尼因子进行加权，比如H’=0.85H+0.15*(1/N)，N是网站总数。接下来求解H’的特征值即可。H’当然还是满足每列元素和为1的性质。
6.2. MapReduce实现思路
上来就什么GraphBuilder、PageRanker实在是突兀，我们还是谈谈到底要怎么将算法MapReduce化。整个算法就是投票、归票、投票、归票，直至收敛。投票和归票可以自然地映射到map和reduce过程。
对于投票，即Mapper，输入一个网站和它所有指向的网站，以及它拥有的票数，我们就可以计算出每个被投票者得到的票数，并将被投票者的URL作为中间结果的键，方便Reducer进行归票。
对于归票，从value列表计算获得的总票数是很简单的。但是多少有点美中不足，因为我们不知道被投票者给哪些网页投了票，这样reduce出来的东西和map进去的东西就不是一回事了，迭代不起来。为此，每次调用map过程都向Reducer发送一些数据，包括该网页所链接的所有网页。这样Reducer就有了足够的信息，生成和迭代开始前格式完全相同的数据。
有了这些思路，还愁考试写不出伪代码么？
7. K-Means聚类算法
聚类的思想是，如果一个点离某个簇的中心更近，那么这个点估计大概率属于该簇。反过来，一个簇中所有点的位置决定了簇中心的位置。这样，迭代就出现了。
同一轮迭代，不同的点计算自己属于哪个簇是不相互干扰的，所以可以并行化。为此，将点的位置输入到Mapper，后者计算出该点所属的簇，并以簇编号为key，点坐标为value，发射中间结果。
Reducer接收到这些点之后，可以更新簇中心的位置，并把更新后的中心写入文件。
这里有一个trick，为什么不将簇中心数据传入map函数，Mapper如何知道各簇中心的位置？这是因为，一轮迭代过程中簇中心是不变的，而这种大量重复且不变的数据，适合用CacheFile进行存储。main函数中会将簇中心数据文件设定为CacheFile，Mapper可在setup函数中读取簇中心数据并保存到Mapper类的数据结构中，以供后续map函数直接使用。
8. KNN分类算法
分类算法有样本输入，我们要做的事情就是用这些样本训练一个模型出来。KNN（K-Nearest Neighbor）相当好理解：如果你不知道你要做什么，就看看身边离你最近的K个人在做什么，心里估计就会有个大概。
算法哪些地方可以并行化？不同的“你”之间不会互相影响，所以可以并行计算、判断。
因此，算法的思路就是，先将训练集读入CacheFile，然后将测试样本输入到map，map求解出离该样本最近的k个训练样本，最后由这k个训练样本投票表决测试样本的标签。求k个最近样本用最大堆很容易实现，至于投票是用平权还是加权都不过是对代码稍作更改罢了。
你问我Reducer做什么？Mapper都把标签算出来了，Reducer还要做什么？
9. 朴素贝叶斯分类算法
刚才的KNN听起来似乎挺草率，好像根本没做“训练”这一步。朴素贝叶斯做了一些训练，大概思路是：如果你不知道你要做什么，就看看以你目前的状态和条件，结合身边人的例子，估计要做什么事情的概率最大，这就是你要做的事情。
这个比刚才KNN抽象了一些，什么叫“结合身边人的例子”？什么叫“目前的状态和条件”？为此，我们要引入数学手段来阐明一切。原谅我没有使用LaTeX，因为这里公式十分简单。对于测试样本X，我们希望知道它属于类Yi的概率有多大，即求解P(Yi|X)，根据Bayes定理，就是求解P(X|Yi)*P(Yi)/P(X)。P(X)是平凡的，所以我们要做的是找出i，使得P(X|Yi)*P(Yi)最大。
P(Yi)好办，它的取值是Yi的频度除以总样本数；P(X|Yi)只在一种情况下好办，就是X的各个属性互不相关，这样它就可以表示为P(x1|Yi)*P(x2|Yi)*…*P(xn|Yi)。不考虑各属性的相关性，这就是该算法被称为“朴素”贝叶斯的原因！每一个P(xj|Yi)都很容易计算，为xjYi出现的频度除以Yi样本的频度。
到此我们发现，朴素贝叶斯的训练过程就是统计频度！这不就又回到WordCount了吗？高端的算法，往往只需要朴实无华的求解方式。我们可以判断测试数据是否包含特定的“word”，是就emit出去，这里的word说的就是标签，或者标签+属性名+属性值。为测试样本打标签的时候，只要在map中读取CacheFile中的频度数据，就可以计算出概率，并预测测试样本的标签。
10. SVM短文本多分类算法
把多分类问题拆成多个二分类问题。设有n个类别，那么Mapper为每个训练样本生成n个二分类标记（true或false），然后n个Reducer分别执行SVM二分类训练。处理测试数据亦是同理，每个SVM会给出相应类别的评分，选出评分最高者作为其标签。
11. 频繁项集挖掘算法
频繁项集问题可以描述为：现给定大量transaction，它们中的每个都保存着一个由若干元素组成的集合。如何找出一些子集，使得该子集在所有transaction中频繁出现？
11.1. Apriori算法
该算法的思想是：频繁项集的子集一定是频繁项集。具体而言，我们将大小为k的频繁项集称为k-频繁项集，那么算法会先找出1-频繁项集，然后找出2-频繁项集，以此类推。
11.2. SON算法
该算法用于大量数据的频繁项挖掘，思想是：全局频繁项集一定是局部频繁项集。为此，可以先将数据划分成若干部分，对各部分应用Apriori算法，然后对各局部频繁项集作统计，得到候选全局频繁项集。
在生成这些项集之后，可进一步进行验证并选出真正的频繁项集。具体来说，统计每一个候选项集的出现次数，然后筛掉不合格的项集。
11.3. PSON算法
SON算法其实已经有了可以并行化的迹象，就是多个Mapper同时求解各分块的局部频繁项集，最终由Reducer进行统计并产生候选全局频繁项集。
候选筛选时，Mapper将候选频繁项集作为CacheFile读入，然后以类似WordCount的方式给Reducer发送中间结果，Reducer会统计各候选项集的出现次数并执行筛选。
