我试图用K means
语言在hadoop-1.0.1
中实现java
。我现在很沮丧。虽然我得到了github完整实现的k means
链接,但作为Hadoop
的新手,我想学习它而不复制其他代码。我有map
的reduce
和hadoop功能的基本知识。有人能为我提供实施k means
mapper
和reducer
类的想法。它需要迭代吗?
好吧,我试着告诉你我在MapReduce中实现k-means时的想法。此实现与Mahout的实现不同,主要是因为它显示了算法如何在分布式设置中工作(而不是用于实际生产用途)。另外我假设你真的知道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任务中为单个中心获取每个指定的向量。
降低水平
如上所述,你将在减少阶段有一个ClusterCenter
及其指定的VectorWritable
。这是正常k-means中通常的更新步骤。因此,您只需迭代所有向量,对它们求和并对它们求平均值。
现在你有了一个新的“均值”,你可以将它与之前分配的平均值进行比较。在这里,您可以测量两个中心之间的差异,告诉我们中心移动了多少。理想情况下,它不会移动和converged
。
Hadoop中的计数器用于跟踪这种收敛,这个名称有点误导,因为它实际上跟踪了多少中心没有收敛到最终点,但我希望你可以忍受它。
基本上你现在正在编写新的中心和所有向量的磁盘再次用于下一次迭代。此外,在清理步骤中,您将所有新聚集的中心写入映射步骤中使用的路径,因此新迭代具有新的向量。
现在回到工作阶段,MapReduce工作现在应该完成了。现在我们正在检查该工作的计数器,以获得尚未收敛的中心数量。在while循环中使用此计数器来确定整个算法是否可以结束。如果没有,请再次返回Map Level段,但使用上一个作业的输出作为输入。
实际上这就是整个VooDoo。
出于显而易见的原因,这不应该用于生产,因为它的性能非常糟糕。更好地使用更多调整版的Mahout。但出于教育目的,这个算法很好;)
如果您还有其他问题,请随时给我发邮件或评论。