Density-Based Spatial Clustering of Applications with Noise#

Density-based spatial clustering of applications with noise (DBSCAN) is a data clustering algorithm proposed in [Ester96]. It is a density-based clustering non-parametric algorithm: given a set of observations in some space, it groups together observations that are closely packed together (observations with many nearby neighbors), marking as outliers observations that lie alone in low-density regions (whose nearest neighbors are too far away).


Given the set \(X = \{x_1 = (x_{11}, \ldots, x_{1p}), \ldots, x_n = (x_{n1}, \ldots, x_{np})\}\) of \(n\) \(p\)-dimensional feature vectors (further referred as observations), a positive floating-point number epsilon and a positive integer minObservations, the problem is to get clustering assignments for each input observation, based on the definitions below [Ester96]:

core observation#

An observation \(x\) is called core observation if at least minObservations input observations (including \(x\)) are within distance epsilon from observation \(x\);

directly reachable#

An observation \(y\) is directly reachable from \(x\) if \(y\) is within distance epsilon from core observation \(x\). Observations are only said to be directly reachable from core observations.


An observation \(y\) is reachable from an observation \(x\) if there is a path \(x_1, \ldots, x_m\) with \(x_1 = x\) and \(x_m = y\), where each \(x_{i+1}\) is directly reachable from \(x_i\). This implies that all observations on the path must be core observations, with the possible exception of \(y\).

noise observation#

Noise observations are observations that are not reachable from any other observation.


Two observations \(x\) and \(y\) are considered to be in the same cluster if there is a core observation \(z\), and \(x\) and \(y\) are both reachable from \(z\).

Each cluster gets a unique identifier, an integer number from \(0\) to \(\text{total number of clusters } – 1\). Each observation is assigned an identifier of the cluster it belongs to, or \(-1\) if the observation considered to be a noise observation.


The following computation modes are available:


Batch Processing:

Distributed Processing: