Machine Learning Foundations / Core / 02.32
Exclusive clustering: one point, one group
Every point gets exactly one group. See why k-means can start badly, how k-means++ and k-medoids help, and how DBSCAN spots strays.
13 min readFree
One point, one group
The last lesson ended with a promise: exclusive clustering, where every point belongs to exactly one group. Think of seating guests at a wedding. Each guest gets one table. Nobody sits at two, and nobody stands in the hall.
You have already met the most famous method of this kind. Scikit-learn says k-means divides a set of samples into disjoint clusters, which means no point is shared. This lesson goes further. We see why k-means can start badly, a cousin that ignores strays, and a method allowed to say "this point belongs nowhere".
Key words
- Exclusive clustering
- Every point is placed in exactly one group. Also called hard clustering.
- Centre
- The middle point of a group. In k-means it is the average of the group.
- Initialization
- Choosing where the centres start, before any moving happens.
- Local optimum
- A result that is good compared with its neighbours, but not the best possible.
- Medoid
- A real point from the data, picked to be the middle of its group.
- Outlier
- A point far from all the others. A stray.
- Noise
- The label DBSCAN gives to points that are too alone to join any group.
Two lines of k-means
K-means picks k centres, then repeats two moves: every point joins its nearest centre, and every centre jumps to the average of its group. It stops when nothing moves. The Clustering lesson built it step by step, so we will not do that again.
One detail from that lesson matters now. Wikipedia says k-means is guaranteed to stop, but only at a local optimum, a decent answer that may not be the best. Where the centres start decides which answer you land in.
Why a bad start gives bad groups
Imagine four study tables in the four corners of a hall, and four flags dropped on the floor. If the flags land one near each corner, everyone walks to a sensible table. If two land in the same corner, another corner gets none, and its people walk far to a flag. The flags then settle in that poor arrangement and stay.
That is exactly what goes wrong in k-means. Wikipedia says random initialization is often used, but it can result in poor cluster quality. Scikit-learn adds that the k-means++ initialization scheme starts the centres generally distant from each other, leading to probably better results than random initialization.
k-means++: spread the starts out
K-means++ is only a smarter way to choose the starting centres. After that, ordinary k-means takes over.
- 1
1. First centre
Pick one point completely at random from the data.
- 2
2. Measure
For every point, find how far it is from its nearest centre so far.
- 3
3. Pick the next
Choose the next centre at random, but give far-away points a bigger chance. Wikipedia says the chance is proportional to a point's contribution to the overall error.
- 4
4. Repeat
Do steps 2 and 3 until you have k centres. Then run k-means as usual.
In words: D(x) is the distance from point x to its nearest centre. Square it, then divide by the same number added up over all points. A point twice as far away is four times as likely to be picked. It is still luck, not a rule, so two centres can occasionally land close together.
Wikipedia notes that this method achieves an O(log k) approximation of the optimum solution. Plain random starts make no such promise.
Random starts against k-means++
Let us test it. Our made-up data has four blobs of 25 points each, one per corner, so the right answer is clear. The code runs k-means 10 times from random starts and 10 times from k-means++ starts, and prints the final spread of each run. Spread means the squared distances from every point to its nearest centre, added up. Lower is better.
import random
random.seed(5)
# Made-up data: four blobs of 25 points each.
blobs = [(2, 2), (9, 2), (2, 9), (9, 9)]
points = [(random.gauss(cx, 0.8), random.gauss(cy, 0.8)) for cx, cy in blobs for _ in range(25)]
def dist2(a, b):
return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2
def random_start(k):
return random.sample(points, k)
def plus_plus_start(k):
centres = [random.choice(points)]
while len(centres) < k:
# Far-away points get a bigger chance of being picked next.
weights = [min(dist2(p, c) for c in centres) for p in points]
centres.append(random.choices(points, weights)[0])
return centres
def kmeans(centres):
while True:
groups = [[] for _ in centres]
for p in points:
nearest = min(range(len(centres)), key=lambda i: dist2(p, centres[i]))
groups[nearest].append(p)
new = [(sum(p[0] for p in g) / len(g), sum(p[1] for p in g) / len(g)) if g else c
for g, c in zip(groups, centres)]
if new == centres:
return sum(min(dist2(p, c) for c in centres) for p in points)
centres = new
for name, start in [("random", random_start), ("k-means++", plus_plus_start)]:
spreads = [round(kmeans(start(4)), 1) for _ in range(10)]
print(name, "10 runs")
print(" ", spreads)
print(" best", min(spreads), "worst", max(spreads))
# A bigger test: how often does each start give a bad result (spread above 200)?
for name, start in [("random", random_start), ("k-means++", plus_plus_start)]:
bad = sum(kmeans(start(4)) > 200 for _ in range(500))
print(name, "bad runs out of 500:", bad)Output
random 10 runs [159.6, 159.6, 734.8, 159.6, 159.6, 159.6, 159.6, 757.0, 159.6, 159.6] best 159.6 worst 757.0 k-means++ 10 runs [159.6, 744.6, 159.6, 159.6, 159.6, 159.6, 159.6, 159.6, 159.6, 159.6] best 159.6 worst 744.6 random bad runs out of 500: 160 k-means++ bad runs out of 500: 49
Look at the first list. Eight of the ten random runs reached 159.6, the best value. Two got stuck at 734.8 and 757.0, almost five times worse. The k-means++ list had one such run (744.6) in ten.
Ten runs are a small test, so the last two lines repeat it 500 times and count the bad runs, those above 200. Random starts went bad 160 times (32 in every 100). K-means++ went bad 49 times (about 10 in every 100).
Tip
K-means++ lowers the odds of a bad start. It does not remove them. Still run k-means several times and keep the run with the smallest spread.
k-medoids: a real point as the centre
In k-means the centre is an average, so it can land in empty space between points. K-medoids uses a medoid instead. Wikipedia defines the medoid of a cluster as the object in the cluster whose total dissimilarity to all the others is minimal, so it is the most centrally located point. And unlike the centres of other methods, the medoid is an actual point in the cluster.
Averages are easy to drag. Picture a cafe: six regulars come 4 to 8 times a month, and one tourist came 60 times. The code finds the average and the medoid.
# Cafe visits per month for six regulars, plus one tourist who came 60 times.
visits = [4, 5, 5, 6, 7, 8, 60]
mean = sum(visits) / len(visits)
# The medoid is the member whose total distance to all the others is smallest.
medoid = min(visits, key=lambda v: sum(abs(v - other) for other in visits))
print("mean :", round(mean, 2))
print("medoid :", medoid)Output
mean : 13.57 medoid : 6
The tourist pulls the average up to 13.57, a number no regular is near. The medoid stays at 6, a real customer who looks like the others. Wikipedia says the same: because k-medoids minimizes a sum of pairwise dissimilarities instead of a sum of squared Euclidean distances, it is more robust to noise and outliers than k-means.
Gain
Strays pull the centre less, and the centre is a real example you can look at, such as one actual customer.
Cost
Wikipedia says the runtime of most k-medoids algorithms is quadratic in the size of the dataset, so big data is slow.
Same weak spot
The first step picks k medoids at random, which can give different results. It also does not suit clusters that are not round.
Mini-batch k-means for big data
Scikit-learn's MiniBatchKMeans uses small random subsets of the data in each round to cut the computation time, and its results are generally only slightly worse than the standard algorithm.
DBSCAN: groups are crowded places
So far the groups were round blobs around a centre. DBSCAN thinks differently. Scikit-learn says it views clusters as areas of high density separated by areas of low density. Picture a map of a city at night. Crowds gather in squares and markets, and the empty streets between them are the gaps. A tourist alone on a quiet road is not part of any crowd.
It is still exclusive: a point is in one group, or in none. The name stands for density-based spatial clustering of applications with noise. Wikipedia says it marks as outliers the points that lie alone in low-density regions.
It needs two settings, which scikit-learn calls eps and min_samples. They define what "crowded" means.
eps
A distance: how far you look around a point. Think of the radius of a circle drawn around it. The Greek letter is epsilon.
min_samples
A head count: how many points must be inside that circle (Wikipedia counts the point itself) for the spot to count as crowded.
Core point
A point whose circle holds at least min_samples points. Core points are the heart of a crowd.
Scikit-learn says higher min_samples or lower eps mean a higher density is needed to form a cluster, and that eps is crucial to choose appropriately and usually cannot be left at the default value.
How DBSCAN decides
- 1
1. Look around
Take a point that has not been checked and count the points within eps of it.
- 2
2. Core or not
If the count is at least min_samples, it is a core point and starts a new group. If not, mark it noise for now.
- 3
3. Spread
Add every neighbour to the group. When a neighbour is a core point too, add its neighbours as well. Keep going until the crowd stops growing.
- 4
4. Edges
Neighbours that are not core points join the group, but they do not spread it further. Wikipedia says they form its edge.
- 5
5. Next
Pick another unchecked point. Points never reached by any crowd stay as noise.
Notice what is missing: you never say how many groups you want. Wikipedia says DBSCAN does not require the number of clusters to be specified in advance.
DBSCAN from scratch, with strays
Our made-up data has two blobs of 30 points, plus five stray points placed far from both. Noise gets the label -1. The code uses eps = 1.0 and min_samples = 4.
import math
import random
random.seed(11)
# Made-up data: two blobs of 30 points, plus 5 stray points far from both.
points = [(random.gauss(2, 0.5), random.gauss(2, 0.5)) for _ in range(30)]
points += [(random.gauss(7, 0.5), random.gauss(6, 0.5)) for _ in range(30)]
points += [(5, 0), (0, 7), (9, 1), (4.5, 4), (10, 9)]
def neighbours(i, eps):
return [j for j, q in enumerate(points) if math.dist(points[i], q) <= eps]
def dbscan(eps, min_samples):
labels = [None] * len(points) # None = not looked at yet, -1 = noise
cluster = -1
for i in range(len(points)):
if labels[i] is not None:
continue
near = neighbours(i, eps)
if len(near) < min_samples:
labels[i] = -1 # not dense enough: noise for now
continue
cluster += 1 # a new core point starts a new group
labels[i] = cluster
queue = [j for j in near if j != i]
while queue:
j = queue.pop()
if labels[j] == -1:
labels[j] = cluster # a noise point on the edge joins in
if labels[j] is not None:
continue
labels[j] = cluster
more = neighbours(j, eps)
if len(more) >= min_samples:
queue.extend(more) # j is a core point, so keep spreading
return labels
labels = dbscan(eps=1.0, min_samples=4)
for name in sorted(set(labels)):
count = labels.count(name)
print("noise" if name == -1 else f"group {name}", ":", count, "points")
print("strays marked as noise:", [labels[i] for i in range(60, 65)])Output
noise : 5 points group 0 : 30 points group 1 : 30 points strays marked as noise: [-1, -1, -1, -1, -1]
It found two groups of 30, exactly our two blobs, without being told there were two. All five strays came out as noise (-1), and each of them sits in neither group. K-means would have forced every stray into a group.
When round blobs fail
Scikit-learn says clusters found by DBSCAN can be any shape, as opposed to k-means which assumes that clusters are convex shaped. Convex means roughly "bulging outward, like a ball". A banana or a ring is not convex.
Here is the classic test: two moons, an upper arc and a lower arc that hook around each other, 40 points each. The code asks k-means (k = 2) and DBSCAN (eps = 0.3, min_samples = 3) to split them, then counts which group each moon's points landed in. The DBSCAN function is the same as before, just written shorter.
import math
import random
random.seed(2)
# Two moons: the top arc and the bottom arc, 40 points each, a little jitter.
def arc(cx, cy, flip):
out = []
for i in range(40):
angle = math.pi * i / 39
x = cx + math.cos(angle)
y = cy + flip * math.sin(angle)
out.append((x + random.gauss(0, 0.04), y + random.gauss(0, 0.04)))
return out
points = arc(0, 0, 1) + arc(1, 0.4, -1)
truth = [0] * 40 + [1] * 40
def kmeans2(points):
centres = [points[0], points[-1]]
for _ in range(20):
groups = [[], []]
for p in points:
groups[0 if math.dist(p, centres[0]) <= math.dist(p, centres[1]) else 1].append(p)
centres = [(sum(p[0] for p in g) / len(g), sum(p[1] for p in g) / len(g)) for g in groups]
return [0 if math.dist(p, centres[0]) <= math.dist(p, centres[1]) else 1 for p in points]
def dbscan(points, eps, min_samples):
labels = [None] * len(points)
cluster = -1
near = lambda i: [j for j, q in enumerate(points) if math.dist(points[i], q) <= eps]
for i in range(len(points)):
if labels[i] is not None:
continue
if len(near(i)) < min_samples:
labels[i] = -1
continue
cluster += 1
labels[i] = cluster
queue = near(i)
while queue:
j = queue.pop()
if labels[j] in (None, -1):
labels[j] = cluster
if len(near(j)) >= min_samples:
queue.extend(near(j))
return labels
def report(name, labels):
print(name)
for moon in (0, 1):
found = [labels[i] for i in range(80) if truth[i] == moon]
print(" moon", moon, "->", {g: found.count(g) for g in sorted(set(found))})
report("k-means, k = 2", kmeans2(points))
report("DBSCAN, eps = 0.3, min_samples = 3", dbscan(points, 0.3, 3))Output
k-means, k = 2
moon 0 -> {0: 9, 1: 31}
moon 1 -> {0: 30, 1: 10}
DBSCAN, eps = 0.3, min_samples = 3
moon 0 -> {0: 40}
moon 1 -> {1: 40}K-means cut straight through both moons. The top moon is split into 9 and 31 points, the bottom moon into 30 and 10. DBSCAN followed the crowds along each arc and put each moon in one group: 40 points and 40 points.
Quick check
You have a map of shop locations along two winding rivers, plus a few shops far out in the countryside. Which method fits best?
What to remember
Starts matter
K-means can stop at a poor answer if its first centres are badly placed. K-means++ spreads them out, and several runs keep the best.
Centres
K-medoids uses a real point as the centre and handles strays better. Mini-batch k-means trades a little quality for speed on big data.
Density
DBSCAN grows groups from crowded places, finds any shape, needs no k, and labels loners as noise. Spend your effort choosing eps.
Next: overlapping clustering, where one point can belong to more than 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.