Detecting Outliers Using DBSCAN

Density-based clustering, which finds groups of any shape as regions where points are crowded together and labels the points in sparse regions as noise. The definitions of Ester, Kriegel, Sander and Xu (1996), core, border and noise points worked by hand on twelve points, the algorithm and why its result can depend on processing order, choosing Eps and MinPts with a sorted k-distance plot, the eruptions of the Old Faithful geyser, and where a single density threshold fails.

The Old Faithful geyser in Yellowstone National Park erupts at intervals of an hour or more. A record of 272 eruptions (Härdle, 1991; Azzalini and Bowman, 1990, analyzed a more complete version) gives the length of each eruption and the waiting time until the next. Plotted, the eruptions fall into two groups: short eruptions of about two minutes followed by a wait of about 54 minutes, and long eruptions of about four and a quarter minutes followed by a wait of about 80. A clustering method such as The k-means Algorithm can find the two groups, but it assigns every eruption to one of them, including any that fit neither. DBSCAN, short for density-based spatial clustering of applications with noise, takes a different view of what a cluster is. A cluster is a region where points are crowded together, and a point in a sparse region belongs to no cluster at all: it is noise. On the standardized Old Faithful data, DBSCAN finds the same two groups as k-means, of 175 and 96 eruptions, and sets one eruption aside, a 2.38-minute eruption followed by a 71-minute wait, which lies between the groups.

Because it labels the points that belong nowhere, DBSCAN is used as much for outlier detection as for clustering, the second of the three families of unsupervised learning. It also finds clusters of shapes that centroid-based methods cannot, and it does not need to be told how many clusters to look for. In return it needs two parameters that define what "crowded" means, and much of the practical work is choosing them. This article follows the original paper's definitions, works them by hand, and then applies the method to Old Faithful and to cases where it struggles.

The problem DBSCAN was designed for

Ester, Kriegel, Sander and Xu (1996) designed DBSCAN for clustering in large spatial databases, such as points derived from satellite images. They asked for three properties that the clustering algorithms of the time did not offer together: minimal domain knowledge needed to set the parameters, discovery of clusters of arbitrary shape, and good efficiency on databases of many thousands of points. Partitioning methods such as k-means and its relatives need the number of clusters in advance and produce convex clusters, because each point goes to the nearest center. Hierarchical methods do not need the number of clusters, but need a rule for where to cut the tree and, in the forms then common, compared every pair of points (Hierarchical Clustering covers these methods).

Their starting observation was visual. In a scatter plot, people recognize clusters as regions where the density of points is considerably higher than around them, and noise as isolated points in regions of lower density. DBSCAN formalizes "density" in the simplest way: count the points within a fixed distance.

Definitions

Let $D$ be the set of points and $\operatorname{dist}$ a distance, usually Euclidean. DBSCAN has two parameters, a radius $\varepsilon$ (written Eps in the paper) and a count MinPts.

  • The $\varepsilon$-neighborhood of a point $p$ is the set of points within distance $\varepsilon$ of it, including $p$ itself: $N_\varepsilon(p) = \{ q \in D : \operatorname{dist}(p, q) \le \varepsilon \}$ (Ester et al., 1996, Definition 1).
  • A core point is a point whose $\varepsilon$-neighborhood contains at least MinPts points, counting itself. Core points lie inside dense regions.
  • A point $p$ is directly density-reachable from $q$ if $p$ is in $N_\varepsilon(q)$ and $q$ is a core point (Definition 2). This relation is not symmetric: a point near the edge of a cluster can be reachable from a core point without being a core point itself, and then the core point is not reachable from it.
  • $p$ is density-reachable from $q$ if there is a chain $q = p_1, p_2, \dots, p_k = p$ in which each point is directly density-reachable from the one before (Definition 3). Every point of the chain except possibly the last must be a core point.
  • $p$ and $q$ are density-connected if both are density-reachable from some point $o$ (Definition 4). Two points on the edge of the same cluster are connected in this sense through the core points between them.

A cluster is a nonempty set of points that is maximal, in that every point density-reachable from a member is also a member, and connected, in that every two members are density-connected (Definition 5). Noise is every point that belongs to no cluster (Definition 6). The points of a cluster that are not core points are its border points.

So every point is exactly one of three kinds. A core point has at least MinPts points within $\varepsilon$. A border point has fewer, but lies within $\varepsilon$ of a core point. A noise point has fewer and lies within $\varepsilon$ of no core point. Being near a border point is not enough to join a cluster, because density-reachability only passes through core points.

Twelve points by hand

Take the twelve points in the figure, with $\varepsilon = 1.5$ and MinPts $= 4$.

