data_mining:clustering:dbscan

Dichtebasierte Clustering Methoden

  • Können Cluster willkürlicher Form finden
  • Rauschen behandeln
  • Ausreißer erkennen
  • $\varepsilon$: Maximaler Radius (Nachbarschaft) um Punkt $p_i$
  • MinPts m: Minimale Zahl der Punkte in einer $\varepsilon$-Nachbarschaft von $p_i$.

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.

  1. Willkürlich Punkt p wählen
  2. Alle Punkte ermitteln die d-r. von P sind (bzgl. $\varepsilon$ und MinPts m).
  3. 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.
  4. Nächsten Punkt wählen, bis alle Punkte verarbeitet wurden.
  • data_mining/clustering/dbscan.txt
  • Last modified: 2017/02/19 15:30
  • by phreazer