05 · Unsupervised · 4 min read · Interactive · updated 8 October 2026

How does k-means work and how do you know whether the clusters it finds are real?

What it is

K-means is a clustering (unsupervised learning) algorithm that partitions a set of points into k groups so as to minimise the sum of squared distances between points and the centres of their groups. It alternates two steps: assign each point to the nearest centre, then move each centre to the mean of the points assigned to it (Lloyd's algorithm).

It is used for segmentation, compression (vector quantisation), feature engineering and as a component of larger systems. The number of groups k must be specified in advance.

Mechanism — why it works this way

The objective is to minimise the inertia J = Σ ‖xᵢ − μ_c(i)‖², the sum of squared distances between points and their cluster centres. Neither of the two steps can increase it: with the centres fixed, assigning each point to the nearest one gives the smallest term, and with the assignments fixed, the mean minimises the sum of squared distances — a property of the arithmetic mean, from which the algorithm takes its name. Since J never increases and there are finitely many possible assignments, the algorithm converges in a finite number of steps.

It converges, however, to a local minimum, so the result depends on the starting point. That is why it is run many times and the smallest J is kept, and the k-means++ initialisation (Arthur and Vassilvitskii 2007) draws centres far apart from one another, which guarantees a result no worse than O(log k) times the optimum in expectation.

A property that misleads people: k-means will always return k groups. A homogeneous cloud of points with no structure at all will be sliced into k roughly equal tiles (Voronoi cells). The algorithm does not test the hypothesis "do clusters exist" — that has to be checked separately, e.g. with the silhouette score, a comparison against random data (the gap statistic) or the stability of the partition across subsamples.

Euclidean distance sums squared differences across features, so a feature with a large numeric range decides everything. Without standardisation, k-means in practice clusters on that feature alone.

Caveat: k-means assumes spherical clusters of similar size and spread. Elongated, nested or variable-density groups require other methods: Gaussian mixtures, DBSCAN, hierarchical clustering.

By example

Palmer Penguins: 342 penguins with all four measurements (bill length and depth in mm, flipper length in mm, body mass in grams), three species — 151 Adelie, 123 Gentoo, 68 Chinstrap. The species is not given to the algorithm; we use it only for evaluation. KMeans(n_clusters=3, n_init=10, random_state=0) on the raw data agreed with the species with an ARI (adjusted Rand index) of 0.33: body mass has a standard deviation of about 800 g, bill depth about 2 mm, so the split followed almost nothing but mass.

After standardisation (StandardScaler) the ARI rose to 0.79. All 123 Gentoo penguins landed in one cluster; 127 of the 151 Adelie in a second, and 63 of the 68 Chinstrap in a third, together with 24 Adelie. The silhouette of this partition is 0.45, whereas for 333 points from a homogeneous random cloud in four dimensions it is about 0.2 for every k from 2 to 4.

Try it yourself: the interactive illustration (labels in Polish for now).

In practice

• scikit-learn: KMeans(n_clusters=..., init="k-means++", n_init="auto", random_state=0) — the default k = 8 is arbitrary, always set your own. inertia_ is J, silhouette_score for evaluation.
• Standardise features (StandardScaler) before clustering; encode categorical variables or use methods for mixed data (k-prototypes).
• Choosing k: silhouette peak, inertia "elbow", gap statistic — none of them is decisive, all are hints.
• For large datasets, MiniBatchKMeans computes centres on samples and is many times faster.
• The cluster index or distances to centres can be a useful feature for other models, if the clusters line up with the label structure.
• Typical mistake: interpreting k clusters as "discovered segments" without checking whether the structure differs from a random partition.

Frequently asked questions

How do you choose the number of clusters k?

Compute the silhouette for k from 2 to a dozen or so, and compare it with the inertia elbow and your knowledge of the data. If the silhouette is low for every k (below about 0.25), the data probably has no clear groups and k-means is slicing a uniform cloud.

Why does k-means give different results every time?

Because it converges to a local minimum that depends on the random starting centres. scikit-learn runs the algorithm several times (`n_init`) and returns the best result, and k-means++ reduces the spread. Set `random_state` for reproducibility and check how stable the assignments are.

Does k-means need standardised data?

Yes, if the features have different units. On the penguins, standardisation raised agreement with the species from 0.33 to 0.79 ARI. If some features should matter more, rescale them deliberately, not by an accident of units.

Sources

See also