\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb}
\usepackage{algorithm,algpseudocode}
\usepackage{bm}
\usepackage{hyperref}
\usepackage{float}
\usepackage{subcaption}
\usepackage{enumitem}
\usepackage{xcolor}
\definecolor{darkgreen}{rgb}{0.0, 0.5, 0.0}
\definecolor{aaltoBlue}{RGB}{0, 51, 102}
\definecolor{pinegreen}{cmyk}{0.92,0,0.59,0.25}
\definecolor{royalblue}{cmyk}{1,0.50,0,0}
\definecolor{lavander}{cmyk}{0,0.48,0,0}
\definecolor{violet}{cmyk}{0.79,0.88,0,0}
\definecolor{lightblue}{RGB}{173, 216, 230}
\usepackage{tikz}
\usepackage{pgfplots}
\usetikzlibrary{calc,arrows.meta,positioning,fit,shapes.geometric,shapes.misc,intersections,patterns,decorations.pathreplacing,backgrounds,matrix}
\usepgfplotslibrary{fillbetween,groupplots}
\setcounter{secnumdepth}{-\maxdimen}
% Long unbreakable tokens (the ISO/IEC author names in citations, term names
% in the title) otherwise overflow the margin by a few points; a modest
% emergency stretch lets TeX loosen the paragraph instead.
\emergencystretch=2em
\usepackage{mleftright}
% Project macros used by this entry (auto-extracted).
\newcommand{\featurevec}{\vx}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\vx}[0]{{\bf x}}

\begin{document}

\section{density-based spatial clustering of applications with noise (DBSCAN)}

