MerQuR+Statistics Glossary

Statistics Glossary → DBSCAN / HDBSCAN

DBSCAN / HDBSCANanalysis

A density-based clustering method that treats regions where points are densely packed as clusters and points left in sparse regions as noise (outliers), without needing the number of clusters in advance.

Concept

Methods such as K-means implicitly assume that clusters are round and of similar size, and they assign every point to some cluster. In real data, however, clusters may be crescent-shaped, strip-like or irregular, and some points belong to no group at all. DBSCAN defines a cluster as 'an area where points are packed closely together, separated from others by sparse regions'; it thus finds dense regions whatever their shape and sets lone points aside as noise.

The method rests on two settings: the neighbourhood radius ε and the minimum number of samples (minPts). A point is a core point if at least minPts points (including itself) lie within radius ε. Core points within each other's neighbourhoods are chained together into a cluster; points in a core point's neighbourhood that are not core points themselves join the cluster as border points; points within no core point's neighbourhood count as noise. HDBSCAN, instead of choosing a single ε, builds a hierarchy that scans all density levels and selects the most stable clusters, so it can find clusters of different densities together.

The main difficulty with DBSCAN is choosing ε: a small ε turns many points into noise and breaks clusters up, while a large ε merges separate clusters. The k-distance (elbow) plot gives guidance on a suitable ε. Because a single ε is used, clusters of very different density cannot all be separated well at once; HDBSCAN is preferred in that case. Distances are scale-sensitive, so the variables should usually be standardised; as the number of variables grows, the notion of density weakens. Points marked as noise are not errors to be deleted but unusual observations that deserve separate attention.

When to use it

  • When clusters are irregular in shape, their number is unknown and outlying points should be identified separately; especially with spatial data (accident or earthquake locations, point clouds, GPS records).
  • If the clusters differ clearly in density, or a suitable value of ε cannot be estimated, HDBSCAN is used instead of DBSCAN.
  • If the clusters are roughly round and of similar size and every observation must be assigned to a group, K-means is more suitable; if nested structure is of interest, hierarchical clustering.

An everyday example

A city's traffic department is examining the map coordinates of 600 accidents over the last three years. Some accidents are packed tightly at certain junctions and along one boulevard, while the rest are scattered across the city. DBSCAN marks places with, say, at least 8 accidents within 150 metres as 'black spot' clusters, and captures the strip of accidents along the boulevard as a single cluster even though it is not round. Isolated accidents count as noise, and the city gives priority for road improvements to the clusters.

Parameters in MerQur

ε (eps; 0.01 = automatic)

Concept: ε is the radius that counts as a point's 'neighbourhood'; density is measured by the number of points within this radius. A small ε counts only very dense regions as clusters; a large ε draws sparse regions into clusters too and can merge separate clusters.

Everyday example: With ε = 50 metres, only accidents piled up at the corners of the same junction form a cluster and many accidents count as noise. With ε = 1 kilometre, the black spots of neighbouring districts merge into one giant cluster.

What it does: Neighbourhood radius; a point with at least "min samples" points (itself included) within ε is a core point. The automatic ε is the 90th percentile of the k-distances (k = min samples).

Effect on the result: A small ε gives much noise and many small clusters, a large ε little noise and merged clusters; all counts change.

On the validation data: (iris z, min samples 5): ε 0.3: 3 clusters and 120 noise; 0.5: 2 and 34; 1.0: 2 and 3; automatic ε = 0.7565.

→ ε-neighbourhood and minimum points (DBSCAN)

Min. samples (minPts)

Concept: The minimum number of points (including itself) that must lie in a point's ε-neighbourhood for it to count as a core point; it sets the density threshold. A large value gives fewer core points and more noise; a small value gives small clusters that are sensitive to noise.

Everyday example: With minPts = 3, every corner with three accidents becomes a black-spot candidate and chance closeness can count as a cluster. Requiring minPts = 10 leaves only places where accidents truly keep recurring as clusters.

What it does: Minimum number of points in the ε neighbourhood (including the point) for a point to be a core point.

Effect on the result: A larger value reduces the number of core points and increases noise; the number of clusters changes.

On the validation data: (iris z, ε 0.5): 2: 9 clusters and 13 noise; 3: 7 and 17; 5: 2 and 34; 10: 3 and 89. Min samples 2 is equivalent to cutting single-linkage hierarchical clustering at height ε.

→ ε-neighbourhood and minimum points (DBSCAN)

Missing Data

Concept: Either removes observations with missing measurements from the analysis or fills the missing value with the mean, the median or an estimate from the most similar observations. Filled-in values can pull points artificially towards the 'average' and so affect the density structure.

Everyday example: If one of the coordinates is missing in some accident records, deleting those records is the safest route; filling the missing coordinate with the city average piles the accidents up in the city centre on the map and can create a fake cluster.

What it does: Drops rows with missing values or imputes them on the raw scale with the mean, median or 5 nearest neighbours.

Effect on the result: n and therefore the clusters and the number of noise points change.

On the validation data: (airquality, z, ε = 1.0): drop: 1 cluster and 12 noise (n = 111); mean: 1 and 24; median: 1 and 20; KNN: 2 and 9 (n = 153). At ε = 0.5 all points are noise; in this case the silhouette is undefined and "-" is shown.

→ Single imputation (mean, median, kNN filling)

Distance metric (Euclidean / Manhattan / Chebyshev / Haversine (latitude, longitude; ε in km))

