Machine Learning

K-Means: Finding Clusters by Hand

Drop points on a plane and watch Lloyd's algorithm chase the cluster centers, assign, recenter, repeat. The same data can settle differently each run, the local minima that make k-means restart-sensitive.

k-meansclusteringunsupervisedlloyd

LiveInteractive · drag, toggle, run it

Machine Learning · Unsupervised

K-Means: Finding Clusters by Hand

K-means groups points into k clusters by repeating two moves until nothing changes. First it assigns every point to its nearest center. Then it slides each center to the average of the points that picked it. That loop, called Lloyd's algorithm, settles fast, but where it settles depends on where the centers started, so drop your own points and watch it find a different answer each time you reseed.

The two steps

assign:   label(i) = argmin c  ∥ x i − μ c ∥²
update:   μ c = mean of all points with label c
inertia:   J = Σ i  ∥ x i − μ label(i) ∥²

Each move can only lower inertia or leave it unchanged, so the algorithm always stops. It stops when an assignment step reassigns zero points. That guarantee is exactly what makes k-means fast and also what makes it fragile: it settles into the nearest valley from where the centers happened to start, which is not always the deepest one.

Run the algorithm

ready

iteration

0

reassigned

—

inertia (SSE)

—

status

init

Press Assign for the first assignment step, or Play to run the whole loop. Watch inertia fall and the reassignment count head toward zero.

cluster 1cluster 2cluster 3cluster 4

Set up the problem

Clusters k

Point tool

Shuffle data draws a fresh set of seeded blobs. New random init keeps the same points but picks different starting centers, which is the honest way to see local minima: run the algorithm to convergence, note the inertia, then reseed and run again. With awkward starts, two centers can end up splitting one true blob while a single center is stretched across two, and the final inertia comes out clearly higher. Real implementations run several inits and keep the lowest-inertia result for this reason.

Why empty clusters get reseeded

If a center ends an assignment step with no points, its mean is undefined and it would sit dead for the rest of the run. When that happens here, the empty center jumps onto the single point that is currently farthest from its own center, the point most in need of a closer home. That keeps all k clusters alive and tends to shave inertia, since the worst-served point gets a dedicated center on the next pass.

Distances are squared Euclidean on the plane shown. Inertia is the within-cluster sum of squares; it never rises across a step.