2.6 k-means, Gaussian mixtures and EM
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 points 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.
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 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 , and , and two centres at and . The first two points belong to the centre at and contribute each; the third sits on its centre and contributes . The total is . Moving the first centre to would give : worse, so , the mean of and , is the better centre.
The viewport runs k-means with . 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 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.
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 beat every other position for the points and .
- 1
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 after every half-step: after the first assignment, 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 falls slowly, to after 7 iterations. Once that centroid holds most of the long blob, the first one is free to settle on the oval blob: drops from to in a single update, and after 11 iterations the run stops at .
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, , and , lie in the oval blob. After 5 iterations the run stops at , almost three times the 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.
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 : 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 (scikit-learn's n_init). On this data at , random seeding reaches for 9 of the seeds 0 to 9 and k-means++ for all 10. At the ten k-means++ runs end anywhere between and 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.
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