DBSCAN & hierarchical clustering

At 3 a.m., a map of 50,000 delivery GPS pings gives you two winding roads, a busy depot, and 300 points scattered across nearby fields. You ask k-means for three clusters.

It draws three round-ish territories around three centroids. One territory cuts both roads in half. Another claims the field points because every point must belong somewhere. The answer is mathematically tidy and operationally useless.

This is the problem these methods address. Clustering groups unlabelled observations according to a similarity that depends on the geometry of the data.

k-means assigns points to the nearest centroid, so its clusters are effectively convex regions around means. That works well for large, round, similarly sized groups when you know the number of groups. It is a poor description of a winding road.

DBSCAN groups dense, connected regions and can leave isolated observations unassigned. Hierarchical clustering builds a nested history of merges and lets you inspect that history before choosing a cut.

They answer different questions: DBSCAN asks, “Where is the data locally dense?” Hierarchical clustering asks, “Which groups merge first, and what does the whole nesting structure look like?”

DBSCAN: a cluster is a dense, connected place

DBSCAN stands for Density-Based Spatial Clustering of Applications with Noise. Its central idea is literal: a cluster is a region where you can keep finding enough nearby points.

It has two important parameters:

• eps is the radius of a point’s neighbourhood.
• min_samples is the minimum number of samples in that neighbourhood for the point to be a core point.

A core point drives cluster growth. A non-core point within eps of a core point is a border point. A point that is neither is noise.

In scikit-learn, min_samples includes the point itself. Thus, min_samples=4 requires the point plus at least three other samples within eps. Check this convention when translating implementations.

A small neighbourhood, counted carefully

Return to the delivery map. Suppose a local patch has been scaled into coordinate units where one unit is roughly 100 metres. Consider these five pings:

P = (0.0, 0.0)
Q = (1.0, 0.0)
R = (0.0, 1.0)
S = (1.0, 1.0)
U = (0.2, 0.2)

Set eps=1.1 and min_samples=4.

For P, the distances to Q and R are both 1, and the distance to U is about 0.28. Including P, its neighbourhood contains P, Q, R, and U; therefore P is core.

Q has Q, P, S, and U nearby. R likewise has R, P, S, and U. The central point U is core too.

S has only S, Q, and R within radius 1.1, so it is not core. However, it is within eps of core points Q and R; it is a border point and joins their cluster.

A distant ping such as (4.0, 4.0) is neither core nor close to a core point. DBSCAN marks it as noise, usually with label -1 in scikit-learn.

The arithmetic matters. Change eps to 0.9 and P loses Q and R; its neighbourhood may no longer meet the minimum. Change it to 2.0 and separate roads may become connected through points that should not form one route.

How cluster growth actually works

DBSCAN proceeds roughly as follows:

1. Pick an unvisited point and find samples within eps.
2. If there are too few, mark it as noise for now.
3. If it is core, start a cluster and put its neighbours in a work queue.
4. Add queued points that are reachable from the growing region. When a queued point is core, add its neighbours to the queue too.
5. Continue until the queue is empty, then start another cluster.

The crucial mechanism is density connectivity: a chain of nearby core points can bend, loop, or follow a crescent. No centroid is needed. DBSCAN asks whether a point can be reached through locally dense neighbourhoods, not whether it is close to its cluster’s average location.

That is why two interleaved crescents can remain separate. Each has its own chain of core points, while the gap has no sufficiently dense bridge.

A border point can be close to more than one cluster. Its assignment may then depend on expansion order, so do not treat every boundary label as a precise scientific fact.

Choosing eps without guessing blindly

First choose a sensible distance. Raw latitude and longitude are not ordinary Cartesian coordinates: project local maps into metres, or use an appropriate geographic distance for global locations. For ordinary numeric features, scaling is often necessary. If distance ranges from 0 to 5,000 while stop count ranges from 0 to 20, distance can dominate without scaling.

Standardisation changes the geometry, so it is a statement about what similarity should mean, not harmless preprocessing.

A practical starting point is a k-distance plot. For each point, calculate the distance to its k-th nearest neighbour, sort those distances, and look for a sharp upward bend separating the dense bulk from sparse points. This is a diagnostic, not an oracle; no clear bend may mean there is no useful global density threshold.

min_samples controls how easily a local accident becomes a cluster seed. Increasing it requires stronger support and usually labels more points as noise. Decreasing it permits small groups but makes random clumps and bridges more influential. In high dimensions, distances become less informative, so review the curse of dimensionality before trusting neighbourhood density in hundreds of raw features.

What DBSCAN does well, and what it does not

