Statistics Glossary → DBSCAN Spatial Clustering
DBSCAN Spatial Clusteringanalysis
A clustering method that groups location points by density, marking sufficiently crowded areas as clusters and points left in sparse areas as noise, without needing the number of clusters in advance.
Concept
Points on a map often form irregularly shaped dense areas of different sizes, with scattered lone points in between. Methods such as k-means require the number of clusters in advance, assume round clusters and must assign every point to a cluster. DBSCAN instead defines a cluster as 'an unbroken chain of points close enough to one another'; it can therefore find long, winding or irregular clusters and sets apart points that belong to no cluster as noise.
The method works with two parameters: the radius (eps) and the minimum number of points (minPts). A point with at least minPts points within its eps radius is a core point. Core points lying within each other's neighbourhoods are joined into the same cluster; points within a core point's neighbourhood that are not core points themselves join the cluster as border points, and the rest are noise. For latitude-longitude data, distances are measured as great-circle (haversine) distances. HDBSCAN finds clusters of differing density without needing eps at all, while OPTICS orders the points in a reachability plot that shows the cluster structure at different eps values at a glance.
The results are very sensitive to the choice of eps and minPts: a small eps gives many small clusters and much noise, a large eps a few big clusters. The elbow of the k-distance plot is a good starting value, but the clusters found should be checked with other values. Because DBSCAN uses a single density threshold, it struggles to capture clusters of very different densities at the same time. The method does not test the statistical significance of the clusters; it is a descriptive grouping.
When to use it
- To split event, visitor, call or observation points into dense areas without knowing the number of clusters, and to screen out scattered points as noise.
- If the clusters differ greatly in density, use HDBSCAN; if the cluster structure at different radii is to be examined together, use OPTICS.
- If a density surface is enough rather than assigning points to clusters, use KDE; if significant clusters of high or low values of a variable are sought, Getis-Ord Gi* is preferred.
An everyday example
A taxi company examines the locations of 5,000 calls received in a week and wants to decide where to station empty taxis. With eps = 150 metres and a minimum of 20 calls, DBSCAN finds, say, four dense clusters around the bus station, the hospital, the airport entrance and a shopping centre; an entertainment strip along the seafront also comes out as a single cluster despite its winding shape. Lone calls scattered across the city are marked as noise, and the company can place its waiting points at the centres of the clusters.
Parameters in MerQur
Classify by / Method
Concept: Classify is a data-exploration step that colours the points by a categorical column before the analysis; Method chooses the spatial analysis to run on the map tab. DBSCAN splits the points into clusters by density.
Everyday example: Colouring the calls as 'day' and 'night' shows, before any clustering, that night calls gather on the entertainment strip. For the question 'into which dense areas do the calls fall?', DBSCAN is chosen.
What it does: Classify by colours the points by category (data exploration); Method selects the map method.
Effect on the result: Does not change the numeric output.
Radius (eps)
Concept: eps is the largest distance at which two points count as neighbours and defines the spatial scale of 'dense'. The k-distance plot sorts each point's distance to its k-th nearest neighbour; the elbow where the curve suddenly steepens is a good starting value because it marks the natural boundary between cluster interiors and noise.
Everyday example: An eps of 150 metres is a scale at which a waiting taxi is a few minutes' walk away. With eps = 20 metres even the bus station breaks into scattered small pieces; with 2 km all the calls in the city centre become one giant cluster.
What it does: Determines the largest great-circle distance (m) at which two points count as neighbours. When the form opens, the k-distance (k = 4) knee suggestion is written; a physical distance suited to the event scale or the elbow in the k-distance plot is chosen. It is not needed in HDBSCAN.
Effect on the result: Determines the number of clusters, the number of noise points and cluster mergers.
On the validation data: In quakes (minimum 5) the suggestion 77 888.297 m gives 8 clusters and 41 noise points; 20 km gives 31 clusters and 582 noise; 50 km 22 and 163; 100 km 5 and 27; at 1 m all points are noise.
Min. points
Concept: The minimum number of points (including the point itself) that must lie within eps for a point to count as a core point. Large values count only truly crowded areas as clusters and send more points to noise; small values can turn a few chance nearby points into a cluster.
Everyday example: With a minimum of 20 calls, the front of an apartment block that received only a few calls during the week is not counted as a cluster. With a minimum of 3, dozens of small clusters of unclear meaning would form all over the city.
What it does: Determines the number of points required within eps for a core point (including itself). When it changes, the suggestion label is updated; the eps field does not change unless "Apply suggestion" is pressed.
Effect on the result: As it grows, the number of clusters decreases and noise increases.
On the validation data: At 50 km, 46 clusters and 52 noise for 2; 22 and 163 for 5; 12 and 364 for 10.
Algorithm (DBSCAN, HDBSCAN, OPTICS)
Concept: DBSCAN works with a single fixed radius. HDBSCAN builds a hierarchy of clusters across radii and picks the most stable ones; it therefore needs no eps and finds clusters of differing density together. OPTICS orders the points by reachability distance; cutting this plot at a given eps level gives clusters similar to DBSCAN.
Everyday example: If airport calls form a very dense cluster and the area around a neighbourhood market a sparser but still clear one, a single eps struggles to capture both. HDBSCAN can find each as a cluster at its own density.
What it does: DBSCAN uses a fixed eps. HDBSCAN needs no eps and finds clusters of different density (minPts = minimum samples). OPTICS produces a reachability plot; clusters are obtained by cutting the plot at eps.
Effect on the result: Changes the cluster structure markedly.
On the validation data: HDBSCAN with minimum 10 gives 17 clusters and 326 noise; with minimum 5, 37 and 263. OPTICS at 50 km 22 clusters and 180 noise.
Diagnostics ([Parameters] check box)
Concept: The diagnostics give the breakdown of points into core, border and noise, and the silhouette value. The silhouette summarises, between −1 and 1, how much closer each point is to its own cluster than to other clusters; values near 1 indicate well-separated clusters.
Everyday example: If most calls are core points, the clusters are solid and crowded; many border points mean the cluster edges are scattered. A low silhouette such as 0.1 means some clusters lie very close to each other and could be separated by reducing eps.
What it does: Gives the core/border/noise breakdown and the silhouette excluding noise (-1..1; at least 2 clusters are required).
Effect on the result: Does not change the clustering result, produces additional output.
On the validation data: At 50 km core 746, border 91, silhouette 0.1493; Boston 2000 m and minimum 10: 320, 68 and 0.1658.
Cluster table (result window, automatic)
Concept: The cluster table gives each cluster's number of points, its centre and the area of the smallest convex polygon enclosing its points (the convex hull). This lets the size and spread of the clusters be compared.
Everyday example: The table might show that the bus station cluster is the busiest with 900 calls while the entertainment strip covers the largest area. The taxi company can place its waiting points at the cluster centres and set the number of vehicles by cluster size.
What it does: Gives the cluster n, centre and convex hull area.
Effect on the result: Does not change the clustering result; summarises the clusters.
On the validation data: In the quakes cluster crossing the 180th meridian, the largest cluster hull is 298 358.67 km2.
Value (none, column)
Concept: DBSCAN uses only the locations; any value carried by the points does not enter the clustering. The value column has no effect in this method.
Everyday example: Even if each call has a fare attached, the clusters are built only from where the calls were made. To ask where expensive journeys are concentrated, a value-based method such as Getis-Ord Gi* is needed.
What it does: Not used in clustering.
Effect on the result: The selection does not change the result.
Example on real data
Data: Fiji earthquakes, R datasets quakes
Variables: 1000 earthquake epicentres (latitude/longitude, crossing the 180th meridian); radius filled from the k-distance suggestion
- Question: Into which dense clusters do the 1000 earthquake epicentres near Fiji divide in space?
- Method: DBSCAN, great-circle distance; minimum 5 points, radius eps = 77.9 km from the knee of the k-distance plot.
- Result: 8 clusters and 41 noise points; the largest cluster has 743 epicentres (centre -21.36, -177.49), the second 120 (centre -13.61, 166.84), the third 48.
- Additional finding: The data cross the 180th meridian; since longitude differences are wrapped, epicentres on both sides of the meridian are found as a single cluster.
- Limitation: The result is sensitive to the choice of eps and minimum points; the knee suggestion is a starting value and should be checked with other eps values.
- Report line: DBSCAN (eps = 77.9 km, minPts = 5) gave 8 clusters and 41 noise points.
Related concepts
ε-neighbourhood and minimum points (DBSCAN)Silhouette coefficientDistance measure (Euclidean, Manhattan, Gower, great-circle)Choosing the number of clustersElbow method and k-distance plot
The numbers in the examples are MerQur's output on independent, publicly available validation data; see the MerQur Technical Note for details.