Skip to content
Last Dictionary
Plane
Machine LearningData & Datasets

DBSCAN

noun/DEE-bee-scan/Also: density-based spatial clustering of applications with noise, HDBSCAN, OPTICS, density-based clustering

In plain wordsA clustering method that finds groups as crowded regions of data separated by sparse ones, so it can discover oddly shaped groups and set stray points aside as noise.

  1. A density-based clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size. algorithm ('density-based spatial clustering of applications with noise') controlled by two parameters: a neighborhood radius ε and a minimum count minPts. A point with at least minPts points within distance ε is a core point; a cluster is a maximal set of core points connected through overlapping neighborhoods, together with border points that lie within ε of a core point; all remaining points are labeled noise. DBSCAN recovers clusters of any shape, sets outliers aside explicitly and does not have to be told how many clusters to look for, and with a spatial index it is usually fast on low-dimensional data, though its worst case is quadratic. Its weaknesses are a single global density threshold, which fails when clusters differ in density, sensitivity to ε, and poor behavior in high dimensions, where distances concentrate (curse of dimensionalitycurse of dimensionality, n.: The problems that pile up when each item is described by very many measurements: even huge datasets end up thinly scattered across the possibilities, and 'near' and 'far' stop meaning much.). OPTICS and HDBSCAN generalize it to varying densities and return a hierarchy of clusters.

    DBSCAN labeled 3% of the GPS pings as noise and found the delivery hubs without being told how many there were.

Origin

Introduced by Martin Ester, Hans-Peter Kriegel, Jörg Sander and Xiaowei Xu at the Second International Conference on Knowledge Discovery and Data Mining (KDD-96) in 1996. It became one of the most cited clustering algorithms and received the ACM SIGKDD Test of Time Award in 2014. Ricardo Campello, Davoud Moulavi and Sander introduced the hierarchical variant HDBSCAN in 2013.

Related

See also
  • clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size.
  • k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat.
  • hierarchical clusteringhierarchical clustering, n.: A way of grouping data that builds a family tree of clusters, joining the most similar items step by step, so you can cut the tree at whatever level of detail you need.
  • anomaly detectionanomaly detection, n.: Automatically spotting the rare data points that don't fit the usual pattern, such as a fraudulent card payment, a machine about to fail or an intruder on a network.
  • density estimationdensity estimation, n.: Working out from a sample of data how likely different values are, by drawing a smooth curve or surface showing where data points bunch up and where they are rare.
  • curse of dimensionalitycurse of dimensionality, n.: The problems that pile up when each item is described by very many measurements: even huge datasets end up thinly scattered across the possibilities, and 'near' and 'far' stop meaning much.
Contrast with
  • k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat.

Sources

  1. Ester, M., Kriegel, H.-P., Sander, J. & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. Proc. KDD-96, AAAI Press.
  2. Campello, R. J. G. B., Moulavi, D. & Sander, J. (2013). Density-Based Clustering Based on Hierarchical Density Estimates. Proc. PAKDD 2013.

Mentioned in

anomaly detectionanomaly detection, n.: Automatically spotting the rare data points that don't fit the usual pattern, such as a fraudulent card payment, a machine about to fail or an intruder on a network., clusteringclustering, n.: Automatically sorting things into groups of similar items when nobody has said in advance what the groups should be, like sorting a drawer of odd socks into piles by color and size., hierarchical clusteringhierarchical clustering, n.: A way of grouping data that builds a family tree of clusters, joining the most similar items step by step, so you can cut the tree at whatever level of detail you need., isolation forestisolation forest, n.: A method for spotting unusual data points by repeatedly slicing the data at random: odd points get cut off from the rest after only a few slices, while ordinary points take many., k-means clusteringk-means clustering, n.: A simple way to split data into a chosen number of groups: guess group centers, assign every point to its nearest center, move each center to the middle of its points, and repeat.