Clustering DBSCAN

—> Density-Based Spatial Clustering of Applications with Noise (dichtebasiert)

Der Algorithmus dient der Identifikation von Clustern in einer gegebenen Datenmenge. Er arbeitet basierend auf der Definition einer Punktdichte (2D: "Punkte je Fläche", " MinPts je eps "), wodurch er einige Unzulänglichkeiten von k-means ausgleicht

—> wenn mindestens MinPts in Epsilonumgebung zu finden sind, dann Cluster gefunden

1. Was ist ein geeignetes Epsilon?

   —> Radius Kreis für Abstand

   —> Wie viele MinPoints?

2. Punkt (Featurevektor) zufällig wählen

   —> als bekannt labeln

3. Menge N von Featurevektoren in Epsilonumgebung + Punkt selbst mitzählen (Id oder Vektorkoordinaten vermerken)

4. Anzahl an Umgebungspunkten > MinPoints?

   —> dann kein Rauschen

5. Cluster um 1 erhöhen (zuerst 0+1) und Punkt Cluster hinzufügen

6. alle Punkte in N betrachten, als bekannt Labeln und aus N löschen, stattdessen Menge M hinzufügen

7. Anzahl an Umgebungspunkten > MinPoints?

   —> dann kein Rauschen

8. M und N vereinigen, wodurch Punkt wieder N hinzugefügt wird

9. alle Punkte die nicht rauschen sind und keinem Cluster zugehörig sind —> Cluster des Kernpunkts hinzufügen

10. Und von vorne

Kernpunkte: Befindet sich der Punkt X innerhalb der Epsilonumgebung und hat dieser mindestens R Nachbarn, dann nennt DBSCAN diesen Punkt einen ‚Kernpunkt‘

Randpunkte / dichterreichbare Punkte: Wenn weniger als R Nachbarn in der Umgebung liegen, dann nennt der Algorithmus diesen ‚Randpunkt‘. Die Kernpunkte befinden sich in unmittelbarer Nähe. In Epsilonumgebung nah genug aber kein Kernpunkt. Werden zu Cluster gezählt.

Rauschen: Ein Rauschpunkt hat keine Nachbarn in seinem direkten Umkreis. Nicht in der Epsilonumgebung von einem Kernpunkt. Weder Kernpunkte noch dichteereichbarer Punkt.

Vorteile

• Keine geometrische Grundlage notwendig

• Ähnlichkeits- oder Distanzmaß reicht aus

Nachteile

• Funktion gibNachbarn()

• Werte für ε und MinPts