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

Question

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

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

我写的那个并不总是这样做,但是内置函数不应该能够解决这么简单的问题,总能找到最佳解决方案吗？

Answer 1

正如@Alexandre C.解释的那样,K-means算法取决于初始的簇质心位置,并且不能保证它会收敛到最优解.

您可以做的最好的事情是使用随机起点重复实验几次.

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

此外,MATLAB提供了多种距离测量(Euclidean,Manhattan,Cosine,......)的选择.一个简洁的选项emptyaction允许您控制在迭代期间集群丢失其所有已分配成员时发生的情况.

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