apache-spark - 为什么 Spark Mllib KMeans 算法非常慢？

Question

我遇到了与此相同的问题 post ，但我没有足够的分数在那里添加评论。我的数据集有 100 万行，100 列。我也在使用 Mllib KMeans，它非常慢。事实上，这项工作永远不会完成，我必须杀死它。我在谷歌云(dataproc)上运行它。如果我要求较少数量的集群 (k=1000)，它就会运行，但仍然需要超过 35 分钟。我需要它运行 k~5000。我不知道为什么它这么慢。考虑到工作人员/节点的数量和 100 万 x ~300,000 col 矩阵上的 SVD 需要大约 3 分钟，数据被正确分区，但是当涉及到 KMeans 时，它只是进入了一个黑洞。我现在尝试减少迭代次数(2 次而不是 100 次)，但我觉得某处有问题。

KMeansModel Cs = KMeans.train(datamatrix, k, 100);//100 iteration, changed to 2 now. # of clusters k=1000 or 5000

Answer 1

看起来原因比较简单。您使用相当大的 k 并将其与昂贵的初始化算法相结合。

默认情况下，Spark 使用作为 K-means++ 的分布式变体，称为 K-means|| (见 What exactly is the initializationSteps parameter in Kmeans++ in Spark MLLib? )。分布式版本大约为 O(k)，因此 k 越大，启动速度就越慢。这应该可以解释为什么在减少迭代次数时没有看到任何改进。

在训练模型时使用大 K 也很昂贵。 Spark 使用的是 Lloyds 的变体，大约为 O(nkdi)。

如果您期望数据结构复杂，那么很可能有比 K-Means 更好的算法来处理这个问题，但如果您真的想坚持使用它，您可以从使用随机初始化开始。