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

$$\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 \}$$

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