SyntaxPilot
Courses/Machine Learning/Lesson 44
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Machine Learning · Lesson 44 of 90

Hierarchical clustering and DBSCAN

agglomerative clusteringdivisive clusteringlinkage (single, complete, average, Ward)dendrogramdensity-based clusteringDBSCANepsmin_samplescoreborder and noise pointsHDBSCAN

Machine Learning Full Course · Episode 44. Every code sample below was run with Python 3.13, NumPy 2.5.3, pandas 3.0.5, SciPy 1.18.1 and scikit-learn 1.9.1; the output shown is the real output. Riya's shops, houses, lakeside roads, GPS glitches, market lanes and suburbs are all made up for teaching. Because we made the data ourselves, we know the "true" groups, which lets us check whether each method found them.

The big idea: k-means (Episode 43) made us choose k before starting, only finds round blobs, and pushes every point into some cluster, even rubbish. Today fixes all three. Hierarchical clustering builds a whole family tree of clusters: agglomerative clustering starts with every point alone and keeps merging the two closest groups; divisive clustering starts with one group and keeps splitting. The rule for "how far apart are two groups" is the linkage (single, complete, average, Ward). The tree is drawn as a dendrogram, and cutting it at a height gives any number of clusters afterwards. Density-based clustering thinks in crowds instead: DBSCAN calls a point core if at least min_samples points (counting itself) lie within distance eps, grows clusters through chains of core points, adds border points at the edges and labels everything else noise (-1). It finds clusters of any shape and never asks for k. Choose eps with a k-distance plot; when crowds have very different densities, HDBSCAN looks at every eps at once and keeps the clusters that last longest.

Sources: M. Ester, H.-P. Kriegel, J. Sander and X. Xu, "A density-based algorithm for discovering clusters in large spatial databases with noise", KDD-96, pp. 226-231, AAAI Press, 1996 (bibbase); R. J. G. B. Campello, D. Moulavi and J. Sander, "Density-based clustering based on hierarchical density estimates", 2013, doi:10.1007/978-3-642-37456-2_14 (knowledge-base page); the docstrings of the installed scikit-learn 1.9.1 and SciPy 1.18.1: AgglomerativeClustering (linkage ward / complete / average / single; ward needs euclidean), DBSCAN (eps, min_samples counts the point itself, labels_ of -1 = noise, core_sample_indices_), HDBSCAN (min_cluster_size), BisectingKMeans (divisive), scipy.cluster.hierarchy.linkage / fcluster / dendrogram.

Words you need first

  • Clustering, cluster, label, unsupervised learning (Episode 43): clustering puts similar (close) rows into the same group without any answer column; each row's group number is its label (here a cluster number, not a given answer).
  • Euclidean distance (Episode 3): straight-line distance. From (1, 1) to (1.5, 1.2) it is √(0.5² + 0.2²) ≈ 0.54 km. Manhattan distance adds the moves along each axis instead, like walking city blocks: |0.5| + |0.2| = 0.7.
  • k-means, centroid, inertia (Episode 43): k-means puts k centres and gives each row to the nearest one; inertia is the sum of squared distances from each row to its own centroid.
  • Broadcasting (Episode 2): X[:, None] - X subtracts every row from every row without a loop; with np.linalg.norm(..., axis=2) it gives the table of pairwise distances (every row to every row).
  • np.bincount: counts how often each whole number appears: np.bincount([0, 1, 1]) is [1 2]. minlength=2 also shows a count of 0.
  • np.flatnonzero: the positions where a condition is True: np.flatnonzero([5, 0, 7] > 1) would be [0 2].
  • fit, fit_predict, labels_ (Episode 43): fit runs the algorithm; fit_predict also returns each row's cluster; labels_ holds them after fit.
  • k-nearest neighbours (Episode 27): a classifier that labels a new row like its nearest labelled rows. We use it once to label new points.

The real-life hook: zones at every level

Riya works with 8 partner shops, A to H, on a map (x and y in km, made up). Her manager wants delivery zones but does not know how many: maybe for four riders, maybe for two. She wants to see every option before deciding.

k-means would need a separate run for each k, and the answers would not even nest: the 2-zone answer need not be made of whole 4-zone zones. A simpler idea:

  1. Start with every shop as its own zone (8 zones).
  2. Merge the two closest zones.
  3. Repeat until everything is one zone.

You get every level at once: 8, 7, 6, ... 1 zones, each level made by joining two zones of the level below.

Bottom-up and top-down

  • Agglomerative clustering (bottom-up): start with n clusters of one point each and merge. Agglomerate means to collect into a heap. It is like a family tree read from the children upward: siblings join into a family, families into a clan.
  • Divisive clustering (top-down): start with one cluster holding all n points and split. scikit-learn's BisectingKMeans does this: it splits a cluster in two with k-means (k = 2, "bisecting" means cutting in two), then splits again, until it has the number of clusters you asked for (Practice 5).
  • Both give a hierarchy: a tree of clusters inside clusters. So both are hierarchical clustering.

One question before we code: the distance between two shops is easy. How far apart are two groups of shops?

Linkage: the distance between two groups

Think of two families deciding whether they live close to each other.

Linkage Group distance = In plain words
single the closest pair (one point from each group) if any two people are near, the families count as near
complete the farthest pair near only if everyone is near everyone
average the average over all pairs the typical distance
Ward how much the inertia rises if you merge them merge the pair that keeps clusters tightest and roundest

Example with groups {A, B} and {F, G}: single linkage looks only at the nearest pair across them, complete only at the farthest pair. The rule you pick is called the linkage. AgglomerativeClustering uses Ward by default.

Agglomerative clustering from scratch (single linkage)

import numpy as np
P = {"A": (1, 1), "B": (1.5, 1.2), "C": (5, 5), "D": (5.4, 4.6),
     "E": (6, 5.5), "F": (1.2, 6), "G": (2, 6.5), "H": (9, 1)}
names = list(P); X = np.array(list(P.values()))                      # 8 shops on Riya's map (km), made up
D = np.linalg.norm(X[:, None] - X, axis=2)                               # every shop-to-shop distance
groups = [[i] for i in range(len(X))]                                    # start: every shop is its own cluster
def link(g, h): return D[np.ix_(g, h)].min()                             # single linkage: closest pair
def nm(g): return "".join(names[i] for i in g)                          # cluster name, e.g. "CDE"
while len(groups) > 1:
    pairs = [(link(g, h), a, b) for a, g in enumerate(groups) for b, h in enumerate(groups) if a < b]
    d, a, b = min(pairs)                                                 # the two closest clusters ...
    print(f"merge {nm(groups[a]):>7} + {nm(groups[b]):<5} at {d:.2f} km")
    groups[a] = groups[a] + groups[b]; del groups[b]                     # ... become one

