k-means finds structure in data that has *no labels*. You tell it how many groups to look for — k — and it discovers k clusters on its own. It keeps k centroids (cluster centers) and refines them with two steps that alternate until nothing moves: assign every point to its nearest centroid, then slide each centroid to the middle of the points it just captured.
The two-step loop (Lloyd's algorithm)
1Initialize — place k centroids, often at k randomly chosen data points.
2Assign step — give every point to the centroid it is closest to (usually by squared Euclidean distance). This carves the data into k clusters.
3Update step — move each centroid to the mean position of the points now assigned to it.
4Repeat assign and update until assignments stop changing — that's convergence.
What it's secretly minimizing
Each round lowers the inertia — the total squared distance from points to their assigned centroid (also called within-cluster sum of squares). Both steps can only decrease it or leave it equal, which is why the loop is guaranteed to stop.
A tiny worked pass
Take 1-D points [1, 2, 10, 11] with k=2 and centroids starting at c₁=1, c₂=2. Assign: 1 → c₁; 2, 10, 11 → c₂ (all nearer 2 than 1). Update: c₁ = 1, c₂ = mean(2,10,11) ≈ 7.67. Assign again: 1,2 → c₁; 10,11 → c₂. Update: c₁ = 1.5, c₂ = 10.5. One more pass leaves the assignments unchanged — converged on the natural groups {1,2} and {10,11}.
It finds a local optimum, not the best one
The result depends on where the centroids start — a bad start can settle on a poor grouping. Run it several times with different seeds and keep the lowest-inertia result, or use k-means++ initialization, which spreads the initial centroids apart. You also have to pick k yourself; the elbow of the inertia-vs-k curve is a common guide.
OperationTimeSpace
Per iteration · n points, k clusters, d dims; each point checked against every centroidO(n·k·d)O(n + k·d)
Total · usually converges in a modest number of iterationsO(n·k·d · iters)O(n + k·d)
Check yourself
Why can two runs of k-means on the same data give different clusters?
