data_mining:clustering:dbscan [AE Wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Dichtebasierte Clustering Methoden ======

  * Können Cluster willkürlicher Form finden
  * Rauschen behandeln
  * Ausreißer erkennen

===== Input-Parameter =====

  * $\varepsilon$: Maximaler Radius (Nachbarschaft) um Punkt $p_i$
  * MinPts m: Minimale Zahl der Punkte in einer $\varepsilon$-Nachbarschaft von $p_i$.

===== Definitionen =====

Funktion, die alle $p_q$ innerhalb einer $\varepsilon$-Nachbarschaft liefert: $n_\varepsilon(p_i) : \{p_q | d(p_i,p_q) \leq \varepsilon\}$

Directly density-reachable point: 

  * $p_q$ gehört zu $n_\varepsilon(p_i)$.
  * Kernpunkt liegt vor, d.h. es gilt $|n_\varepsilon(p_i)|\geq m$

Density-reachable: $p_q$ d-r. von $p_i$ in Bezug auf $\varepsilon$ und MinPts, wenn eine Kette von Punkten $p_i \rightarrow p_{i+1} \rightarrow p_{i+x} = p_q$ existiert, sodass $p_{i+x}$ **directly** density-reachable von $p_{i+x-1}$ ist.

Density-connected: $p_q$ d-c. zu $p_i$ in Bezug auf $\varepsilon$ und MinPts, wenn es einen Punkt o gibt, sodass p und q d-r. von o sind.

===== DBSCAN Algorithmus =====
  - Willkürlich Punkt p wählen
  - Alle Punkte ermitteln die d-r. von P sind (bzgl. $\varepsilon$ und MinPts m).
  - Wenn p ein Kernpunkt ist, wird ein Cluster gebildet: Iterieren über alle d-r. Punkte und Cluster erweitern, wo zulässig. Wenn p ein Randpunkt ist, sind keine Punkte mehr von p erreichbar.
  - Nächsten Punkt wählen, bis alle Punkte verarbeitet wurden.