Output:

merge       A + B     at 0.54 km
merge       C + D     at 0.57 km
merge       F + G     at 0.94 km
merge      CD + E     at 1.08 km
merge     CDE + FG    at 3.35 km
merge      AB + CDEFG at 4.81 km
merge ABCDEFG + H     at 5.09 km

Line by line:

  • D is the (8, 8) table of every shop-to-shop distance.
  • groups starts as [[0], [1], ..., [7]]: every shop its own cluster.
  • D[np.ix_(g, h)] picks the block of distances between every shop in group g and every shop in group h; .min() takes the closest pair: single linkage.
  • Each round lists every pair of groups with its distance, min(pairs) picks the closest, and the two lists are joined.
  • The small, tight merges come first: A + B at 0.54 km, C + D at 0.57, F + G at 0.94, then E joins CD at 1.08.
  • Then the big jumps: CDE + FG at 3.35, AB + CDEFG at 4.81, and last of all the lonely shop H at 5.09. Seven merges for eight shops: the full merge history.

The dendrogram, and cutting it

That merge history drawn as a tree is a dendrogram (from the Greek word for tree). The shops are the leaves at the bottom. Each join is a merge, drawn at the height of its merge distance: A and B join at height 0.54, H joins everything at 5.09.

Now the manager's question is easy. Cutting the dendrogram means drawing a horizontal line at some height: every branch the line crosses is one cluster.

  • Cut at 1.5 km: the line crosses 4 branches: four zones, AB, FG, CDE, and H alone.
  • Cut at 4 km: three zones: AB, CDEFG, H.
  • Long vertical branches mean a big gap before the next merge: those clusters are really separate. A good place to cut is across the longest branches.

SciPy does all of this. linkage returns the merge table (often called Z), and fcluster cuts the tree either at a height (criterion="distance") or into an exact number of clusters (criterion="maxclust").

import numpy as np
from scipy.cluster.hierarchy import linkage, fcluster
P = {"A": (1, 1), "B": (1.5, 1.2), "C": (5, 5), "D": (5.4, 4.6),
     "E": (6, 5.5), "F": (1.2, 6), "G": (2, 6.5), "H": (9, 1)}
X = np.array(list(P.values()))
Z = linkage(X, method="single")                                          # the whole merge history
print(Z.round(2))                                                        # [cluster i, cluster j, distance, size]
print("shops:              ", *P)
for h in (1.5, 4):                                                       # cut the tree at a height
    print(f"cut at {h:>3} km:     ", *fcluster(Z, t=h, criterion="distance"))
print("exactly 3 clusters:", *fcluster(Z, t=3, criterion="maxclust"))

Output:

[[ 0.    1.    0.54  2.  ]
 [ 2.    3.    0.57  2.  ]
 [ 5.    6.    0.94  2.  ]
 [ 4.    9.    1.08  3.  ]
 [10.   11.    3.35  5.  ]
 [ 8.   12.    4.81  7.  ]
 [ 7.   13.    5.09  8.  ]]
shops:               A B C D E F G H
cut at 1.5 km:      1 1 3 3 3 2 2 4
cut at   4 km:      1 1 2 2 2 2 2 3
exactly 3 clusters: 1 1 2 2 2 2 2 3
  • Each row of Z is one merge: [cluster i, cluster j, distance, size of the new cluster]. Clusters 0 to 7 are the shops; each merge creates a new cluster numbered 8, 9, 10, ... So row 4, [4, 9, 1.08, 3], joins shop E (4) with cluster 9 (C + D, created in row 2, counting from 1) at 1.08 km, giving 3 shops.
  • The distances are the same as our scratch version: 0.54 up to 5.09.
  • fcluster returns one label per shop (numbered from 1). Cut at 1.5: 4 labels (1 1 3 3 3 2 2 4). Cut at 4, or t=3, criterion="maxclust": 3 labels. One tree, every answer.
  • dendrogram(Z) draws the tree (with matplotlib); dendrogram(Z, no_plot=True) returns its layout without drawing (Practice 2).

Does the linkage matter? Chaining

Two neighbourhoods of 200 houses each (west around (2, 5), east around (8, 5)), and a thin highway of 25 houses between them. Ask each linkage for two clusters.

import numpy as np, pandas as pd
from sklearn.cluster import AgglomerativeClustering
r = np.random.default_rng(0)                                             # two neighbourhoods + a highway of houses
X = np.vstack([r.normal([2, 5], .8, (200, 2)), r.normal([8, 5], .8, (200, 2)),
               np.c_[np.linspace(3, 7, 25), np.full(25, 5)] + r.normal(0, .08, (25, 2))])
true = np.repeat(["west", "east", "highway"], [200, 200, 25])
for how in ["single", "complete", "average", "ward"]:
    lab = AgglomerativeClustering(n_clusters=2, linkage=how).fit_predict(X)
    print(f"{how:8}", "sizes", np.bincount(lab), " west", np.bincount(lab[true == "west"], minlength=2),
          " east", np.bincount(lab[true == "east"], minlength=2))   # where the west / east houses went

Output:

single   sizes [424   1]  west [199   1]  east [200   0]
complete sizes [233 192]  west [200   0]  east [ 10 190]
average  sizes [218 207]  west [200   0]  east [  1 199]
ward     sizes [218 207]  west [200   0]  east [  1 199]
  • np.c_[np.linspace(3, 7, 25), np.full(25, 5)] puts 25 houses evenly along y = 5 from x = 3 to x = 7, plus a little noise.
  • sizes is how many houses each of the two clusters got; west and east show how that neighbourhood's 200 houses were split between cluster 0 and cluster 1.
  • single: sizes [424 1]. Useless: one cluster has everything except one house. Each highway house is close to the next, so single linkage hops along the road like stepping stones and joins both neighbourhoods. This is called chaining: a chain of close pairs links groups that are far apart as a whole.
  • complete: west and east separated, with 10 east houses put with the west.
  • average and ward: west and east separated with only one mistake (east [1 199]). Ward is scikit-learn's default and a good first choice.

Shapes k-means can't see: two lakeside roads

Next job. Riya's riders deliver along two curved roads that wrap around a lake, like two crescent moons: 600 drop-off points. Plus 30 GPS glitches: points recorded where nobody lives, because the phone lost its signal. She wants one zone per road, and the glitches flagged, not stuffed into a zone.

