0

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

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

  1. 学习阶段 - 我传入所有创建/填充类的数据
  2. 分配阶段 - 我可以在其中询问集群给定的数据属于哪个类

我计划使用 Hadoop reduce 阶段构建集群模型，在该阶段我将一一接收数据（这就是为什么我不能一次将数据全部传递给算法的原因）

我的问题是：

  • OpenIMAJ 实现对于这种“大数据”用例来说是最优的吗？计算它需要永远吗？
  • 是否可以在 hadoop reduce faze 期间将数据“流式传输”到算法中以学习集群？
  • 是否可以将学习到的集群（模型）保存为字节，以便将模型传递给下一个 hadoop 作业？
  • 在hadoop映射期间运行算法分配阶段可以吗？

感谢帮助

4

1 回答 1

2

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

关于 OpenIMAJFloatKMeans实现：是的，这可以处理“大数据”，因为它不介意从哪里获取数据——DataSource它作为输入的实例可以在必要时从磁盘读取数据。唯一的要求是您可以在算法运行期间将所有质心保存在内存中。该实现是多线程的，因此在计算期间可以使用所有 cpu 内核。这里有示例代码：https ://github.com/openimaj/openimaj/blob/master/demos/examples/src/main/java/org/openimaj/examples/ml/clustering/kmeans/BigDataClusterExample.java 。OpenIMAJIOUtils.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. 这两种实现的一个问题是它们需要在映射器和reducer之间传输大量数据（每个映射器都会发出当前数据点及其分配的集群ID）。这种情况的程度可能意味着使用算法的非 Hadoop 实现可能会更快，但这取决于您有哪些可用的处理资源和数据集的性质。map 和 reduce 之间的数据传输问题也可以通过巧妙的 Hadoop 减少，Combiner并从数据子集计算加权质心，然后将这些传递给（修改后的）reducer 以计算实际质心。

于 2015-03-24T10:18:52.450 回答