如何加速Scikit learn中的k-means算法？

Question

在我的项目中，我使用了k-means来将数据分类为不同组别，但是我在使用Scikit-learn计算k-means时遇到了问题 - 计算速度非常慢。我需要加速。

我尝试更改n_jobs的数量为-1，但是速度仍然很慢！

有什么建议可以加速吗？

- user8058941

---

你正在处理什么类型的数据？你需要提供更多细节，没有什么万能的解决方案，我怀疑问题不在于scikit-learn的实现，而是k-means算法的基本低效性。 - juanpa.arrivillaga

有关编程的内容：3000个数据点，17维空间，k=400。 - user8058941

是的，好的，该算法的时间复杂度为O(n^(dk+1))，其中n是观测值的数量，d是维度，k是k。 - juanpa.arrivillaga

你应该考虑是否真的有意义将3000个点放入400个簇中。平均每个簇只有7.5个点。你可能需要更小的"k"值。 - Jeremy McGibbon

Answer 1

在scikit-learn中，主要解决方案是切换到小批量kmeans，可以大大减少计算资源。从某种程度上来说，这是一种类似于SGD（随机梯度下降）与GD（梯度下降）优化非线性函数的方法- SGD通常更快（以收敛到局部解所需的计算周期为衡量标准）。请注意，这会引入更多的优化差异，因此结果可能更难以复现（优化往往会更频繁地结束于不同的解，而不是“完整批次”kmeans）。

- lejlot

---

@user8058941，您可以在这篇论文中找到mini-batch k-means的摘要。我不确定，但是您可能需要将mini-batch大小设置为大于（或显着大于）k才能使其正常工作。 - Jeremy McGibbon

你为了获得一些可实现的相对加速，而牺牲 Wojciech 的什么理由，但是“以降低集群质量为代价”，并且“初始化策略对解决方案的稳定性影响较小，因为其计算是在随机样本中进行的，而不是使用整个数据集”，这打开了一个明确且未处理的风险，即在真实问题领域（非合成）数据集上陷入局部而非全局极值？ - user3666197

K-means算法总是收敛于局部最优解，无论是使用整个数据集还是小批量数据；固定的初始化方案会导致可重复的优化到局部最优解，而不是全局最优解。当然，在任何随机性过程中都存在风险，因此经验分析是唯一能够回答它在实际问题上工作效果如何的方法；Jeremy引用的论文显示最终kmeans准则值下降了0-4%。 - lejlot

当k-means过程切换到建议的小批量模式时，预期相对减少的[时间]和[空间] ~ CPU周期和处理MEM占用量是多少？是否公平地期望并常见于使用经典k-means处理整个数据集相比，实现1.01x | 1.1x | 2x | 3x | 5x | 10x甚至更快的速度提升范围？ - user3666197

有关文档聚类的基本分析，请参考原始工作http://www.eecs.tufts.edu/~dsculley/papers/fastkmeans.pdf。请随意进行这些调查，并验证您关心的真实问题的代表性数据集；答案中所述的所有内容都是OP选择的库中寻求解决方案的唯一更快的工具，因此在感兴趣的数据集上尝试是有效的；当然还有数十种其他可以测试的近似解决方案。 - lejlot

Answer 2

scikit-learn 0.23+现在提供了一种新的优化实现方式，可以在多个CPU之间并行处理工作：

https://scikit-learn.fondation-inria.fr/implementing-a-faster-kmeans-in-scikit-learn-0-23/

- ogrisel