Cluster Analysis
Finding groups nobody labelled. With no answers to learn from, clustering discovers the natural structure hidden in raw data, using k-means and more.
Until now, every problem came with a clear goal or a set of rules. Machine learning changes the game: we hand the computer data and ask it to find the pattern itself. Cluster analysis is the purest example. Nobody labels the data, nobody says what the groups are, yet the algorithm sorts thousands of points into natural clusters, customers who behave alike, cells of the same type, documents on the same theme. This page shows how, with k-means as the star, and lets you watch it converge live.
Learning without labels
Machine learning splits into families by what the data looks like. In supervised learning (next week) every example comes with the right answer, and the model learns to reproduce it. Cluster analysis is unsupervised: there are no answers, no labels, just raw data points. The task is to discover structure that was never pointed out.
Clustering groups data so that points in the same cluster are similar to each other and different from points in other clusters. The algorithm is not told what the groups mean or even how many there are; it finds groupings from the shape of the data alone.
Measuring closeness
Clustering is built on one idea: similar things are close together. So we need a way to measure distance between two data points. Each point is a list of numbers (its features), and the most common measure is plain Euclidean distance, the straight-line distance you would measure with a ruler.
In two dimensions this is the familiar distance on a graph; the same formula extends to any number of features. Smaller distance means more similar. Everything clustering does comes down to comparing these distances.
The k-means algorithm
K-means is the most popular clustering method, and its loop is beautifully simple. You first pick k, the number of clusters you want. The algorithm then places k centroids (cluster centres) and repeats two steps until nothing changes.
- Assignment step: assign every point to its nearest centroid. This carves the data into k groups.
- Update step: move each centroid to the mean (average position) of the points assigned to it.
Then repeat: reassign every point to the nearest (now moved) centroid, move the centroids again, and so on. Each round the centroids settle a little more, until an entire round changes nothing. At that point k-means has converged and the clusters are final.
Watch k-means converge
Reading the two steps is one thing; watching them is another. Below is a cloud of unlabelled points. Choose how many clusters to look for, then step through. Each round, points recolour to their nearest centroid, then the centroids (the large diamonds) glide to the middle of their group. Watch them lock onto the natural clusters.
Dots are data points, coloured by their current cluster. Diamonds are the centroids.
Choosing k
K-means has one awkward catch: you must choose k before you start, but the whole reason you are clustering is that you do not know the structure. Pick k badly and you split one real group in two, or merge two into one. Two standard methods help.
- The elbow method: run k-means for several values of k and plot how tightly the points hug their centroids. As k rises this always improves, but there is usually a k where the improvement suddenly slows, forming an "elbow" in the plot. That elbow is a good choice of k.
- The silhouette score: a number for each k measuring how well points sit inside their own cluster versus how close they are to the next cluster. The k with the highest silhouette is a strong candidate.
Hierarchical clustering
K-means is not the only way. Hierarchical clustering builds a whole tree of clusters instead of a single flat grouping, and it does not need you to pick k up front. The most common form works bottom-up:
- Start with every point as its own tiny cluster.
- Repeatedly merge the two closest clusters into one.
- Continue until everything is joined into a single cluster.
The result is drawn as a dendrogram, a tree showing which clusters merged and at what distance. To get a flat set of clusters, you simply cut the tree at a chosen height: cut low for many small clusters, cut high for a few large ones. This is its big advantage over k-means, you decide the number of clusters after seeing the structure, not before.
| K-means | Hierarchical | |
|---|---|---|
| Choose k first? | Yes | No, decide by cutting the tree |
| Output | Flat groups | A tree (dendrogram) |
| Speed on big data | Fast | Slower |
Strengths and pitfalls
K-means is popular because it is simple and fast, but it has real limitations worth knowing for the exam and for practice.
| Strengths | Pitfalls |
|---|---|
| Simple, fast, scales to large data | You must choose k in advance |
| Easy to understand and implement | Sensitive to the initial centroid placement |
| Works well on round, well-separated clusters | Struggles with elongated or oddly shaped clusters |
| Gives a clear centre for each group | Outliers can drag centroids off-centre |
Key points and practice
- Clustering is unsupervised: it finds groups in unlabelled data.
- It relies on a distance measure, usually Euclidean; rescale features first.
- K-means repeats two steps: assign points to the nearest centroid, then move centroids to the mean, until convergence.
- You must choose k; the elbow method and silhouette score help.
- Hierarchical clustering builds a dendrogram and lets you pick the number of clusters afterwards.
- K-means is fast but sensitive to initialisation and the choice of k.
In the assignment step, every data point is assigned to the nearest centroid, dividing the data into k groups. In the update step, each centroid is moved to the mean position of the points assigned to it. These two steps repeat, reassigning points and moving centroids, until an entire round produces no change, at which point the algorithm has converged.
Supervised learning trains on data that already carries the correct answers (labels), while clustering is unsupervised and works on unlabelled data, discovering groups from the data's structure alone. Choosing k is a problem because k-means needs the number of clusters set in advance, yet the reason for clustering is that the true structure is unknown. A poor k splits genuine groups or merges distinct ones; the elbow method and silhouette score are used to estimate a sensible k.
An advantage of hierarchical clustering is that it does not require the number of clusters to be chosen in advance; it builds a dendrogram and the number of clusters is selected afterwards by cutting the tree at a chosen height. A weakness of k-means is that it is sensitive to the initial placement of centroids, so different random starts can produce different clusterings, and it also requires k to be fixed beforehand.