DBSCAN (Density-Based Spatial Clustering of Applications with Noise)

DBSCAN (Density-Based Spatial Clustering of Applications with Noise) ist ein beliebter Algorithmus für unüberwachtes Lernen, der verwendet wird, um Datenpunkte, die eng beieinander liegen, zu gruppieren und Punkte, die allein in Regionen mit geringer Dichte liegen, als Ausreißer zu kennzeichnen. Im Gegensatz zu anderen Clustering-Methoden muss bei DBSCAN die Anzahl der Cluster nicht im Voraus festgelegt werden. Seine Fähigkeit, Cluster mit beliebiger Form zu finden, und seine Robustheit gegenüber Rauschen machen ihn zu einem leistungsstarken Werkzeug für Data Mining und Data Analytics. Der Algorithmus wurde erstmals 1996 in einem Paper von Martin Ester, Hans-Peter Kriegel, Jörg Sander und Xiaowei Xu vorgestellt, das zu einer grundlegenden Arbeit auf diesem Gebiet wurde.

Wie DBSCAN funktioniert

DBSCAN definiert Cluster basierend auf der Dichte von Datenpunkten in einem bestimmten Raum. Er arbeitet mit zwei Schlüsselparametern:

• Epsilon (ε oder eps): Dieser Parameter definiert den Radius einer Nachbarschaft um einen Datenpunkt. Alle Punkte innerhalb dieser Distanz werden als Nachbarn betrachtet.
• Minimale Punkte (MinPts): Dies ist die Mindestanzahl von Datenpunkten (einschließlich des Punktes selbst), die erforderlich sind, um eine dichte Region oder einen Cluster zu bilden.

Basierend auf diesen Parametern kategorisiert DBSCAN jeden Datenpunkt in einen von drei Typen:

1. Kernpunkte: Ein Punkt ist ein Kernpunkt, wenn er mindestens MinPts innerhalb seiner eps Nachbarschaft. Diese Punkte bilden das Innere eines Clusters.
2. Grenzpunkte: Ein Punkt ist ein Randpunkt, wenn er sich innerhalb des eps Nachbarschaft eines Kernpunkts, hat aber nicht genügend Nachbarn, um selbst ein Kernpunkt zu sein. Diese Punkte bilden den Rand eines Clusters.
3. Rauschpunkte (Ausreißer): Ein Punkt wird als Rauschen betrachtet, wenn er weder ein Kernpunkt noch ein Randpunkt ist. Dies sind die Ausreißer, die zu keinem Cluster gehören.

Der Algorithmus beginnt mit einem beliebigen Punkt und ruft seine Nachbarschaft ab. Wenn es sich um einen Kernpunkt handelt, wird ein neuer Cluster erstellt. Der Algorithmus erweitert dann iterativ den Cluster, indem er alle direkt erreichbaren Nachbarn hinzufügt. Dieser Vorgang wird fortgesetzt, bis keine Punkte mehr zu einem Cluster hinzugefügt werden können. Eine visuelle Implementierung finden Sie in der Scikit-Learn-Dokumentation.

KI/ML-Anwendungen in der realen Welt

Die Fähigkeit von DBSCAN, Rauschen zu identifizieren und nicht-lineare Cluster zu entdecken, macht es in verschiedenen Bereichen sehr wertvoll:

• Geospatial Analysis: Stadtplaner und Geographen verwenden DBSCAN zur Analyse räumlicher Daten. Durch die Clusterung von GPS-Koordinaten von Verkehrsunfällen können sie beispielsweise Unfallschwerpunkte identifizieren. In ähnlicher Weise kann es verwendet werden, um Cluster von gemeldeten Krankheitsfällen zu finden, was Epidemiologen bei der Verfolgung von Ausbrüchen hilft. Organisationen wie die Geospatial Information Authority of Japan verwenden ähnliche dichteabhängige Methoden für die Kartierung.
• Anomalieerkennung im Finanzwesen: Im Finanzsektor kann DBSCAN verwendet werden, um betrügerische Transaktionen zu erkennen. Durch das Clustern typischer Ausgabenmuster eines Kunden kann jede Transaktion, die außerhalb dieser Cluster liegt (d. h. als Rauschen gekennzeichnet ist), zur weiteren Untersuchung markiert werden. Dieser Ansatz ist eine Schlüsselkomponente moderner Betrugserkennungssysteme.

DBSCAN und Ultralytics

Das Ultralytics-Ökosystem konzentriert sich hauptsächlich auf überwachte Lernmodelle, wie z. B. Ultralytics YOLO für Aufgaben wie Objekterkennung, Bildklassifizierung und Instanzsegmentierung. Während DBSCAN eine unüberwachte Methode ist, sind seine Prinzipien im breiteren Kontext der Computer Vision (CV) relevant.

Zum Beispiel könnte DBSCAN nach der Durchführung der Objekterkennung mit einem Modell wie YOLO11 auf einem Video einer belebten Straße auf die Mittelpunktkoordinaten der erkannten Bounding Boxes angewendet werden. Dieser Nachbearbeitungsschritt kann einzelne Fußgängererkennungen zu unterschiedlichen Menschenmengen gruppieren und so ein höheres Maß an Szenenverständnis ermöglichen. Das Verständnis der Datenverteilung ist auch bei der Vorbereitung von Datensätzen für das Training entscheidend. Die explorative Datenanalyse mit DBSCAN kann Muster oder Anomalien im Datensatz aufdecken, die mit Plattformen wie Ultralytics HUB verwaltet und visualisiert werden können.

Abgrenzung von verwandten Begriffen

• K-Means-Clustering: Der wesentlichste Unterschied besteht darin, dass K-Means die Angabe der Anzahl der Cluster durch den Benutzer erfordert (k) im Voraus festlegen müssen, während DBSCAN die Anzahl der Cluster automatisch bestimmt. K-Means hat auch Schwierigkeiten mit nicht-sphärischen Clustern und reagiert empfindlich auf Ausreißer, da es jeden Punkt in einen Cluster zwingt. DBSCAN zeichnet sich dadurch aus, dass es Cluster mit beliebiger Form findet und Ausreißer effektiv als Rauschen isoliert.
• Hierarchisches Clustering: Diese Methode erstellt einen Baum von Clustern, der als Dendrogramm bezeichnet wird. Es ist zwar nützlich, um verschachtelte Clusterstrukturen zu visualisieren, kann aber im Vergleich zu DBSCAN bei großen Datensätzen rechenintensiver sein. Die Wahl zwischen ihnen hängt oft von der Datensatzgröße und der gewünschten Ausgabe ab, wie in den Anleitungen zur Auswahl des richtigen Clustering-Algorithmus beschrieben.