Twelve points with Eps = 1.5 and MinPts = 4. Core points (circles) have at least four points, counting themselves, within the dotted circles of radius 1.5. Border points e and s (squares) are within 1.5 of a core point but have too few neighbors of their own; s is within 1.5 of a core point in each cluster. Noise points m and n (crosses) are within 1.5 of no core point; m is close to the border point e, which does not count.
Twelve points with Eps = 1.5 and MinPts = 4. Core points (circles) have at least four points, counting themselves, within the dotted circles of radius 1.5. Border points e and s (squares) are within 1.5 of a core point but have too few neighbors of their own; s is within 1.5 of a core point in each cluster. Noise points m and n (crosses) are within 1.5 of no core point; m is close to the border point e, which does not count.

The first step is to count each point's neighborhood. Distances are Euclidean; the diagonal of a unit square is $\sqrt{2} = 1.41$, inside the radius, and a distance of exactly 1.5 counts, since the definition uses "at most".

Point Coordinates Other points within 1.5 (distance) $\lvert N_\varepsilon \rvert$ Kind
a (1, 1) b (1.00), c (1.00), d (1.41) 4 core
b (2, 1) a (1.00), c (1.41), d (1.00) 4 core
c (1, 2) a (1.00), b (1.41), d (1.00), e (1.28) 5 core
d (2, 2) a (1.41), b (1.00), c (1.00), s (1.50) 5 core
e (0.2, 3) c (1.28), m (1.41) 3 border
f (5, 1) g (1.00), h (1.00), i (1.41) 4 core
g (6, 1) f (1.00), h (1.41), i (1.00) 4 core
h (5, 2) f (1.00), g (1.41), i (1.00), s (1.50) 5 core
i (6, 2) f (1.41), g (1.00), h (1.00) 4 core
s (3.5, 2) d (1.50), h (1.50) 3 border
m (−0.8, 4) e (1.41) 2 noise
n (4, 4.5) none 1 noise

The core points a, b, c and d are all within 1.5 of one another, so they are density-connected and form one cluster; f, g, h and i form another. The two groups are not connected, because the only point between them, s, is not a core point: a chain of density-reachability cannot pass through it. The point e has only three points in its neighborhood, too few to be a core point, but it is within 1.5 of the core point c, so it is a border point of the first cluster. The point m is within 1.5 of e, but e is not a core point, so m is not density-reachable from anything and is noise, as is the isolated n. DBSCAN finds two clusters and two noise points without having been told how many clusters there are.

The point s is the interesting case. It is exactly 1.5 from the core point d and exactly 1.5 from the core point h, so by Definition 5 it belongs to both clusters. The algorithm, described next, gives each point a single label, and s goes to whichever cluster reaches it first. Run in alphabetical order, scikit-learn's implementation puts s in the cluster of a, b, c and d; run with f, g, h and i first, it puts s with them. Ester et al. (1996, §4.1) note this possibility and describe it as rare; Schubert, Sander, Ester, Kriegel and Xu (2017, §2.2) add that the result is deterministic for a given order of the data but may change if the data are permuted, both in which border points go where and in how the clusters are numbered. Core points and noise points never depend on the order.

The algorithm

The algorithm visits the points in turn (Ester et al., 1996, §4.1). When it reaches a point that has not yet been labeled, it retrieves the point's $\varepsilon$-neighborhood, a region query.

  1. If the neighborhood has fewer than MinPts points, the point is provisionally labeled noise. It may be relabeled later as a border point if some core point reaches it.
  2. Otherwise the point is a core point and starts a new cluster. All its neighbors join the cluster and go into a list of seeds. For each seed in turn, a region query is made; if the seed is also a core point, its unlabeled or noise-labeled neighbors join the cluster too, and those not yet seen are added to the list. When the list is empty, the cluster is complete: it contains exactly the points density-reachable from the starting point.
  3. Continue with the next unlabeled point.

Each point triggers one region query. With a linear scan, a query compares a point with every other point, so the whole algorithm takes time proportional to $n^2$ for $n$ points. Ester et al. assumed a spatial index such as an R*-tree, with which a query for a small neighborhood is fast, and gave an average cost of $O(n \log n)$. Schubert et al. (2017, §§2.2 and 3.1–3.2) point out that this depends on the index answering small queries quickly, which holds in low dimensions with a well-chosen $\varepsilon$ but cannot be guaranteed; a large $\varepsilon$ that puts most of the data in each neighborhood brings back quadratic cost. In the original experiments, DBSCAN ran between 250 and 1,900 times faster than CLARANS, a k-medoids method, on samples of up to 12,512 points.

