K-Means Clustering: Centroids, Convergence and k-means++

Two steps, repeated to a fixed point

K-means partitions n points into k clusters, each represented by a single centroid. Given k initial centroids, Lloyd's algorithm (Stuart Lloyd, 1957, published 1982) alternates two steps until nothing changes: assign every point to its nearest centroid, splitting the plane into a Voronoi diagram, and then move each centroid to the mean position of the points assigned to it. Both steps only ever reduce or hold constant the objective being optimised, so the process is guaranteed to settle.

live demo · Voronoi cells settling around moving centroids● LIVE

What is actually being minimised

The objective is inertia, also called the within-cluster sum of squares: for every point, the squared Euclidean distance to its assigned centroid, summed over all points. The assignment step, for fixed centroids, is provably the assignment that minimises inertia. The update step, for fixed assignments, sets each centroid to the arithmetic mean of its points, which is provably the point that minimises the sum of squared distances to that group. Alternating two exact minimisations of the same objective is why the loop cannot increase inertia and must eventually stop changing.

while (assignments changed) {
  for (const p of points)                          // assignment step
    p.cluster = argmin_k( dist2(p, centroid[k]) );
  for (let k = 0; k < K; k++)                       // update step
    centroid[k] = mean(points where p.cluster === k);
}

Only a local minimum, and why initialisation matters

Minimising inertia exactly over all possible partitions is NP-hard, so Lloyd's algorithm only guarantees a local minimum - the result it converges to depends heavily on where the centroids started. Two bad starting centroids can permanently split what should be one cluster, or merge two clusters that should stay separate, because there is no mechanism in the loop that moves a centroid across an empty region once the assignments have locked in. The standard fix is to run the whole algorithm several times from different random starts and keep the run with the lowest final inertia.

k-means++: seeding that avoids the worst starts

Arthur and Vassilvitskii's k-means++ (2007) improves the odds of a good start without changing the main loop at all. Pick the first centroid uniformly at random from the data. For each subsequent centroid, pick a point with probability proportional to the square of its distance to the nearest centroid chosen so far - points far from existing centroids are far more likely to be picked, spreading the initial centroids across the data instead of clumping them. This seeding alone provably gives an expected approximation ratio of O(log k) relative to the true optimum, and in practice it noticeably reduces both the number of iterations to converge and the chance of a bad local minimum.

Frequently asked questions

Does k-means always converge?

Yes, in a finite number of steps, because there are finitely many ways to partition n points into k groups and inertia strictly decreases or stays the same at every reassignment and every recentring. It converges to a local minimum, not necessarily the global one, and the number of steps needed can in rare worst cases be large.

How do I choose k?

There is no single correct answer. The elbow method plots inertia against k and looks for the point where adding another cluster stops helping much; the silhouette score compares within-cluster to between-cluster distance for a range of k values. Both are heuristics, not proofs, and domain knowledge usually settles ties.

Why does k-means struggle with elongated or unevenly sized clusters?

Because it minimises squared Euclidean distance to a single centroid per cluster, which implicitly assumes clusters are roughly spherical and similarly sized. A long, thin cluster or two clusters of very different density will often get cut incorrectly by centroids that only see distance, not shape. Density-based methods such as DBSCAN handle those cases better.

Try it live

Everything above runs in your browser - open K-Means Clustering and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open K-Means Clustering simulation