Concept: How the distance between points is measured: Euclidean is the straight line, Manhattan the total difference along the axes, Chebyshev the largest single difference. Haversine gives the great-circle distance over the Earth's surface in kilometres from latitude and longitude; it is used with geographic coordinates because straight-line distance in degrees is misleading.

Everyday example: If the accidents' latitude and longitude are recorded in degrees, one degree of longitude corresponds to different distances at the equator and at northern latitudes. With Haversine, ε is given directly as '0.15 km' and the clusters are built on real distances.

What it does: Distance between points; Haversine gives the great-circle distance in km from latitude and longitude (ε in km).

Effect on the result: The neighbourhoods and therefore the clusters and the noise change.

On the validation data: iris z Manhattan 4 clusters and 110 noise; Chebyshev 2 and 7; quakes haversine (km, raw): ε 50: 22 and 163; automatic ε = 71.2503 km: 9 and 57; ε 100 and min samples 10: 5 and 48. Haversine uses the great-circle formula with an Earth radius of 6371.0088 km.

→ Distance measure (Euclidean, Manhattan, Gower, great-circle)

z-standardize

Concept: Transforms the variables to mean 0 and standard deviation 1. If the variables are in different units, the one with the largest units decides the neighbourhoods; standardisation prevents this, but a suitable ε must then also be thought of in standard-deviation units.

Everyday example: If accidents are to be clustered by time of day (0-24) and vehicle speed (0-150 km/h) as well as location, speed takes much larger numbers than time and decides the neighbourhoods on its own. After standardisation the three variables carry similar weight.

What it does: Converts the variables to z-scores (n-1 denominator).

Effect on the result: With variables on different scales the neighbourhoods change; the suitable ε depends on the transformation.

On the validation data: When off, iris ε 0.5: 2 clusters and 17 noise; ε 0.7: 2 and 3; automatic ε = 0.6164: 2 and 9; ruspini ε 15: 4 and 3. When on, z uses the standard deviation with the n-1 denominator.

→ z-score (standardization)

Chart (Cluster scatter / k-distance (elbow) plot) and Save cluster membership

Concept: The cluster scatter shows the clusters and noise points in colour. The k-distance plot sorts every point's distance to its k-th nearest neighbour from smallest to largest; the 'elbow' where the curve suddenly rises is a good candidate for ε. The save option writes the cluster number (including noise) to the dataset.

Everyday example: If in the k-distance plot most accidents lie 100-150 metres from their 8th nearest neighbour while the curve shoots up beyond 200 metres, 150-200 metres is a reasonable choice for ε. With the saved cluster column, the table shows which black spot each accident belongs to.

What it does: Cluster scatter plot or k-distance (elbow) plot; writing the cluster number to the dataset.

Effect on the result: Only the chart, or adds a column to the dataset; the numerical results do not change.

→ Scatter plot

Algorithm (DBSCAN / HDBSCAN)

Concept: DBSCAN works with a single density threshold (ε); HDBSCAN builds a hierarchy that tracks how clusters are born and merge across all possible values of ε, and selects the clusters that persist the longest (the most stable). It can thus find both dense and sparse clusters at once and removes the problem of choosing ε.

Everyday example: If accidents are very frequent at the city-centre junctions, but sparser though still clearly concentrated at a dangerous bend on the ring road, a single ε either merges the centre or misses the bend. HDBSCAN can catch both black spots separately, each at its own density level.

What it does: HDBSCAN does not require ε; min samples is both the core distance and the minimum cluster size.

Effect on the result: HDBSCAN does not use ε; clusters are selected from the density hierarchy, and the numbers of clusters and noise points change.

On the validation data: iris z: 2 clusters and 2 noise. moons (raw, minPts 5): 3 clusters, 0 noise, 25/25/50. DS3 (raw, minPts 25): 6 clusters and 813 noise.

Example on real data

Data: Fisher 1936 iris, R datasets (n = 150)

Variables: features Sepal.Length, Sepal.Width, Petal.Length, Petal.Width (sepal and petal measurements)

  • Question: Into how many natural density-based clusters do the four measurements of iris flowers divide, and which observations belong to no cluster (noise)?
  • Setup: The variables were converted to z-scores; neighbourhood radius ε = 0.5, minimum samples 5 (including the point). The k-distance percentiles (50% = 0.4601, 90% = 0.7565) show that ε = 0.5 lies in the middle of the distribution, a rather narrow choice.
  • Result: 2 clusters were found (45 and 71 points); 34 points (22.7%) were counted as noise. Of the points, 93 are core and 23 border points.
  • Cluster quality: The mean silhouette of the non-noise points is 0.6559; the clusters are well separated.
  • Descriptive: The first cluster corresponds to the setosa species; versicolor and virginica are very close to each other and merge into one cluster. Most of the noise consists of sparse extreme observations of these two species.
  • Limitation: The result is very sensitive to ε (ε = 0.3 gives 3 clusters and 120 noise points, ε = 1.0 gives 2 clusters and 3 noise points); ε should be chosen at the elbow of the k-distance plot.
  • APA: DBSCAN (ε = 0.5, minPts = 5, z-scores) gave two clusters (n = 45 and 71) and 34 noise points; mean silhouette = .66.

Related concepts

Scatter plotε-neighbourhood and minimum points (DBSCAN)z-score (standardization)Single imputation (mean, median, kNN filling)Distance measure (Euclidean, Manhattan, Gower, great-circle)Elbow method and k-distance plotOutlierChoosing the number of clusters

The numbers in the examples are MerQur's output on independent, publicly available validation data; see the MerQur Technical Note for details.