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.

Figure 1: Small example to depict the neighbourhood \(N_{\varepsilon}(\fvec{p})\) of \eqref{eq:DBSCAN_Neighbourhood} used in DBSCAN. Every point inside a circle is considered to be part of the neighbourhood. Use the slider to control the size of the circle via the neighbourhood radius \(\varepsilon\). The circles can be displayed in various ways: temporary when hovering over a point, permanently on click or all together via the buttons.

List of attached files:

โ† Back to the overview page