Clustering: Finding Groups in Data That Carries No Labels
Definition
Clustering
Clustering is a technique used to group a set of objects so that objects in the same group (or cluster) are more similar to each other than to those in other groups.
Clustering is a form of unsupervised learning, so it works on unlabelled data and is never told what the right groups are.
The algorithm reads the features of each data point and groups points that resemble each other more than they resemble anything else.
The groups it returns are discovered rather than predefined, which means the analyst has to work out afterwards what each cluster represents.
Common Mistake
Clustering is not classification, even though both end with data points sorted into groups.
Classification is trained on labelled examples and assigns a known label, while clustering starts with no labels and invents the groups.
A cluster is an approximation, not a verified category, so treating cluster 3 as though it were a confirmed customer type overstates what the algorithm found.
The Three Steps Every Clustering Algorithm Takes
Feature extraction decides which measurable characteristics of each data point the algorithm will look at.
Similarity measurement applies a mathematical distance between points, most often the Euclidean distance, to say how alike two points are.
Grouping then assigns points to clusters so that points inside a cluster are close together and points in different clusters are far apart.
Analogy
Clustering is like tidying an unlabelled library.
You cannot read the genre off the spine, so you group books by whatever they have in common, such as length, language and subject vocabulary.
You end up with piles that clearly belong together, and only then do you decide what to call each pile.
K-Means: The Standard Clustering Algorithm
K-means splits the data into $k$ separate, non-overlapping clusters, where $k$ is chosen by the analyst before the algorithm runs.
Initialise by placing $k$ centroids at random positions in the data.
Assign every data point to whichever centroid is nearest to it.
Update each centroid to the mean position of all the points now assigned to it.
Repeat the assign and update steps until the centroids stop moving.
What a Centroid Actually Is
A centroid is the average position of every point in its cluster, so it sits at the centre of the group.
It is a calculated position rather than a real data point, and usually no observation sits exactly on it.
Because it is a mean, one extreme outlier can drag a centroid a long way and distort the cluster around it.
Common Mistake
K-means assumes clusters are roughly round and similar in size, because every point simply goes to the nearest centre.
On two long curved bands of data it will slice straight across both rather than following either.
It also requires $k$ up front, so running it with $k = 3$ on data that really contains five groups will merge groups that should stay apart.
Three Alternatives for Data That K-Means Handles Badly
DBSCAN groups points that are packed closely together and labels points in sparse regions as outliers.
It needs two settings: ε (epsilon), the radius of the neighbourhood around a point, and minPts, the number of neighbours needed for a dense region.
A point with at least minPts neighbours inside ε is a core point, and a cluster grows by joining core points to each other and to their neighbours.
It finds clusters of any shape and does not need the number of clusters in advance, but it struggles when different clusters have very different densities.
Hierarchical clustering repeatedly merges the two most similar clusters, building a tree of nested groupings from individual points up to one whole.
The analyst can cut the tree at any level, which means the number of clusters is decided after seeing the structure rather than before.
It suits data where nested relationships matter, such as building a taxonomy, but it is slow on very large data sets.
Mean shift moves a sliding window towards the densest nearby region and treats each point of convergence as a cluster centre.
It starts from an estimate, computes the mean of the points inside the window, moves the window to that mean, and repeats until it settles.
Like DBSCAN it discovers the number of clusters itself and copes with irregular shapes, at the cost of more computation.
Preparing the Data Before Clustering
Every algorithm here decides membership by distance, so a feature measured on a large scale dominates the result.
Clustering customers on age in years and income in dollars without adjustment means income decides the clusters almost single-handedly.
Normalisation or standardisation puts the features on a comparable scale and is a required step, not an optional refinement.
Common Mistake
The supervised metrics do not apply here, because there are no correct answers to compare against.
Accuracy, precision and recall all need labels, so they cannot measure a clustering.
Use the silhouette score, inertia or the Davies-Bouldin index instead, which judge how tight and how well separated the clusters are.
Market Segmentation: Clustering at Work
Market segmentation is the application the syllabus names, and it uses purchasing data to break a customer base into distinct groups.
The business does not know in advance what types of customer it has, which is exactly why clustering rather than classification fits the problem.
Example
Segmenting a Retailer's Customers
Data collection gathers each customer's total spend, purchase frequency and basket size.
Clustering with k-means on those three features returns groups such as high spenders who shop often, occasional shoppers with low spend, and bulk buyers who visit rarely but spend heavily.
Interpretation names each cluster by looking at what its centroid values actually say.
Action then targets each group differently, with loyalty rewards for the frequent high spenders and bulk offers for the infrequent large buyers.
Other Uses of Clustering
Image compression groups similar pixel colours and stores one representative colour per group.
Network monitoring clusters normal traffic patterns so that anything falling outside every cluster can be flagged for inspection.
Document organisation groups articles by shared vocabulary without anyone tagging the topics first.
Active recall
Why does clustering count as unsupervised learning?
List the four steps of the k-means algorithm in order.
What is a centroid, and why is it usually not a real data point?
Give one type of data on which k-means performs poorly, and name an algorithm that handles it better.
Why must features be normalised before clustering?
Why can accuracy and recall not be used to evaluate a clustering?
