Density-Based Clustering with DBSCAN, machine learning lesson

Two curved groups of points can wrap around each other, with a few scattered points that belong to neither. K-means gives every point to its nearest center, so its clusters meet along straight boundaries and every scattered point must join some cluster. DBSCAN instead calls a place crowded when enough points lie within a fixed radius, lets a cluster spread along chains of crowded places and leaves isolated points unassigned as noise. This lesson defines the neighborhoods and point types it uses, works through a small constructed example under a stated counting convention, and shows how the radius, the count and the feature scale decide what becomes a cluster.

Key terms

Epsilon neighborhood

Definition Let the data be points $\mathbf{x}_1, \dots, \mathbf{x}_n$ with a distance $d$ , such as Euclidean distance on suitably scaled features, and fix a radius $\varepsilon > 0$ . The epsilon neighborhood of point $i$ is the set of indices

N_\varepsilon(i) = \{ j : d(\mathbf{x}_i, \mathbf{x}_j) \le \varepsilon \}

of all data points within distance $\varepsilon$ of $\mathbf{x}_i$ , the boundary included. Since $d(\mathbf{x}_i, \mathbf{x}_i) = 0$ , every point belongs to its own neighborhood, and since a distance is symmetric, two points lie in each other’s neighborhoods or in neither. The neighborhood is a set of observed points, not a region of space, and duplicated rows count separately. Some descriptions use the strict inequality $d < \varepsilon$ , which changes the result only for pairs at distance exactly $\varepsilon$ .

In plain words Draw a disk of radius $\varepsilon$ around a point, or a ball when there are more than two features, and list the data points inside it or on its edge. The list depends on the distance and on the units of every feature, so rescaling one feature changes who counts as a neighbor. When the clustering is part of a predictive pipeline, any scaler is fitted on the training data only, as for k-nearest neighbors.

Example Eight constructed points in the plane lie on the horizontal axis at the first coordinates 0, 0.4, 0.8, 1.2, 3, 3.4, 3.8 and 6, all with second coordinate 0 and no units. With Euclidean distance and $\varepsilon = 0.5$ , the neighborhood of the point at 0.4 holds the points at 0, 0.4 and 0.8. The point at 1.2 lies 0.8 away and stays outside. The neighborhood of the point at 6 holds only the point itself, since its nearest other point, at 3.8, is 2.2 away.

Core point

Definition Fix a whole number $m \ge 1$ , the minimum count, called MinPts in the original description of DBSCAN and min_samples in scikit-learn. A data point $\mathbf{x}_i$ is a core point when

\lvert N_\varepsilon(i) \rvert \ge m ,

where the count includes the point itself, as the neighborhood above does automatically. For $2 \le m \le n$ this says that the distance from $\mathbf{x}_i$ to its $(m - 1)$ th nearest other data point is at most $\varepsilon$ . Descriptions and programs differ on whether the point counts itself. A rule that counts only the other points and asks for at least $m$ of them is this page’s rule with threshold $m + 1$ , so the convention is part of the parameter.

In plain words A core point sits in a crowded place, with enough company within reach. Raising $m$ or shrinking $\varepsilon$ demands more crowding, so fewer points qualify. With $m = 1$ every point is a core point, and with $m > n$ none is.

Example For the eight points with $\varepsilon = 0.5$ and $m = 3$ , the neighborhood counts in order are 2, 3, 3, 2, 2, 3, 2 and 1, so the core points are those at 0.4, 0.8 and 3.4. For the point at 0.4, the two nearest other points, at 0 and 0.8, are both 0.4 away, so its second nearest other point lies within 0.5, as the criterion with $m - 1 = 2$ requires. A program that counts only the other points but keeps the threshold 3 sees the counts 1, 2, 2, 1, 1, 2, 1 and 0. It finds no core point at all and labels all eight points noise. The same program with threshold 2 reproduces this page’s result.

Border point and noise point

Definition A border point is a data point that is not a core point but lies in the epsilon neighborhood of at least one core point. A noise point is a data point that is neither a core point nor a border point, so no core point lies within distance $\varepsilon$ of it. Every data point has exactly one of the three types, and the types depend only on the data, the distance, $\varepsilon$ and $m$ . With $m = 1$ there is no noise. With $m = 2$ there are no border points, because a point within $\varepsilon$ of a core point has at least two members in its neighborhood and is itself a core point.

