Mastering Machine Learning with scikit-learn - Second Edition

Local optima

Recall that K-means often initializes the centroids to the positions of randomly selected observations. Sometimes, this random initialization is unlucky and the centroids are set to positions that cause K-means to converge to a local optimum. For example, assume that K-means randomly initializes two cluster centroids to the following positions:

K-means will eventually converge on a local optimum, like what is shown in the preceding figure. These clusters may be informative, but it is more likely that the top and bottom groups of observations are more informative clusters. Some local optima are better than others. To avoid unlucky ...