DBSCAN basiert auf dem Konzept der dichtebasierten Erreichbarkeit. Es definiert Cluster als dichte Regionen von Datenpunkten, die durch Bereiche geringerer Dichte voneinander getrennt sind. Zwei Hauptparameter steuern das Verhalten:

• Epsilon (ε): der Radius, innerhalb dessen nach benachbarten Punkten gesucht wird;

• Minimale Anzahl von Punkten (MinPts): die Mindestanzahl an Punkten, die innerhalb des ε-Radius vorhanden sein müssen, um eine dichte Region zu bilden (einschließlich des Punktes selbst).

DBSCAN klassifiziert Punkte in drei Kategorien:

• Kernpunkte: Ein Punkt ist ein Kernpunkt, wenn er mindestens MinPts innerhalb seines ε-Radius hat;

• Randpunkte: Ein Punkt ist ein Randpunkt, wenn er weniger als MinPts innerhalb seines ε-Radius hat, aber von einem Kernpunkt aus erreichbar ist (d. h. innerhalb des ε-Radius eines Kernpunkts liegt);

• Rauschpunkte: Ein Punkt, der weder ein Kernpunkt noch ein Randpunkt ist, wird als Rauschpunkt betrachtet.

Algorithmus

1. Start mit einem beliebigen, noch nicht besuchten Punkt;

2. Suche alle Punkte innerhalb seines ε-Radius;

3. Hat ein Punkt mindestens MinPts Nachbarn innerhalb eines ε-Radius, wird er als Kernpunkt markiert und ein neuer Cluster wird initiiert, der sich rekursiv durch das Hinzufügen aller direkt dichte-erreichbaren Punkte erweitert;

4. Befinden sich innerhalb des ε-Radius weniger als MinPts Punkte, wird der Punkt als Randpunkt markiert (wenn er innerhalb des ε-Radius eines Kernpunkts liegt) oder als Rauschpunkt (wenn nicht);

5. Wiederhole die Schritte 1-4, bis alle Punkte besucht wurden.

Stellen Sie sich ein Streudiagramm von Datenpunkten vor. DBSCAN beginnt, indem ein Punkt ausgewählt wird. Findet es genügend Nachbarn innerhalb seines ε-Radius, wird dieser als Kernpunkt markiert und ein Cluster gebildet. Dieser Cluster wird dann erweitert, indem die Nachbarn des Kernpunkts und deren Nachbarn überprüft werden, und so weiter. Punkte, die in der Nähe eines Kernpunkts liegen, aber selbst nicht genügend Nachbarn haben, werden als Randpunkte markiert. Isolierte Punkte werden als Rauschen identifiziert.