DBSCAN1 is a very popular density-based clustering algorithm. The main idea is to detect clusters in a similar way as we perceive structure: the density of data points \(\fvec{p}_i\) is higher inside the cluster than outside of it. DBSCAN links these points together allowing it to detect arbitrarily shaped clusters. For this, each point defines a neighbourhood
\begin{equation} \label{eq:DBSCAN_Neighbourhood} N_{\varepsilon}(\fvec{p}) = \{ \fvec{p}_i, i=1,2\ldots \,|\, \left\| \fvec{p}_i - \fvec{p} \right\|_2 \leq \varepsilon \} \end{equation}which is used to search for other points so that the links can be created. Since \eqref{eq:DBSCAN_Neighbourhood} uses the Euclidean distance, the neighbourhood is defined by a circle with radius \(\varepsilon\) around a point \(\fvec{p}_i\) in the dataset. This is visualized in the following figure for a small two-dimensional example.
List of attached files:
- DBSCAN.nb [PDF] (Mathematica notebook used to create the basic visualization (as SVG file) which is later animated with JavaScript)
← Back to the overview page