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

DBSCAN (dichtebasiertes räumliches Clustering von Anwendungen mit Rauschen) ist ein Algorithmus für unüberwachtes Lernen, der eng beieinanderliegende Punkte zu Clustern zusammenfasst und Punkte in dünn besiedelten Bereichen als Rauschen kennzeichnet. Martin Ester, Hans-Peter Kriegel, Jörg Sander und Xiaowei Xu stellten den Algorithmus 1996 auf der KDD-Konferenz vor. Er benötigt keine vorgegebene Anzahl von Clustern, findet Cluster beliebiger Form – etwa Ringe, Halbmonde oder gewundene Straßen – und seine Rauschmarkierung dient zugleich als einfache Form der Anomalieerkennung. Der gesamte Algorithmus wird durch zwei Parameter gesteuert: den Radius der Nachbarschaft und die Anzahl der Punkte, ab der eine Nachbarschaft als dicht gilt.

Kernpunkte, Randpunkte und Rauschen#

DBSCAN betrachtet für jeden Punkt dessen Nachbarschaft – die Menge der Punkte innerhalb eines Abstands von eps – und zählt die enthaltenen Punkte:

• Kernpunkt: Hat mindestens min_samples Punkte in seiner Nachbarschaft; in der Implementierung von scikit-learn wird der Punkt selbst mitgezählt. Kernpunkte bilden den dichten inneren Bereich eines Clusters.
• Randpunkt: Hat zu wenige Nachbarn, um ein Kernpunkt zu sein, liegt aber höchstens eps von einem Kernpunkt entfernt. Randpunkte bilden die Ränder eines Clusters.
• Rauschpunkt: Ist weder Kern- noch Randpunkt, gehört daher zu keinem Cluster und erhält das Label -1.

Ein Cluster wächst ausgehend von jedem noch nicht besuchten Kernpunkt. DBSCAN fügt alle Punkte in dessen Nachbarschaft hinzu und wiederholt den Vorgang für jeden neu hinzugefügten Kernpunkt, bis keine weiteren Punkte erreichbar sind. So bildet eine Kette überlappender dichter Nachbarschaften unabhängig von ihrem Verlauf ein einziges Cluster. Randpunkte werden einem Cluster zugeordnet, vergrößern es aber nicht. Bei einer gegebenen Eingabereihenfolge ist das Ergebnis deterministisch. Ein Randpunkt, der von zwei Clustern aus erreichbar ist, wird jedoch dem Cluster zugeordnet, das ihn zuerst erreicht. Daher kann sich die Zuordnung von Randpunkten ändern, wenn die Daten gemischt werden.

eps und min_samples auswählen#

Der Radius eps ist am wichtigsten und hängt vom Maßstab der Daten ab. Deshalb werden die Merkmale üblicherweise zuerst standardisiert. Ist der Radius zu klein, bleiben die meisten Punkte Rauschen. Ist er zu groß, verschmelzen benachbarte Cluster zu einem einzigen. Eine verbreitete Faustregel sortiert den Abstand jedes Punktes zu seinem k-ten nächsten Nachbarn, wobei k gleich min_samples ist, und wählt eps am Knick der Kurve aus, an dem die Abstände stark anzusteigen beginnen. Höhere Werte für min_samples machen das Clustering toleranter gegenüber Rauschen und sind bei großen oder verrauschten Datensätzen üblich. In hochdimensionalen Räumen wie Bildeinbettungen ähneln sich die Abstände zwischen den Punkten immer stärker. Daher reduzieren Anwenderinnen und Anwender die Dimensionalität häufig vor DBSCAN, etwa mit der Hauptkomponentenanalyse (PCA).

DBSCAN im Vergleich zu K-Means und HDBSCAN#

