Dichtebasierte

Dichtebasierte Clustering-Ansätze sind Methoden zur Gruppierung von Daten, die Cluster als Regionen mit hoher Punktdichte definieren. Im Gegensatz zu distanz- oder modellbasierten Ansätzen beruhen sie nicht primär auf Abständen zwischen Punkten, sondern auf der lokalen Dichte der Punkte. Typischerweise entstehen Cluster dort, wo viele Punkte nah beieinander liegen, während dünn besiedelte Bereiche als Rauschen oder Ausreißer betrachtet werden.

Zentrale Konzepte sind Kernpunkte, Randpunkte und Rauschen. Ein Punkt gilt als Kernpunkt, wenn in seiner ε-Nachbarschaft (Radius ε) mindestens MinPts weitere Punkte liegen. Cluster bilden sich durch die Verbindung von Kernpunkten und durch Randpunkte, die in der Nachbarschaft eines Kernpunkts liegen. Die Parameter ε und MinPts bestimmen Sensibilität und Größe der gefundenen Cluster.

Der bekannteste Vertreter ist DBSCAN (Density-Based Spatial Clustering of Applications with Noise). Weitere wichtige Ansätze sind OPTICS (Ordering Points To Identify the Clustering Structure) und HDBSCAN (Hierarchical DBSCAN). Anwendungsgebiete reichen von Geoinformationssystemen und Mustererkennung bis hin zu Bildverarbeitung und Anomalieerkennung. Vorteile sind die Fähigkeit, Cluster beliebiger Form zu identifizieren und Rauschen zu ignorieren; Nachteile umfassen die Abhängigkeit von Parametern und Schwierigkeiten bei unterschiedlichen Dichtebereichen sowie in hohen Dimensionen.

Historisch stammt das Konzept aus der Arbeit von Ester, Kriegel, Sander und Xu (1996), die DBSCAN als erstes weithin beachtetes density-based Clustering-Verfahren vorstellten. Seitdem wurden zahlreiche Erweiterungen entwickelt, die Skalierbarkeit verbessern oder mit ungleicher Dichte umgehen.