DBSCAN is a strong candidate when:

• groups have winding, ring-like, or other non-convex shapes;
• isolated observations should be identified rather than forced into groups;
• the number of groups is unknown;
• neighbourhood searches are practical for the dataset size.

It is not automatically an outlier detector. “Noise” means “not density-reachable under this distance, eps, and min_samples.” A legitimate sparse village may be labelled noise beside a dense city, while a fraudulent point inside a dense region receives an ordinary cluster label. For rare-event detection, compare with anomaly detection.

Its main structural limitation is one global density threshold. If one road has pings every metre and another every 20 metres, a radius that follows the first may erase the second; a radius that rescues the second may merge nearby roads in the first.

HDBSCAN and OPTICS address varying density by considering multiple scales. They still require choices and interpretation; they do not remove the need for a meaningful distance.

Hierarchical clustering: keep the whole family tree

Agglomerative clustering starts with every observation as its own cluster. It repeatedly merges two clusters until all observations form one group. The merge history is a dendrogram, whose vertical level represents the distance or dissimilarity at which each merge occurred.

You can cut the tree to obtain two clusters, five clusters, or all groups below a distance threshold. This exposes the nested structure before you commit to one number. For the delivery map, one tree might show streets at a fine level, neighbourhoods at a medium level, and depot regions at a coarse level.

The tree is not automatically true: it depends on the distance metric and the linkage rule, which defines the distance between clusters.

Four linkage rules, four geometries

Suppose cluster A contains a1 and a2, while cluster B contains b1 and b2.

Single linkage uses the closest cross-cluster pair:

distance(A, B) = minimum distance between any ai and bj

One close pair is enough to merge groups. This can follow curved structures, but it is vulnerable to chaining, where a thin line of accidental points connects separate roads.

Complete linkage uses the farthest cross-cluster pair:

distance(A, B) = maximum distance between any ai and bj

This favours compact groups and resists some chaining, but it may split a long crescent that DBSCAN would keep intact.

Average linkage uses the mean of all cross-cluster pairwise distances. It is a middle ground, but no linkage is universally appropriate.

Ward linkage chooses the merge that causes the smallest increase in within-cluster squared error. It tends to create compact, similarly sized groups, much like k-means. Use it when that structure is intended, not for arbitrary shapes; common implementations tie it to Euclidean geometry.

At each step, the algorithm updates the new cluster’s distances to the remaining clusters according to the linkage. Thus linkage changes the merge order and the entire dendrogram, not just its appearance.

Hierarchical clustering is usually best for small or medium datasets where inspecting structure matters. Straightforward pairwise distances require quadratic memory, and computation becomes expensive as observations grow. A million-row dendrogram is less an analytical tool than a cry for help.

A library call with n_clusters=5 may stop once five groups remain. It uses the same merge logic but may not retain a complete tree for later inspection. If you need the hierarchy, use the library’s full-tree or distance-threshold options according to its current documentation.

What breaks first in practice

Almost every DBSCAN label is -1

The radius may be too small, min_samples too high, or a feature may dominate the distance. In high dimensions, the metric may not distinguish local density.

Check feature scales and the k-distance distribution. Test a small, documented range of eps and min_samples. If every reasonable setting produces noise, reconsider the representation and whether density really separates the groups.

One giant DBSCAN cluster

A large radius may create a chain between groups. Try a smaller eps, larger min_samples, or a better distance metric, and inspect the suspected bridge. Bad scaling can make a radius effectively tiny in one direction and huge in another.

The dense city survives, but the rural town disappears

This is the varying-density failure: one global radius cannot fit both regions. Try a method that ranks density across scales, or model regions separately if they represent different measurement processes. Do not keep increasing eps until unrelated places merge.

Single linkage makes one implausible chain

That is its intended geometry: one close pair justifies a merge. Switch linkage if compact groups are the goal, investigate bridge noise, or use DBSCAN when local density and noise are the concepts you need.

A silhouette score says correct crescents are bad

The silhouette score rewards compact, well-separated groups. A crescent can contain points that are closer in straight-line distance to the other crescent than to distant points on its own curve, even when the crescent is the correct cluster.

Silhouette is therefore not a universal referee. Report how DBSCAN noise was handled, use external metrics such as ARI when trustworthy reference labels exist, and otherwise examine stability under resampling and reasonable parameter changes. Finally, map groups back to the application: a mathematically clean cluster nobody can act on is just an expensive shape.

Quick check

Next

For the compact, centroid-based baseline that these methods challenge, start with k-means. For a systematic view of rare or isolated points, see anomaly detection.