In plain words A border point sits at the edge of a crowded place, near it but not crowded itself. A noise point is isolated at the chosen scale. Noise is a label produced by the parameters, not a finding that the record is wrong. A noise point can be a measurement error, a rare but genuine case, or a member of a group too sparse for the chosen $\varepsilon$ and $m$ .

Example For the eight points with $\varepsilon = 0.5$ and $m = 3$ the types are as follows.

Point	Points within 0.5	Count	Type
$0$	$0,\ 0.4$	$2$	border
$0.4$	$0,\ 0.4,\ 0.8$	$3$	core
$0.8$	$0.4,\ 0.8,\ 1.2$	$3$	core
$1.2$	$0.8,\ 1.2$	$2$	border
$3$	$3,\ 3.4$	$2$	border
$3.4$	$3,\ 3.4,\ 3.8$	$3$	core
$3.8$	$3.4,\ 3.8$	$2$	border
$6$	$6$	$1$	noise

The count alone does not decide between border and noise. If two more points were added at 10 and 10.3, each would have count 2, like the border points in the table, yet both would be noise, because neither has a core point within 0.5.

Density reachability

Definition A point $\mathbf{x}_j$ is directly density-reachable from $\mathbf{x}_i$ when $\mathbf{x}_i$ is a core point and $j \in N_\varepsilon(i)$ . A point $\mathbf{x}_j$ is density-reachable from $\mathbf{x}_i$ when there is a chain of one or more steps

\mathbf{x}_i = \mathbf{p}_0, \mathbf{p}_1, \dots, \mathbf{p}_k = \mathbf{x}_j

in which each $\mathbf{p}_{t+1}$ is directly density-reachable from $\mathbf{p}_t$ . Every point of the chain except possibly the last is then a core point, and consecutive points are at most $\varepsilon$ apart. The relation is transitive. It is not symmetric, because a border point can be reached from a core point while nothing can be reached from a border point. Between two core points it is symmetric, since the chain can be walked backward. A noise point is density-reachable from no point.

In plain words Reachability describes how a cluster spreads. Start at a core point, step to any of its neighbors, and keep stepping only from core points. A border point can be reached, but the walk stops there. This is how a cluster can follow a long or curved shape without any border point passing it on.

Example In the eight-point data, the point at 1.2 is density-reachable from the point at 0.4 along the chain 0.4, 0.8, 1.2. The first two are core points and each step is 0.4 long. The reverse fails, because 1.2 is not a core point, so no chain starts there. No chain from 0.4 reaches the point at 3 either, since every step must start at a core point within 0.5 of its successor, and the gap from 1.2 to 3 is 1.8.

Density connectivity

Definition Two points $\mathbf{x}_i$ and $\mathbf{x}_j$ are density-connected when some point $\mathbf{x}_o$ exists from which both are density-reachable. The relation is symmetric, and on core points it agrees with density reachability. For a core point $\mathbf{p}$ , the cluster of $\mathbf{p}$ is the set of all points density-reachable from $\mathbf{p}$ . It consists of every core point joined to $\mathbf{p}$ by a chain of core points with consecutive distances at most $\varepsilon$ , together with every border point within $\varepsilon$ of one of them, and every two of its points are density-connected. Two core points have the same cluster exactly when they are density-reachable from each other, and the clusters of two core points either coincide or share only border points. Density connectivity is not transitive when border points are involved, as the example below shows.

In plain words Two points are density-connected when a single crowded region reaches both of them, even if they are far apart. This lets a long or curved cluster hold together. A border point between two crowded regions touches both, but it cannot join them, because no walk continues through a point that is not crowded.

Example In the eight-point data, the points at 0 and 1.2 are density-connected through the point at 0.4, although they are 1.2 apart, more than twice $\varepsilon$ . For a shared border point, take seven other constructed points on a line at $-1$ , $-0.9$ , $-0.5$ , 0, 0.5, 0.9 and 1, with $\varepsilon = 0.5$ and $m = 4$ . Only the points at $-0.5$ and 0.5 are core points, with the neighborhoods $\{-1, -0.9, -0.5, 0\}$ and $\{0, 0.5, 0.9, 1\}$ . The point at 0 has count 3 and is a border point of both clusters. It is density-connected to $-0.5$ and to $0.5$ , yet those two core points are 1 apart with no chain of core points between them, so they are not density-connected and the clusters stay separate.

