DBSCAN and hierarchical clustering: when shape and structure matter

DBSCAN: clusters as dense regions

k-means asks which centre a point is nearest. DBSCAN asks a different question: is this point in a crowded neighbourhood?

Two parameters define the answer. eps is a radius. min_samples is how many points must be within that radius for a point to count as a core point. Core points that are within eps of each other join into one cluster. Points near a cluster but not themselves core are border points, and points in neither category are labelled noise, with cluster id -1.

from sklearn.cluster import DBSCAN
labels = DBSCAN(eps=0.5, min_samples=5).fit_predict(X_scaled)
(labels == -1).sum()      # how many were called noise

Three consequences follow directly, and they are exactly the things k-means could not do.

Clusters can be any shape. Two interleaved crescents, a ring around a blob, a long winding band: DBSCAN follows density, so shape is irrelevant. k-means cannot find any of them.

You do not specify the number of clusters. It emerges from the density structure.

Outliers are labelled as outliers rather than being forced into a group. For many purposes this alone justifies the method.

Where DBSCAN struggles

Varying density. One eps for the whole dataset means a value that separates a dense region will merge everything in a sparse one, and a value tuned for the sparse region will fragment the dense one. This is the main practical limitation.

HDBSCAN solves it by building a hierarchy across all density levels and extracting the most stable clusters from it. It has one intuitive parameter (the minimum cluster size) and it is generally the better default now. It is a separate free package and it is worth installing.

Choosing eps. The standard method: compute each point’s distance to its min_samples-th nearest neighbour, sort those distances, and plot them. The curve has a knee, and eps at the knee is a good starting value. This is a more reliable elbow than the k-means one because the quantity being plotted is directly meaningful.

High dimensions. Density is a volume-based notion, and volume behaves badly in high dimensions for the reasons in the k-NN lesson. Reduce dimensions first.

Hierarchical clustering: the whole tree

Instead of one partition, build a nested sequence. Agglomerative clustering starts with every point as its own cluster and repeatedly merges the two closest, recording the order. The result is a dendrogram: a tree you can cut at any height to get any number of clusters.

from scipy.cluster.hierarchy import linkage, dendrogram, fcluster
Z = linkage(X_scaled, method="ward")
labels = fcluster(Z, t=5, criterion="maxclust")

The linkage choice defines what “closest” means between two clusters, and it changes the results substantially:

• Ward minimises the increase in within-cluster variance. Produces compact, similar-sized clusters. The usual default.
• Complete uses the maximum distance between members. Compact clusters, sensitive to outliers.
• Average uses the mean distance. A middle option.
• Single uses the minimum distance. Can follow chains of points, which finds elongated shapes and also produces the chaining effect where two distinct clusters merge because of one bridging point.

The dendrogram itself is often the real output. Being able to see that two segments merge at a low height (they are similar) while a third joins only at the top (it is different) tells you more than any flat partition, and it is the reason hierarchical clustering survives in fields like biology where the nesting is the object of interest.

Its cost is quadratic in memory and roughly cubic in time, so it is impractical above about 20,000 rows without approximation.

Choosing between the three

• Roughly spherical groups, large data, need speed: k-means.
• Arbitrary shapes, unknown cluster count, outliers you want identified: HDBSCAN.
• Small data, and you want to see the nesting: hierarchical with a dendrogram.
• You want soft assignments and elliptical clusters: Gaussian mixture.

And run at least two of them. If k-means and HDBSCAN broadly agree, the structure is probably real. If they disagree completely, that disagreement is the most informative result you have, and it usually means the groups are not well separated in the space you built.