MATLAB kMeans 并不总是收敛到全局最小值

Question

我写了一个k-Means clustering MATLAB 中的算法，我想我会针对内置在 kmeans(X,k) 中的 MATLAB 进行尝试。

但是，对于非常简单的四集群设置(见图)，MATLAB kMeans并不总是收敛到最优解(左)，而是收敛到(右)。

我写的也不总是这样，但是内置函数不应该能够解决这么简单的问题，总是找到最优解吗？

Answer 1

作为@Alexandre C.解释说，K-means算法依赖于初始聚类质心位置，并不能保证它会收敛到最优解。

你能做的最好的事情就是用随机的起点重复实验几次。

MATLAB 的实现提供了这样一个选项:replicates 重复聚类 N 次，并选择聚类内点到质心总距离最小的一个。您还可以使用 start 选项控制如何选择初始质心。

此外，MATLAB 提供了多种距离度量(欧几里德、曼哈顿、余弦等)的选择。一个简洁的选项 emptyaction 允许您控制当集群在迭代期间失去所有分配给它的成员时发生的情况。

但真正的优势在于它采用了两阶段算法:通常的分配-重新计算迭代，然后是在线更新阶段。请务必阅读 documentation page 的算法部分获取更多信息。