DBSCAN

Definition DBSCAN, short for density-based spatial clustering of applications with noise, takes points $\mathbf{x}_1, \dots, \mathbf{x}_n$ , a distance $d$ , a radius $\varepsilon > 0$ and a minimum count $m \ge 1$ with a stated self-count convention, and labels every point.

Compute every epsilon neighborhood and mark the core points.
Join two core points whenever their distance is at most $\varepsilon$ , and give each connected component of this graph of core points its own cluster label.
Give each border point the label of a cluster that has a core point within $\varepsilon$ of it, by a declared rule when there are several such clusters.
Label every remaining point as noise.

The clusters are the sets of the previous card, except that a shared border point receives only one label. The number of clusters is an output, fixed by the data, $d$ , $\varepsilon$ and $m$ , not an input. The core points, their components and the noise points do not depend on the order of the rows. Only the label of a shared border point can, because the usual implementation gives it to whichever cluster reaches it first. With $m = 1$ the clusters are the connected components of the graph that joins points at distance at most $\varepsilon$ , the same groups that single-linkage clustering gives when it stops before its first merge above height $\varepsilon$ . A direct implementation computes all $n(n - 1)/2$ pairwise distances. Index structures such as k-d trees often speed up the neighborhood searches in low dimensions, although the worst case stays quadratic.

In plain words DBSCAN does not ask for the number of clusters, but it does need a definition of crowded, and $\varepsilon$ , $m$ , the distance and the feature scaling supply it. Two clusters in the output say that, at this density scale, the data form two connected crowded regions. They do not show that the data contain two natural classes. A single $\varepsilon$ for the whole data set can fail when groups differ in density, and in many dimensions, where distances between points tend to become similar to one another, a good radius is hard to find. When the clusters feed a supervised model, the choice of $\varepsilon$ and $m$ belongs inside the training data, and held-out labels that were used to pick the most convincing clustering cannot then also confirm it.

Example For the eight points with $\varepsilon = 0.5$ and $m = 3$ , step 1 finds the core points 0.4, 0.8 and 3.4. In step 2 the core points 0.4 and 0.8 are 0.4 apart and form one component, while 3.4 is alone. Step 3 gives 0 and 1.2 to the first cluster and 3 and 3.8 to the second, and step 4 leaves 6 as noise. With $\varepsilon = 1.8$ instead, the counts become 4, 4, 4, 5, 4, 3, 3 and 1, so the first seven points are all core points. The gap from 1.2 to 3 is exactly 1.8 and the boundary is included, so the two groups merge into one cluster of seven points, while 6 stays noise at distance 2.2 from 3.8. Under the strict inequality the merge would need $\varepsilon > 1.8$ . Keeping $\varepsilon = 0.5$ and raising $m$ to 4 leaves no core point, so all eight points become noise. A NumPy version of the four steps, with self-counting and the boundary included, is short.

import numpy as np

def dbscan(X, eps, m):
    n = len(X)
    D = np.sqrt(((X[:, None, :] - X[None, :, :]) ** 2).sum(axis=2))
    near = D <= eps                          # neighborhoods, each point included
    core = near.sum(axis=1) >= m
    labels = np.full(n, -1)                  # -1 marks noise
    c = 0
    for i in range(n):                       # one cluster per core component
        if core[i] and labels[i] == -1:
            labels[i] = c
            stack = [i]
            while stack:
                q = stack.pop()
                for j in np.flatnonzero(near[q] & (labels == -1)):
                    labels[j] = c            # a core or border neighbor joins
                    if core[j]:
                        stack.append(j)      # only core points expand further
            c += 1
    return core, labels

x = np.array([0, 0.4, 0.8, 1.2, 3, 3.4, 3.8, 6])
X = np.column_stack([x, np.zeros_like(x)])
core, labels = dbscan(X, eps=0.5, m=3)
print(labels)                                # [ 0  0  0  0  1  1  1 -1]