K-Means-Clustering benötigt die Anzahl der Cluster im Voraus, ordnet jeden Punkt dem nächstgelegenen Schwerpunkt zu und bevorzugt daher kompakte, runde Cluster. Ausreißer werden dabei ebenfalls einer Gruppe zugewiesen. DBSCAN ermittelt die Anzahl der Cluster anhand der Dichte und lässt Ausreißer außen vor. Seine Schwäche ist ein einziger globaler Wert für eps: Bei Clustern mit sehr unterschiedlicher Dichte trennt kein Radius zugleich die dünn besiedelten Cluster vom Rauschen und die dichten Cluster voneinander. HDBSCAN begegnet diesem Problem, indem es DBSCAN im Grunde für alle Werte von eps ausführt und die stabilsten Cluster beibehält. Beide Algorithmen sind neben dem verwandten OPTICS im Clustering-Modul von scikit-learn enthalten.

In diesem Beispiel werden zwei ineinandergreifende Halbmonde mit 20 hinzugefügten zufälligen Ausreißern gruppiert. Die Ergebnisse werden anhand des korrigierten Rand-Index mit den wahren Gruppen verglichen, wobei 1.0 einer perfekten Übereinstimmung entspricht:

import numpy as np
from sklearn.cluster import DBSCAN, KMeans
from sklearn.datasets import make_moons
from sklearn.metrics import adjusted_rand_score

# Two interleaving crescents plus 20 scattered outliers (true label -1)
X, y = make_moons(n_samples=300, noise=0.05, random_state=0)
rng = np.random.default_rng(0)
X = np.vstack([X, rng.uniform(-1.5, 2.5, size=(20, 2))])
y = np.concatenate([y, np.full(20, -1)])

# DBSCAN infers clusters from density; k-means is told there are 2
db_labels = DBSCAN(eps=0.2, min_samples=5).fit_predict(X)
km_labels = KMeans(n_clusters=2, random_state=0).fit_predict(X)

print(f"DBSCAN: {db_labels.max() + 1} clusters, {(db_labels == -1).sum()} noise points")
print(f"ARI: DBSCAN {adjusted_rand_score(y, db_labels):.2f}, k-means {adjusted_rand_score(y, km_labels):.2f}")

Das Skript gibt für DBSCAN 2 Cluster und 15 Rauschpunkte sowie korrigierte Rand-Indizes von 0.97 für DBSCAN und 0.20 für k-means aus. DBSCAN bildet beide Halbmonde nach und sondert die Ausreißer ab, die außerhalb davon liegen. K-means trennt die Halbmonde dagegen mit einer geraden Grenze, obwohl die korrekte Anzahl der Cluster vorgegeben wurde.

Anwendungen in der Praxis#

• LiDAR-Wahrnehmung: Bei Verarbeitungsketten für autonome Fahrzeuge und Robotik werden zunächst Bodenpunkte aus einem LiDAR-Scan entfernt und anschließend die übrigen 3D-Punkte zu einzelnen Hindernissen gruppiert. Dichtebasiertes Clustering ist dabei eine gängige Wahl, da die Anzahl der Objekte unbekannt ist.
• Nachbearbeitung von Erkennungen: Die Boxmittelpunkte von YOLO26-Erkennungen, verfügbar als result.boxes.xywh, lassen sich mit DBSCAN gruppieren, um Menschenansammlungen oder wiederkehrende Fehlerstellen in einer Produktionslinie zu finden. Vereinzelte Erkennungen werden dabei als Rauschen ausgesondert.
• Betrugs- und Sensorüberwachung: Transaktionen oder Messwerte mit der Kennzeichnung -1 liegen weit entfernt von jeder dichten Gruppe normalen Verhaltens und kommen daher für eine Überprüfung infrage.
• Geodatenanalyse: Liefer- und Fahrdienstunternehmen clustern GPS-Punkte, um häufige Haltepunkte und stark frequentierte Abholorte zu finden. DBSCAN in Scikit-learn akzeptiert metric="haversine" für Breiten- und Längengrade im Bogenmaß. In diesem Fall ist eps ein Winkel auf der Einheitskugel, sodass ein Radius von 100 Metern zu eps = 0.1 / 6371 wird, wobei der mittlere Erdradius von 6.371 km verwendet wird.