A4.3.4 · Machine learning approaches
Clustering
By the end you can
Describe how clustering groups unlabelled data by similarity, work through k-means step by step, and compare it with hierarchical and density-based methods.
A supermarket has data on a million customers and no one has told it what “types” of customer exist. lets the computer find out. It groups the customers so that those within a group are alike, and those in different groups are not. There are no labels and no right answer to check against, which is what makes this unsupervised learning.
k-means#
The most common method is . You choose how many clusters, k, you want, then:
- Place k starting centres, called (for example on k random data points).
- Assign: give every point to its nearest centroid.
- Update: move each centroid to the mean of the points it now owns.
- Repeat steps 2 and 3 until no point changes group.
Each repeat can only keep the total squared distance from points to their centres the same or lower, so the algorithm always settles. But it may settle on a poor answer if the starting centroids were unlucky, which is why it is often run several times with different starts.
A worked example in one dimension#
Eight values: 2, 4, 6, 20, 22, 24, 40, 44. We want k = 3 clusters and, to make the point, start the centroids close together at 2, 4 and 6.
| Round | Centroids at the end of the round | Total squared distance | Changed? |
|---|---|---|---|
| 1 | 2, 4, 26 | 976.0 | Yes, go again |
| 2 | 2, 5, 30 | 498.0 | Yes, go again |
| 3 | 2, 5, 30 | 498.0 | No: finished |
The algorithm settled after 3 rounds with centroids at 2, 5, 30 and a total squared distance of 498.0. That is a poor answer: the two far-away groups (20 to 24 and 40 to 44) are forced to share one centroid, because all three centroids started in the low group and the third one had to cover everything above 6. Starting at 2, 22 and 42 would have finished at once with centroids 4, 22 and 42 and a total squared distance of only 24. The method is fast and it always stops, but where it stops depends on where it started, which is why k-means is usually run several times and the best result kept.
Round
0
Total squared distance
–
to each point's centre
Status
Not started
Each round has two steps: every point joins the nearest centre (shown by its shape and colour), then each centre moves to the middle of the points that joined it. The crosses stop moving when no point changes group. The result depends on where the centres start, which is why k-means is often run several times.
Other clustering methods#
| Method | Idea | Good for | Watch out |
|---|---|---|---|
| Start with every point alone and repeatedly merge the two closest clusters, until one is left. The merge history is drawn as a tree (a dendrogram); cut it at a height to get clusters. | Seeing how groups nest inside each other; no need to choose k first. | Slow on very large data sets. | |
| Points with enough close neighbours are core points; clusters grow by linking core points. Points in sparse regions are labelled noise. | Clusters of any shape, and data with outliers; no need to choose k. | Needs a radius and a minimum number of points, and struggles when clusters differ greatly in density. | |
| Mean shift | Each point moves step by step towards the nearest dense region (the peak of the data density). Points that arrive at the same peak form a cluster. | Finding blobs when you do not know how many. | Slow, and depends on a window size. |
| Spectral | Treats the data as a graph of near neighbours and clusters using its structure. | Clusters that are connected but not round. | More complicated to set up. |
Using clusters#
Clusters have no names until someone gives them one. A retailer who clusters customers by spend and visit frequency might find a group of frequent low-spenders, a group of rare big-spenders, and a group of one-time buyers, and then give each a different offer. This is market segmentation; with price data it supports pricing strategy. The same method groups news stories, genes with similar behaviour, or sensor readings. Two cautions: scale the features first (A4.2.1) because clustering is built on distances, and remember that the algorithm will always return clusters, even when the data has none worth finding.
Check yourself
Clustering
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
5 questions · 17 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.Describe the steps of the k-means clustering algorithm.
[4]Describe: A detailed account: say what happens, step by step if it is a process.
2.In one round of k-means, the points (2, 6), (4, 8) and (6, 10) are assigned to the same cluster. Calculate the new centroid, and state which point of the next round would join this cluster if its other centroid were at (20, 20): (5, 9) or (18, 19).
[3]Calculate: Work out the number, showing the working.
3.Explain why clustering is an unsupervised technique.
[3]Explain: Give reasons: say what happens AND why, or how one thing causes another.
4.Compare k-means clustering with DBSCAN.
[4]Compare: Similarities and differences, about both things, point by point.
5.Describe how clustering could be used by a retailer for market segmentation.
[3]Describe: A detailed account: say what happens, step by step if it is a process.
In a nutshell
- Clustering is unsupervised: it groups unlabelled data so that points in a group are more alike than points in different groups.
- k-means: choose k, place k centroids, assign each point to the nearest centroid, move each centroid to the mean of its points, repeat until nothing changes. Different starting centroids can give different results.
- Hierarchical clustering merges (or splits) groups step by step and draws a dendrogram. DBSCAN grows clusters from dense regions, finds any shape and marks noise. Mean shift moves points towards dense regions.
- Uses: market segmentation, pricing strategy, grouping documents, finding unusual items.
- Scale the features before clustering, because the algorithm depends on distances.