Clustering & k-Means
Finding natural groups in unlabelled data.
The k-means algorithm
Clustering is the task of finding natural groups in data that has no labels. A shop might want to discover groups of customers with similar buying habits, or a biologist might want to group genes that behave similarly, without knowing in advance what the groups are. The most widely used clustering method is k-means, and it is simple enough to describe in a few sentences.
You first decide how many clusters you want, . The algorithm represents each cluster by a single point at its centre, called a centroid, and starts by placing the centroids somewhere in the data, for example at randomly chosen data points. It then repeats two steps.
In the assignment step, every data point is assigned to whichever centroid is closest to it. This divides the data into groups. In the update step, each centroid is moved to the average position (the mean) of all the points assigned to it, which is the centre of its group. Moving the centroids changes which centroid is closest to some points, so we go back to the assignment step, and the two steps alternate until the assignments stop changing.
The algorithm is trying to make the clusters as tight as possible. The quantity it reduces is the inertia, also called the within-cluster sum of squares: the total of the squared distances from every point to the centroid of its own cluster. Both steps can only lower this total (or leave it unchanged), so the algorithm is guaranteed to stop. However, it may stop at a local optimum, a reasonable-looking clustering that is not the best possible one, and which one it finds depends on where the centroids started. Two standard remedies are used. The k-means++ initialisation chooses starting centroids that are spread out across the data, which gives much better results than purely random starts. And it is common to run the whole algorithm several times from different starting points and keep the result with the lowest inertia; scikit-learn's n_init parameter does this.
Watch it: k-means clustering, iteration by iteration
A short narrated animation. Press ▶ Play, or step through it with ⏮ ⏭. Tick 🔊 narrate to hear each step.
Interactive: this part runs in your browser.
Try it: run k-means
Click Assign then Move centroids alternately, or run it to convergence. Try different k and Restart to see different starting positions. There are really 4 blobs.
Interactive: this part runs in your browser.
Choosing k & other methods
k-means requires you to choose the number of clusters in advance, and that is often the hardest decision. There are two common aids.
The elbow method runs k-means for a range of values of and plots the inertia for each. Inertia always decreases as increases (with equal to the number of points it would be zero), so the lowest value is not the goal. Instead, we look for the "elbow": the value of after which adding more clusters only reduces inertia slightly. That point suggests the data's natural number of groups.
The silhouette score takes a different approach, measuring how well each point fits its own cluster compared with the nearest other cluster. For each point, it compares , the average distance to the other points in its own cluster, with , the average distance to the points in the nearest other cluster. The score ranges from −1 to +1: near +1 means the point is much closer to its own cluster than to any other, near 0 means it sits on a border, and negative means it would fit better in another cluster. Averaging over all points gives a quality score for the whole clustering, and we can choose the that maximises it. In practice, though, domain knowledge is often the deciding factor: a marketing team may need five customer segments regardless of what the elbow suggests.
k-means is not the only clustering method, and it makes assumptions that don't always fit: it works best when clusters are roughly round, of similar size and similar density. Three alternatives cover most other situations.
Hierarchical (agglomerative) clustering starts with every point as its own cluster and repeatedly merges the two closest clusters, until only one remains. The full history of merges can be drawn as a tree called a dendrogram, and cutting it at different heights gives different numbers of clusters, so you don't have to choose in advance and can see the structure at every scale.
DBSCAN defines clusters as regions where points are densely packed, separated by regions where they are sparse. It can find clusters of any shape, such as long curved bands, it chooses the number of clusters by itself, and it labels points in sparse regions as noise, which makes it useful for detecting outliers. It struggles when different clusters have very different densities.
Gaussian mixture models treat each cluster as a bell-shaped (Gaussian) cloud that can be stretched into an ellipse, and assign each point a probability of belonging to each cluster rather than a hard label. They are fitted with the EM algorithm, described in the Advanced section.
Interactive: this part runs in your browser.
| Method | Main idea | Best for |
|---|---|---|
| k-means | centroids; each point joins the nearest | large data; round, similar-sized clusters |
| Hierarchical | repeatedly merge the closest clusters | seeing structure at all scales; small to medium data |
| DBSCAN | dense regions are clusters; sparse points are noise | irregular shapes; outlier detection |
| Gaussian mixture | soft, probabilistic elliptical clusters | overlapping or stretched clusters |
The k-means objective and why Lloyd's algorithm converges
k-means has one goal: make every point close to its cluster's centre. It alternates two easy moves, each of which can only improve the goal: re-assign points to their nearest centre, then move each centre to the middle of its points. Because the goal can't keep improving forever, the algorithm must stop, though not necessarily at the best possible clustering.
🔤 Symbols in this section
| cluster assigned to point i | |
| centre of cluster k | |
| within-cluster sum of squares (inertia) | |
| distance to the nearest chosen centre | |
| mean distance to own cluster / nearest other cluster |
This section states the k-means objective precisely and proves that Lloyd's algorithm (the standard k-means procedure) always converges.
Let be the cluster assigned to point , and let be the centroid of cluster . k-means seeks the assignments and centroids that minimise the within-cluster sum of squares, or inertia:
Minimising over the assignments and the centroids simultaneously is hard, but minimising over either one while the other is held fixed is easy. Lloyd's algorithm exploits this by alternating between the two, a strategy known as coordinate descent.
Since neither step can increase , the inertia never goes up. It also can't go below zero, and there are only finitely many ways to assign points to clusters, so the algorithm cannot keep improving forever: it must converge in a finite number of steps. What it converges to, however, is only a local minimum; finding the globally best clustering is an NP-hard problem. Each iteration costs time proportional to , since every point's distance to every centroid must be computed.
k-means++ initialisation. The first centroid is chosen uniformly at random from the data. Each subsequent centroid is chosen at random with probability proportional to , the squared distance from each point to the nearest centroid already chosen. Points far from all existing centroids are therefore much more likely to be picked, which spreads the starting centroids across the data. This simple rule comes with a guarantee: the expected inertia of the result is within a factor of about of the optimal inertia.
The silhouette score, precisely. For each point, let be its average distance to the other points in its own cluster and its average distance to the points of the nearest other cluster. Its silhouette is
If the point is much closer to its own cluster (), is close to 1; if it is equally close to both, is near 0; if it is closer to another cluster, is negative.
Gaussian mixtures and the EM algorithm
A Gaussian mixture is a "soft" k-means: each point belongs partly to every cluster, with probabilities, and clusters can be stretched ellipses. EM alternates between guessing those memberships and refitting each cluster using them. DBSCAN and hierarchical clustering take completely different approaches: density, and merging.
🔤 Symbols in this section
| mixing weight of cluster k | |
| Gaussian density for cluster k | |
| covariance matrix (shape) of cluster k | |
| responsibility: P(cluster k | point i) | |
| effective number of points in cluster k | |
| model-selection score (lower is better) |
This section develops Gaussian mixture models and the EM algorithm, which generalise k-means to soft, elliptical clusters, and then describes the mechanics of DBSCAN and hierarchical clustering.
The model. A Gaussian mixture model imagines that each data point was generated in two stages: first a cluster is chosen at random with probability , and then the point is drawn from that cluster's Gaussian distribution, which has its own mean and covariance matrix . The covariance describes the cluster's shape, allowing it to be stretched and tilted into an ellipse. The overall density of a point is therefore a weighted sum of Gaussians:
We would like to choose the parameters by maximum likelihood, but the log of a sum doesn't simplify, so the likelihood can't be maximised directly. The Expectation–Maximisation (EM) algorithm sidesteps this by alternating two easier steps, much as k-means alternates assignment and update.
It can be proved, using Jensen's inequality, that each EM iteration maximises a lower bound on the log-likelihood (called the evidence lower bound) and therefore never decreases the likelihood. Like k-means, it converges to a local optimum, so several restarts are advisable. In fact, k-means is a special case: if every cluster is forced to be a round Gaussian with the same tiny variance , the responsibilities become 0 or 1 (each point is assigned entirely to its nearest centre), and EM turns into exactly the k-means algorithm. To choose the number of clusters for a mixture model, a common criterion is the BIC, , which rewards likelihood but penalises the number of parameters ; lower is better.
DBSCAN has two parameters, a radius and a minimum count minPts. A point is a core point if at least minPts points lie within distance of it. A cluster is built by starting from a core point and repeatedly adding every point within of any core point already in the cluster. Points that can't be reached from any core point are labelled as noise. With a spatial index, this takes roughly time. A single can't suit clusters of very different densities, which is the problem the variant HDBSCAN was designed to solve.
Agglomerative clustering repeatedly merges the two closest clusters, and the result depends on how the distance between two clusters is defined, which is called the linkage. Single linkage uses the closest pair of points, which can create long chains; complete linkage uses the farthest pair, favouring compact clusters; average linkage uses the average over all pairs; and Ward's linkage merges whichever pair of clusters causes the smallest increase in total within-cluster variance, which tends to give k-means-like clusters. A naive implementation needs memory proportional to for all the pairwise distances, so the method suits small and medium datasets.
Code: k-means++ and Lloyd from scratch, plus GMM and DBSCAN
The scratch k-means includes k-means++ seeding and prints the inertia, which should never increase.
import numpy as np
from sklearn.datasets import make_blobs
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=0.8, random_state=1)
def kmeans_pp_init(X, K, rng):
centres = [X[rng.integers(len(X))]]
for _ in range(K - 1):
d2 = np.min(((X[:, None, :] - np.array(centres)[None]) ** 2).sum(-1), axis=1)
centres.append(X[rng.choice(len(X), p=d2 / d2.sum())]) # prob ∝ D(x)^2
return np.array(centres)
def kmeans(X, K, iters=100, seed=0):
rng = np.random.default_rng(seed)
mu = kmeans_pp_init(X, K, rng)
for it in range(iters):
d2 = ((X[:, None, :] - mu[None]) ** 2).sum(-1) # (n, K) squared distances
z = d2.argmin(1) # assignment step
inertia = d2[np.arange(len(X)), z].sum()
new_mu = np.array([X[z == k].mean(0) if np.any(z == k) else mu[k] for k in range(K)])
print(f"iter {it}: inertia {inertia:.1f}")
if np.allclose(new_mu, mu):
break
mu = new_mu # update step
return z, mu
z, mu = kmeans(X, K=4)from sklearn.cluster import KMeans, DBSCAN
from sklearn.mixture import GaussianMixture
from sklearn.metrics import silhouette_score
from sklearn.datasets import make_moons
for K in range(2, 8):
km = KMeans(n_clusters=K, n_init=10, random_state=0).fit(X)
print(f"K={K}: inertia={km.inertia_:8.1f} silhouette={silhouette_score(X, km.labels_):.3f}")
bics = [GaussianMixture(K, covariance_type="full", random_state=0).fit(X).bic(X) for K in range(1, 8)]
print("GMM best K by BIC:", int(np.argmin(bics)) + 1)
gmm = GaussianMixture(4, random_state=0).fit(X)
print("soft memberships of first point:", gmm.predict_proba(X[:1]).round(3))
Xm, _ = make_moons(400, noise=0.06, random_state=0) # non-convex shapes
print("DBSCAN labels:", np.unique(DBSCAN(eps=0.2, min_samples=5).fit_predict(Xm))) # -1 = noise
print("k-means on moons silhouette:", round(silhouette_score(Xm, KMeans(2, n_init=10).fit_predict(Xm)), 3))Quiz
1. In k-means, the update step moves each centroid to…
2. Which method finds odd-shaped clusters and marks outliers as noise?
3. Why run k-means multiple times?
4. Lloyd's k-means algorithm is an instance of…
5. In EM for a GMM, the E-step computes…
6. k-means is the limit of a GMM when…
📚 Further reading
Trusted, mostly free sources: official documentation, well-known textbooks and courses. When you want to confirm or go deeper on anything here, start with these.
- scikit-learn: Clustering ↗ Official guide
- An Introduction to Statistical Learning (free book) ↗ James, Witten, Hastie, Tibshirani (Python edition available)