\subsection*{Author and editors}
Alexander Jung\textsuperscript{*}, Department of Computer Science, Aalto University, Espoo, Finland (ORCID \mbox{\href{https://orcid.org/0000-0001-7538-0990}{0000-0001-7538-0990}}) \\
Editors: Konstantina Olioumtsevits (ORCID \mbox{\href{https://orcid.org/0000-0003-2697-8659}{0000-0003-2697-8659}}), Ekkehard Schnoor (ORCID \mbox{\href{https://orcid.org/0000-0001-8252-1499}{0000-0001-8252-1499}}), Aalto University, Espoo, Finland \\
\textsuperscript{*}Corresponding author: \href{mailto:alex.jung@aalto.fi}{alex.jung@aalto.fi}



\subsection{Abstract}
Density-based spatial clustering of applications with noise
		(DBSCAN) is a clustering method for data points with
		numeric feature vectors that finds clusters of any
		shape and decides their number itself. Given a radius
		$\varepsilon$ and a count $m^{*}$, a data point
		is a core point if at least $m^{*}$ data points
		lie within Euclidean distance $\varepsilon$ of it, and a cluster
		is a maximal set of data points connected through core
		points at most $\varepsilon$ apart. Data points that lie
		within $\varepsilon$ of no core point are noise and belong to no
		cluster. The clusters are the connected
		components of the $\varepsilon$-neighborhood graph on the
		core points, computed in a single pass, so DBSCAN iterates no
		operator and minimizes no empirical risk. Unlike
		$k$-means and a Gaussian mixture model (GMM), whose clusters are
		convex regions and ellipsoids, DBSCAN finds elongated and
		curved clusters, with the radius $\varepsilon$ and the
		count $m^{*}$ as its hyperparameters.

\subsection{Definition}
An aerial
		photograph of the Wachau, with Weissenkirchen, Rossatz and
		Duernstein along a bend of the Danube, is cut into square
		patches of $76$ m, and the $1000$ patches that lie mostly on
		vineyard parcels are data points, each characterized by a
		feature vector $\featurevec \in \reals^{2}$ that holds its
		position: easting and northing in km		(Fig.~\ref{fig_dbscan_dict}). The wine-growing areas that these
		patches form follow the river banks and the slopes. They are
		therefore elongated and curved, and their number is not known
		in advance. DBSCAN is a clustering method for
		data points with numeric feature vectors that finds
		clusters of any shape and decides their number itself: a
		cluster is a region in which data points lie densely,
		and data points that lie in no dense region are noise
		(Ester et al., 1996; Han et al., 2011). DBSCAN clusters
		by density, not by shape, and
		leaves isolated data points as noise. It is a
		hard clustering method in the sense that every
		data point belongs to at most one cluster, but unlike
		a partition of the dataset it leaves the noise points
		outside every cluster.
		\begin{figure}[H]
			\centering
			\includegraphics[width=0.9\textwidth]{dbscan_wachau_vineyard.png}
			\\[0.4em]
			\begin{tikzpicture}
			\begin{axis}[
				width=0.9\linewidth,
				xlabel={easting (km)},
				ylabel={northing (km)},
				axis lines=left, xmin=0, xmax=7.4, ymin=0, ymax=3.7,
				unit vector ratio=1 1,
				tick label style={font=\small}, label style={font=\small},
				legend style={draw=none, fill=none, font=\small,
					at={(0.98,0.98)}, anchor=north east, legend columns=3,
					/tikz/every even column/.append style={column sep=0.8em}}]
				\addplot[only marks, mark=*, mark size=0.7pt, color=black]
					table[col sep=comma, x=x1, y=x2]{dbscan_points_area1.csv};
				\addlegendentry{area 1}
				\addplot[only marks, mark=square*, mark size=0.7pt, color=gray]
					table[col sep=comma, x=x1, y=x2]{dbscan_points_area2.csv};
				\addlegendentry{area 2}
				\addplot[only marks, mark=triangle*, mark size=1.0pt, color=black]
					table[col sep=comma, x=x1, y=x2]{dbscan_points_area3.csv};
				\addlegendentry{area 3}
				\addplot[only marks, mark=diamond*, mark size=0.9pt, color=gray]
					table[col sep=comma, x=x1, y=x2]{dbscan_points_area4.csv};
				\addlegendentry{area 4}
				\addplot[only marks, mark=pentagon*, mark size=0.9pt, color=black]
					table[col sep=comma, x=x1, y=x2]{dbscan_points_area5.csv};
				\addlegendentry{area 5}
				\addplot[only marks, mark=o, mark size=1.0pt, color=gray]
					table[col sep=comma, x=x1, y=x2]{dbscan_points_small.csv};
				\addlegendentry{small cluster}
				\addplot[only marks, mark=x, mark size=2.2pt, thick, color=black]
					table[col sep=comma, x=x1, y=x2]{dbscan_points_noise.csv};
				\addlegendentry{noise}
			\end{axis}
			\end{tikzpicture}
		\caption{Top: the aerial photograph of the Wachau at patch
			resolution ($7.31 \times 3.65$ km, $96 \times 48$ patches of
			$76$ m); the $1000$ patches that lie mostly on vineyard
			parcels keep their color, all others are dimmed. Bottom: the
			same patches as data points, each drawn at its position
			and marked by the cluster that DBSCAN with
			$\varepsilon = 1.5$ patch spacings and $m^{*} = 4$
			assigns it to: five wine-growing areas, three small
			clusters, and $26$ noise patches. Orthophoto:
			basemap.at (CC BY 4.0); parcels: INVEKOS 2025, AgrarMarkt
			Austria (CC BY 3.0 AT). Data generated by
			\texttt{pythondemos/dbscan.py}
			\label{fig_dbscan_dict}}
		\end{figure}
		DBSCAN has two hyperparameters: a radius $\varepsilon > 0$
		and a count $m^{*}$. The $\varepsilon$-neighborhood of
		a data point is the set of data points within
		Euclidean distance $\varepsilon$ of it, the data point itself		included. A data point is a core point if its
		$\varepsilon$-neighborhood holds at least $m^{*}$
		data points. It is a border point if it is not a core
		point but lies in the $\varepsilon$-neighborhood of one, and it
		is noise otherwise (Fig.~\ref{fig_dbscan_points_dict}). A
		cluster is a maximal set of data points that are
		connected through core points: two core points at most
		$\varepsilon$ apart belong to the same cluster, and a
		border point belongs to the cluster of a core point in its
		$\varepsilon$-neighborhood (Ester et al., 1996). The clusters
		are therefore the connected components of the
		$\varepsilon$-neighborhood graph on the core points, the
		graph whose edges connect core points at most
		$\varepsilon$ apart, with the border points attached. DBSCAN is
		a graph-based method.
		\begin{figure}[H]
			\centering
			\begin{tikzpicture}[scale=1.1]
				\draw[gray!60, dashed] (1.0,1.0) circle (0.75);
				\draw[gray!60, dashed] (2.35,1.35) circle (0.75);
				\foreach \p in {(1.0,1.0),(1.4,0.8),(0.7,1.4),(1.5,1.35),(2.35,1.35),(2.7,1.0),(2.1,1.9)}
					\fill \p circle (2pt);
				\node[circle, draw, fill=white, inner sep=1.6pt] at (3.0,1.9) {};
				\node[circle, draw, fill=white, inner sep=1.6pt] at (0.4,0.5) {};
				\draw[thick] (4.4,0.4) -- (4.7,0.7) (4.4,0.7) -- (4.7,0.4);
				\draw[thick] (4.0,2.1) -- (4.3,2.4) (4.0,2.4) -- (4.3,2.1);
				\draw[<->, thin] (1.0,1.0) -- (1.75,1.0) node[midway, below, font=\scriptsize] {$\varepsilon$};
				\node[font=\scriptsize, anchor=west] at (5.0,2.2) {$\times$ noise};
				\node[font=\scriptsize, anchor=west] at (5.0,1.7) {$\circ$ border point};
				\node[font=\scriptsize, anchor=west] at (5.0,1.2) {$\bullet$ core point};
			\end{tikzpicture}
			\caption{Core points, border points and noise for
				$m^{*} = 4$. The two dashed circles are the
				$\varepsilon$-neighborhoods of two core points; each holds
				at least four data points. The two border points lie
				within $\varepsilon$ of a core point but have fewer than
				four data points in their own neighborhoods, and the
				two noise points lie within $\varepsilon$ of no core point.
				All filled and open points form one cluster
				\label{fig_dbscan_points_dict}}
		\end{figure}		DBSCAN computes the clusters in a single pass over the
		data points. It picks a core point not yet assigned to a
		cluster, collects every data point reachable from it
		through core points at most $\varepsilon$ apart, declares the
		collection a cluster, and moves on to the next core point
		not yet assigned. Algorithm~\ref{alg_dbscan_dict} states the
		pass in full.
		\begin{algorithm}[H]
		\caption{DBSCAN (Ester et al., 1996)
			\label{alg_dbscan_dict}}
		\begin{algorithmic}[1]
			\Statex \textbf{Input:} feature vectors of the
				data points, radius $\varepsilon > 0$, count $m^{*}$
			\State mark a data point as a core point if at least
				$m^{*}$ data points, itself included, lie within
				Euclidean distance $\varepsilon$ of it
			\State mark every data point as unassigned
			\For{each unassigned core point}
				\State open a new cluster and assign the core point
					to it
				\While{the cluster holds a core point whose
					$\varepsilon$-neighborhood has not been collected}
					\State assign every unassigned data point of that
						$\varepsilon$-neighborhood to the cluster
				\EndWhile
			\EndFor
			\Statex \textbf{Output:} the clusters; every
				data point still unassigned is noise
		\end{algorithmic}
		\end{algorithm}
		No operator is iterated, so the fixed-point iteration view
		that applies to Lloyd's algorithm and the expectation–maximization (EM)
		algorithm does not apply here. A second pass over the
		result changes nothing, and the result depends on no
		initialization, so DBSCAN has no local optima to get trapped
		in. DBSCAN minimizes no empirical risk; it is defined by its
		notion of a cluster alone.
\par
		On the vineyard patches with $\varepsilon = 1.5$ patch spacings
		and $m^{*} = 4$, DBSCAN finds $934$ core points, $40$
		border points and $26$ noise patches, grouped into eight
		clusters, five of which hold at least $20$ patches: the
		wine-growing areas of the strip (Fig.~\ref{fig_dbscan_dict}).
		The river, wider than $\varepsilon$, separates the areas on its
		two banks.
\par
		The radius $\varepsilon$ decides which structures count as
		clusters (Fig.~\ref{fig_dbscan_eps_dict}). With
		$\varepsilon = 1.1$ patch spacings, so that only the four
		axis-aligned neighbors of a patch are within reach, the
		patches fall into $24$ clusters with $6\%$ noise, and
		several areas break along their thin stretches. With $\varepsilon = 3$ patch spacings, six clusters remain and
		no patch is noise. However, two areas that $\varepsilon = 1.5$
		keeps apart are joined. The number of clusters and the
		noise share both fall as $\varepsilon$ grows. A common way to
		choose $\varepsilon$ is to place it where the sorted
		Euclidean distances of the data points to their
		$m^{*}$-th nearest neighbor start to rise
		steeply (Ester et al., 1996).
		\begin{figure}[H]
			\centering
			\begin{tabular}{@{}c@{\hspace{0.015\textwidth}}c@{\hspace{0.015\textwidth}}c@{}}
				\includegraphics[width=0.32\textwidth]{dbscan_wachau_eps1.png} &
				\includegraphics[width=0.32\textwidth]{dbscan_wachau_eps2.png} &
				\includegraphics[width=0.32\textwidth]{dbscan_wachau_eps3.png} \\
				(a) & (b) & (c)
			\end{tabular}
			\caption{The vineyard patches of Fig.~\ref{fig_dbscan_dict}
				painted by cluster for $m^{*} = 4$ and
				(a) $\varepsilon = 1.1$, (b) $\varepsilon = 1.5$, and
				(c) $\varepsilon = 3$ patch spacings; noise patches are
				black. A color identifies a cluster within one
				panel only, and the colors differ in brightness, so the
				clusters stay apart in a grayscale print.
				Orthophoto: basemap.at (CC BY 4.0). Data
				generated by \texttt{pythondemos/dbscan.py}
				\label{fig_dbscan_eps_dict}}
		\end{figure}
		DBSCAN differs from $k$-means and from a Gaussian mixture model (GMM) in three
		ways. First, a cluster of $k$-means is a convex
		region of the feature space and a cluster of a
		GMM is an ellipsoid, whereas a DBSCAN cluster can
		have any shape that a chain of nearby data points can
		trace. On the vineyard patches, $k$-means with five
		clusters splits one area and one of its clusters
		joins two areas, since an area that curves along the river is
		not convex. Second, the number of clusters is an
		input of $k$-means and of a GMM but an output of
		DBSCAN, at the price of the two hyperparameters
		$\varepsilon$ and $m^{*}$. Third, $k$-means and a
		GMM assign every data point to a cluster,
		whereas DBSCAN leaves outliers as noise. DBSCAN shares
		its graph-based view of a cluster with
		spectral clustering. That method builds a similarity graph, a
		graph whose edges connect similar data points, and
		clusters its nodes by the eigenvectors of the
		Laplacian matrix, a matrix that encodes the graph,
		instead of by the connected components of the
		$\varepsilon$-neighborhood graph.

\subsection{Cross References}
clustering, cluster, hard clustering, $k$-means, GMM, spectral clustering, graph, neighborhood, Euclidean distance, outlier, hyperparameter

\subsection{References}
\begin{enumerate}
  \item Ester et al. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. In: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, pp.~226--231.
  \item Han et al. (2011). Data Mining: Concepts and Techniques. 3rd ed., Morgan Kaufmann, Waltham, MA, USA.
\end{enumerate}

\end{document}