The data, used in several programs below and called HDR:

import numpy as np, pandas as pd
from sklearn.datasets import make_moons
X, road = make_moons(600, noise=.06, random_state=0)                    # drop-offs along two curved lakeside roads
X = np.vstack([X * 4, np.random.default_rng(0).uniform([-5, -3], [9, 5], (30, 2))])   # km, plus 30 GPS glitches
road = np.r_[road, [-1] * 30]                                           # -1 = glitch (noise), made up
  • make_moons(600, noise=.06, random_state=0) makes two interleaving half-circles (300 points each) and road, which says which one (0 or 1). * 4 stretches them to kilometres.
  • uniform([-5, -3], [9, 5], (30, 2)) scatters 30 random points over the map: the glitches. They get the true label -1.
  • np.r_[a, b] joins two arrays end to end. X has 630 rows.

k-means, Ward and single linkage, two clusters each; for each road, how many of its points went to cluster 0 and to cluster 1:

import numpy as np, pandas as pd
from sklearn.datasets import make_moons
X, road = make_moons(600, noise=.06, random_state=0)                    # drop-offs along two curved lakeside roads
X = np.vstack([X * 4, np.random.default_rng(0).uniform([-5, -3], [9, 5], (30, 2))])   # km, plus 30 GPS glitches
road = np.r_[road, [-1] * 30]                                           # -1 = glitch (noise), made up
from sklearn.cluster import KMeans, AgglomerativeClustering
for name, m in [("k-means", KMeans(2, n_init=10, random_state=0)), ("ward", AgglomerativeClustering(2)),
                ("single", AgglomerativeClustering(2, linkage="single"))]:
    lab = m.fit_predict(X)
    print(f"{name:8}", "road 0 ->", np.bincount(lab[road == 0], minlength=2),
          "  road 1 ->", np.bincount(lab[road == 1], minlength=2))           # how each road was split

Output:

k-means  road 0 -> [224  76]   road 1 -> [ 75 225]
ward     road 0 -> [ 78 222]   road 1 -> [300   0]
single   road 0 -> [  0 300]   road 1 -> [  0 300]
  • k-means: each road is cut in two: road 0 goes 224 / 76, road 1 goes 75 / 225.
  • ward: road 1 is all in cluster 0, but road 0 is split too (78 / 222).
  • single: both roads entirely in cluster 1. The second cluster is just 2 far-away glitches (we checked: the single-linkage sizes are [2 628]).
  • None of them can say "this point is a glitch": every point must belong somewhere.

Why? k-means and Ward want round, compact groups, so they slice straight across the curves. But a road is not round. What makes it a road is that its points sit in a continuous crowd along it.

Density-based clustering: crowds at a fair

Picture a village fair seen from above. Density means how crowded a place is: how many points are packed into a small area.

  • Core point: a person with at least 5 people within arm's reach, counting themselves: in the thick of a crowd. "Arm's reach" is a distance called eps (epsilon, the Greek letter often used for a small distance), and 5 is called min_samples.
  • Border point: someone at the edge of a crowd: within eps of a core person, but without enough neighbours of their own to be core. They belong to that crowd too.
  • Noise point: someone alone by the parking lot, near no core point at all. Noise gets the label -1.
  • A cluster is all the core points that are within eps of each other, chained together, plus their border points.

This is density-based clustering. The algorithm is DBSCAN: density-based spatial clustering of applications with noise, by Ester, Kriegel, Sander and Xu (KDD-96, 1996). Notice what is missing: you never say how many clusters.

Example: with eps = 0.6 km and min_samples = 5, a ring of radius 0.6 km around a point that holds 5 or more points (including itself) makes it core. A point with only 3 inside its ring, but a core point among them, is border. A point with 1 (itself) and no core point nearby is noise.

DBSCAN from scratch

import numpy as np, pandas as pd
from sklearn.datasets import make_moons
X, road = make_moons(600, noise=.06, random_state=0)                    # drop-offs along two curved lakeside roads
X = np.vstack([X * 4, np.random.default_rng(0).uniform([-5, -3], [9, 5], (30, 2))])   # km, plus 30 GPS glitches
road = np.r_[road, [-1] * 30]                                           # -1 = glitch (noise), made up
def dbscan(X, eps, min_samples):
    D = np.linalg.norm(X[:, None] - X, axis=2)
    near = [np.flatnonzero(row <= eps) for row in D]                     # neighbours within eps (incl. itself)
    core = np.array([len(n) >= min_samples for n in near])               # core point: a crowd around it
    lab = np.full(len(X), -1); c = 0                                     # -1 = noise until claimed
    for i in np.flatnonzero(core):
        if lab[i] != -1: continue
        lab[i] = c; todo = [i]                                           # new cluster: grow it from this core
        while todo:
            for k in near[todo.pop()]:
                if lab[k] == -1:
                    lab[k] = c                                           # core or border joins
                    if core[k]: todo.append(k)                           # only cores keep spreading
        c += 1
    return lab, core
lab, core = dbscan(X, eps=0.6, min_samples=5)
print("clusters", lab.max() + 1, "  core", core.sum(), "  border", ((lab >= 0) & ~core).sum(), "  noise", (lab == -1).sum())
print("road 0 ->", np.unique(lab[road == 0]), "  road 1 ->", np.unique(lab[road == 1]),
      "  glitches as noise:", (lab[road == -1] == -1).sum(), "of 30")

Output:

clusters 2   core 610   border 5   noise 15
road 0 -> [1]   road 1 -> [0]   glitches as noise: 15 of 30

Line by line:

  • near[i] holds every point within eps of point i, including i itself (its distance to itself is 0).
  • core is True where a point has at least min_samples neighbours.
  • Every label starts at -1 (noise until claimed).
  • From each unclaimed core point, a new cluster c grows: todo is a to-do list, and todo.pop() takes (and removes) its last point. Every neighbour of that point joins the cluster; only core points are added to the list, so only they keep spreading it. A border point joins but stops the spread there.
  • Result: 2 clusters, one per road, each road entirely in one cluster (road 0 -> [1], road 1 -> [0]; the cluster numbers are just names).
  • 610 core, 5 border, 15 noise (610 + 5 + 15 = 630).
  • All 15 noise points are glitches. The other 15 glitches happened to land right on a road, so they look exactly like real drop-offs; no method could tell those apart.

DBSCAN in scikit-learn, and choosing eps

