Machine Learning
Topic 20 · Unsupervised learning · ⏱ about 3 h

Clustering & k-Means

Finding natural groups in unlabelled data.

Show:
In this topic
Beginner

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.

1. place k centroids2. assign to nearest3. move to the mean
One round of k-means: assign each point to its nearest centroid, then move each centroid to the mean of its points. Repeat.

You first decide how many clusters you want, kk. The algorithm represents each cluster by a single point at its centre, called a centroid, and starts by placing the kk 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 kk 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.

Beginner

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

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.

Beginner

Choosing k & other methods

k-means requires you to choose the number of clusters kk 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 kk and plots the inertia for each. Inertia always decreases as kk increases (with kk 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 kk 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 aa, the average distance to the other points in its own cluster, with bb, 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 kk 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 kk 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.

Interactive. DBSCAN finds clusters of any shape and labels outliers as noise. Tune ε and minPts.
MethodMain ideaBest for
k-meanscentroids; each point joins the nearestlarge data; round, similar-sized clusters
Hierarchicalrepeatedly merge the closest clustersseeing structure at all scales; small to medium data
DBSCANdense regions are clusters; sparse points are noiseirregular shapes; outlier detection
Gaussian mixturesoft, probabilistic elliptical clustersoverlapping or stretched clusters
Intermediate · Maths

The k-means objective and why Lloyd's algorithm converges

📐 Maths you'll need: m-vectors · m-calculus · m-optim
💡 The idea in plain words

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
ziz_icluster assigned to point i
μk\mu_kcentre of cluster k
JJwithin-cluster sum of squares (inertia)
D(x)D(x)distance to the nearest chosen centre
a, ba,\ bmean 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 zi∈{1,…,K}z_i\in\{1, \dots, K\} be the cluster assigned to point xix_i, and let μk\mu_k be the centroid of cluster kk. k-means seeks the assignments and centroids that minimise the within-cluster sum of squares, or inertia:

J(z,μ)=∑i=1n∥xi−μzi∥2. J(z, \mu) = \sum_{i=1}^{n} \lVert x_i - \mu_{z_i}\rVert^2 .

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.

Assignment step (centroids fixed). With the centroids fixed, JJ is a sum of separate terms, one per point, and each point's term depends only on its own assignment. So we can minimise each term independently, by assigning each point to the centroid nearest to it: zi=arg⁡min⁡k∥xi−μk∥2z_i = \arg\min_k\lVert x_i - \mu_k\rVert^2. This can only lower JJ or leave it unchanged.
Update step (assignments fixed). With the assignments fixed, JJ separates into one term per cluster. For cluster kk, we minimise ∑i:zi=k∥xi−μk∥2\sum_{i: z_i = k}\lVert x_i - \mu_k\rVert^2 over μk\mu_k. Its gradient is −2∑i:zi=k(xi−μk)-2\sum_{i:z_i=k}(x_i - \mu_k), and setting this to zero gives nkμk=∑i:zi=kxin_k\mu_k = \sum_{i:z_i=k}x_i, so μk=1nk∑i:zi=kxi\mu_k = \frac{1}{n_k}\sum_{i: z_i=k} x_i, the mean of the cluster. This, too, can only lower JJ or leave it unchanged.

Since neither step can increase JJ, the inertia never goes up. It also can't go below zero, and there are only finitely many ways to assign nn points to KK 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 nKdnKd, 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 D(x)2D(x)^2, 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 log⁡K\log K of the optimal inertia.

The silhouette score, precisely. For each point, let aa be its average distance to the other points in its own cluster and bb its average distance to the points of the nearest other cluster. Its silhouette is

s=b−amax⁡(a,b)∈[−1,1]. s = \frac{b - a}{\max(a, b)} \in [-1, 1].

If the point is much closer to its own cluster (a≪ba \ll b), ss is close to 1; if it is equally close to both, ss is near 0; if it is closer to another cluster, ss is negative.

Key takeaway. Lloyd's algorithm is coordinate descent on J; it always converges, but only to a local minimum, so use k-means++ and several restarts.
Advanced

Gaussian mixtures and the EM algorithm

📐 Maths you'll need: m-prob · m-stats · m-eigen
💡 The idea in plain words

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
πk\pi_kmixing weight of cluster k
N(x∣μk,Σk)\mathcal N(x\mid\mu_k,\Sigma_k)Gaussian density for cluster k
Σk\Sigma_kcovariance matrix (shape) of cluster k
γik\gamma_{ik}responsibility: P(cluster k | point i)
NkN_keffective number of points in cluster k
BIC\text{BIC}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 kk is chosen at random with probability πk\pi_k, and then the point is drawn from that cluster's Gaussian distribution, which has its own mean μk\mu_k and covariance matrix Σk\Sigma_k. 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:

p(x)=∑k=1Kπk N(x∣μk,Σk),∑kπk=1. p(x) = \sum_{k=1}^K \pi_k\,\mathcal N(x\mid\mu_k, \Sigma_k), \qquad \sum_k\pi_k = 1.

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.

E-step: compute soft assignments. Using the current parameters and Bayes' theorem, compute for every point the probability that it came from each cluster. This is called the responsibility of cluster kk for point ii:
γik=πk N(xi∣μk,Σk)∑jπj N(xi∣μj,Σj). \gamma_{ik} = \frac{\pi_k\,\mathcal N(x_i\mid\mu_k,\Sigma_k)}{\sum_j \pi_j\,\mathcal N(x_i\mid\mu_j,\Sigma_j)}.
The numerator measures how well cluster kk explains the point, and the denominator makes the responsibilities add up to 1 across clusters.
M-step: refit each cluster. Treat the responsibilities as fractional memberships and refit each Gaussian to its weighted points. With Nk=∑iγikN_k = \sum_i\gamma_{ik} as the effective number of points in cluster kk:
πk=Nkn,μk=1Nk∑iγikxi \pi_k = \frac{N_k}{n}, \qquad \mu_k = \frac{1}{N_k}\sum_i\gamma_{ik}x_i
Σk=1Nk∑iγik(xi−μk)(xi−μk)⊤ \Sigma_k = \frac{1}{N_k}\sum_i\gamma_{ik}(x_i - \mu_k)(x_i - \mu_k)^\top
These are just the weighted proportion, weighted mean and weighted covariance.

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 σ2\sigma^2, 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, −2log⁡L^+plog⁡n-2\log\hat L + p\log n, which rewards likelihood but penalises the number of parameters pp; lower is better.

DBSCAN has two parameters, a radius ε\varepsilon and a minimum count minPts. A point is a core point if at least minPts points lie within distance ε\varepsilon of it. A cluster is built by starting from a core point and repeatedly adding every point within ε\varepsilon 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 nlog⁡nn\log n time. A single ε\varepsilon 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 n2n^2 for all the pairwise distances, so the method suits small and medium datasets.

Key takeaway. EM alternates soft assignments (E) and weighted refits (M), never decreasing the likelihood; k-means is its hard-assignment limit.
Code

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.

Python · NumPy from scratch
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)
Open in playground ↗
Python · scikit-learn: choosing K, GMM, DBSCAN
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))
Open in playground ↗
Before it runs, the code block above runs first (silently), because this one continues it.
Check yourself

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…

Go deeper

📚 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.

Ready