K-Means Clustering

Learning without labels

Every algorithm you've seen so far was supervised: you gave it inputs and correct outputs, and it learned to map one to the other. Unsupervised learning is different. You only give it inputs. There are no labels, no correct answers. The goal is to discover structure — patterns, groups, or relationships — that exist in the data itself.

K-Means clustering is the most widely used unsupervised algorithm. Given a dataset and a number k, it partitions the data into k groups (clusters) where points within a cluster are similar to each other and dissimilar to points in other clusters. Nobody tells the algorithm what the groups should be — it figures them out from the data geometry.

The algorithm

K-Means is elegantly simple. It alternates between two steps until convergence:

Step 1 — Assign: For each data point, find the nearest centroid (cluster centre) and assign the point to that cluster.

Step 2 — Update: Move each centroid to the mean of all points assigned to it.

Repeat until the assignments stop changing. That's the entire algorithm. It is guaranteed to converge (assignments cannot increase forever), though it may converge to a local rather than global minimum.

Choosing k: the elbow method

K-Means requires you to specify k — the number of clusters — in advance. How do you know what k is?

The elbow method: Run K-Means for k = 1, 2, 3, ..., 10. For each, record the inertia (total within-cluster sum of squared distances). Plot inertia vs. k. As k increases, inertia always decreases — but the rate of decrease typically slows sharply at the "right" k, creating an elbow in the curve. Choose the k at the elbow.

The elbow is sometimes ambiguous. When it is, try the silhouette score instead — a metric from -1 to 1 measuring how similar each point is to its own cluster vs. the nearest other cluster. Maximise it.

Limitations and when to use alternatives

K-Means has three significant limitations:

Assumes spherical clusters. K-Means uses Euclidean distance, so it partitions space into convex regions. Crescent-shaped or concentric clusters will be misclassified. Use DBSCAN or spectral clustering for irregular shapes.

Sensitive to initialisation. Bad starting centroids can lead to poor local minima. The fix: K-Means++ initialisation (spread initial centroids far apart) and running multiple restarts. Sklearn uses K-Means++ and 10 restarts by default.

Outliers distort centroids. A single extreme point can pull a centroid far from the true cluster centre. Use K-Medoids (uses actual data points as centres rather than means) or DBSCAN (explicitly marks outliers) for outlier-heavy data.

Real-world applications

Customer segmentation: Group customers by purchase behaviour, demographics, and engagement patterns. Each cluster gets a different marketing strategy.

Document clustering: Embed text, cluster the embeddings. Group support tickets by topic, news articles by theme, or research papers by subject — without any predefined categories.

Anomaly detection: Points far from any centroid (high inertia contribution) are anomalies. Used in fraud detection and network intrusion detection.

Vector quantisation in LLMs: K-Means is used internally in some quantisation techniques to compress model weights, and in codebook learning for audio and image compression.

Try it yourself — watch K-Means converge

What's next

K-Means clusters points by distance in feature space. Cosine Similarity is a different way to measure distance — one that ignores magnitude and measures only direction. It's the metric that powers semantic search, recommendation systems, and most embedding-based applications.