K-means++

K-means++ is an algorithm for choosing the starting centres, called seeds, for the k-means clustering algorithm. David Arthur and Sergei Vassilvitskii proposed it in 2007 as an approximation algorithm for the NP-hard k-means problem, to avoid the poor clusterings that the standard k-means method sometimes reaches from unlucky starting points. The first centre is picked uniformly at random from the data points. Each later centre is picked from the remaining points with probability proportional to the squared distance from the point to its nearest centre already chosen, which spreads the seeds apart. Ordinary k-means iterations then run from those seeds. The seeding is guaranteed to give an expected O(log k) approximation to the optimal clustering, and its authors measured typical speedups of about two times and, on some datasets, close to a thousand-fold reduction in error. Because it needs k passes over the data it scales poorly to very large datasets, which led to a parallel variant called k-means||. Ostrovsky, Rabani, Schulman and Swamy had independently proposed a similar seeding in 2006.