Clusters of any shape

Because clusters grow by chains of neighbors, their shape is whatever the chain follows. The figure compares k-means and DBSCAN on two standard synthetic examples of 400 points each (seed 742): two interleaved half-moons and two concentric rings.

Two interleaved half-moons (top) and two concentric rings (bottom), 400 points each. k-means with k = 2 (left) cuts each dataset with a straight boundary, because each point goes to the nearer of two centers. DBSCAN with Eps = 0.2 and MinPts = 4 (right) follows each shape and recovers the generating groups exactly.
Two interleaved half-moons (top) and two concentric rings (bottom), 400 points each. k-means with k = 2 (left) cuts each dataset with a straight boundary, because each point goes to the nearer of two centers. DBSCAN with Eps = 0.2 and MinPts = 4 (right) follows each shape and recovers the generating groups exactly.

The adjusted Rand index (ARI), which compares a clustering with known groups and is 1 for perfect agreement and near 0 for chance (see Evaluating Clusterings), measures the difference. k-means scores 0.263 on the moons and −0.002 on the rings: on the rings it does no better than chance, since no straight line separates a ring from the disk inside it. DBSCAN with $\varepsilon = 0.2$ scores 1.000 on both. The choice of $\varepsilon$ matters, though. On the moons, $\varepsilon = 0.1$ is too small and breaks the data into four clusters with 15 noise points (ARI 0.490), and $\varepsilon = 0.25$ is large enough to bridge the gap between the moons and merges everything into one cluster (ARI 0.000). The rings are more forgiving: every $\varepsilon$ from 0.15 to 0.25 recovers them exactly.

Choosing the parameters

MinPts

MinPts sets how many points make a neighborhood dense, and it smooths the density estimate: with MinPts $= 1$ every point is a core point and there is no noise, and with MinPts $= 2$ DBSCAN joins any two points within $\varepsilon$, which is single-link hierarchical clustering cut at height $\varepsilon$. Ester et al. (1996, §4.2) found that the sorted $k$-distance graphs (described next) for $k > 4$ did not differ significantly from the one for $k = 4$ while costing more to compute, and fixed MinPts at 4 for two-dimensional data. A later rule from Sander and colleagues, described by Schubert et al. (2017, §4.1), sets it to twice the number of dimensions, which also gives 4 in two dimensions; Schubert et al. suggest larger values for data that are noisy, very large, high-dimensional or full of duplicates.

Eps and the sorted k-distance plot

Given MinPts, Ester et al. (1996, §4.2) proposed choosing $\varepsilon$ from a plot. For each point, compute the distance to its $k$th nearest neighbor, its $k$-distance; sort the points by it from largest to smallest; and plot the result. If $\varepsilon$ is set to some point's $k$-distance, every point with a $k$-distance at most that large is a core point. Points inside clusters have small $k$-distances and form a long, slowly declining stretch of the plot; noise points have large ones and form a steep head at the left. The threshold is the first point of the first "valley", where the curve turns from steep to flat; points to its left are noise, and its $k$-distance is $\varepsilon$. Ester et al. used this interactively: the system draws the plot, the user estimates the proportion of noise, and $\varepsilon$ is read off.

Counting conventions need care here. The neighborhood count in the core-point condition includes the point itself, while "the $k$th nearest neighbor" usually does not, so the $k$-distance that matches MinPts is the distance to the $(\text{MinPts} - 1)$th other point (Schubert et al., 2017, §4.1). scikit-learn's min_samples counts the point itself, as the definition does, so with min_samples = 4 the plot uses the third nearest other point.

Old Faithful

The two Old Faithful measurements are in different units with very different spreads: eruption time has a standard deviation of 1.141 minutes and waiting time 13.595 minutes. Without rescaling, waiting time accounts for 99.3% of the total squared Euclidean distance between pairs of eruptions, and eruption length would barely affect which points are neighbors. Each measurement is therefore standardized by subtracting its mean (3.488 and 70.897 minutes) and dividing by its standard deviation, as for k-nearest neighbors and k-means.

With MinPts $= 4$, the sorted distances to the third nearest other eruption are shown below. The largest is 0.521 standard units, and the first six fall from 0.521 to 0.415. Then the curve drops to 0.366 for the seventh and 0.314 for the eighth, and after that it declines slowly: the median is 0.094. The valley lies between about 0.31 and 0.37, and $\varepsilon = 0.35$ is chosen from it. With MinPts $= 8$ the curve is higher, since the seventh neighbor is farther than the third, but has the same shape.

