Kurs:Maschinelles Lernen/DBSCAN

Vorherige Seite: K5 - k-Means Algorithmus

Intuition

k-Means erlaubt es zwar Cluster-Analysen durchzuführen, doch selbst mit Fuzzy-k-Means wird die Grundannahme kugelförmiger Datenwolken nicht vollkommen überwunden. Daher stellt sich die Frage, ob es auch andere Methoden gibt.

Eine Möglichkeit besteht darin, Cluster über Nachbareigenschaften zu beschreiben. Mit dem Zählen der Nachbarn innerhalb enes festen räumlichen Abstands $\varepsilon$, lassen sich so drei Fälle unterschieden:

• Ein Punkt hat viele Nachbarn. Dieser Punkt wird sich sehr zentral in einem Cluster befinden
• Ein Punkt hat wenig Nachbarn. Dieser Punkt wird also am Rand eines Clusters liegen.
• Ein Punkt hat keine Nachbarn. Dieser Punkt gehört keinem Cluster an und kann als Ausreißer, bzw. als Rauschen gewertet werden.

Dies führt zur Dichtebasierten räumlichen Clusteranalyse unter Annahme von Rauschen (engl. Density based spatial clustering of application with noise) oder kurz DBSCAN.

Beschreibung & Diskussion

Zum Durchführen von DBSCAN werden zwei Hyperparameter benötigt

1. $\varepsilon$ gibt an, in welchem Abstand die Nachbarpunkte gezählt werden. Dazu wird eine $\varepsilon$-Umgebung um den betrachteten Datenpunkt ${\vec {x}}_{i}$ gelegt.
2. Die Anzahl der Punkt $N_{\mathrm {Pts} }$ (inklusive des zentralen Punkts), ab dem von vielen Nachbarn gesprochen wird.

Auf diese Weise werden drei Klassen von Punkten unterschieden:

1. Kernelemente: In ihrer $\varepsilon$-Umgebung befinden sich mindestens $N_{\mathrm {Pts} }$ Punkte, es ist also der Zusammenhang $|U_{\varepsilon }({\vec {x}}_{i})|>N_{\mathrm {Pts} }$ gültig.
2. Nachbarn (von Kernelementen): In ihrer $\varepsilon$-Umgebung befindet sich mindestens ein Kernelement.
3. Rauschen: In ihrer $\varepsilon$-Umgebung befinden sich keine Kernelemente.

Durch die Verwendung dieser Klassifikation ist es nicht notwendig von vorneherein die Anzahl der Cluster zu kennen und es muss keine Annahme über die Form der Cluster gemacht werden.

Interaktives Beispiel

In der GeoGebra-Datei DBSCAN ist eine Reihe von Punkten zu sehen. Dazu ist eine bewegliche $\varepsilon$-Umgebung mit einer vorgegeben Anzahl $N_{\mathrm {Pts} }=5$ gegeben. Klassifiziere die Punkte in Kernelemente, Nachbarn und Rauschen und färbe sie entsprechend ein.