Menu
I understand k-means algorithms steps. However I'm not sure if the algorithm will always converge? Or can the observations always switch from one centroid to another?
902
The algorithm always converges (by-definition) but not necessarily to global optimum. The algorithm may switch from centroid to centroid but this is a parameter of the algorithm ( precision , or delta ). This is sometimes refered as "cycling". The algorithm after a while cycles through centroids.
We previously mentioned that the k-means algorithm doesn't necessarily converge to the global minima and instead may converge to a local minima (i.e. k-means is not guaranteed to find the best solution). In fact, depending on which values we choose for our initial centroids we may obtain differing results.
The K-means algorithm is non-deterministic. This means that the outcome of clustering can be different each time the algorithm is run even on the same data set.
The algorithm always converges (by-definition) but not necessarily to global optimum.
The algorithm may switch from centroid to centroid but this is a parameter of the algorithm (precision, or delta). This is sometimes refered as "cycling". The algorithm after a while cycles through centroids. There are two solutions (which both can be used at the same time). Precision parameter, maximum number of iterations parameter.
Precision parameter, if centroids amount of change is less than a threshold delta, stop the algorithm.
Max Num Iterations, if algorithm reaches that number of iterations stop the algorithm.
Note that the above schemes do not spoil the convergence characteristics of the algorithm. it still will converge but not necessarily to global optimum (this is irrelevant of the scheme used, as in many optimisation algorithms).
You may be interested in the related question on stats.SE Cycling in k-means algorithm and a referenced proof of convergence
90
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
