Density-based spatial clustering of applications with noise (DBSCAN)

Table of Contents

Overview

  • Clustering algorithm

Preliminary

core points
A point $p$ which has at least min_pts within a distance $\epsilon$ of it (including itself) These points within distance $\epsilon$ are said to be directly reachable from $p$.
(density-)reachable points
A point $q$ is reachable from point $p$ if there exists a path $p_1, ..., p_n$ with $p_1 = p$ and $p_n = q$, where each $p_{i+1}$ is directly reachable from $p_i$. That is; all points on the path must be core points, with the possible exception of $q$.
outliers
All points not reachable from other points.