底层、推理、联想思维之应用(使用map reduce实现大规模kmeans聚类)

之前小组的同事说了一道题目怎么高效的使用map-reduce完成kmeans聚类。我想了一些时间想出了最高效最简洁的完成方法。本篇文章我想把我的思路阐述清楚更为关键的是我想说清楚我是怎么运用底层思维、推理思维及联想思维想到最终方案的。第一步因为涉及到kmeans聚类我首先要做的是复习熟悉kmeans聚类算法。在这个过程中我了解到kmeans算法的迭代过程是这样的。a.先随机选取(或者更有策略地选取因为不是本篇文章的重点所以我们就采用随机选取吧)K个质心。b.对每条数据分别计算其距离K个质心的距离然后把距离最近的那个质心当做它的类别。c.因为b使得每条数据产出了它的类别在这里将每个类别的数据聚合在一起计算新的质心。d.不断迭代b和c直到终止条件。在这里我们使用的终止条件是所有数据距离他们所属质心的距离加和改变幅度在一个比较小的数值。第二步了解map reduce的各个细节。比如map task内部的细节、reduce task的细节shuffle阶段干了什么combiner阶段干了什么多路输出是什么。第三步了解了kmeans聚类算法和map reduce的各个细节。我们现在构思怎么使用我们手里拿到的砖块实现一栋楼房。首先对于第一步中的a和b我们可以想到在map task中加载质心文件然后对map task中的每个数据计算其距离K个质心的距离输出其类别是可以做到的。其次我们考虑如何实现c(注意为了不让大脑思考的东西一下子过于复杂我对算法的实现进行了细分也就是说在思考方案的时候我们每次只在大脑里考虑实现方案的一部分而不是想着一下子把整个算法完美无缺的实现出来一开始太过追求完美会让你的大脑沉迷于各种琐碎的细节中而失去了宏观的把控和思考你应该先从宏观进行把控然后再完善细节。我管这个过程叫做宏观思考任务拆解和细分、不完美后续迭代优化)。在首先中我们需要输出每个数据所对应的类别那么一下子可以想到的是把类别做为key然后同类别的数据会进入到同一个reduce里面然后在reduce里面计算每个key(类别)的新质心。这个思路是最直观也是最容易想到的。但是其有一个很坏的缺点。就是当你的k很小的时候比如3这个时候大量的数据会shuffle到3个reduce里面。你的reduce很可能会爆炸(k很小导致实际被使用的reduce也很少即便你的reduce num设置得很大)。那么还有没有更好的解决方案可以避免大量的数据shuffle到reduce中去呢注意这些数据的格式是数据类别_数据这样的格式的。这就涉及到对map reduce各个模块和细节的熟悉程度了。然后我们就赶快想啊我们把上述格式的数据shuffle到reduce中是为了计算新的质心而我们还不想让这些数据进行shuffle那么在map端可否进行新质心的计算呢或者是完成一部分的新质心计算工作呢我们联想到combiner正是在map端的reduce我们想到在map端combiner出现在两个地方一个地方是sortcombiner以让内存缓冲区中的数据先排序然后combiner以减小写入磁盘数据的大小。另外一个地方是merge过程在这个过程中多个spill文件会归并成一个大文件combiner会缩小数据规模以减小shuffle数据的大小。而在combiner过程中我们可以计算同类别数据他们的加和(这里我们把每条数据的形式当做一个向量这里的加和指的是向量求和)只要我们把有多少同类别数据进行加和也保留下来我们就能得到每个map task同类别数据他们的加和以及有多少同类别数据进行加和那么我们的方案就来了。在map端对同类别数据进行combine输出 类别 \t 同类别数据加和 \t 同类别数据的数目。然后这部分数据是很小的完全可以shuffle到reduce中去而每个数据所属类别这样的信息我们也要输出。对于我们来说要计算新质心前面的信息已经足够了后面的信息完全没有必要shuffle到reduce中去。所以我们的技术方案是每个数据及其类别信息就地输出(map端输出)而类别 \t 同类别数据加和 \t 同类别数据的数目这样的信息shuffle到reduce中以计算新的质心。然而然而map reduce框架并不支持这样的玩法(map的输出有一部分输出在map端就地输出有一部分shuffle到reduce)。那么退而求其次考虑到我们在这里需要reduce处理的数据已经很小了那么reduce完成的功能我们完全可以使用hadoop fs -get 把质心信息弄到本地再在本地进行计算。所以最终的方案是不使用reduce只使用map。在map端使用多路输出一路输出是每个map task输出的质心信息一路输出是每条数据所属的类别信息。第四步现在我们考虑终止条件怎么计算。实际上当完成第三步以后这个计算的构思就变得简单了。我们可以在第二步的时候计算每条数据距离它所属质心的距离然后在第三步的combiner中合并同类别数据距离质心之和。在map端同样输出到另外一路在之后我们只需要使用hadoop fs -get然后离线就可以计算得到终止条件所要求的那个数值。