K-Means Clustering: Finding Groups in Data Without Labels

Grouping data with no answer key

Most of the machine learning techniques people encounter first — spam filters, price predictors, image classifiers — are supervised: they learn from examples that already come with the correct answer attached. Clustering belongs to a different family, unsupervised learning, where no labels exist at all. The algorithm is simply handed a pile of data points and asked to find structure in it: which points seem to belong together, and which seem distinct? K-means is the most widely used clustering algorithm precisely because its answer to that question is simple, fast, and usually reasonable.

Typical uses include grouping customers by purchasing behaviour for targeted marketing, compressing an image's colour palette down to a small number of representative shades, grouping documents by topic, and pre-processing data before feeding it into a supervised model.

The algorithm, step by step

K-means requires the user to choose one number in advance: k, the number of clusters to look for. From there, the algorithm alternates between two simple steps until nothing changes:

1. Initialise: place k "centroids" (imaginary cluster centres) at random positions among the data, or using a smarter scheme such as k-means++ which spreads the initial centroids out to avoid poor starting positions.
2. Assignment step: for every data point, measure its distance to each of the k centroids and assign it to whichever centroid is nearest.
3. Update step: move each centroid to the average (mean) position of all the points now assigned to it — this is where the "means" in k-means comes from.
4. Repeat: alternate the assignment and update steps. Points switch clusters as centroids move, and centroids drift as their memberships change. The process is guaranteed to converge — it will always reach a stable state where no point changes cluster — though that state is not guaranteed to be the best possible one.

Mathematically, k-means is trying to minimise the total within-cluster sum of squares (also called inertia): the sum, over every point, of the squared distance between that point and its assigned centroid. Smaller inertia means tighter, more compact clusters.

Why initialisation and cluster shape matter

Because k-means only ever converges to a local optimum, the random starting positions of the centroids can meaningfully change the final result. Two runs on the same data with different random seeds can land on visibly different clusterings, particularly when clusters overlap or vary in density. This is why most practical implementations run the algorithm multiple times from different random starts and keep the result with the lowest inertia, or use the k-means++ initialisation strategy, which deliberately spreads out the starting centroids to reduce this sensitivity.

A second, more fundamental limitation is baked into the algorithm's geometry: because every point is assigned to its nearest centroid by straight-line distance, k-means implicitly assumes clusters are roughly spherical (technically, convex) and of comparable size. It performs poorly on elongated, crescent-shaped, or nested clusters, and on clusters of very different sizes or densities — a smaller, tighter cluster sitting near a much larger one can get its points "stolen" simply because the large cluster's centroid happens to be nearby. In those situations, density-based methods like DBSCAN or hierarchical clustering, which do not assume a particular cluster shape, tend to perform better.

Choosing k: the elbow method and silhouette score

The requirement to specify k in advance is k-means' biggest practical hurdle, since the "correct" number of natural groups in real data is rarely obvious. Two techniques are commonly used to make an informed choice:

The elbow method runs k-means repeatedly across a range of k values (say, 1 through 10) and plots the resulting inertia against k. Inertia always decreases as k increases — more clusters can always fit the data more tightly, all the way down to zero when k equals the number of data points — but the rate of improvement typically slows sharply after the "true" number of clusters is reached. Plotted, this produces a curve that bends like an elbow, and the k value at the bend is a reasonable choice.

The silhouette score takes a different approach, scoring each point on how well it fits its assigned cluster compared with the next-nearest cluster, producing a value between -1 and 1 for every point (and an average across the dataset). Scores close to 1 indicate tight, well-separated clusters; scores near 0 indicate points sitting on cluster boundaries; negative scores suggest a point may have been assigned to the wrong cluster entirely. Trying several values of k and picking the one with the highest average silhouette score is often more reliable than the elbow method, especially when the elbow itself is not sharply defined.

K-means in practice: scaling and preprocessing

Because k-means relies entirely on distance calculations, the scale of each feature matters enormously. If one feature is measured in pounds sterling (ranging into the thousands) and another is a percentage (ranging from 0 to 1), the pounds feature will dominate every distance calculation and effectively decide the clustering on its own, regardless of how meaningful the percentage feature actually is. Standardising or normalising every feature onto a comparable scale before clustering is therefore not optional — it is a required preprocessing step, and skipping it is one of the most common practical mistakes.

K-means also struggles as the number of dimensions grows, a manifestation of the so-called curse of dimensionality: in high-dimensional spaces, the distance between the nearest and farthest points tends to become similar, making the notion of a "nearby" centroid less meaningful. For high-dimensional data, it is common to first apply a dimensionality reduction technique such as principal component analysis (PCA) to compress the data down to a smaller number of informative dimensions before clustering.