Density-based Spatial Clustering of Applications with Noise.

Density-based spatial clustering of applications with noise (DBSCAN) is a clustering algorithm.

Key Concepts

Let's say $X$ is the sef of all data points, $dist(x, y) \in R$ is a function to measure the distance between any two data points, $\epsilon \in R^+$ is the distance limitation and $minPts \in Z^+$ is the density limitation.

• Given $\epsilon \in R^+$ and $p \in X$, the $\epsilon$ neighbors of $p$ is $N_{\epsilon}(x) = \{ y \in X \mid dist(x, y) \leq \epsilon \}$.
• Given $x \in X$, the density of $x$ is $\rho(x) = \lvert N_{\epsilon}(x) \rvert$.
• Given $x, y \in X$, if $y \in N_{\epsilon}(x)$ and $\rho(x) \geq minPts$, then we say $y$ is directly density-reachable from $x$.
• Given $x, y \in X$, if there is a sequence $p_1,p_2,\cdots,p_n$, where $x = p_1$, $y = p_n$, and every $p_{i + 1}$ is directly density-reachable from $p_i$, then we say $y$ is density-reachable from $x$.
• Given $x, y \in X$, if there is a data point $o \in X$, where both $x$ and $y$ are density-reachable from $o$, then we say $x$ and $y$ are density-connected.

The data points $X$ will be divided by DBSCAN into several clusters (containing core points and density-reachable points) based on density-connectivity and outliers.

• Given $\epsilon \in R^+$, $minPts \in Z^+$ and $x \in X$, if $\rho(x) \geq minPts$ then we say $x$ is a core point.
• Given $x \in X$, if $x$ is not a core point but is density-reachable from any core points, then we say $x$ is a density-reachable point.
• Any other data points in $X$ are outliers.

Pseudo Code

References

• Wikipedia contributors. (2020, April 17). DBSCAN. Wikipedia, The Free Encyclopedia. Retrieved from https://en.wikipedia.org/wiki/DBSCAN