import numpy as np, pandas as pd
from sklearn.datasets import make_moons
X, road = make_moons(600, noise=.06, random_state=0)                    # drop-offs along two curved lakeside roads
X = np.vstack([X * 4, np.random.default_rng(0).uniform([-5, -3], [9, 5], (30, 2))])   # km, plus 30 GPS glitches
road = np.r_[road, [-1] * 30]                                           # -1 = glitch (noise), made up
from sklearn.cluster import DBSCAN; from sklearn.neighbors import NearestNeighbors
db = DBSCAN(eps=0.6, min_samples=5).fit(X)
print("sklearn: clusters", db.labels_.max() + 1, "  noise", (db.labels_ == -1).sum(),
      "  core", len(db.core_sample_indices_))
for eps in [0.1, 0.3, 0.6, 1.5, 3.0]:                                    # eps too small ... too big
    lab = DBSCAN(eps=eps, min_samples=5).fit_predict(X)
    print(f"eps={eps:<4} clusters {lab.max() + 1:3}   noise {(lab == -1).sum():4}")
dist, _ = NearestNeighbors(n_neighbors=5).fit(X).kneighbors(X)           # distance to the 5th nearest (incl. itself)
k_dist = np.sort(dist[:, -1])
print("5th-neighbour dist. at 50/90/95/98%:", np.percentile(k_dist, [50, 90, 95, 98]).round(2))

Output:

sklearn: clusters 2   noise 15   core 610
eps=0.1  clusters   9   noise  583
eps=0.3  clusters   4   noise   48
eps=0.6  clusters   2   noise   15
eps=1.5  clusters   1   noise    5
eps=3.0  clusters   1   noise    0
5th-neighbour dist. at 50/90/95/98%: [0.22 0.36 0.44 0.88]
  • DBSCAN(eps=0.6, min_samples=5).fit(X) gives the same answer as ours: 2 clusters, 15 noise, 610 core points. labels_ holds the labels (-1 = noise) and core_sample_indices_ the row numbers of the core points.
  • The eps sweep: eps = 0.1 makes 583 of 630 points noise (nobody has 5 neighbours that close) and 9 little clusters. eps = 0.3: 4 clusters, 48 noise. eps = 0.6: the right answer. eps = 1.5 or 3.0: one big cluster; the roads touch through the glitches. Too small and everything is noise; too big and everything merges.

The k-distance plot. For each point, measure the distance to its 5th nearest neighbour (the same 5 as min_samples, counting the point itself), sort those distances, and plot them. NearestNeighbors(n_neighbors=5).kneighbors(X) returns each row's 5 nearest rows; the first is the row itself at distance 0, so dist[:, -1] is the 5th, counting itself.

  • Road points have close neighbours, so most of the curve is low and flat: half the points are within 0.22 km (the 50th percentile: the value below which 50% of the numbers lie).
  • Then the curve shoots up for the lonely glitches: 90% are under 0.36, 95% under 0.44, 98% under 0.88.
  • Pick eps near the knee (the bend where the curve starts shooting up). eps = 0.6 sits right in the bend.
  • For min_samples, a common rule of thumb is about twice the number of columns (2 columns → 4 or 5), and more if the data is noisy.
  • eps is a distance in your units: data in metres needs a different eps than data in km, and columns in different units must be scaled first (Practice 6).

When crowds have different densities: HDBSCAN

New city, new problem. The old market has two packed lanes of customers, 1.5 km apart (300 points each, spread 0.25 km). There are two big, spread-out suburbs (200 points each, spread 1.3 km). A small eps fits the market but turns the suburbs into noise; a big eps catches the suburbs but glues the two lanes together. One eps can't fit both.

import numpy as np
from sklearn.cluster import DBSCAN, HDBSCAN
r = np.random.default_rng(3)                                        # a crowded old market and two spread-out suburbs
X = np.vstack([r.normal([0, 0], .25, (300, 2)), r.normal([1.5, 0], .25, (300, 2)),     # two dense market lanes
               r.normal([8, 6], 1.3, (200, 2)), r.normal([8, -5], 1.3, (200, 2))])      # two sparse suburbs (km)
true = np.repeat([0, 1, 2, 3], [300, 300, 200, 200])
print("groups = cluster ids found in: lane A, lane B, north, south")
def report(name, lab):
    found = [sorted(int(c) for c in set(lab[true == g]) - {-1}) for g in range(4)]   # cluster ids in each true group
    print(f"{name:15} clusters {lab.max() + 1}  noise {(lab == -1).sum():3}  groups:", *found)
for eps in (0.2, 0.5, 1.0):
    report(f"DBSCAN eps={eps}", DBSCAN(eps=eps, min_samples=8).fit_predict(X))
report("HDBSCAN", HDBSCAN(min_cluster_size=40, copy=True).fit_predict(X))

Output:

groups = cluster ids found in: lane A, lane B, north, south
DBSCAN eps=0.2  clusters 2  noise 405  groups: [0] [0, 1] [] []
DBSCAN eps=0.5  clusters 3  noise 108  groups: [0] [0] [1] [2]
DBSCAN eps=1.0  clusters 3  noise   9  groups: [0] [0] [1] [2]
HDBSCAN         clusters 4  noise  33  groups: [2] [3] [0] [1]
  • After groups:, report prints four lists, in the order of the header line (lane A, lane B, north suburb, south suburb): the cluster ids that group's points got (noise left out). [] means the whole group became noise.
  • eps = 0.2: 405 noise points and both suburbs gone ([] []); the market lanes are found, but lane B's points are spread over clusters 0 and 1.
  • eps = 0.5 or 1.0: the suburbs appear, but lane A and lane B get the same cluster, 0.
  • HDBSCAN: 4 clusters, one per group, with 33 edge points as noise. We never gave it an eps.

How HDBSCAN works, in plain words. HDBSCAN (Campello, Moulavi and Sander, 2013) is hierarchical DBSCAN. Imagine running DBSCAN for every eps at once, from tiny to huge. As eps grows, crowds appear, grow, split apart or join, like the dendrogram's merges. HDBSCAN builds that tree of clusters and then keeps the clusters that persist (survive) over the widest range of eps: the most stable ones. The packed lanes survive as separate clusters at small eps; the suburbs exist at larger eps. You set one main knob, min_cluster_size: the smallest group you would call a cluster (Practice 4). copy=True in the code tells it to work on a copy of X and leave your array untouched.

Two errors you will meet

