Machine Learning Foundations / Core / 02.31
Clustering: finding groups by yourself
Nobody labels the data, so the model sorts it into groups of look-alikes. Learn how, with k-means built from scratch.
13 min readFree
Groups nobody labelled
The last lesson ended with a promise: finding groups when nobody gives you the answers. Here it is. Picture a shop owner with ten thousand customers and no idea who they are. Nobody has written "bargain hunter" or "loyal regular" next to a name. Could a computer still sort them into sensible piles?
Yes. That job is called clustering. It is the best-known task in unsupervised learning, where the data comes with no answers attached. If that phrase is new, the lesson on Unsupervised Learning covers it. Google's course defines clustering as a technique designed to group unlabeled examples based on their similarity to each other. And it adds a useful contrast: if the examples are labeled, this kind of grouping is called classification.
Key words
- Cluster
- A group of things that look alike, found by the computer.
- Clustering
- Sorting data into clusters without being told the right answer.
- Distance
- A number for how far apart two things are. Small distance means similar.
- Centroid
- The middle of a cluster: the average of all its points. Also called the cluster centre.
- k
- How many clusters you ask for. You choose it.
- Within-cluster spread
- How far the points sit from their own centre, added up. Small means tight groups. Scikit-learn calls it inertia.
We will meet the main families of clustering, then build the most popular one, k-means, in plain Python.
What does "similar" mean?
A computer cannot feel that two customers are alike. It needs a number. The usual trick is to turn each thing into a short list of measurements, then measure the distance between lists.
Think of a map. Two cafes a street apart are close. Two cafes in different cities are far. A customer works the same way, only the "map" has axes like age, visits per month and money spent. Two customers with similar numbers sit near each other.
This is the same idea as in K-Nearest Neighbors, where a new point looks at its closest neighbours. There the neighbours already have labels. In clustering they do not, so the distances alone must reveal the groups.
Scikit-learn's table lists the "geometry" each method uses, and for k-means it is simply distances between points. Google's overview says clustering groups points based on defined similarity measures.
The families of clustering
Wikipedia says the notion of a cluster cannot be precisely defined, which is one of the reasons why there are so many clustering algorithms. That sounds scary, but the methods fall into a few families. Each gets its own lesson. Here is one plain line for each.
Exclusive clustering: every point belongs to exactly one group. Wikipedia calls this strict partitioning. K-means is the famous example.
Overlapping clustering, often called fuzzy: a point may belong to several groups at once, or to each one a little. A song can be both "jazz" and "chill". Wikipedia describes fuzzy c-means as a soft version of k-means, where each point has a fuzzy degree of belonging to each cluster.
Hierarchical clustering: groups sit inside bigger groups, like folders inside folders. Wikipedia explains it builds a hierarchy of clusters that merge at different distances, drawn as a tree called a dendrogram.
Probabilistic clustering, with mixture models: each point gets a chance of belonging to each group. Wikipedia describes Gaussian mixture models as keeping probabilistic assignments to clusters instead of fixed ones.
Density-based clustering: a cluster is a crowded area, with thin, empty space around it. Wikipedia says methods such as DBSCAN define clusters as connected dense regions in the data space, and lonely points count as noise.
Tip
You do not need to pick a favourite. Wikipedia notes there is no objectively correct clustering algorithm. The right one depends on the shape of your data and what you need.
K-means, step by step
K-means is the simplest and most used. Scikit-learn says it clusters data by trying to separate samples in groups of equal variance, and that it requires the number of clusters to be specified. Wikipedia puts it as: each observation belongs to the cluster with the nearest mean.
Picture sorting a messy classroom into three study tables. You drop three flags on the floor. Everyone walks to the nearest flag. Then each flag moves to the middle of the people around it. Some people now find a different flag closer, so they move. Repeat until nobody moves.
- 1
1. Pick k centres
Choose k starting centres. The simplest way is to take k random points from your data.
- 2
2. Assign
Every point joins the group of its nearest centre.
- 3
3. Move
Each centre jumps to the average position of its group. Wikipedia calls steps 2 and 3 the assignment step and the update step.
- 4
4. Repeat
Do steps 2 and 3 again. Stop when the centres no longer move.
Wikipedia notes that this method is guaranteed to stop in a finite number of steps, but only at a local optimum. A local optimum is a decent answer that is not necessarily the best one. Because the start is random, the common fix is to run it several times and keep the best.
Now we will build it. Our made-up data has three blobs of 30 points each, so we know the answer. The code runs k-means once with k = 3 and prints the centres after every round. Then, for k from 1 to 5, it runs ten times and prints the smallest within-cluster spread.
In words: for every point, find the distance to its nearest centre, square it, and add them all up. This is scikit-learn's inertia formula. Lower is better, and zero is best.
import random
random.seed(3)
# Made-up data: three blobs of 30 points each.
blobs = [(2, 2), (8, 3), (5, 8)]
points = [(random.gauss(cx, 1), random.gauss(cy, 1)) for cx, cy in blobs for _ in range(30)]
def dist2(a, b):
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
def mean(group):
return (sum(p[0] for p in group) / len(group), sum(p[1] for p in group) / len(group))
def kmeans(k, show=False):
centres = random.sample(points, k) # step 1: pick k starting centres
for it in range(1, 20):
groups = [[] for _ in range(k)]
for p in points: # step 2: each point joins its nearest centre
nearest = min(range(k), key=lambda i: dist2(p, centres[i]))
groups[nearest].append(p)
new = [mean(g) if g else centres[i] for i, g in enumerate(groups)] # step 3: move centres
if show:
print("round", it, [(round(x, 2), round(y, 2)) for x, y in new])
if new == centres: # step 4: stop when nothing moves
break
centres = new
spread = sum(dist2(p, c) for g, c in zip(groups, centres) for p in g)
return centres, spread
print("one run with k = 3, centres after each round:")
_, spread = kmeans(3, show=True)
print("spread of that run:", round(spread, 1))
print()
for k in range(1, 6):
best = min(kmeans(k)[1] for _ in range(10)) # 10 restarts, keep the tightest
print("k =", k, "within-cluster spread", round(best, 1))Output
one run with k = 3, centres after each round: round 1 [(3.45, 2.12), (4.86, 7.83), (8.7, 2.62)] round 2 [(1.95, 1.6), (4.86, 7.83), (8.12, 2.97)] round 3 [(1.95, 1.6), (4.86, 7.83), (8.12, 2.97)] spread of that run: 164.7 k = 1 within-cluster spread 1383.6 k = 2 within-cluster spread 670.1 k = 3 within-cluster spread 164.7 k = 4 within-cluster spread 137.9 k = 5 within-cluster spread 113.3
Read the first block. The starting centres were random points. After round 1 they sat at (3.45, 2.12), (4.86, 7.83) and (8.7, 2.62). In round 2 two of them moved. In round 3 nothing moved, so the run stopped. The final centres, near (1.95, 1.6), (4.86, 7.83) and (8.12, 2.97), are close to the true blob centres we used to make the data: (2, 2), (5, 8) and (8, 3).
That run ended with a spread of 164.7, which matches the k = 3 line in the table. Nobody told the program there were three blobs. It found them from distances alone.
Choosing k
Here is the catch: k-means needs k before it starts, and real data does not come with a sign saying how many groups it has. So how do you pick?
Look at the table again. With k = 1 the spread is 1383.6. It drops to 670.1 at k = 2, then to 164.7 at k = 3. After that it creeps down: 137.9, then 113.3. More groups always make the spread smaller, because the centres sit closer to the points. With one centre per point it would reach zero, and that tells you nothing.
The elbow
Plot the spread against k and look for the bend, like an elbow in an arm. Here the big drops stop at k = 3. Wikipedia warns the notion of an "elbow" is not well-defined and this is known to be unreliable, so treat it as a hint.
The silhouette
For one point, take a: its average distance to the others in its own cluster, and b: its average distance to the points in the next nearest cluster. The silhouette is (b minus a) divided by the larger of the two. Scikit-learn says a higher score relates to a model with better defined clusters. Average it over all points to score a whole clustering.
Your own purpose
Wikipedia shows k = 2 can suit the famous Iris flower data better than k = 3, even though it holds three flower types. The best k is the one that is useful for the job, such as three email campaigns you can actually run.
Quick check
You run k-means for k = 1 to 6. The spread falls steeply until k = 4, then barely changes. What is a reasonable pick?
Scaling matters
K-means decides who is close by adding up differences in every measurement. If one measurement uses huge numbers, it drowns out the rest. The feature scaling lesson explains the fix in detail. Here you can see why clustering needs it.
Take three people described by age in years and income in dollars. Ana is 25, Ben is 60 and Cleo is 26. Their incomes are close. Is Ana more like Ben or like Cleo?
import math
# (age in years, yearly income in dollars)
people = {"Ana": (25, 30000), "Ben": (60, 30500), "Cleo": (26, 31000)}
def dist(a, b):
return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
def show(label, data):
print(label)
print(" Ana to Ben :", round(dist(data["Ana"], data["Ben"]), 3))
print(" Ana to Cleo:", round(dist(data["Ana"], data["Cleo"]), 3))
show("raw numbers", people)
# Squeeze each column to run from 0 to 1.
ages = [p[0] for p in people.values()]
incomes = [p[1] for p in people.values()]
scaled = {
name: ((a - min(ages)) / (max(ages) - min(ages)),
(i - min(incomes)) / (max(incomes) - min(incomes)))
for name, (a, i) in people.items()
}
show("scaled to 0-1", scaled)Output
raw numbers Ana to Ben : 501.224 Ana to Cleo: 1000.0 scaled to 0-1 Ana to Ben : 1.118 Ana to Cleo: 1.0
With the raw numbers, Ben looks about twice as close to Ana as Cleo does (501 against 1000). That is silly: Ben is 35 years older, and Cleo is one year older. A gap of 500 dollars simply outweighs a gap of 35 years, because dollars are bigger numbers. After squeezing each column onto a 0 to 1 scale, Cleo is the nearer one (1.0 against 1.118), which matches common sense.
Tip
Always scale before measuring distances. Scikit-learn also warns that in very high-dimensional spaces, Euclidean distances tend to become inflated, and suggests running a dimensionality reduction first. The lesson on Dimensionality Reduction covers that.
One more limit to know. Scikit-learn says k-means assumes clusters are convex and isotropic, which is not always the case, and that it responds poorly to elongated clusters or irregular shapes. In plain words, it likes round, similar-sized blobs. For rings, moons or snakes, a density-based method is a better fit.
Judging clusters without answers
In supervised learning you can compare predictions with the right answers. Clustering has no answer key, so how do you know if the groups are any good? Wikipedia is honest here: evaluation of clustering results is as difficult as the clustering itself.
It lists four approaches.
Internal
Score the groups using only the data, such as the silhouette. Wikipedia warns that such scores can only compare how well a method follows its own aim, not necessarily how useful the clusters are.
External
Compare with known labels, if you happen to have some. Wikipedia points out that in practice we usually do not have them, and that labels show only one possible grouping.
Manual and indirect
Ask a person who knows the subject to look at the groups, or test whether they help in the real job, such as whether the email campaigns for each group sell more.
Tip
A quick habit that works: for each cluster, look at five real examples and write a one-line name for it. If you cannot name a group, it may not mean anything.
Quick check
Your clusters have a great silhouette score, but the shop owner cannot tell the groups apart in real life. What does that suggest?
Where clustering is used
Google lists common uses: market segmentation, social network analysis, search result grouping, medical imaging, image segmentation and anomaly detection. Two are close to what designers meet.
Customer groups
Market segmentation is clustering customers. Each cluster can get its own message, product or design. The shop owner from the start would see a few clear types instead of ten thousand names.
Pictures
Image segmentation splits a picture into regions by grouping pixels that look alike, such as sky, grass and a person. Scikit-learn shows this on a picture of coins.
Shorter data
Google notes that clustering can replace many features with a single cluster ID, saving storage and processing. A customer becomes "group 3" instead of fifty numbers.
What to remember
The task
Clustering groups similar things with no labels, using distance as the measure of similar. There are many families, because there is no single right idea of a cluster.
K-means
Pick k centres, assign every point to the nearest one, move each centre to the middle of its group, and repeat until nothing moves. Run it several times, because the start is random.
Care
Choose k with the elbow and silhouette as hints, scale your data first, and judge the groups by whether they are useful.
Next: exclusive clustering, where every point belongs to exactly one group.
Sources
Last updated on 16 November 2026
Learn with me
Every lesson is free. I add new ones as I learn. Have a question, or want help with your own work? Book a short call.