java - K-means 聚类算法运行时间和复杂度

Question

我编写了一个 Java 代码来聚类一个巨大的数据集，该数据集大约有 100000rowsx100000columns（稀疏行）。但是数据集是用稀疏实例创建的，因此它具有稀疏矩阵的结构。

我可以在我的代码中使用 3 个聚类函数：

JavaML：Kmeans，Weka：SimpleKmeans，Weka：Xmeans

我已经运行了 Weka 的 SimpleKmeans 函数，但它工作了大约 9 个小时，集群过程还没有结束。这些函数的预计运行时间是多少，哪一个最适合这个数据集？

Answer 1

K-means不适用于稀疏数据。

原因是均值不会稀疏，因此，对于您的数据集而言，均值实际上是异常的。更糟糕的是：均值之间的距离可能会小于实例到均值的距离。

你会在某个时候得到一些结果——Weka 非常慢，你可能想寻找更快的东西；对于这个数据集大小，您可能想要使用分布式的 Mahout（但从这里的问题来看，还有其他问题）。IIRC 它还具有稀疏向量的加速技巧，通过预先计算欧几里得长度 - 但是，结果可能没有意义。

问题是 K-means 寻找最优的 Voronoi 单元划分。但是您的数据集在稀疏时可能没有自然的 Voronoi 单元结构。因此，您花费大量时间来寻找您的数据无法拥有的最佳结构。