K-Means: Assignment to Convergence

Clustering asks a question with no labels attached: given a cloud of points, what groups are hiding inside it? K-means answers with a concrete goal.

First choose k, the number of groups you want. Place k centers, called centroids, among the points. Assign every point to its nearest centroid. Then add up the squared distances between each point and its assigned center — written Σ ‖x − μ_c‖², where x runs over points, μ_c is the center of the group x joined, and the double bars mean distance. That total is called inertia. Small inertia means tight, compact groups.

K-means searches for centroid positions that make inertia as small as possible. Because each point belongs to exactly one group, the assignments are discrete and there are far too many combinations to try them all. But the goal has enough structure for a simple two-step loop to make steady progress.

The assignment step is exact once the centroids are fixed. For every point, measure its distance to each centroid and give the point to the nearest one. Ties can go to the lower index; inertia does not care.

This step can only lower inertia, because moving a point to its nearest center never increases its distance to the center it ends up with. The cost is mild: with n points, k clusters, and d dimensions, the step takes roughly n·k·d operations.

The update step is exact once the assignments are fixed. For each cluster, replace its centroid with the average of the points in it. This is calculus, not guesswork: the sum of squared distances to a center is smallest when the center sits at the arithmetic mean of its members, because that is where the slope of the sum is zero.

Assignment and update then alternate. Every full round either lowers inertia or leaves it unchanged, and there are only finitely many ways to assign the points, so the loop must eventually stop — usually after a handful of rounds.

Step through the demo and watch inertia in the status line. It falls after every round, then freezes once the assignments stop changing.

The same picture shows the method's weakness. The descent is monotone, but it is not guaranteed to find the best possible clustering. Different starting positions can lead to different final clusters, some clearly worse. Initialization deserves as much attention as the loop itself.

The standard fix for bad starting centers is k-means++. The first center is chosen uniformly at random from the data. Each next center is drawn at random too, but with probability proportional to its squared distance from the nearest already-chosen center. Far-apart seeds are likely to be picked, so the clusters start spread out. It is still random, but it comes with a guarantee of near-optimal results, which is why it is the default in most libraries.

A related snag is an empty cluster: a centroid that no point is nearest to. The usual repair is to keep its old position or to move it onto the farthest point.

K-means assumes groups are roughly round, similar in size, and separated by distances that mean something. It will cheerfully slice an elongated cluster in half or merge two nearby ones. It also makes you choose k in advance.

The elbow method plots inertia against k and looks for the bend where the curve stops falling quickly. Silhouette scores compare how well each point fits its own cluster versus the next nearest one, and they work even when there is no clear bend.

Either way, remember that inertia always shrinks as k grows, since more centers can only help. The interesting signal is how fast it shrinks, not its raw value. The problems below cover one iteration, the two steps separately, inertia, and k-means++ seeding.