Sorted k-distance plot for the 272 standardized Old Faithful eruptions: each eruption's distance to its third nearest neighbor (solid, for MinPts = 4) and seventh nearest (dashed, MinPts = 8), from largest to smallest, on a log scale of rank. The solid curve drops steeply over the first seven or eight eruptions and then flattens; Eps = 0.35 is read from that bend.
Sorted k-distance plot for the 272 standardized Old Faithful eruptions: each eruption's distance to its third nearest neighbor (solid, for MinPts = 4) and seventh nearest (dashed, MinPts = 8), from largest to smallest, on a log scale of rank. The solid curve drops steeply over the first seven or eight eruptions and then flattens; Eps = 0.35 is read from that bend.

The table shows what each $\varepsilon$ gives with MinPts $= 4$:

Eps Clusters Noise points Cluster sizes
0.15 7 43 125, 74, 10, 7, 6, 4, 3
0.20 3 16 162, 90, 4
0.25 3 6 168, 93, 5
0.30 3 3 168, 96, 5
0.35 2 1 175, 96
0.40 2 0 175, 97
0.50 1 0 272

Small values fragment the data: at 0.15 the sparser edges of the two groups break off into small clusters and 43 eruptions, 16% of the data, are noise. Large values merge everything: at 0.5 the gap between the groups is bridged and there is one cluster. At 0.25 and 0.30 a third cluster of the same five eruptions appears, eruptions of 3.1 to 3.5 minutes with waits of 64 to 69 minutes, sitting in the sparse region between the main groups; at 0.30 the noise points are the 2.38-minute eruption, a 3.83-minute eruption followed by a 64-minute wait, and the longest eruption in the data, 5.1 minutes followed by a 96-minute wait. At $\varepsilon = 0.35$, the value read from the plot, the result is two clusters, 265 core points, 6 border points and one noise point.

DBSCAN on the standardized Old Faithful data with Eps = 0.35 and MinPts = 4, plotted in the original units. The two clusters are short eruptions with short waits (triangles) and long eruptions with long waits (circles). The one noise point, a 2.38-minute eruption followed by a 71-minute wait, lies between them: its eruption is short but its wait is typical of long eruptions.
DBSCAN on the standardized Old Faithful data with Eps = 0.35 and MinPts = 4, plotted in the original units. The two clusters are short eruptions with short waits (triangles) and long eruptions with long waits (circles). The one noise point, a 2.38-minute eruption followed by a 71-minute wait, lies between them: its eruption is short but its wait is typical of long eruptions.

The two clusters have mean eruption times of 2.03 and 4.29 minutes and mean waits of 54.3 and 80.0 minutes. On the 271 eruptions that DBSCAN clusters, k-means with $k = 2$ agrees almost perfectly (ARI 0.985); the difference is that k-means also assigns the 2.38-minute eruption to one of its two groups. Holding $\varepsilon = 0.35$ and varying MinPts changes the noise count from 1 (MinPts 3 or 4) to 2 (MinPts 6) and 8 (MinPts 8), with the same two clusters each time. Schubert et al. (2017, §4.2) suggest that a useful result usually leaves between 1% and 30% of the data as noise; one eruption in 272 is below that range, and $\varepsilon = 0.30$, with three noise eruptions (1.1%), is a defensible alternative that also separates the five intermediate eruptions as a small cluster of their own. The data do not settle the choice. What they do show is that the result is stable over a range of settings: two main groups, and a handful of eruptions that are unusual because they combine an eruption length typical of one group with a wait typical of the other, or are the most extreme of all.

DBSCAN as an outlier detector

DBSCAN finds outliers as a by-product of clustering, and that defines what kind of outlier it finds: a point in a region whose density is below the threshold set by $\varepsilon$ and MinPts, and not close to any dense region. Several consequences follow.

  • The answer is a label, not a score. A point is noise or it is not. Ranking points by how unusual they are needs a graded measure, such as the $k$-distance itself, which is what the sorted plot shows: the eruptions at the left of the plot are the most isolated.
  • Outliers are relative to the chosen density. At $\varepsilon = 0.15$ a sixth of the eruptions are "outliers", at 0.4 none are. Calling a point an outlier is a statement about the data and the parameters together.
  • Small groups of unusual points can form their own cluster. At $\varepsilon = 0.30$ five intermediate eruptions were dense enough among themselves to become a cluster instead of noise. Whether such a group is a cluster or a collection of anomalies is a question about the application.
  • A point can be unusual without being isolated. A point in the middle of the data with an impossible combination of values in other variables, or an error that happens to land in a dense region, is not noise to DBSCAN.

The Data Exploration topic's Detecting Outliers covers outlier methods based on single variables and on fitted models, which are often the first check.

