1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The algorithm improves on its iterations w.r.t. its objective function to minimize the pooled within-cluster SS. However, some starting sets of centroids allow to lay a "path" towards the global (utter) minimum attainable with the given dataset, while other sets may not allow it: they can lead towards somewhat worse values of the minimum, called local minima. $\endgroup$
    – ttnphns
    Sep 12 '20 at 12:49
0
$\begingroup$

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

enter image description here

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.