k-means clustering

Summary

$k$-means clustering splits points of $\R^d$ into $k$ groups. It makes the sum of squared distances from each point to the mean of its group as small as possible. It is one of the most widely used methods of cluster analysis. Finding the exact optimum is computationally hard in general, so it is approximated by Lloyd's algorithm, which alternates between assigning points and updating means. The method works best for compact, roughly round clusters of similar size.