hadoop - OpenIMAJ 库中的 K-Means 聚类

Question

我在机器学习和聚类分析方面不是很有经验，但我有以下问题:

我有大约 100kk-1000kk 条数据，我无法一次将它们全部加载到内存中，我需要将其分成多个类(例如 1-10k 甚至 100k 类)以供进一步分析。为此，我选择了在 OpenIMAJ 库(FloatKMeans 类)中实现的 K-Means 算法。 我了解到 K-Means 算法可以分为 2 个阶段:

1. 学习阶段 - 我传递所有我必须创建/填充类(class)的数据
2. 分配阶段 - 在这里我可以询问集群给定数据属于哪个类

我计划使用 Hadoop 减少阶段构建集群模型，我将一个接一个地接收数据片段(这就是为什么我不能一次将所有数据传递给算法的原因)

我的问题是:

• OpenIMAJ 实现是否最适合此类“大数据”用例？计算它不会花很长时间吗？
• 是否可以在 hadoop reduce faze 期间将数据“流”到算法中以学习集群？
• 是否可以将学习的集群(模型)保存为字节，以便将模型传递给下一个 hadoop 作业？
• 在 hadoop 映射期间运行算法分配阶段是否可以？

感谢帮助

Answer 1

K-Means 聚类是一种对数据进行多次传递的迭代算法。在每次传递中，点都被分配给聚类质心，然后在所有点都被分配后，聚类质心被重新计算为分配点的平均值。您不能将数据“流”到传统意义上的算法，因为您需要在后续迭代期间返回到它。

关于 OpenIMAJ FloatKMeans 实现:是的，它可以处理“大数据”，因为它不介意从哪里获取数据 - DataSource 实例它作为输入可以在必要时从磁盘读取数据。唯一的要求是您可以在算法运行期间将所有质心保存在内存中。该实现是多线程的，因此在计算期间可以使用所有 cpu 内核。这里有示例代码:https://github.com/openimaj/openimaj/blob/master/demos/examples/src/main/java/org/openimaj/examples/ml/clustering/kmeans/BigDataClusterExample.java . OpenIMAJ IOUtils.writeBinary(...) 方法可用于将生成的簇质心保存在 FloatCentroidsResult 对象中。

K-Means 中最大的成本之一是计算每个数据点与每个聚类质心之间的距离，以便找到最接近的点。这样做的成本与数据的维度和质心的数量有关。如果您有大量的质心和高维数据，那么使用近似的 K-Means 实现可以在精度略有下降的情况下获得很大的速度优势(参见 FloatKMeans.createKDTreeEnsemble() 例如——这使用 KD 树的集合来加速邻居计算)。

关于与 Hadoop 的集成，可以将 K-Means 实现为一系列 Map-Reduce 任务(每对对应于算法的一次迭代)。有关讨论，请参阅本文:http://eprints.soton.ac.uk/344243/1/paper.pdf .如果你想走这条路，OpenIMAJ 在这里有一个非常粗略的实现，你可以构建它:https://github.com/openimaj/openimaj/tree/master/hadoop/tools/HadoopFastKMeans .如链接文件中所述，Apache Mahout 还包含一个实现:https://mahout.apache.org .这两种实现的一个问题是它们需要在映射器和缩减器之间传输大量数据(每个映射器发出当前数据点及其分配的集群 ID)。这种程度可能意味着使用算法的非 Hadoop 实现可能会更快，但这将取决于您有哪些可用的处理资源和数据集的性质。 map 和 reduce 之间的数据传输问题也可以通过聪明的 Hadoop Combiner 来减少，并从数据子集计算加权质心，然后将这些传递给(修改后的)reducer 以计算实际质心。