import numpy as np, pandas as pd
from sklearn.datasets import make_moons
X, road = make_moons(600, noise=.06, random_state=0)                    # drop-offs along two curved lakeside roads
X = np.vstack([X * 4, np.random.default_rng(0).uniform([-5, -3], [9, 5], (30, 2))])   # km, plus 30 GPS glitches
road = np.r_[road, [-1] * 30]                                           # -1 = glitch (noise), made up
from sklearn.cluster import DBSCAN, AgglomerativeClustering; import textwrap
db = DBSCAN(eps=0.6, min_samples=5).fit(X)
try: db.predict([[0, 0]])                                                # MISTAKE: label a new drop-off
except AttributeError as e: print("AttributeError:", e)
try: AgglomerativeClustering(2, linkage="ward", metric="manhattan").fit(X)   # MISTAKE: ward needs euclidean
except ValueError as e: print(*textwrap.wrap("ValueError: " + str(e), 62), sep="\n")    # wrap long lines

Output:

AttributeError: 'DBSCAN' object has no attribute 'predict'
ValueError: manhattan was provided as metric. Ward can only
work with euclidean distances (i.e. 'euclidean' and 'l2').

textwrap.wrap(text, 62) cuts a long message into lines of at most 62 characters, only so it fits the screen; print(*lines, sep="\n") prints one per line. The message itself is one sentence, quoted in full below.

  • AttributeError: 'DBSCAN' object has no attribute 'predict'. An AttributeError means the object has no method or value with that name. Unlike k-means, DBSCAN (and AgglomerativeClustering) only labels the rows it was fit on; there are no centroids to compare a new row with. For new rows, refit on all the data, or train a classifier on the labels, like k-nearest neighbours (Episode 27; the mini project does this).
  • ValueError: manhattan was provided as metric. Ward can only work with euclidean distances (i.e. 'euclidean' and 'l2'). A metric is the way distance is measured. Ward is built on inertia, which uses squared straight-line distance, so it only works with Euclidean distance (also called L2). For Manhattan distance, use linkage="average" or "complete".

One more limit: memory

Agglomerative clustering needs every pairwise distance: with n rows, n(n − 1)/2 pairs. Its memory grows like O(n²) ("order n squared": double the rows, four times the memory).

for n in (1_000, 10_000, 100_000, 1_000_000):
    pairs = n * (n - 1) // 2                                         # each pair once (SciPy's condensed form)
    print(f"n={n:>9,}  pairs {pairs:>18,}  memory at 8 bytes each: {pairs * 8 / 1e9:10,.3f} GB")

Output:

n=    1,000  pairs            499,500  memory at 8 bytes each:      0.004 GB
n=   10,000  pairs         49,995,000  memory at 8 bytes each:      0.400 GB
n=  100,000  pairs      4,999,950,000  memory at 8 bytes each:     40.000 GB
n=1,000,000  pairs    499,999,500,000  memory at 8 bytes each:  3,999.996 GB

100,000 rows means about 5 billion pairs (10 billion if the full n × n table is stored), about 40 GB at 8 bytes per number. Use agglomerative clustering on thousands of rows, not millions.

Common mistakes

Mistake Exact message / symptom Why Fix
Single linkage on noisy data sizes [424 1] Chaining: stepping stones join groups Ward or average linkage
k-means (or Ward) on curved shapes each road cut [224 76] Assumes round blobs DBSCAN / HDBSCAN
eps too small eps = 0.1: noise 583 of 630 Nobody has 5 neighbours that close k-distance plot: eps at the knee
eps too big eps = 1.5 or 3.0: clusters 1 Crowds touch and merge Smaller eps, k-distance plot
One eps for mixed densities eps 0.2 loses the suburbs; 0.5 glues the lanes Density differs between groups HDBSCAN
Same eps in different units km: 2 clusters; metres: 0 clusters, 630 noise eps is a distance in your units Scale the data, then re-choose eps
db.predict(new_rows) AttributeError: 'DBSCAN' object has no attribute 'predict' Labels only the fitted rows Refit, or train a classifier on the labels
Ward + Manhattan ValueError: manhattan was provided as metric. Ward can only work with euclidean distances (i.e. 'euclidean' and 'l2'). Ward is built on inertia metric="euclidean", or average linkage
Agglomerative on millions of rows huge memory (100,000 rows: about 40 GB) O(n²) pairwise distances Sample, or use DBSCAN / HDBSCAN / k-means
Treating -1 as a cluster a "cluster" of glitches -1 means noise Count clusters with labels_.max() + 1

Mini project: road zones and a glitch filter for new drop-offs

Build Riya's zoning tool: choose eps automatically from the k-distance curve (95th percentile), run DBSCAN, check the zones against the true roads, then label new drop-offs: a new point takes the zone of its nearest core point, unless that core point is more than eps away, in which case it is flagged as a glitch (-1). This is the "train a classifier on the labels" fix for the missing predict.

import numpy as np, pandas as pd
from sklearn.datasets import make_moons
X, road = make_moons(600, noise=.06, random_state=0)                    # drop-offs along two curved lakeside roads
X = np.vstack([X * 4, np.random.default_rng(0).uniform([-5, -3], [9, 5], (30, 2))])   # km, plus 30 GPS glitches
road = np.r_[road, [-1] * 30]                                           # -1 = glitch (noise), made up
from sklearn.cluster import DBSCAN; from sklearn.neighbors import NearestNeighbors, KNeighborsClassifier
k = 5                                                                    # min_samples
dist, _ = NearestNeighbors(n_neighbors=k).fit(X).kneighbors(X)
eps = float(np.percentile(dist[:, -1], 95))                              # eps from the k-distance curve
db = DBSCAN(eps=eps, min_samples=k).fit(X); lab = db.labels_
print(f"eps chosen {eps:.2f} km   clusters {lab.max() + 1}   noise {(lab == -1).sum()}")
print(pd.crosstab(pd.Series(road, name="true road"), pd.Series(lab, name="zone")))
cores = X[db.core_sample_indices_]
knn = KNeighborsClassifier(n_neighbors=1).fit(cores, lab[db.core_sample_indices_])   # label = nearest core's zone
new = np.array([[0, 4], [4, -2], [8, 4]])                                # 3 new drop-offs (made up)
d_core = NearestNeighbors(n_neighbors=1).fit(cores).kneighbors(new)[0][:, 0]
zone = np.where(d_core <= eps, knn.predict(new), -1)                     # too far from every core = glitch
for p, z, d in zip(new, zone, d_core):
    print(f"new drop-off {p} -> zone {z:2}   (nearest core {d:.2f} km)")

Output:

eps chosen 0.44 km   clusters 2   noise 17
zone       -1    0    1
true road              
-1         17    4    9
 0          0    0  300
 1          0  300    0
