OpenIMAJ 库中的 K-Means 聚类
K-Means clustering in OpenIMAJ library
我在机器学习和聚类分析方面不是很有经验,但我有以下问题:
我有 ~100kk-1000kk 条数据,我无法一次将其全部加载到内存中,我需要将其分成多个 classes(例如 1-10k 甚至 100k classes) 进行进一步分析。为此,我选择了在 OpenIMAJ 库 (FloatKMeans class) 中实现的 K-Means 算法。
我了解K-Means算法可以分为2个阶段:
- 学习阶段 - 我将所有数据传递给 create/fill classes
- 分配阶段 - 在这里我可以询问给定数据属于class的集群
我计划使用 Hadoop 缩减阶段构建集群模型,我将一个接一个地接收数据(这就是为什么我不能一次将所有数据传递给算法的原因)
我的问题是:
- 对于这样的 'bigdata' 用例,OpenIMAJ 实现是最优的吗?计算它不会花很长时间吗?
- 是否可以'stream'在hadoop reduce faze 期间将数据输入算法以学习集群?
- 是否可以将学习到的集群(模型)保存为字节,以便将模型传递给下一个 hadoop 作业?
- 运行 hadoop 映射期间的算法分配阶段可以吗?
感谢帮助
K-Means 聚类是一种对数据进行多次传递的迭代算法。在每次传递中,点都被分配给聚类质心,然后在所有点都被分配后,聚类质心被重新计算为分配点的平均值。您不能 "stream" 传统意义上的算法数据,因为您需要在后续迭代中返回它。
关于 OpenIMAJ FloatKMeans
实现:是的,它可以处理 "big data",因为它不介意从哪里获取数据 - 它需要的 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 实现可以以稍微损失精度为代价获得很大的速度优势(例如参见 [=14=]——这使用一组 KD 树来加速邻居计算)。
关于与 Hadoop 的集成,可以将 K-Means 实现为一系列 Map-Reduce 任务(每对对应于算法的一次迭代)。有关讨论,请参阅本文:http://eprints.soton.ac.uk/344243/1/paper.pdf . If you want to go down this route, OpenIMAJ has a very rough implementation here, which you could build off: https://github.com/openimaj/openimaj/tree/master/hadoop/tools/HadoopFastKMeans. As mentioned in the linked paper, Apache Mahout also contains an implementation: https://mahout.apache.org。这两种实现的一个问题是它们需要在映射器和缩减器之间传输大量数据(每个映射器发出当前数据点及其分配的集群 ID)。这种程度可能意味着使用算法的非 Hadoop 实现可能会更快,但这将取决于您有哪些可用的处理资源和数据集的性质。 map 和 reduce 之间的数据传输问题也可以通过聪明的 Hadoop Combiner
来减少,并从数据的子集中计算加权质心,然后将这些传递给(修改后的)reducer 以计算实际的质心。
我在机器学习和聚类分析方面不是很有经验,但我有以下问题:
我有 ~100kk-1000kk 条数据,我无法一次将其全部加载到内存中,我需要将其分成多个 classes(例如 1-10k 甚至 100k classes) 进行进一步分析。为此,我选择了在 OpenIMAJ 库 (FloatKMeans class) 中实现的 K-Means 算法。 我了解K-Means算法可以分为2个阶段:
- 学习阶段 - 我将所有数据传递给 create/fill classes
- 分配阶段 - 在这里我可以询问给定数据属于class的集群
我计划使用 Hadoop 缩减阶段构建集群模型,我将一个接一个地接收数据(这就是为什么我不能一次将所有数据传递给算法的原因)
我的问题是:
- 对于这样的 'bigdata' 用例,OpenIMAJ 实现是最优的吗?计算它不会花很长时间吗?
- 是否可以'stream'在hadoop reduce faze 期间将数据输入算法以学习集群?
- 是否可以将学习到的集群(模型)保存为字节,以便将模型传递给下一个 hadoop 作业?
- 运行 hadoop 映射期间的算法分配阶段可以吗?
感谢帮助
K-Means 聚类是一种对数据进行多次传递的迭代算法。在每次传递中,点都被分配给聚类质心,然后在所有点都被分配后,聚类质心被重新计算为分配点的平均值。您不能 "stream" 传统意义上的算法数据,因为您需要在后续迭代中返回它。
关于 OpenIMAJ FloatKMeans
实现:是的,它可以处理 "big data",因为它不介意从哪里获取数据 - 它需要的 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 实现可以以稍微损失精度为代价获得很大的速度优势(例如参见 [=14=]——这使用一组 KD 树来加速邻居计算)。
关于与 Hadoop 的集成,可以将 K-Means 实现为一系列 Map-Reduce 任务(每对对应于算法的一次迭代)。有关讨论,请参阅本文:http://eprints.soton.ac.uk/344243/1/paper.pdf . If you want to go down this route, OpenIMAJ has a very rough implementation here, which you could build off: https://github.com/openimaj/openimaj/tree/master/hadoop/tools/HadoopFastKMeans. As mentioned in the linked paper, Apache Mahout also contains an implementation: https://mahout.apache.org。这两种实现的一个问题是它们需要在映射器和缩减器之间传输大量数据(每个映射器发出当前数据点及其分配的集群 ID)。这种程度可能意味着使用算法的非 Hadoop 实现可能会更快,但这将取决于您有哪些可用的处理资源和数据集的性质。 map 和 reduce 之间的数据传输问题也可以通过聪明的 Hadoop Combiner
来减少,并从数据的子集中计算加权质心,然后将这些传递给(修改后的)reducer 以计算实际的质心。