8

我正在尝试K means用语言实现hadoop-1.0.1。java我现在很沮丧。虽然我得到了完整实现的githubk means链接，但是作为一个新手Hadoop，我想学习它而不复制别人的代码。我有hadoopmap中可用的基本知识和reduce功能。有人可以为我提供实施和上课的想法。它需要迭代吗？k means mapperreducer

4

1 回答 1

11

好的，我试着告诉你在 MapReduce 中实现 k-means 时我的想法。这个实现与 Mahout 的不同，主要是因为它展示了算法如何在分布式设置中工作（而不是用于实际生产使用）。另外我假设你真的知道 k-means 是如何工作的。

话虽如此，我们必须将整个算法分为三个主要阶段：

  1. 职业等级
  2. 地图级别
  3. 降低级别

工作级别

作业级别相当简单，它正在编写输入（Key = 调用的类ClusterCenter，Value = 调用的类VectorWritable），处理 Hadoop 作业的迭代并读取整个作业的输出。

VectorWritable是向量的可序列化实现，在这种情况下来自我自己的数学库，但实际上只是一个简单的双精度数组。

主要ClusterCenter是 a VectorWritable，但具有中心通常需要的便利功能（例如平均）。

在 k-means 中，您有一些作为初始中心的 k 向量种子集和一些您想要聚类的输入向量。这在 MapReduce 中完全相同，但我将它们写入两个不同的文件。第一个文件只包含向量和一些虚拟键中心，另一个文件包含真正的初始中心（即cen.seq）。

将所有内容写入磁盘后，您就可以开始您的第一份工作了。这当然会首先启动一个Mapper这是下一个主题。

地图级别

在 MapReduce 中，知道什么进来什么出去（就对象而言）总是很聪明的。所以从工作层面我们知道我们有ClusterCenter和VectorWritable作为输入，而ClusterCenter目前只是一个假人。当然，我们希望得到与输出相同的结果，因为 map 阶段是来自普通 k-means 的著名分配步骤。

您正在将您在作业级别创建的真实中心文件读取到内存中，以便在输入向量和中心之间进行比较。因此，您定义了这个距离度量，在映射器中它被硬编码为ManhattanDistance. 更具体地说，您在 map 阶段获得部分输入，然后与每个中心进行比较，然后迭代每个输入“键值对”（它是由键和值组成的对或元组） . ClusterCenter在这里，您正在跟踪哪个中心是最近的，然后通过将最近的对象连同输入向量本身写入磁盘来将其分配给中心。

然后，您的输出是：n 向量及其分配的中心（作为键）。Hadoop 现在按您的键排序和分组，因此您可以在 reduce 任务中为单个中心获得每个分配的向量。

减少级别

如上所述，您将在 reduce 阶段拥有 aClusterCenter及其分配VectorWritable的 's。这是您在普通 k-means 中的常用更新步骤。因此，您只需遍历所有向量，将它们相加并取平均值。

现在您有了一个新的“平均值”，您可以将其与之前分配的平均值进行比较。在这里，您可以测量两个中心之间的差异，这告诉我们中心移动了多少。理想情况下，它不会移动并且converged.

Hadoop 中的计数器用于跟踪这种收敛，名称有点误导，因为它实际上跟踪有多少中心没有收敛到最终点，但我希望你能接受它。

基本上，您现在正在将新中心和所有向量再次写入磁盘以进行下一次迭代。此外，在清理步骤中，您将所有新收集的中心写入地图步骤中使用的路径，因此新迭代具有新向量。

现在回到作业阶段，现在应该完成 MapReduce 作业。现在我们正在检查该作业的计数器，以获取尚未收敛的中心的数量。此计数器用于 while 循环以确定整个算法是否可以结束。如果不是，请再次返回Map Level段落，但使用上一个作业的输出作为输入。

实际上，这就是整个 VooDoo。

出于显而易见的原因，这不应该在生产中使用，因为它的性能很糟糕。最好使用更优化的 Mahout 版本。但出于教育目的，这个算法很好；）

如果您还有任何问题，请随时给我写邮件或发表评论。

于 2012-05-18T18:38:52.193 回答