new drop-off [0 4] -> zone  1   (nearest core 0.09 km)
new drop-off [ 4 -2] -> zone  0   (nearest core 0.09 km)
new drop-off [8 4] -> zone -1   (nearest core 1.95 km)
  • The 95th percentile of the 5th-neighbour distances gives eps = 0.44 km: 2 clusters, 17 noise.
  • pd.crosstab (a count table of true road against zone): road 0 is all in zone 1 (300), road 1 all in zone 0 (300). All 17 noise points are glitches; 13 glitches landed on a road and joined it.
  • KNeighborsClassifier(n_neighbors=1) trained on the core points labels a new point like its nearest core point.
  • (0, 4) is 0.09 km from a core point of zone 1; (4, −2) is 0.09 km from zone 0; (8, 4) is 1.95 km from the nearest core point, more than eps, so it is flagged -1, a likely glitch.

Practice

1. Scratch agglomerative clustering with complete linkage (homework). Compare with SciPy.

Solution
import numpy as np
P = {"A": (1, 1), "B": (1.5, 1.2), "C": (5, 5), "D": (5.4, 4.6),
     "E": (6, 5.5), "F": (1.2, 6), "G": (2, 6.5), "H": (9, 1)}
names = list(P); X = np.array(list(P.values()))
D = np.linalg.norm(X[:, None] - X, axis=2)
groups = [[i] for i in range(len(X))]
def link(g, h): return D[np.ix_(g, h)].max()                             # complete linkage: FARTHEST pair
def nm(g): return "".join(names[i] for i in g)
while len(groups) > 1:
    pairs = [(link(g, h), a, b) for a, g in enumerate(groups) for b, h in enumerate(groups) if a < b]
    d, a, b = min(pairs)
    print(f"merge {nm(groups[a]):>7} + {nm(groups[b]):<5} at {d:.2f} km")
    groups[a] = groups[a] + groups[b]; del groups[b]
from scipy.cluster.hierarchy import linkage
print("scipy complete:", linkage(X, method="complete")[:, 2].round(2))

Output:

merge       A + B     at 0.54 km
merge       C + D     at 0.57 km
merge       F + G     at 0.94 km
merge      CD + E     at 1.12 km
merge     CDE + FG    at 4.83 km
merge      AB + CDEFG at 6.73 km
merge ABCDEFG + H     at 9.26 km
scipy complete: [0.54 0.57 0.94 1.12 4.83 6.73 9.26]

The only change is .max() instead of .min(): the farthest pair. The first four merges are almost the same (E joins CD at 1.12 instead of 1.08), but the big merges happen much higher (4.83, 6.73, 9.26 instead of 3.35, 4.81, 5.09), because complete linkage measures the farthest pair. SciPy's method="complete" gives exactly the same heights.

2. The four linkages on the 8 shops, and the Ward dendrogram's leaf order (homework: method='ward').

Solution
import numpy as np
from scipy.cluster.hierarchy import linkage, fcluster, dendrogram
P = {"A": (1, 1), "B": (1.5, 1.2), "C": (5, 5), "D": (5.4, 4.6),
     "E": (6, 5.5), "F": (1.2, 6), "G": (2, 6.5), "H": (9, 1)}
X = np.array(list(P.values()))
for how in ["single", "complete", "average", "ward"]:
    Z = linkage(X, method=how)
    print(f"{how:8} heights", Z[:, 2].round(2), "  3 clusters:", *fcluster(Z, t=3, criterion="maxclust"))
d = dendrogram(linkage(X, method="ward"), labels=list(P), no_plot=True)    # the tree, without drawing it
print("ward leaf order (left to right):", *d["ivl"])

Output:

single   heights [0.54 0.57 0.94 1.08 3.35 4.81 5.09]   3 clusters: 1 1 2 2 2 2 2 3
complete heights [0.54 0.57 0.94 1.12 4.83 6.73 9.26]   3 clusters: 1 1 2 2 2 2 2 3
average  heights [0.54 0.57 0.94 1.1  4.09 5.54 7.12]   3 clusters: 1 1 2 2 2 2 2 3
ward     heights [0.54 0.57 0.94 1.23 6.28 8.73 8.85]   3 clusters: 1 1 2 2 2 2 2 3
ward leaf order (left to right): H A B F G E C D

All four linkages give the same 3 clusters here (AB, CDEFG, H), because the shops are well separated; they differ in the merge heights. Ward's heights are the largest at the top (6.28, 8.73, 8.85), because they measure an inertia increase, not a plain distance. d["ivl"] is the left-to-right order of the leaves in the drawn tree: H, A B, F G, E C D.

3. DBSCAN on the roads with min_samples 3 and 15 (homework).

Solution
import numpy as np, pandas as pd
from sklearn.datasets import make_moons
X, road = make_moons(600, noise=.06, random_state=0)                    # drop-offs along two curved lakeside roads
X = np.vstack([X * 4, np.random.default_rng(0).uniform([-5, -3], [9, 5], (30, 2))])   # km, plus 30 GPS glitches
road = np.r_[road, [-1] * 30]                                           # -1 = glitch (noise), made up
from sklearn.cluster import DBSCAN
for ms in (3, 5, 15):
    lab = DBSCAN(eps=0.6, min_samples=ms).fit_predict(X)
    print(f"min_samples={ms:<3} clusters {lab.max() + 1}  noise {(lab == -1).sum():3}  glitches flagged {(lab[road == -1] == -1).sum():2} of 30"
          f"  real drop-offs called noise {(lab[road >= 0] == -1).sum()}")

Output:

min_samples=3   clusters 2  noise  15  glitches flagged 15 of 30  real drop-offs called noise 0
min_samples=5   clusters 2  noise  15  glitches flagged 15 of 30  real drop-offs called noise 0
min_samples=15  clusters 2  noise  19  glitches flagged 19 of 30  real drop-offs called noise 0

On this data min_samples 3, 5 and 15 all find the two roads with no real drop-off called noise. The larger 15 is stricter: 19 points are noise instead of 15, and all 19 are glitches. A larger min_samples needs denser crowds, so it flags more loners, and with sparse data it would start calling real points noise.

4. HDBSCAN with min_cluster_size 10, 40, 100 and 400 (homework).

Solution
import numpy as np
from sklearn.cluster import HDBSCAN
r = np.random.default_rng(3)
X = np.vstack([r.normal([0, 0], .25, (300, 2)), r.normal([1.5, 0], .25, (300, 2)),
               r.normal([8, 6], 1.3, (200, 2)), r.normal([8, -5], 1.3, (200, 2))])
