0

我在运行 Mahout K-means 时遇到了一个奇怪的情况：使用预先选择的一组初始质心，我在 lucene.vector 生成的 SequenceFile 上运行 K-means。运行是为了测试目的，所以文件很小（大约 10MB~10000 个向量）。

当使用单个映射器执行 K-means 时（考虑到我的集群中的 Hadoop 拆分大小的默认值是 128MB），它会在 2 次迭代中达到给定的集群结果（案例 A）。但是，我想通过触发更多映射任务（Hadoop 集群总共有 6 个节点）来测试算法的执行速度是否会有任何改进/恶化。因此，我将 -Dmapred.max.split.size 参数设置为 5242880 字节，以使 mahout 触发 2 个映射任务（案例 B）。我确实成功地启动了两个映射器，但奇怪的是，这项工作在 5 次迭代而不是 2 次后完成，而且即使在第一次将点分配给集群时，映射器与单映射执行相比做出了不同的选择。

现有的 K-means Mahout 实现是否可以证明这种行为是合理的？

4

1 回答 1

1

通过快速查看源代码，我发现 Mahout k-means 实现存在两个问题。

首先，对于大型数据集，保持 S0、S1、S2 统计数据的方式可能在数值上不稳定。哦，因为 k-means 实际上甚至不使用 S2，所以它也没有必要慢。我敢打赌，一个好的实现至少可以将这个版本的 k-means 击败 2-5 倍。

对于拆分到多台机器上的小型数据集，它们计算平均值的方式似乎存在错误。哎哟。如果 reducer 应用于多个输入，这将放大，特别是当分区很小时。更详细地说，集群均值显然是用先前的均值而不是 0 向量初始化的。现在，如果您减少它的“t”个副本，则结果向量将偏离先前平均值的“t”倍。

的初始化AbstractCluster：

setS1(center.like());

均值更新：

getS1().assign(x, Functions.PLUS);

合并一个集群的多个副本：

setS1(getS1().plus(cl.getS1()));

最终确定新中心：

setCenter(getS1().divide(getS0()));

因此，使用这种方法，中心将从正确值偏移之前的中心时间t / n，其中t是分割n数和对象数。

为了解决数值不稳定性（每当数据集不以 0 向量为中心时就会出现这种情况），我建议将 S1 统计量替换为真实均值，而不是 S0*均值。S1 和 S2 都可以使用增量均值公式以很小的成本进行增量更新，该公式在 MacQueen 的原始“k-means”出版物中使用了 AFAICT（实际上是在线 kmeans，而这是 Lloyd 样式的批量迭代）。好吧，对于增量 k 均值，无论如何您显然都需要可更新的均值向量……我相信 Knuth 在他的基本书籍中也讨论了该公式。我很惊讶 Mahout 似乎没有使用它。它相当便宜（只是多了几条 CPU 指令，没有额外的数据，所以这一切都发生在 CPU 缓存行中）并且在处理大型数据集时为您提供额外的精度。

于 2012-09-28T13:27:24.213 回答