Skip to content
LearnMLByDoing
Free

2.6 k-means, Gaussian mixtures and EM

34 minProintermediateHOMLPMLMMLESL

k-means splits unlabelled data into k groups by alternating two exact minimisations of the within-cluster squared distance, and a Gaussian mixture replaces its hard, round clusters with soft, elliptical ones that expectation-maximisation fits by climbing the likelihood.

01Structure without labels

In supervised learning every sample arrives with a target. Here there is none: the floor holds n=300n=300 points xi∈R2\tok{point}{\mathbf{x}_i}\in\mathbb{R}^2 and the task is to find groups in them. The points were drawn from three Gaussian blobs, a long tilted one with 120 points, a tight round one with 80 and a wider oval one with 100, but no algorithm in this lesson is told which blob produced which point.

X (data)[,]600 values

One sample per row. Clustering returns a label vector of length n (hard clustering) or an n × k matrix of membership probabilities (soft clustering).

To search for groups you have to say what a good group is. The most common answer measures how tightly each cluster packs around its centre: choose k\tok{num_clusters}{k} centres and an assignment of every point to one of them, and add up the squared distances.

A tiny example first. Put three points on a line at 00, 11 and 55, and two centres at 0.50.5 and 55. The first two points belong to the centre at 0.50.5 and contribute 0.52=0.250.5^2=0.25 each; the third sits on its centre and contributes 00. The total is J=0.25+0.25+0=0.5J=0.25+0.25+0=0.5. Moving the first centre to 00 would give 0+1+0=10+1+0=1: worse, so 0.50.5, the mean of 00 and 11, is the better centre.

J=∑i=1n∥xi−μci∥2\tok{inertia}{J}=\sum_{i=1}^{n}\big\|\tok{point}{\mathbf{x}_i}-\tok{centroid}{\boldsymbol{\mu}}_{\tok{assignment}{c_i}}\big\|^2
Within-cluster sum of squares (inertia). The coloured pillars are the centres, the floor colours the assignment.

The viewport runs k-means with k=3k=3. Points recolour when they change cluster, the pillars glide to the means of their points, and the loop repeats. Clustering is used to segment customers, quantise colours or vectors, flag anomalies as points far from every centre, and add a cluster id as a feature for a later supervised model.

Hands-On Machine Learning, Aurélien Géron, Ch. 9, Unsupervised learning techniques; Clustering

The Elements of Statistical Learning, Hastie, Tibshirani & Friedman, Sec. 14.3, Cluster analysis

02Lloyd's algorithm and why it converges

Minimising JJ jointly over centres and assignments is NP-hard. Lloyd's algorithm alternates two minimisations that are each easy: fix the centres and choose the best assignment, then fix the assignment and choose the best centres.

assign: ci←arg⁡min⁡j∥xi−μj∥2,update: μj←1nj∑i: ci=jxi\textbf{assign: }\tok{assignment}{c_i}\leftarrow\arg\min_{j}\big\|\tok{point}{\mathbf{x}_i}-\tok{centroid}{\boldsymbol{\mu}_j}\big\|^2,\qquad \textbf{update: }\tok{centroid}{\boldsymbol{\mu}_j}\leftarrow\frac{1}{n_j}\sum_{i:\,c_i=j}\tok{point}{\mathbf{x}_i}
One iteration. n_j is the number of points in cluster j; the loop stops when no label changes.
Loading figure
The same 300 points and the same seed 7 start as the viewport. Step through the assign and update half-steps and compare JJ with the numbers below; then drag a centroid somewhere odd and run again.

Why the update uses the mean: the mean is the single point that minimises the sum of squared distances to a set of points, for the same reason the average minimises squared error in regression. In the tiny example above, the centre at 0.50.5 beat every other position for the points 00 and 11.

Why J can only go down1/4
  1. 1
    J(ct+1,μt)=∑imin⁡j∥xi−μjt∥2≤J(ct,μt)J(c^{t+1},\boldsymbol{\mu}^{t})=\sum_i\min_j\|\mathbf{x}_i-\boldsymbol{\mu}^t_j\|^2\le J(c^{t},\boldsymbol{\mu}^{t})

    With the centres fixed, J is a sum of independent per-point terms, and the nearest centre minimises each one.

The viewport starts from three random rows (seed 7): one in the long blob and two in the round one. The telemetry shows J\tok{inertia}{J} after every half-step: 430.088430.088 after the first assignment, 271.008271.008 after the first update. One centroid now owns the oval blob and most of the long one while the other two share the round blob. One of the upper centroids then slides down the long blob, taking its points a band at a time, and JJ falls slowly, to 234.190234.190 after 7 iterations. Once that centroid holds most of the long blob, the first one is free to settle on the oval blob: JJ drops from 218.494218.494 to 179.082179.082 in a single update, and after 11 iterations the run stops at J=97.803J=97.803.

