Tho*_*lut 11
好吧,我试着告诉你我在MapReduce中实现k-means时的想法.此实现从亨利马乌的不同,主要是因为它是呈现怎样的算法可以在分布式安装工作(而不是真正的生产使用).另外我假设你真的知道k-means是如何工作的.
话虽如此,我们必须将整个算法分为三个主要阶段:
工作水平
作业级别非常简单,它正在编写输入(Key =调用的类ClusterCenter和Value =调用的类VectorWritable),使用Hadoop作业处理迭代并读取整个作业的输出.
VectorWritable 是一个矢量的可序列化实现,在这种情况下来自我自己的数学库,但实际上只是一个简单的双数组.
的ClusterCenter主要是VectorWritable,但与该中心通常需要(平均例如)方便的功能.
在k-means中,你有一些k向量的种子集,它们是你的初始中心和一些你想要聚类的输入向量.这在MapReduce中完全相同,但我将它们写入两个不同的文件.第一个文件只包含向量和一些虚拟密钥中心,另一个文件包含真正的初始中心(即cen.seq).
将所有内容写入磁盘后,您就可以开始第一份工作了.这当然会首先发布一个Mapper下一个主题.
地图级别
在MapReduce中,知道即将发生的事情和发生的事情(就物体而言)总是很聪明.因此,从工作层面我们知道我们有ClusterCenter和VectorWritable作为输入,而ClusterCenter目前只是一个虚拟.我们肯定希望输出相同,因为地图阶段是普通k-means的着名分配步骤.
您正在读取在作业级别创建的真实中心文件到内存,以便在输入向量和中心之间进行比较.因此,您已定义此距离度量,在映射器中将其硬编码为ManhattanDistance.更具体一点,你可以在map阶段获得输入的一部分,然后你可以迭代每个输入"键值对"(它是由键和值组成的对或元组)与每个中心进行比较.在这里,您要跟踪哪个中心是最近的,然后通过将最近的ClusterCenter对象连同输入向量本身写入磁盘将其分配给中心.
然后输出:n向量及其指定的中心(作为键).Hadoop现在按键进行排序和分组,因此您可以在reduce任务中为单个中心获取每个指定的向量.
降低水平
如上所述,您将在reduce阶段拥有一个ClusterCenter及其指定VectorWritable的.这是正常k-means中通常的更新步骤.因此,您只需迭代所有向量,对它们求和并对它们求平均值.
现在你有了一个新的"均值",你可以将它与之前分配的平均值进行比较.在这里,您可以测量两个中心之间的差异,告诉我们中心移动了多少.理想情况下,它不会移动和converged.
Hadoop中的计数器用于跟踪这种收敛,这个名称有点误导,因为它实际上跟踪了多少中心没有收敛到最终点,但我希望你可以忍受它.
基本上你现在正在编写新的中心和所有向量的磁盘再次用于下一次迭代.此外,在清理步骤中,您将所有新聚集的中心写入映射步骤中使用的路径,因此新迭代具有新的向量.
现在回到工作阶段,MapReduce工作现在应该完成了.现在我们正在检查该工作的计数器,以获得尚未收敛的中心数量.在while循环中使用此计数器来确定整个算法是否可以结束.如果没有,请再次返回Map Level段,但使用上一个作业的输出作为输入.
实际上这就是整个VooDoo.
出于显而易见的原因,这不应该用于生产,因为它的性能非常糟糕.更好地使用更多调整版的Mahout.但出于教育目的,这个算法很好;)
如果您还有其他问题,请随时给我发邮件或评论.