Skip to content
Tutorials Center
My learning

Topics

Lesson 65 of 111 ยท Unsupervised Learning

DBSCAN, HDBSCAN and Density Clustering

Cluster by density with DBSCAN, choose eps and min_samples with a k-distance plot, label noise, and use HDBSCAN and OPTICS for varying-density data.

k-means imagines clusters as balls. Look at a map of a city at night, though, and you see something else: bright dense regions (neighborhoods) separated by dark, sparse areas. Density-based clustering follows that idea. A cluster is a region where points are packed closely, and anything in a sparse region is not part of any cluster.

This has three attractive consequences. Clusters can have any shape. You do not need to choose the number of clusters. And points that fit nowhere are labeled noise instead of being forced into a group. This lesson covers DBSCAN, the classic method, then HDBSCAN and OPTICS, which handle data where density varies from place to place. Compare with k-means and hierarchical clustering as you go.

How DBSCAN works

DBSCAN (density-based spatial clustering of applications with noise) has two settings:

  • eps: the radius of a neighborhood around a point.
  • min_samples: how many points (including the point itself) a neighborhood must contain to count as dense.

Every point then falls into one of three roles:

  • Core point: at least min_samples points lie within eps of it.
  • Border point: not a core point, but within eps of a core point.
  • Noise point: neither. It gets the label -1.

A cluster is a set of core points connected through overlapping neighborhoods, plus their border points. The algorithm grows clusters by walking from one core point to the next.

Three kinds of points

Core Dense neighborhood around it.
Border Near a core, but not dense itself.
Noise Fits no cluster. Label -1.

Clusters grow by hopping from core point to core point.

1 / 2
Python DBSCAN finds the moons and marks noise

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The crescents come out as two clusters, and 12 of the 15 sprinkled random points (plus none of the crescent points) become noise (gray); the few that fall right next to a crescent are absorbed into it. Unlike in k-means, a few outliers cannot drag a centroid, because there is none.

eps is everything

DBSCAN is very sensitive to eps. Too small and almost everything is noise; too large and separate clusters fuse into one. Scale matters as much as for k-means: eps is a distance, so standardize features first when they are in different units.

Python Sweeping eps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

At eps=0.05 you get 21 tiny clusters and 244 noise points; from 0.3 upward everything collapses into one cluster. In between, 0.15 to 0.2 is a stable range with exactly two clusters. Looking for a plateau like this is a sound way to pick eps.

Choosing eps and min_samples

Two practical heuristics:

  • min_samples: a common starting point is twice the number of features (2 * n_features), and at least 3 to 5. Larger values make the algorithm stricter and more noise-tolerant; for noisy data or large datasets use more.
  • eps: draw a k-distance plot. For every point, compute the distance to its min_samples-th nearest neighbor and sort those distances. Points inside clusters have small distances; noise has large ones. The "knee" where the curve starts to shoot up is a good eps.
Python A k-distance plot

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The curve is nearly flat for most points and bends upward for the last few percent, the noise. Setting eps at the bend finds the three clusters and treats the scattered background as noise. If the curve has no clear knee, the data may have no clean density structure, or it has clusters of different densities, which is the weakness of DBSCAN.

DBSCAN uses one global eps. If one cluster is dense and another is loose, no single value fits both: either the loose one is shattered into noise, or the dense ones merge. Use HDBSCAN or OPTICS for that case.

HDBSCAN: clusters of different densities

HDBSCAN (hierarchical DBSCAN) runs DBSCAN conceptually for every eps at once, builds a hierarchy, and keeps the clusters that stay stable over the widest range of densities. It is in scikit-learn as sklearn.cluster.HDBSCAN. You rarely tune eps; the main settings are min_cluster_size (the smallest group you care about) and min_samples (how conservative the noise decision is, defaulting to min_cluster_size).

Python HDBSCAN versus DBSCAN on mixed densities

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With a small eps, DBSCAN finds the tight clusters but throws 149 points, most of the wide cluster, into noise (and splits it into extra pieces). With a large eps the wide cluster is complete, but all three groups fuse into a single cluster (ARI 0). HDBSCAN adapts the density it uses per cluster and recovers all three groups with far less noise (ARI about 0.89) without an eps. HDBSCAN also provides probabilities_, a score for how strongly each point belongs to its cluster.

OPTICS: a density ordering

OPTICS orders the points so that each is close to its neighbor in the ordering and records the reachability distance: the eps at which the point would join the growing cluster. Plotted in order, valleys in the reachability plot are clusters, and the depth of a valley is its density. You can read it like a dendrogram for density, then extract flat clusters either automatically or at a chosen eps with cluster_optics_dbscan.

Python Reachability plot with OPTICS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Three valleys show three clusters (the automatic extraction found 3, marking 139 of the 450 points as noise), and the valley for the loose cluster is shallower than for the tight one. OPTICS is slower than DBSCAN, and its automatic xi extraction needs some tuning, but the plot itself is very informative even when the extraction is not perfect.

Which density method to use

  • Start with DBSCAN when density is roughly uniform and you can set eps from a k-distance plot.
  • Use HDBSCAN when densities differ or you do not want to tune eps. It is usually the best first try.
  • Use OPTICS when you want to inspect the density structure before deciding.
  • Density methods struggle in very high dimensions, where distances between points become similar. Reduce dimensions first (see PCA).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In DBSCAN, what label do noise points receive?

    DBSCAN labels points that are neither core nor border points as -1. Cluster labels start at 0.
  2. 2. What happens if you set eps far too large?

    A huge neighborhood connects points across the gaps between clusters, so all dense regions fuse. A tiny eps does the opposite and labels almost everything as noise.
  3. 3. What does a k-distance plot help you choose?

    You sort each point's distance to its k-th nearest neighbor and look for the knee where distances start rising steeply; that distance is a good eps.
  4. 4. Why prefer HDBSCAN over DBSCAN when clusters have very different densities?

    One eps cannot suit both a tight and a loose cluster. HDBSCAN considers many density levels and keeps the most stable clusters, so it needs no eps.

Summary

  • Density clustering defines clusters as dense regions: arbitrary shapes, no preset cluster count, and noise labeled -1.
  • DBSCAN has two settings, eps and min_samples; points are core, border or noise.
  • Standardize features and choose eps from a k-distance plot or a stable plateau.
  • A single global eps fails when densities differ; HDBSCAN (min_cluster_size) and OPTICS (reachability plot) handle that.
  • Density methods weaken in high dimensions; reduce dimensions first.

Next: clusters that overlap and belong to points only partly, in Gaussian Mixture Models.