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

Question

我遇到了和这篇文章一样的问题,但我没有足够的积分在那里添加评论.我的数据集有1百万行,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 || (请参阅Spark MLLib中Kmeans ++中的initializationSteps参数究竟是什么？).分布式版本大致为O(k),因此使用更大的k可以预期启动速度较慢.这可以解释为什么在减少迭代次数时没有看到任何改进.

在训练模型时使用大K也很昂贵.Spark使用Lloyds的变体,大致为O(nkdi).

如果您期望数据的复杂结构,那么很可能有更好的算法来处理这个问题而不是K-Means,但是如果你真的想坚持使用它,那么就开始使用随机初始化.