Clustering mit DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) ist ein Clustering-Algorithmus, der Punkte gruppiert, die nahe beieinander liegen, basierend auf einem Dichtekriterium. Im Gegensatz zu anderen Clustering-Modellen wie K-Means kann DBSCAN Cluster beliebiger Formen identifizieren und erfordert nicht, dass die Anzahl der Cluster im Voraus angegeben wird. Es ist weniger empfindlich gegenüber Rauschen und kann Cluster unterschiedlicher Dichte verarbeiten.

Um mit dem DBSCAN-Algorithmus ein zufriedenstellendes Ergebnis zu erzielen, wird angenommen, dass die verschiedenen Cluster in den Daten eine relativ ähnliche Dichte haben, wobei wir mit Dichte die Anzahl der Punkte meinen, die in jeder definierten Nachbarschaft N(x, ε) existieren durch einen Radius ε und einen Datenpunkt x. Diese Behauptung kann optisch verifiziert werden, indem man das DBSCAN-Beispiel in der Mitte des obigen Bildes betrachtet, wo die Punkte um den blauen Cluster, die eine etwas andere Dichte haben, als Teil des orangefarbenen Clusters betrachtet werden.

Die einzigen Parameter, die zur Implementierung von DBSCAN benötigt werden, sind:

• MinPts = Die Mindestpunktzahl, die eine Nachbarschaft eines Datenpunkts haben muss, damit der Datenpunkt als Kernpunkt des Clusters betrachtet wird
• ε = Der Radius der Nachbarschaften (d. h. wie groß unsere „Kreise“ um den zentralen Datenpunkt sein sollen)

1. Kernpunkt: Dieser Datenpunkttyp hat eine Dichte ≥ MinPts. Das bedeutet, dass die Anzahl der Datenpunkte in N(x, ε) größer oder gleich MinPts ist.

2. Grenzpunkt: Dieser Datenpunkttyp hat eine Dichte < MinPts, aber eine Distanz (y, cp) ≤ ε, wobei cp ein Kernpunkt ist. Das bedeutet, dass diese Punkte nicht die erforderliche Dichte haben, um Kernpunkte zu sein, aber sie sind auch nicht so weit von einem Kernpunkt entfernt, um als Rauschen betrachtet zu werden.

Beispiel: MinPts = 4, ε = 3, dann ist y ein Grenzpunkt

3. Rauschpunkt: Dieser Datenpunkttyp hat eine Dichte < MinPts und eine Distanz (z, cp) ≥ ε. Das bedeutet, dass es nicht die erforderliche Dichte hat, um ein Kernpunkt zu sein, und es ist weit entfernt von jedem Kernpunkt.

Beispiel: MinPts = 4, ε = 3, dann ist z ein Rauschpunkt

Basierend auf diesem Prozess der Kategorisierung von Datenpunkten geht der DBSCAN-Algorithmus wie folgt vor:

1. Iterieren Sie über jeden Datenpunkt und klassifizieren Sie ihn in eine dieser drei Kategorien
2. Beseitigen Sie alle Rauschpunkte
3. Betrachten Sie alle Kernpunkte, die nahe beieinander liegen, als im selben Cluster befindlich ( Das heißt, wenn cp_1 und cp_2 Kernpunkte sind und Abstand (cp_1, cp_2) ≤ ε, dann werden cp_1 und cp_2 als im selben Cluster befindlich betrachtet. )
4. Ordnen Sie jeden Grenzpunkt in einem Cluster von Kernpunkten basierend auf ihrer Entfernung zu ( Grenzpunkte, die genau in der Mitte zwischen zwei Clustern liegen, müssen separat gelöst werden, vielleicht eine Münze werfen ;D )