Where one density threshold fails

DBSCAN uses one value of $\varepsilon$ and MinPts for the whole dataset, so it assumes that every cluster is at least as dense as the threshold and that clusters are separated by regions sparser than it. Ester et al. (1996, §4) chose the parameters to suit the "thinnest", least dense cluster, and noted that two clusters of different density that lie close together may then be merged.

Two tight clusters 0.26 apart at their nearest points, and one diffuse cluster to the right (seed 742), clustered with MinPts = 4. With Eps = 0.2 (left), the tight clusters are separated but 91 of the 100 diffuse points are noise, apart from a few fragments. With Eps = 0.5 (right), the diffuse cluster is found, but the tight pair merges into one cluster.
Two tight clusters 0.26 apart at their nearest points, and one diffuse cluster to the right (seed 742), clustered with MinPts = 4. With Eps = 0.2 (left), the tight clusters are separated but 91 of the 100 diffuse points are noise, apart from a few fragments. With Eps = 0.5 (right), the diffuse cluster is found, but the tight pair merges into one cluster.

The synthetic data in the figure have two tight clusters of 150 points each, with standard deviation 0.15 and centers one unit apart, and a diffuse cluster of 100 points with standard deviation 0.9. Any $\varepsilon$ small enough to keep the tight clusters apart (below the 0.26 gap) is too small for the diffuse one: at $\varepsilon = 0.2$, 91 of its 100 points are noise, and at 0.25, 64 are. Any $\varepsilon$ large enough for the diffuse cluster (0.3 or more) bridges the 0.26 gap between the tight ones. No single setting recovers all three. Methods that consider all densities at once, such as OPTICS and HDBSCAN*, were developed for this situation (Schubert et al., 2017, §2.1).

Two further limitations are worth stating:

  • High dimensions. In many dimensions, distances between points become similar to one another, and a radius that separates dense from sparse is hard to find. Schubert et al. (2017, §3.3) note that $\varepsilon$ becomes hard to choose in high-dimensional data, and Ester et al. (1996, §6) listed high-dimensional feature spaces as an open question. Reducing the dimension first, for example with principal component analysis, is a common remedy.
  • Scale. Like every distance-based method, DBSCAN depends on the units of the inputs, as the Old Faithful example showed.

In Python

scikit-learn's DBSCAN takes $\varepsilon$ as eps and MinPts as min_samples (counting the point itself). Its labels_ gives each point's cluster number, with $-1$ for noise, and core_sample_indices_ lists the core points.

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.neighbors import NearestNeighbors
from sklearn.preprocessing import StandardScaler

# F: the 272 x 2 array of eruption time and waiting time, in minutes
Z = StandardScaler().fit_transform(F)

# sorted k-distance plot for min_samples = 4: the query point is its own first neighbor,
# so the last of 4 neighbors is the 3rd nearest other point
kdist = NearestNeighbors(n_neighbors=4).fit(Z).kneighbors(Z)[0][:, -1]
kdist = np.sort(kdist)[::-1]           # plot this against rank

db = DBSCAN(eps=0.35, min_samples=4).fit(Z)
labels = db.labels_
print(labels.max() + 1, (labels == -1).sum())      # 2 clusters, 1 noise point
print(len(db.core_sample_indices_))                # 265 core points
print(F[labels == -1])                             # one eruption: 2.383 min, 71 min wait

StandardScaler divides by the standard deviation computed with $n$ rather than $n - 1$, which makes every distance larger by the same factor, $\sqrt{n/(n-1)} = 1.002$. On these data the results at $\varepsilon = 0.35$ are unchanged; at the edge of the table, $\varepsilon = 0.15$, one more eruption becomes noise (44 instead of 43). The numbers in this article are computed by tools/experiments/data-science/dbscan-outlier-detection.py in the site's repository, which loads the Old Faithful data through tools/experiments/data-science/dsdata.py.

References

  • Azzalini, A., and Bowman, A. W. (1990). A look at some data on the Old Faithful geyser. Applied Statistics, 39(3), 357–365. https://doi.org/10.2307/2347385 record
  • Ester, M., Kriegel, H.-P., Sander, J., and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96) (pp. 226–231). AAAI Press. record
  • Härdle, W. (1991). Smoothing Techniques with Implementation in S. Springer. record
  • Schubert, E., Sander, J., Ester, M., Kriegel, H.-P., and Xu, X. (2017). DBSCAN revisited, revisited: Why and how you should (still) use DBSCAN. ACM Transactions on Database Systems, 42(3), Article 19. https://doi.org/10.1145/3068335 record