μ (centroids)[,]6 values

Each iteration costs O(nkd) distance evaluations; the labels c are a length-n integer vector.

The Elements of Statistical Learning, Hastie, Tibshirani & Friedman, Sec. 14.3.6, K-means

Probabilistic Machine Learning: An Introduction, Kevin P. Murphy, Sec. 21.3, K-means clustering

03Initialisation: k-means++ and restarts

Lloyd's algorithm finds the fixed point its start leads to. With random seed 0 all three starting rows, (0.48,−0.92)(0.48,-0.92), (0.49,−1.58)(0.49,-1.58) and (1.35,−1.02)(1.35,-1.02), lie in the oval blob. After 5 iterations the run stops at J=284.863J=284.863, almost three times the 97.80397.803 of step 2: one centroid owns the long and the round blob together (196 points) while the other two split the oval blob. Neither step can repair this, because every point already sits with its nearest centroid and every centroid already sits at its points' mean.

P(next centre=xi)=D(xi)2∑mD(xm)2,D(x)=min⁡chosen μ∥x−μ∥P(\text{next centre}=\tok{point}{\mathbf{x}_i})=\frac{\tok{d2}{D(\mathbf{x}_i)^2}}{\sum_{m}D(\mathbf{x}_m)^2},\qquad D(\mathbf{x})=\min_{\text{chosen }\boldsymbol{\mu}}\|\mathbf{x}-\boldsymbol{\mu}\|
k-means++ seeding: the first centre is a uniform random row, every next one is drawn with probability proportional to D²

Points far from every centre chosen so far are the likeliest next centres, yet the choice stays random, so a single outlier is not guaranteed to win. Hover D(x)2\tok{d2}{D(\mathbf{x})^2}: the amber sticks are the weights after the first seed, tallest in the blobs that have no centre yet.

Keep seed 0 but switch the initialisation to k-means++.

Seeding improves the odds; it does not remove local optima. Libraries therefore run several restarts and keep the lowest JJ (scikit-learn's n_init). On this data at k=3k=3, random seeding reaches J=97.803J=97.803 for 9 of the seeds 0 to 9 and k-means++ for all 10. At k=6k=6 the ten k-means++ runs end anywhere between 44.9744.97 and 49.6849.68 and only one of them finds the lowest value, which is why restarts still matter. The chart's white dot is the current run; the curve is the best of the 10 restarts.

Ask for six clusters and try restart seed 5.

Hands-On Machine Learning, Aurélien Géron, Ch. 9, Centroid initialization methods

Probabilistic Machine Learning: An Introduction, Kevin P. Murphy, Sec. 21.3, K-means++

The rest of this lesson is in Pro

  • 04Where k-means goes wrong
  • 05Gaussian mixtures: a generative model
  • 06Expectation-maximisation
  • 07Choosing k, and other clustering algorithms
  • Python challenge: k-means++, Lloyd's algorithm and one EM step
  • Knowledge check, 4 questions

Pro opens all 45 lessons, every graded Python challenge and the full 3D labs.

Compiling scene

The Python challenge and knowledge check for this lesson are part of Pro.

Questions learners ask

What is the difference between k-means and a Gaussian mixture model?
k-means gives every point exactly one cluster and measures fit by squared distance to the cluster centre, which implicitly assumes round clusters of similar spread. A Gaussian mixture is a probabilistic model in which each cluster is a Gaussian with its own mean, covariance and weight, and every point gets a probability of belonging to each cluster. It can model elongated, tilted and differently sized clusters and is fitted with expectation-maximisation. k-means is the special case of a mixture with equal spherical covariances shrunk to zero.
How do I choose the number of clusters?
Plot the within-cluster sum of squares against k and look for the elbow where adding clusters stops paying off, compute the mean silhouette score for each k and prefer the highest, or for Gaussian mixtures pick the k with the lowest BIC. These heuristics can disagree, so check that the clusters are stable across restarts and make sense for the task the clustering serves.
Why does k-means give different results each time I run it?
Lloyd's algorithm starts from randomly chosen centres and only ever decreases its objective, so it stops at whichever local optimum its start leads to. Different random starts can end in different partitions. k-means++ seeding spreads the starting centres out and makes poor optima much rarer, and running several restarts and keeping the one with the lowest inertia, as libraries do by default, makes the result reliable. Fix the random seed if you need exactly reproducible clusters.

Next in Classical Machine Learning

2.7PCA and dimensionality reductionFind the directions of greatest variance, project onto them, and see where a linear projection fails on a curled-up manifold.

Sources

  • Hands-On Machine Learning, Aurélien Géron
  • Probabilistic Machine Learning: An Introduction, Kevin P. Murphy
  • Mathematics for Machine Learning, Deisenroth, Faisal & Ong
  • The Elements of Statistical Learning, Hastie, Tibshirani & Friedman