for mcs in (10, 40, 100, 400):
    lab = HDBSCAN(min_cluster_size=mcs, copy=True).fit_predict(X)
    print(f"min_cluster_size={mcs:<4} clusters {lab.max() + 1:2}  noise {(lab == -1).sum():3}  sizes", np.bincount(lab[lab >= 0]))

Output:

min_cluster_size=10   clusters  4  noise  18  sizes [200 200 291 291]
min_cluster_size=40   clusters  4  noise  33  sizes [200 199 285 283]
min_cluster_size=100  clusters  3  noise   3  sizes [200 600 197]
min_cluster_size=400  clusters  0  noise 1000  sizes []

10 and 40: the 4 true groups. 100: only 3 clusters, one of size 600: the two market lanes (300 each) are glued, because HDBSCAN now prefers the bigger, longer-lasting cluster over two smaller ones. 400: no group is that big, so everything is noise. min_cluster_size should be the size of the smallest group you care about.

5. Divisive clustering: BisectingKMeans on the 8 shops for 2, 3 and 4 clusters.

Solution
import numpy as np
from sklearn.cluster import BisectingKMeans
P = {"A": (1, 1), "B": (1.5, 1.2), "C": (5, 5), "D": (5.4, 4.6),
     "E": (6, 5.5), "F": (1.2, 6), "G": (2, 6.5), "H": (9, 1)}
X = np.array(list(P.values()))
print("shops:       ", *P)
for k in (2, 3, 4):                                                      # top-down: keep splitting with 2-means
    print(f"{k} clusters:  ", *BisectingKMeans(n_clusters=k, random_state=0).fit_predict(X))

Output:

shops:        A B C D E F G H
2 clusters:   1 1 0 0 0 1 1 0
3 clusters:   2 2 0 0 0 1 1 0
4 clusters:   3 3 0 0 0 2 2 1

Top-down: the first split puts A, B, F, G (west) against C, D, E, H (east). The next split separates AB from FG; the next separates H from CDE. The 4-cluster answer, AB / FG / CDE / H, is the same as cutting the single-linkage dendrogram at 1.5 km, reached from the other direction.

6. Measure the roads in metres instead of km. What happens to eps = 0.6?

Solution
import numpy as np, pandas as pd
from sklearn.datasets import make_moons
X, road = make_moons(600, noise=.06, random_state=0)                    # drop-offs along two curved lakeside roads
X = np.vstack([X * 4, np.random.default_rng(0).uniform([-5, -3], [9, 5], (30, 2))])   # km, plus 30 GPS glitches
road = np.r_[road, [-1] * 30]                                           # -1 = glitch (noise), made up
from sklearn.cluster import DBSCAN
from sklearn.preprocessing import StandardScaler
for name, data in [("km", X), ("metres", X * 1000), ("metres, scaled", StandardScaler().fit_transform(X * 1000))]:
    lab = DBSCAN(eps=0.6, min_samples=5).fit_predict(data)
    print(f"{name:15} eps=0.6  clusters {lab.max() + 1:2}  noise {(lab == -1).sum():3}")

Output:

km              eps=0.6  clusters  2  noise  15
metres          eps=0.6  clusters  0  noise 630
metres, scaled  eps=0.6  clusters  1  noise   4

In metres every distance is 1,000 times larger, so 0.6 (now 0.6 metres) is far too small: 0 clusters, all 630 points noise. After StandardScaler (Episode 16) the units are standard deviations, and 0.6 is now too big: 1 cluster. eps always has to be re-chosen (k-distance plot) for the units the data is in.

7. Check the quiz with real points.

Solution
import numpy as np
from sklearn.cluster import DBSCAN
pts = np.array([[0, 0], [0.5, 0], [0, 0.5], [-0.5, 0], [0, -0.5],    # a tight crowd around (0, 0)
                [1.4, 0],                                             # P: near (0.5, 0) only
                [2.3, 0],                                             # P's other neighbour
                [6, 6]])                                              # a loner
db = DBSCAN(eps=1.0, min_samples=4).fit(pts)
D = np.linalg.norm(pts[:, None] - pts, axis=2)
print("points within 1.0 (counting itself):", (D <= 1.0).sum(axis=1))
print("core:", np.isin(np.arange(len(pts)), db.core_sample_indices_).astype(int))
print("labels:", db.labels_)

Output:

points within 1.0 (counting itself): [5 6 5 5 5 3 2 1]
core: [1 1 1 1 1 0 0 0]
labels: [ 0  0  0  0  0  0 -1 -1]

Point 5 is P at (1.4, 0): 3 points within 1.0 counting itself (itself, (0.5, 0) and (2.3, 0)), fewer than 4, so not core. But (0.5, 0) is core (6 within reach), so P gets that cluster's label 0: a border point. Point 6 at (2.3, 0) has only 2 and no core point within reach: noise. The loner at (6, 6): noise.

Quick quiz

1. DBSCAN(eps=1.0, min_samples=4). Point P has 2 other points within 1.0 (3 counting itself), and one of them is a core point. Is P core, border, noise, or its own cluster?

Answer

Border. P has only 3 points (counting itself) within eps, fewer than min_samples = 4, so it is not core. But it is within eps of a core point, so it is a border point and joins that core point's cluster (checked in Practice 7).

2. Single linkage returns cluster sizes [424 1]. What probably happened?

Answer

Chaining: a line of close points (the highway houses) linked two groups into one, leaving a single point as the "second cluster". Use Ward or average linkage.

3. DBSCAN with eps = 0.1 labels 583 of 630 points -1. Raise or lower eps?

Answer

Raise it: almost nobody has 5 neighbours within 0.1, so almost everything is noise. Read eps from the knee of the k-distance plot (here about 0.6).

