DBSCAN Clustering

DBSCAN stands for density-based spatial clustering of applications with noise. It groups points by how crowded their neighborhoods are, and it can also flag points that belong to no group at all. The fastest way to learn it is to run an example and look at what comes back, then work out why it came back that way.

Suppose you run DBSCAN on a very small dataset and every point comes back labeled as noise. That is not a bug in the algorithm. It is a signal that the two parameters decide everything, and a toy dataset this small will rarely satisfy the default density rule. Keep that in mind: when a DBSCAN result surprises you, the first suspects are the parameter values and the density they imply, not the algorithm itself.

The example below is the one the source uses to show DBSCAN working well. It creates the two_moons dataset, which is two interleaved half-circles, rescales the features to zero mean and unit variance, and clusters with the default settings. Read it first and decide which parts you would check if the labels came back wrong.

With these default settings the source reports that DBSCAN finds the two half-circles and separates them, which is the desired result. Notice that you did not tell DBSCAN how many clusters to find. The number of clusters is an outcome of the density rule, not an input.

DBSCAN has exactly two parameters, and every label it returns is a consequence of them. The first, eps, is a distance. Two points count as close when the distance between them is eps or less. Think of eps as the radius of a circle drawn around a point: any other point inside that circle is a close neighbor.

The second parameter, min_samples, is a count. It is the minimum number of data points that must lie within eps of a given point before that point counts as belonging to a dense region. Where eps sets how far a neighbor can be, min_samples sets how many neighbors are needed to call a spot crowded.

DBSCAN looks for points that sit in crowded regions of the feature space, where many data points lie close together. These crowded regions are called dense regions. The core idea is that a cluster is a dense region of data, and clusters are separated from one another by regions that are comparatively empty.

This is the key contrast with agglomerative clustering. In scikit-learn, agglomerative clustering requires you to supply n_clusters yourself, and the algorithm returns that many groups whether or not the data contains that many natural groups. DBSCAN never asks for a cluster count. Its output is whatever dense regions the two parameters reveal, and some points may belong to none of them.

The price for this flexibility is speed. The source notes that DBSCAN is somewhat slower than agglomerative clustering and k-means, although it still scales to relatively large datasets.

After DBSCAN finishes, every point falls into exactly one of three kinds. A core sample has at least min_samples points within eps. A boundary point lies within eps of a core sample but does not satisfy the min_samples rule itself. A noise point is the rest: it belongs to no cluster, and scikit-learn labels it -1.

The distinction between core and boundary points matters for reproducibility. Running DBSCAN repeatedly on the same dataset always gives the same clustering of core points, and the same points are always labeled noise. A boundary point, however, may sit next to core samples from more than one cluster. Which cluster it joins then depends on the order in which points are visited. The source points out that there are usually only a few boundary points, so this dependence is rarely important in practice, but it is worth knowing when two runs disagree on a single point.

DBSCAN does not look at all points at once. It works through the dataset one unvisited point at a time, deciding for each point whether it starts a new cluster, joins an existing one, or is noise. The procedure below follows the order the source gives it.

Follow one starting point through this flow to see the core and boundary distinction in action. If the starting point has too few neighbors, it is set aside and the algorithm moves on. If it has enough neighbors, a cluster is born, and growth proceeds outward through core samples only. Boundary points are reached and labeled, but the search does not continue from them. That asymmetry is the mechanism behind the difference between the two kinds of points.

DBSCAN returns one integer label per point. The label -1 is reserved for noise. Every other label is a cluster identifier, and the non-negative values only name groups; they carry no meaning about size or order. When you read a result, first separate the noise from the clusters, because a naive count of distinct labels will include -1 as if it were a cluster.

This matters whenever you use the labels to index another array, such as the original feature rows or a column of targets. If you index with raw labels, the -1 values silently select the last element of the array instead of marking a noise point. Always handle -1 explicitly before using labels as positions.

Because eps is a single distance, DBSCAN depends on how features are measured. The neighbors of a point are determined by the distance between points in the raw feature space. If one feature has values in the thousands and another has values between zero and one, the large-scale feature dominates the distance, and the small-scale feature barely affects which points count as close.

This is why the two_moons example rescales the data to zero mean and unit variance before clustering. After rescaling, each feature contributes comparably to the distance, so an eps value means the same thing across dimensions. Without rescaling, the same eps can produce a very different set of neighbors and therefore very different labels.

Once you know that eps sets the neighborhood radius and min_samples sets the density threshold, you can predict how a change to either one will reshape the clusters. Lowering eps shrinks each neighborhood, so fewer points qualify as core samples and more points are left as noise or split into separate groups. Raising eps grows the neighborhoods, so separate dense regions can join into one cluster.

min_samples works in the opposite direction from eps for the density rule. Raising min_samples demands more neighbors before a point counts as a core sample, so sparse regions are more likely to be labeled noise. Lowering it lets thinner groups of points qualify as dense, which can produce clusters from scattered points. Because eps and min_samples interact, change one at a time and compare the labels before and after.

When a DBSCAN result looks wrong, locate the step where it stopped matching what you expected. Start with the parameters, then the scaling, then the labels, and only then the algorithm. The list below covers the mistakes that account for most surprising results.

Agglomerative clustering starts with every point as its own cluster and joins clusters step by step until one final cluster remains. Each stage is itself a valid clustering, and choosing a cluster count amounts to stopping the process at the matching stage. The source states that agglomerative clustering still fails at separating complex shapes, and it gives the two_moons dataset as an example. DBSCAN does not share that particular failure, because it grows clusters from dense regions rather than merging clusters by distance.