Mastering Machine Learning Algorithms

K-means++

We have said that a good choice for the initial centroids can improve the convergence speed and leads to a minimum that is closer to the global optimum of the inertia S. Arthur and Vassilvitskii (in The Advantages of Careful Seeding, Arthur, D., Vassilvitskii S., k-means++: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms) proposed a method called K-means++, which allows increasing the accuracy of the initial centroid guess considering the most likely final configuration.

In order to expose the algorithm, it's useful to introduce a function, D(x, i), which is defined as:

D(x, i) defines the shortest ...