Interview questions

  1. Agglomerative vs divisive clustering? Agglomerative starts with every point alone and merges the closest groups; divisive starts with one group and splits (for example BisectingKMeans). Both build a hierarchy.
  2. What is linkage? Name four. The rule for the distance between two groups: single (closest pair), complete (farthest pair), average (mean of all pairs), Ward (smallest increase in inertia).
  3. What is chaining, and which linkage suffers from it? Single linkage joins far-apart groups through a chain of close points (two neighbourhoods plus a highway gave [424 1]).
  4. What is a dendrogram and how do you get clusters from it? A tree of merges, with each join at its merge height. Cut it with a horizontal line (fcluster(Z, t, criterion="distance")) or ask for a number of clusters (criterion="maxclust"). Cut across long branches.
  5. Main advantage of hierarchical clustering over k-means? You don't choose k in advance; one tree gives every number of clusters, and the levels nest.
  6. Main drawback? Memory and time grow at least like n², because every pairwise distance is needed (100,000 rows: about 40 GB).
  7. Explain DBSCAN. A point is core if at least min_samples points (counting itself) lie within eps. Clusters are core points connected through each other plus border points within eps of them; everything else is noise (-1). No k needed; any shape (Ester et al., 1996).
  8. Core vs border vs noise? Core: enough neighbours within eps. Border: not enough, but within eps of a core point. Noise: neither.
  9. How do you choose eps and min_samples? min_samples around twice the number of columns (more for noisy data); eps at the knee of the sorted k-distance plot, on scaled data.
  10. When does DBSCAN fail? When clusters have very different densities (one eps can't fit both), and in high dimensions where distances become similar. HDBSCAN handles the first.
  11. What does HDBSCAN add? It considers every eps at once, builds a tree of clusters and keeps the most stable ones (Campello et al., 2013). Main knob: min_cluster_size.
  12. How do you label new points after DBSCAN? There is no predict: refit, or train a classifier (such as k-nearest neighbours) on the labels, and flag points far from every core point as noise.
  13. Why must Ward use Euclidean distance? It is defined through inertia, a sum of squared Euclidean distances.

Glossary

Term Meaning (plain words + example)
Hierarchical clustering Clustering that builds a tree of clusters inside clusters, bottom-up or top-down
Hierarchy Levels inside levels: shops → zones → regions
Agglomerative clustering Bottom-up: start with every point alone and keep merging the two closest groups
Divisive clustering Top-down: start with one group and keep splitting it
BisectingKMeans scikit-learn's divisive method: split a cluster in two with k-means, repeat
Merge history The list of merges and their distances: A + B at 0.54 km ... H at 5.09 km
Linkage The rule for the distance between two groups
Single linkage Group distance = the closest pair across the groups
Complete linkage Group distance = the farthest pair across the groups
Average linkage Group distance = the average of all pairs across the groups
Ward linkage Merge the two groups whose merge raises inertia the least; the default in AgglomerativeClustering
Chaining Single linkage joining far groups through stepping stones: sizes [424 1]
Dendrogram The merge history drawn as a tree, each join at its merge height
Leaf A single point at the bottom of a dendrogram: shop A
Merge height The distance at which a join happens: H joins at 5.09
Cutting a dendrogram Drawing a horizontal line; each branch it crosses is a cluster: at 1.5 km, 4 zones
Merge table (Z) SciPy's output of linkage: one row [cluster i, cluster j, distance, size] per merge
linkage (SciPy) Computes the merge table: linkage(X, method="single")
fcluster Cuts the tree: criterion="distance" at a height, criterion="maxclust" for a number of clusters
dendrogram (SciPy) Draws the tree; no_plot=True returns the layout, ivl the leaf order
AgglomerativeClustering scikit-learn's agglomerative clustering: AgglomerativeClustering(2, linkage="ward")
Pairwise distances Every point's distance to every other point: 8 shops → an (8, 8) table
O(n²) Grows with the square of n: double the rows, four times the memory
Density How crowded a place is: how many points within a small distance
Density-based clustering Clusters = crowds of points; loners are noise
DBSCAN Density-based spatial clustering of applications with noise (Ester, Kriegel, Sander, Xu, 1996)
eps The neighbourhood radius: "arm's reach", 0.6 km for the roads
min_samples Points needed within eps, counting the point itself, to be core: 5
Core point Has at least min_samples points within eps: 610 on the roads
Border point Not core, but within eps of a core point; joins its cluster: 5 on the roads
Noise point Neither core nor near a core point; label -1: 15 on the roads
Label -1 DBSCAN's / HDBSCAN's mark for noise, not a cluster
labels_, core_sample_indices_ After fit: every row's label; the row numbers of the core points
k-distance plot Each point's distance to its k-th nearest neighbour, sorted; pick eps at the knee
Knee The bend where a curve starts to shoot up: about 0.6 km here
Percentile The value below which a given share of numbers lies: 50% of points within 0.22 km
NearestNeighbors scikit-learn tool that finds each row's nearest rows and their distances
HDBSCAN Hierarchical DBSCAN (Campello, Moulavi, Sander, 2013): looks at every eps and keeps clusters that persist longest
Stable cluster A cluster that survives over a wide range of eps
min_cluster_size HDBSCAN's main knob: the smallest group you'd call a cluster: 40
make_moons scikit-learn helper making two interleaving half-circles: our two lakeside roads
GPS glitch A made-up wrong location where nobody lives: our noise
Euclidean distance (L2) Straight-line distance: (1, 1) to (1.5, 1.2) is 0.54
Manhattan distance Sum of moves along each axis, like city blocks: (1, 1) to (1.5, 1.2) is 0.7
Metric The way distance is measured: "euclidean", "manhattan"
Inertia Sum of squared distances to the own cluster's centre (Episode 43); Ward is built on it
Scaling Putting columns on comparable scales (StandardScaler); eps must be re-chosen after
pd.crosstab A count table of one column against another: true road vs zone
KNeighborsClassifier Labels a new row like its nearest labelled rows (Episode 27): used to label new drop-offs
AttributeError Python error for a missing method or value: 'DBSCAN' object has no attribute 'predict'
ValueError Python error for a bad value: Ward with metric="manhattan"

Summary

  • Hierarchical clustering builds a tree of clusters: agglomerative merges bottom-up, divisive (BisectingKMeans) splits top-down.
  • The linkage decides how groups are compared: single (closest pair), complete (farthest), average, Ward (smallest rise in inertia, the default).
  • A dendrogram draws the merges at their heights; cut it at a height or ask for a count with fcluster (1.5 km → 4 zones, 4 km → 3).
  • Single linkage chains through stepping stones ([424 1]); Ward and average separated the neighbourhoods with one mistake.
  • k-means and Ward slice across curved shapes (224 / 76) and cannot flag noise.
  • DBSCAN: core (min_samples within eps, counting itself), border, noise (-1). On the roads: 2 clusters, 610 core, 5 border, 15 noise, all glitches.
  • eps too small → all noise (583 of 630); too big → one cluster. Choose it at the knee of the k-distance plot, in the data's units.
  • HDBSCAN handles mixed densities by keeping clusters that persist over many eps values: all 4 groups found.
  • DBSCAN has no predict; Ward needs Euclidean distance; agglomerative clustering needs O(n²) memory.

Next episode: Gaussian mixture models: soft clustering with probabilities, the EM algorithm, AIC and BIC.