Definition
k-means partitions points into clusters, each summarized by a centroid (its mean). It alternates two steps — assign every point to its nearest centroid, then move every centroid to the mean of its points — until the assignments stop changing. This is coordinate descent on the within-cluster sum of squares .
At a glance
- Task
- Clustering (unsupervised): hard partition into exactly groups
- Input → output
- points and → a label per point and centroids
- Learns
- centroids — nothing else; the clusters are the Voronoi cells of the centroids
- Training
- per iteration, usually 5–50 iterations; times the number of restarts
- Prediction
- nearest centroid: per point
- Hyperparameters
n_clusters,init(k-means++ or random),n_initrestarts,max_iter,tol- Assumes
- Euclidean distance is meaningful (features scaled); clusters are compact, convex, roughly spherical and of similar spread
The problem
You have unlabeled data — customers described by visit frequency and basket size, pixels by colour, documents by embedding — and suspect it falls into groups. You want to find those groups without being told what they are, and to describe each one by a single representative that you can inspect, store and compare new points against.
Searching over partitions directly is hopeless: the number of ways to split points into non-empty groups (a Stirling number of the second kind) is about — for 100 points and 3 groups that is over . Even the clean question "which partition minimizes squared distance to the group means?" is NP-hard in general. We need a fast method that finds a good partition, accepting that it may not be the best one.
Hierarchical methods (see hierarchical clustering and agglomerative clustering) build a whole tree of merges but cost memory; k-means scales linearly in , which is why it is the default first clustering for large data.
The idea
It is a chicken-and-egg problem with an easy solution on each side. If you knew the centres, the obvious clustering would be: put each point with its nearest centre. If you knew the clusters, the obvious centre of each would be its average point. You know neither, so guess the centres, then alternate the two obvious moves. Each move can only make the clustering tighter, and there are finitely many clusterings, so the process must stop.
Vocabulary
- Centroid
- , the mean of the points in cluster — a point in feature space that need not be a data point (contrast the medoid of k-medoids, which must be one)
- Assignment
- , the index of the cluster point belongs to; k-means is a hard assignment (each point in exactly one cluster)
- Inertia / WCSS
- within-cluster sum of squares , the objective; scikit-learn reports it as "inertia_"
- Voronoi cell
- the region of space closer to than to any other centroid; the cells tile the space and their borders are straight lines (hyperplanes)
- Lloyd's algorithm
- the assign / update loop itself (Lloyd 1957, published 1982); "k-means" usually means this
- Seeding
- how the first centroids are chosen: random data points, or k-means++
- Restart
- one full run from a fresh seeding; keep the run with the lowest
- Local minimum
- a clustering where neither step can lower , though a different clustering has lower
The math
Encode the clustering as an assignment and centroids . k-means minimizes
- the -th data point, a vector in
- cluster index assigned to point
- centroid of cluster
- squared Euclidean distance: sum over features of squared differences
- within-cluster sum of squares (inertia); lower = tighter clusters
is hard to minimize jointly — is discrete — but easy to minimize in each block of variables with the other held fixed. That is exactly what the two steps do.
Assign step (fix , optimize ). is a sum of independent terms, one per point, and point only affects its own term. So each point independently picks the centroid that makes its term smallest:
- the index j that minimizes the expression (ties: lowest index)
The border between two cells is where . Expanding, the terms cancel and we get — a straight line (hyperplane), the perpendicular bisector of the two centroids. So k-means can only ever carve space into convex polygons.
Update step (fix , optimize ). Now splits into one term per cluster. For cluster with point set , set the gradient to zero:
- the set of points currently assigned to cluster
- number of points in cluster j
The function is a convex quadratic in , so this stationary point is the global minimum: the mean is the point that minimizes the sum of squared distances. That is why the method is called k-means. (With absolute distances the minimizer would be the median — the idea behind k-medians; restricting centres to data points gives k-medoids.)
Variance decomposition. The total sum of squares around the grand mean splits exactly into a within-cluster and a between-cluster part:
- mean of all n points
- between-cluster sum of squares: how far apart the centroids are, weighted by cluster size
TSS is fixed by the data, so minimizing is the same as maximizing the separation between clusters. The ratio is the fraction of variance "explained" by the clustering.
What each hyperparameter does to the objective
- k
- The optimum is non-increasing in (adding a centroid can never hurt) and reaches 0 at . So cannot choose by itself — look for the elbow where the drop flattens, or use silhouette / gap statistic.
- init
- Chooses the starting point of the descent, and therefore which local minimum you land in. k-means++ seeding gives before any Lloyd iteration.
- n_init
- Number of independent restarts; the final is the minimum over runs, so it can only go down as
n_initgrows, at linear cost. - max_iter, tol
- Stop after a fixed number of iterations or when the centroids move less than
tol(relative to feature variance). Too loose a tolerance stops before the assignments settle.
k-means++ seeding. Pick the first centre uniformly from the data. Then pick each next centre with probability proportional to , the squared distance from to the nearest centre already chosen. Far-away, not-yet-covered regions are very likely to get a centre; points next to an existing centre almost never are.
- distance from x to its nearest already-chosen centre (0 for chosen points)
Worked example: 12 customers, k = 3
Twelve customers described by two already-scaled features. By eye there are three groups — bottom-left (1–4), top (5–8) and bottom-right (9–12) — but the algorithm doesn't know that. We start from a deliberately poor seeding: and both inside the bottom-left group and in the top group, so the bottom-right group has no centroid at all.
| # | to | to | to | assigned | ||
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 0 | 2 | 61 | |
| 2 | 2 | 1 | 2 | 0 | 65 | |
| 3 | 2 | 3 | 2 | 4 | 41 | |
| 4 | 3 | 2 | 4 | 2 | 45 | |
| 5 | 6 | 8 | 61 | 65 | 0 | |
| 6 | 7 | 7 | 61 | 61 | 2 | |
| 7 | 7 | 9 | 85 | 89 | 2 | |
| 8 | 8 | 8 | 85 | 85 | 4 | |
| 9 | 8 | 2 | 49 | 37 | 40 | |
| 10 | 9 | 1 | 65 | 49 | 58 | |
| 11 | 9 | 3 | 65 | 53 | 34 | |
| 12 | 10 | 2 | 81 | 65 | 52 |
Lloyd's algorithm by hand
- 1Iteration 1 · assign. Each row takes its smallest (bold). Clusters: , , . Summing the bold column: .
- 2Iteration 1 · update. Means: ; ; . With the same clusters, drops to . has been dragged halfway across the plot by points 9 and 10.
- 3Iteration 2 · assign. Points 2 and 4 are now closer to ( vs 12.5 and 6.5) and point 12 is closer to ( vs ). Clusters: , , ; .
- 4Iteration 2 · update. , , ; .
- 5Iteration 3 · assign. Only point 11 moves: to vs to . Clusters are now the three visual groups; .
- 6Iteration 3 · update. , , ; — every point is at squared distance 1 from its centroid.
- 7Iteration 4 · assign. No point changes cluster, so the centroids would not move either: converged after 3 updates. , and TSS around the grand mean , so and the clustering explains of the variance.
- 8Predict a new customer : to is . Nearest is , so joins the bottom-right cluster.
| Iteration | Step | Points that moved | ||||
|---|---|---|---|---|---|---|
| 1 | assign | (1, 2) | (2, 1) | (6, 8) | all 12 | 184.000 |
| 1 | update | (1.5, 2.5) | (5.5, 1.5) | (7.833, 6.167) | — | 92.667 |
| 2 | assign | 2, 4, 12 | 77.111 | |||
| 2 | update | (2, 2) | (9, 1.667) | (7.4, 7) | — | 33.867 |
| 3 | assign | 11 | 17.084 | |||
| 3 | update | (2, 2) | (9, 2) | (7, 8) | — | 12.000 |
| 4 | assign | none → stop | 12.000 |
Local minima and seeding
Start instead from — all three centroids in the bottom-left group. After two iterations Lloyd settles on , , : the bottom-left group is split in two and the top and bottom-right groups are merged into one cluster. , seven and a half times the optimum, and neither step can improve it: no point is closer to another centroid, and every centroid is at its mean.
How often does a random start fail here? Of the ways to seed with three data points, 183 (83.2%) reach . k-means++ does much better: from a first centre at , the squared distances sum to 560, and only of that mass is in the bottom-left group, versus 52.1% in the top and 46.4% in the bottom-right. Using scikit-learn's k-means++ with a single run, all 1000 seeds we tried reached . Restarts (n_init) handle the remaining bad luck.
- 1μ₁ … μₖ ← k starting points
- 2repeat:
- 3 c(i) ← argminₖ ‖xᵢ − μₖ‖²
- 4 μₖ ← mean{ xᵢ : c(i) = k }
- 5until no c(i) changes
Place k = 3 centroids. Here two start inside the same cluster — a bad but common start.
The algorithm, step by step
KMeans(X, k)
- 1Scale the features (standardize) so that no feature dominates the distance.
- 2Seed centroids with k-means++: first uniformly at random, each next one with probability .
- 3Assign each point to its nearest centroid: compute the matrix of squared distances and take the row-wise arg-min.
- 4Update each centroid to the mean of its points. If a cluster is empty, re-seed it (e.g. at the point farthest from its centroid).
- 5Repeat assign and update until no assignment changes, the centroids move less than
tol, ormax_iteris reached. - 6Restart
n_inittimes and keep the run with the lowest . - 7Predict a new point by its nearest centroid.
Complexity
- Per iteration
- for the distances, for the means
- Total
- with iterations; is small in practice although the worst case is exponential
- Memory
- — no pairwise distance matrix, unlike hierarchical clustering or affinity propagation
- Prediction
- per point
Variants and practical tuning
| Variant | What changes | When to use |
|---|---|---|
| Elkan's algorithm | triangle inequality bounds skip most distance computations | dense data, moderate k (scikit-learn algorithm="elkan") |
| Mini-batch k-means | updates centroids from small random batches with a decaying learning rate | millions of points or streaming data; slightly higher J |
| Bisecting k-means | repeatedly splits the cluster with the largest J in two | large k; gives a hierarchy and more even cluster sizes |
| k-medoids (PAM) | centres must be data points; any distance | non-Euclidean distances, robustness to outliers — see k-medoids |
| Spherical k-means | cosine similarity, centroids normalized to unit length | text / embedding vectors |
| Kernel k-means | distances in a kernel feature space | non-convex clusters; closely related to spectral clustering |
| Fuzzy c-means | soft memberships with fuzzifier m | points can belong partly to several groups (or use a GMM) |
| k | best | drop from | silhouette |
|---|---|---|---|
| 1 | 212 | — | — |
| 2 | 92 | 120 | 0.536 |
| 3 | 12 | 80 | 0.753 |
| 4 | 10 | 2 | 0.547 |
| 5 | 8 | 2 | 0.365 |
The elbow: going from 2 to 3 clusters removes 80 units of , going from 3 to 4 removes only 2. The silhouette of a point is , where is its mean distance to its own cluster and to the nearest other cluster; the average is highest (0.753) at .
In code
1import numpy as np23def kmeans_pp(X, k, rng):4 centres = [X[rng.integers(len(X))]]5 for _ in range(k - 1):6 d2 = ((X[:, None] - np.array(centres)[None]) ** 2).sum(-1).min(1)7 centres.append(X[rng.choice(len(X), p=d2 / d2.sum())]) # D² sampling8 return np.array(centres, float)910def lloyd(X, mu, max_iter=100):11 mu = np.array(mu, float)12 labels = None13 for it in range(1, max_iter + 1):14 d2 = ((X[:, None] - mu[None]) ** 2).sum(-1) # n × k squared distances15 new = d2.argmin(1) # assign16 if labels is not None and (new == labels).all():17 break # converged18 labels = new19 for j in range(len(mu)): # update20 if (labels == j).any():21 mu[j] = X[labels == j].mean(0)22 J = ((X - mu[labels]) ** 2).sum()23 print(f"iter {it}: J = {J:.3f} centroids = {np.round(mu, 3).tolist()}")24 return labels, mu, ((X - mu[labels]) ** 2).sum()2526def kmeans(X, k, n_init=10, seed=0):27 rng = np.random.default_rng(seed)28 runs = [lloyd(X, kmeans_pp(X, k, rng)) for _ in range(n_init)]29 return min(runs, key=lambda r: r[2]) # keep the lowest J3031X = np.array([[1, 2], [2, 1], [2, 3], [3, 2], [6, 8], [7, 7],32 [7, 9], [8, 8], [8, 2], [9, 1], [9, 3], [10, 2]], float)3334labels, mu, J = lloyd(X, [[1, 2], [2, 1], [6, 8]]) # the article's start35print(labels, J) # [0 0 0 0 2 2 2 2 1 1 1 1] 12.036x_new = np.array([6, 3])37print("new point ->", ((mu - x_new) ** 2).sum(1).argmin()) # 11import numpy as np2from sklearn.cluster import KMeans3from sklearn.metrics import silhouette_score45X = np.array([[1, 2], [2, 1], [2, 3], [3, 2], [6, 8], [7, 7],6 [7, 9], [8, 8], [8, 2], [9, 1], [9, 3], [10, 2]], float)78# 1) Reproduce the hand computation: fixed start, a single run.9km = KMeans(n_clusters=3, init=np.array([[1, 2], [2, 1], [6, 8]]), n_init=1).fit(X)10print(km.labels_, km.cluster_centers_.tolist(), km.inertia_, km.n_iter_)11# [0 0 0 0 2 2 2 2 1 1 1 1] [[2.0, 2.0], [9.0, 2.0], [7.0, 8.0]] 12.0 412print(km.predict([[6, 3]])) # [1]1314# 2) The poor start gets stuck in a local minimum.15bad = KMeans(n_clusters=3, init=np.array([[1, 2], [2, 1], [3, 2]]), n_init=1).fit(X)16print(bad.inertia_) # 90.01718# 3) In practice: k-means++ with restarts, and choosing k.19for k in range(2, 6):20 m = KMeans(n_clusters=k, init="k-means++", n_init=10, random_state=0).fit(X)21 print(k, round(m.inertia_, 3), round(silhouette_score(X, m.labels_), 3))22# 2 92.0 0.536 | 3 12.0 0.753 | 4 10.0 0.547 | 5 8.0 0.365Use when
- +You need a fast, scalable clustering: linear in n, millions of points, mini-batch for streams.
- +Clusters are compact, round-ish and similar in size, and a mean is a meaningful prototype.
- +You want a codebook: vector quantization, colour quantization, coarse indexes for nearest-neighbour search, or to initialize a Gaussian mixture.
- +You need to assign new points cheaply — one distance per centroid.
Avoid when
- −Clusters are elongated, nested, non-convex or very different in size or density — use GMM, DBSCAN/HDBSCAN or spectral clustering.
- −There are strong outliers: one far point drags a mean — use k-medoids or remove outliers first.
- −Features are categorical or distance is not Euclidean — use k-modes or k-medoids.
- −You have no idea what k is and want a hierarchy instead — use agglomerative clustering or HDBSCAN.
Where it's used
Customer segmentation
Group customers by recency, frequency and spend; each centroid is a readable "typical customer" for a marketing persona.
Colour quantization & compression
Cluster pixel colours into centroids (say 16) and store each pixel as a 4-bit index into that palette.
Vector search indexes
Inverted-file (IVF) indexes in FAISS and similar libraries use k-means centroids as coarse buckets, so a query only scans the few nearest buckets.
Bag of visual words / features
Cluster local image descriptors or embeddings; the cluster index becomes a discrete token or a feature for a downstream model.
Check yourself
Why is a centroid updated to the mean of its cluster's points?
Check yourself
With centroids (2, 2), (9, 2) and (7, 8), which centroid does the new point (6, 3) join?
Check yourself
k-means++ has placed its first centre at (1, 2) in the worked example (squared distances sum to 560). What is the probability that the second centre lands in the bottom-left group (points 1–4)?
Check yourself
Why can't you choose k by picking the value with the lowest inertia J?
Remember
- ✓k-means minimizes the within-cluster sum of squares by coordinate descent: assign each point to its nearest centroid, move each centroid to its mean.
- ✓Each step can only lower , so the algorithm always terminates — but at a local minimum (on the example, versus the optimum 12).
- ✓Seed with k-means++ (D² sampling) and run several restarts; keep the lowest J.
- ✓Standardize features: Euclidean distance lets large-unit features decide the clusters.
- ✓Choose k by the elbow, silhouette or gap statistic — J alone always prefers more clusters.
- ✓Cells are convex (perpendicular bisectors), so k-means suits compact, round, similar-sized clusters; otherwise use GMM, DBSCAN or spectral clustering.