Hands-On Unsupervised Learning with Python

K-means++

Finding the optimal initial configuration is equivalent to minimizing the inertia; however, Arthur and Vassilvitskii (in K-means++: The Advantages of Careful Seeding, Arthur D., Vassilvitskii S., Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007) have proposed an alternative initialization method (called K-means++), which can dramatically improve the convergence speed by choosing initial centroids with a higher probability of being close to the final ones. The complete proof is quite complex and can be found in the aforementioned paper. In this context, we are providing directly the final results and some important consequences.

Let's consider the function D(•) defined as:

D(•) represents the ...