DBSCAN

Einfache Sprache

DBSCAN ist ein Algorithmus zum clustern von Daten. Dabei sind einzelne Cluster Regionen im Beobachtungsraum mit hoher Dichte. Kann mit Rauschen/Ausreißer umgehen und es muss nicht die Anzahl der cluster vordefiniert werden, aber dafür braucht es zwei Parameter. Das wäre zum einen $\varepsilon$ welcher die größer der Nachbarschaft definiert und $\mu$ definiert die minimale Anzahl an Nachbarn die in der Nachbarschaft eine Beobachtung sein müssen, damit die Beobachtung als dicht zählt.

Die Variablen des Clusterproblems werden durch folgende Variablen erweitert:

• $\varepsilon$ der Radius der Nachbarschaft.
• $\mu$ die minimale Anzahl an Nachbarn die in eine Nachbarschaft sein müssen damit die Nachbarschaft als dicht zählt.
• $\textrm{dist}$ sei eine Distanzfunktion in $D$.

Def. $\varepsilon$-Nachbarschaft

Für einen Datenpunkt $p\in D$ ist die $\varepsilon$-Nachbarschaft $\mathcal N_\varepsilon(p) \in D$ definiert durch

$$\mathcal N_\varepsilon(p) = \left\{q\in D\mid\textrm{dist}(p,q)\leq \varepsilon\right\}\;.$$

Def. Innenpunkte

Ein Datenpunkt $p\in D$ ist ein Innenpunkt genau dann wenn

$$|\mathcal N_\varepsilon(p)|\geq\mu\;.$$

Def. Randpunkt

Ein Datenpunkt $p\in D$ ist ein Randpunkt genau dann wenn

$$|\mathcal N_\varepsilon(p)|<\mu\land\exists q\in D:p\in\mathcal N_\varepsilon(q)\land|\mathcal N_\varepsilon(q)|\geq\mu\;.$$

Def. Ausreißerpunkt

Ein Datenpunkt $p\in D$ ist ein Randpunkt genau dann wenn er kein Randpunkt oder Innenpunkt ist.

Def. Randpunkt

Ein Datenpunkt $p\in D$ ist ein Randpunkt genau dann wenn

$$|\mathcal N_\varepsilon(p)|<\mu\land\exists q\in D:p\in\mathcal N_\varepsilon(q)\land|\mathcal N_\varepsilon(q)|\geq\mu\;.$$

Def. direkt Dichte-erreichbar

Ein Datenpunkt $p\in D$ ist direkt Dichte-erreichbar von einem Datenpunkt $q\in D$ genau dann wenn

1. $q$ ist ein Innenpunkt und
2. $p\in\mathcal N_\varepsilon(q)$.

Def. Dichte-erreichbar

Ein Datenpunkt $p\in D$ ist Dichte-erreichbar von einem Datenpunkt $q\in D$ genau dann wenn eine Folge von Datenpunkten $p_1,\ldots,p_m$ existiert die folgende Eigenschaft erfüllt:

1. $p_1=p$,
2. $p_m=q$ und
3. $p_{i+1}$ ist direkt Dichte-erreichbar von $p_i$ aus.

Def. Dichte-verbunden

Zwei Datenpunkt $p,q\in D$ sind Dichte-verbunden genau dann wenn ein Datenpunkt $o\in D$ existiert, von dem aus sowohl $p$ als auch $q$ Dichte-erreichbar ist.

Def. Cluster

Ein Cluster, im Kontext von DBSCAN, ist ein maximale Menge von Dichte-verbundenen Datenpunkten.

	\begin{algorithm}
	\caption{\textbf{DBSCAN} Algorithmus}
	\begin{algorithmic}
	\Input $D,\textrm{dist},\varepsilon, \mu$
	\Procedure{RangeQuery}{$D,\textrm{dist},p,\varepsilon$} 
    \return Die $\varepsilon$-Nachbarschaft von $p$ in $D$ mit der Distanzfunktion $\textrm{dist}$.
    \EndProcedure
    \State $c \gets 0$ 
    \Comment{Cluster-zähler und -label.}
    \ForAll{$p\in D$}
	\If{$\textrm{label}(p) \not= \textrm{undefined}$}
		\Comment{Schon bearbeitete (unten).}
		\Continue
	\EndIf
	\State $\mathcal N_\varepsilon(p) \gets $\Call{RangeQuery}{$D,\textrm{dist},p,\varepsilon$}
	\If{$\mathcal N_\varepsilon(p)<\mu$}
		\State $\textrm{label}(p) \gets \textrm{Noise}$
		\Continue
    \EndIf
    \State $c \gets c+1$
    \State $\textrm{label}(p)\gets c$
    \State $S \gets \mathcal N_\varepsilon(p) \setminus \{p\}$
	\Comment{Startmenge für das Cluster.}
    \ForAll{$q\in S$}
	    \If{$\textrm{label}(q) = \textrm{Noise}$}
		    \State $\textrm{label}(q) \gets \textrm{Border(c)}$
        \EndIf
        \If{$\textrm{label}(q) \not= \textrm{undefined}$}
		\Comment{Schon bearbeitete.}
		\Continue
		\EndIf
		\State $\mathcal N_\varepsilon(q) \gets $\Call{RangeQuery}{$D,\textrm{dist},q,\varepsilon$}
		\If{$|\mathcal N_\varepsilon(q)|\geq \mu$}
		    \State $\textrm{label}(q) \gets \textrm{Core(c)}$
		    \State $S\gets S\cup\mathcal N_\varepsilon(q)$
		    \Comment{Erweiter das Cluster.}
		\Else
			\State $\textrm{label}(q) \gets \textrm{Border(c)}$
		\EndIf
    \EndFor
    \EndFor
	\end{algorithmic}
	\end{algorithm}

Sei $n$ die Anzahl an Objekten in der Datenbank $D$. Die Durchschnittslaufzeit von DBSCAN in Räumen (Raum) mit niedriger Dimension und mit Indexstruktur (z.B. R-Baum) ist $\mathcal O(n\log n)$. Im schlimmsten Fall aber $\mathcal O(n^2)$.