MATLAB kMeans并不总是收敛于全局最小值 [英] MATLAB kMeans does not always converge to global minima

问题描述

我在MATLAB中编写了 k-Means聚类算法，我以为d在kmeans(X,k)中内置的MATLAB上进行尝试.

I wrote a k-Means clustering algorithm in MATLAB, and I thought I'd try it against MATLABs built in kmeans(X,k).

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

However, for the very easy four cluster setup (see picture), MATLAB kMeans does not always converge to the optimum solution (left) but to (right).

我写的那个也不总是做到这一点，但是内置函数不应该总是能够找到最佳解决方案来解决这样一个简单的问题吗?

The one I wrote does not always do that either, but should not the built-in function be able to solve such an easy problem, always finding the optimal solution?

推荐答案

作为

As @Alexandre C. explained, the K-means algorithm depends on the initial cluster centroid positions, and there is no guarantee that it will converge to the optimal solution.

您能做的最好的就是以随机的起点重复几次实验.

The best you can do is to repeat the experiment several times with random starting points.

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

MATLAB's implementation offers such an option: replicates which repeats the clustering N times and pick the one with the lowest total within-cluster point-to-centroid distances. You get also to control how the initial centroids are chosen with the start option.

此外，MATLAB还提供了许多距离度量(欧几里得，曼哈顿，余弦等)中的选择.一个整洁的选项emptyaction允许您控制当集群在迭代过程中丢失所有分配的成员时发生的情况.

In addition, MATLAB provides the choice among a number of distance measures (Euclidean, Manhattan, Cosine, ...). One neat option emptyaction allows you to control what happens when a cluster loses all its assigned member during the iterations.

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

But the real advantage is that it employs a two-phase algorithm: the usual assign-recompute iterations, followed by an online update phase. Be sure to read the algorithm section of the documentation page for more information.

这篇关于MATLAB kMeans并不总是收敛于全局最小值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！