python - 聚类十亿个项目(或哪些聚类方法在线性时间内运行？)

Question

我有十亿个特征向量，我想将它们放入近似的簇中。查看来自 http://scikit-learn.org/stable/modules/clustering.html#clustering 的方法例如，我完全不清楚它们的运行时间如何随数据大小变化(亲和性传播除外，它显然太慢了)。

What methods are suitable for clustering such a large data set? I assume any method will have to run in O(n) time.

Answer 1

对于您的数据(仅 4 个分量)，K 均值复杂度听起来合理。棘手的部分是初始化和集群数量的选择。您可以尝试不同的随机初始化，但这可能很耗时。另一种方法是对数据进行子采样并运行更昂贵的聚类算法，如亲和传播。然后使用该解决方案作为 k-means 的 init，并使用您的所有数据运行它。