The iterative loop: assign and recenter
K-means partitions data into k clusters by iterating two steps. First, assign each point to the nearest centroid (cluster center). Second, move each centroid to the mean position of all points assigned to it. Repeat until the assignments stabilize (centroids stop moving or move less than a threshold).
This greedy algorithm is fast and works well for spherical, evenly-sized clusters. It requires specifying k in advance, though methods like the elbow curve (plotting error vs k and looking for an inflection) can guide the choice. Initialization matters: poor starting centroids can lead to suboptimal local minima, so practitioners often run the algorithm multiple times with random starts and pick the best result.
When K-means works and when it fails
K-means excels at finding compact, well-separated clusters in moderate dimensions. It is computationally efficient and widely implemented. However, it struggles with elongated or non-convex clusters, very different cluster sizes, or high-dimensional sparse data where distance becomes meaningless. For such cases, density-based methods (DBSCAN) or hierarchical clustering are better.
A common gotcha: K-means minimizes within-cluster variance, not between-cluster separation. A cluster with high variance around a dense center can wrongly be split, while two overlapping clouds might be treated as one. Always validate cluster quality visually or with domain knowledge, not just by algorithm metrics.