K-Means step by step

How K-Means works

K-Means splits $n$ points into $k$ clusters by looking for $k$ centroids that minimise the inertia, the sum of squared distances from each point to its centroid:

Lloyd's algorithm alternates two steps, each of which can only lower $J$:

1. Assignment — each point joins its nearest centroid: $c(i) = \arg\min_j \lVert x_i - \mu_j \rVert^2$;
2. Update — each centroid moves to the mean of its points: $\mu_j = \frac{1}{\lvert C_j \rvert} \sum_{i \in C_j} x_i$.

It stops when the assignment no longer changes. Convergence is guaranteed, but to a local minimum: the result depends on the starting centroids.

What the demo shows

• Three clusters: the favourable case. Run it several times with "random" centroids: sometimes two centroids share one cluster while a third covers two. k-means++ spreads the centroids at the start and almost always avoids that trap.
• Stretched clusters: K-Means measures Euclidean distances and assumes round clusters of similar size; elongated clusters get cut across.
• No structure: the algorithm always returns $k$ clusters, even when there are none. It is up to you to check they make sense.
• Two rings: no straight boundary separates one ring from the other; K-Means fails by design. A density-based (DBSCAN) or spectral method is suited.

Choosing k

Inertia always decreases as $k$ grows (it is zero for $k = n$): it cannot choose $k$ on its own. Look for the "elbow" of the inertia-versus-$k$ curve, or use the silhouette score.