快速k-像算法$10^{10}$点？

Question

我希望在一组10维点上做k均值聚类。问题是:有一些10^{10}点。

我只是在寻找最大集群的中心和大小(比方说10到100个集群)；我不关心每一个点最终会出现在哪个集群中。具体而言，使用k-均值并不重要；我只是在寻找类似的效果，任何近似的k-均值或相关算法都将是很好的(小型批处理-SGD方法，.)。由于GMM在某种意义上是与k-均值相同的问题，对相同大小的数据进行GMM也很有趣。

在这种规模下，对数据进行次采样可能不会显著改变结果:使用数据的1/10000样本找到相同的前10位集群的概率非常高。但即使如此，这也是一个10^6点问题，它位于可处理的边缘/边缘之外。

Answer 1

K-均值是根据平均数计算的。

它使用方法对聚类进行建模，因此，通过增加更多的数据来提高聚类的效率是微不足道的。平均估计误差以1/sqrt(N)减小，因此增加更多的数据回报越来越少。

如此大的数据的战略总是围绕着抽样：

如果您想要次线性运行时，您必须进行采样！

事实上，小型批处理-Kmeans等就是这样做的:重复从数据集中抽取样本.

然而，抽样(特别是无偏抽样)也不是完全免费的.通常，您必须线性地读取数据才能进行采样，因为您没有对单个记录的随机访问。

我会用麦昆的算法。它是在线的；默认情况下，它只对您的数据进行一次传递(尽管迭代它很流行)。这是不容易分发，但我想你可以负担得起线性阅读你的数据，例如10次从一个SSD？

Answer 2

作为一个副词，注意，使用K-意味着10D数据可能会在没有任何结果，根据诅咒的维度。当然，它会根据数据的性质略有变化，但是当我试图确定K-均值开始在维数上表现出奇怪的阈值时，我得到了类似7D的东西。经过7维，它开始错过正确的集群(我的数据是手动生成的，根据4个良好的分离高斯分布，我使用MATLAB函数为我的小实验)。