Definition - DBSCAN

• Generalisierungen:
  • Dichtebasiertes Clustering
• Involvierte Definitionen:
  • Kernobjekt
  • Direkte Dichte-Erreichbarkeit
  • Dichte-Erreichbarkeit
  • Dichteverbundenheit
• Veranstaltung: EDS
• Referenz: @beecks2024 (LE4, Clustering)

⠀

Definition: DBSCAN

Als DBSCAN-Algorithmus (kurz für Density-Based Spatial Clustering of Applications with Noise) bezeichnen wir einen Clustering-Algorithmus, der Datenpunkte gruppiert, indem er Bereiche mit hoher Dichte von Punkten identifiziert.

Punkte, die nicht zu diesen dichten Bereichen gehören, werden als Rauschen (Noise) betrachtet.

Der Algorithmus kann Cluster beliebiger Form erkennen und ist robust gegenüber Ausreißern. Die Zeitkomplexität liegt bei . Die erwartete Anzahl der Cluster muss nicht angegeben werden.

Algorithmus: DBSCAN-Algorithmus

Eingabe: Radius und , Datensatz
Ausgabe: Clusterzuordnungen

DBSCAN
for do
if noch nicht verarbeitet then
if ist ein Kernobjekt then
clustere alle mit dichte-verbundenen Punkte
else
registriere als Rauschen.