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).

Details¶

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.
reachable¶: 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.
cluster¶: 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.

Computation¶

The following computation modes are available:

Examples¶

Batch Processing:

dbscan_dense_batch.cpp

Distributed Processing:

dbscan_dense_distr.cpp

oneDAL documentation

Density-Based Spatial Clustering of Applications with Noise¶

Details¶

Computation¶

Examples¶