What does it mean for the k-means algorithm to be trapped in a local minimum?

Question

I am learning about the k-means clustering algorithm. I have read that one of the characteristics of this algorithm is that it can get trapped in a local minimum, and that a simple way to increase the chance of finding a global optimum is to restart the algorithm with different random seeds. I understand the basic concept of the algorithm, which initialises arbitrary centroids/means in the first iteration and then assigns data points to these clusters. The centroids are then updated after the points are all assigned, and points are re-assigned again. The algorithm continues to iterate until the clusters do not change anymore.

However, I am having trouble understanding exactly what is meant by a local minimum in the context of this algorithm. Any insights are appreciated.

Answer 1

I think this image from wikipedia is a pretty good example of the problem of local minimum in k-means.

In the first image we see a 2 dimensional example where we are trying to use k-means considering 4 centroids, and as we can see, the data can be easily divided into 4 groups arranged more or less in the four corners of the square image. However, due to the random intialization of the centroids, in the top left corner we have two centroids close one to another. This impacts the performance of the algorithm because on the last image, once the algorithm suposedly converged, we see that red color covers two clusters of datapoints that are considered by the algorithm as one single cluster. And one cluster has been divided into two clusters (pink and brown) so the algorithm did not identify correctly the clustered structure of the data.

Another initialization of the centroids where pink and brown centroids are not so close one another can avoid this problem, and for this reason it is recommended to perform not just one run of k-means.