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

Question

我有十亿个特征向量,我想把它们放到近似的簇中.以http://scikit-learn.org/stable/modules/clustering.html#clustering中的方法为例,我对它的运行时间如何与数据大小进行比较并不清楚(Affinity Propagation除外)显然太慢了).

哪些方法适合聚类这么大的数据集？我假设任何方法都必须在O(n)时间内运行.

Answer 1

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