K-Means++: Why Seeding Beats Blind Luck

Lloyd's algorithm, in four lines

K-Means partitions n points into k clusters by alternating two steps until nothing changes: assign each point to its nearest centroid, then move each centroid to the mean of the points assigned to it. That loop is the Lloyd algorithm, and each full pass provably never increases the objective it is minimising, the within-cluster sum of squares (inertia):

J = sum over clusters c, sum over points x in c  of  ||x - mean(c)||^2

assign  : each x -> argmin_c ||x - centroid_c||^2   (nearest centroid wins)
update  : centroid_c <- mean of all x currently assigned to c
repeat until assignments stop changing

Geometrically, fixing the centroids and assigning every point to its nearest one carves the plane into a Voronoi diagram -- the boundary between two clusters' regions is exactly the perpendicular bisector of their centroids, because that is the set of points equidistant to both. K-Means is, at every iteration, computing a Voronoi tessellation and then relaxing it toward its own centres of mass.

Why initialisation is the whole game

Lloyd's algorithm is only guaranteed to converge to a local minimum of J, and which local minimum it lands in depends almost entirely on where the centroids start. Two initial centroids placed in the same true cluster will often stay tangled there forever, splitting one real cluster in two while merging two others -- the update step can only reshuffle boundaries, it cannot teleport a centroid across empty space to a cluster that has no centroid nearby. Naive random initialisation (pick k random points as centroids) is cheap but produces exactly this failure mode often enough to matter.

K-Means++: seed far apart, on purpose

K-Means++ (Arthur & Vassilvitskii, 2007) fixes this with a weighted random seeding pass, run once before Lloyd's algorithm ever starts:

1. pick the first centroid uniformly at random from the data
2. for each remaining point x, compute D(x) = distance to the nearest chosen centroid
3. pick the next centroid at random, with probability proportional to D(x)^2
4. repeat step 2-3 until k centroids are chosen
5. run ordinary Lloyd's algorithm from these seeds

Squaring the distance before weighting is deliberate: points far from every existing centroid become much likelier picks, actively spreading the seeds across distinct clusters instead of clumping them, while still leaving a small chance of picking a nearby point so the seeding does not get permanently derailed by a single outlier. The guarantee that comes with this: K-Means++ seeding gives an expected approximation ratio of O(log k) relative to the true optimal clustering, a mathematical bound that plain random seeding does not have. In practice it also converges in noticeably fewer Lloyd iterations, because the seeds already sit close to good final positions.

Choosing k: the elbow and the silhouette

Nothing in the algorithm tells you the right number of clusters -- k is a hyperparameter you supply. Two common diagnostics: the elbow method plots inertia J against k and looks for where adding another cluster stops buying much reduction (inertia always decreases as k grows, hitting zero when k = n, so the useful signal is the point of diminishing returns, not the minimum). The silhouette score instead scores each point by how much closer it is to its own cluster than to the next-nearest one, averaged over all points, and rewards a value of k that produces tight, well-separated clusters rather than merely low total variance.

Where K-Means fails

K-Means implicitly assumes clusters are roughly spherical and similar in size, because it minimises squared Euclidean distance to a single centroid per cluster -- the same assumption baked into a mixture of equal, isotropic Gaussians. Feed it the classic two-half-moons or concentric-rings datasets and it fails visibly: a straight bisecting boundary cannot separate two interleaved crescents or two nested circles no matter how the centroids move, because no placement of centroids makes those shapes convex Voronoi cells. Density-based methods (DBSCAN) or spectral clustering handle those shapes; K-Means stays popular anyway because it is O(n·k·i) per run (i = iterations), trivially parallel, and good enough whenever clusters really are blob-shaped.

Frequently asked questions

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.