Check yourself

Seven constructed points in the plane are A at $(0, 0)$ , B at $(1, 0)$ , C at $(0, 1)$ , D at $(3, 0)$ , E at $(4, 0)$ , F at $(3, 1)$ and G at $(6, 3)$ . With Euclidean distance, $\varepsilon = 1$ and $m = 3$ , counting each point itself and including the boundary, find each neighborhood count, each point’s type and the clusters.

Show the answer

The neighborhood of A holds A, B and C, since B and C are exactly 1 away, so A has count 3 and is a core point. B and C are $\sqrt{2} \approx 1.414$ apart, so B sees only A and itself, and C sees only A and itself. Both have count 2 and lie within 1 of the core point A, so both are border points. In the same way D sees D, E and F and is a core point, while E and F, also $\sqrt{2}$ apart, have count 2 and are border points. The nearest points to G are E and F, both at distance $\sqrt{13} \approx 3.606$ , so G has count 1, no core point nearby, and is noise.

The clusters are A, B and C in one and D, E and F in the other, with G as noise. Under the strict inequality $d < 1$ every count would be 1, no point would be a core point, and all seven points would be noise. The boundary convention decides the whole answer here.

For the same seven points with $m = 3$ , find the smallest $\varepsilon$ at which the two clusters merge. What happens to G at that radius, and from which radius on does G join?

Show the answer

The closest pair across the two groups is B and D, at distance 2, and the next is B and F, at $\sqrt{5} \approx 2.236$ . For $\varepsilon < 2$ no point of the left group lies within $\varepsilon$ of any point of the right group, so no chain of steps can cross the gap and the clusters stay separate.

At $\varepsilon = 2$ the neighborhood of B holds A, B, C and D, since C is $\sqrt{2}$ away and D is exactly 2 away, so B has count 4 and is a core point. The neighborhood of D holds B, D, E and F, so D is a core point too. Two core points within $\varepsilon$ of each other belong to one component, so the six points A to F form a single cluster. G is still $\sqrt{13} \approx 3.606$ from its nearest points and stays noise. G joins once $\varepsilon \ge \sqrt{13}$ , when its neighborhood holds E, F and G itself, so it becomes a core point next to the core points E and F and all seven points form one cluster.

Constructed points on a line lie at 0, 0.2, 0.4, 0.6, 1.0, 1.2, 1.4, 1.6, 5, 6, 7 and 8, which look like two tight groups and one loose group. With $m = 3$ , counting each point itself and including the boundary, is there a single $\varepsilon$ for which DBSCAN returns these three groups as three clusters?

Show the answer

No. The two tight groups are separated by the gap from 0.6 to 1.0, of length 0.4. For every $\varepsilon \ge 0.4$ , the point at 0.6 has at least the four points 0.2, 0.4, 0.6 and 1.0 in its neighborhood, and the point at 1.0 has at least 0.6, 1.0, 1.2 and 1.4, so both are core points within $\varepsilon$ of each other and the tight groups merge. Keeping them apart therefore needs $\varepsilon < 0.4$ .

In the loose group the points are 1 apart, so for $\varepsilon < 1$ each of 5, 6, 7 and 8 has only itself in its neighborhood. The nearest tight point, 1.6, is 3.4 away, so these four points are noise. Making the loose group a cluster needs $\varepsilon \ge 1$ , which contradicts $\varepsilon < 0.4$ . Checking the ranges confirms it. For $0.2 \le \varepsilon < 0.4$ the result is the two tight clusters with the loose group as noise, for $0.4 \le \varepsilon < 1$ it is one merged tight cluster with the loose group as noise, for $1 \le \varepsilon < 3.4$ it is the merged tight cluster and the loose cluster, and from 3.4 on everything is one cluster.

One density scale cannot fit groups of very different density. Rescaling the single feature does not help, because it multiplies every distance by the same factor and only moves these thresholds together. Methods that consider many density levels at once, such as OPTICS and HDBSCAN, were designed for this situation.

Density-Based Clustering with DBSCAN

Key terms

Epsilon neighborhood

Core point

Border point and noise point

Density reachability

Density connectivity

DBSCAN

Check yourself

How this lesson connects

Builds on

Used later in