DBSCAN

DBSCAN (Density-Based Spatial Clustering of Applications with Noise, etwa: Dichtebasierte räumliche Clusteranalyse mit Rauschen) ist ein von Martin Ester, Hans-Peter Kriegel, Jörg Sander und Xiaowei Xu entwickelter Data-Mining-Algorithmus zur Clusteranalyse. Er ist einer der meistzitierten Algorithmen in diesem Bereich. Der Algorithmus arbeitet dichtebasiert und ist in der Lage, mehrere Cluster zu erkennen. Rauschpunkte werden dabei ignoriert und separat zurückgeliefert.

Übersicht

Die Grundidee des Algorithmus ist der Begriff der Dichteverbundenheit. Zwei Objekte gelten als dichte-verbunden, wenn es eine Kette von dichten Objekten (Kernobjekte, mit mehr als $m i n P t s$ Nachbarn) gibt, die diese Punkte miteinander verbinden. Die durch dieselben Kernobjekte miteinander verbundenen Objekte bilden einen Cluster. Objekte, die nicht Teil eines dichte-verbundenen Clusters sind, werden als Rauschen (engl. Noise) bezeichnet.

In DBSCAN gibt es drei Arten von Punkten:

Kernobjekte, welche selbst dicht sind.
Dichte-erreichbare Objekte. Dies sind Objekte, die zwar von einem Kernobjekt des Clusters erreicht werden können, selbst aber nicht dicht sind. Anschaulich bilden diese den Rand eines Clusters.
Rauschpunkte, die weder dicht, noch dichte-erreichbar sind.

Der Algorithmus hat zwei Parameter $ε$ und $m i n P t s$ .

Dabei definiert $ε$ die Nachbarschaftslänge eines Punktes: Von einem Punkt erreichbar ist ein zweiter Punkt genau dann, wenn sein Abstand kleiner als $ε$ ist.
$m i n P t s$ definiert dagegen, wann ein Objekt dicht (d. h. ein Kernobjekt) ist: wenn es mindestens $m i n P t s$ $ε$ -erreichbare Nachbarn hat.

Dichte-erreichbare Punkte können von mehr als einem Cluster dichte-erreichbar sein. Diese Punkte werden von dem Algorithmus nicht-deterministisch einem der möglichen Cluster zugeordnet. Dies impliziert auch, dass Dichteverbundenheit nicht transitiv ist; Dichte-Erreichbarkeit ist nicht symmetrisch.

Wichtige Eigenschaften

DBSCAN ist exakt in Bezug auf die Definition von dichte-verbunden und Noise. Das bedeutet, zwei dichte-verbundene Objekte sind garantiert im selben Cluster, während Rauschobjekte sicher in Noise sind. Nicht exakt ist der Algorithmus bei nur dichte-erreichbaren Objekten, diese werden nur einem Cluster zugeordnet, nicht allen möglichen.

Im Gegensatz beispielsweise zum K-Means-Algorithmus, muss nicht im vornherein bekannt sein, wie viele Cluster existieren.

Der Algorithmus kann Cluster beliebiger Form (z. B. nicht nur kugelförmige) erkennen.

DBSCAN ist weitgehend deterministisch und reihenfolgeunabhängig: Unabhängig davon, in welcher Reihenfolge Objekte in der Datenbank abgelegt oder verarbeitet werden, entstehen dieselben Cluster (mit der Ausnahme der nur dichte-erreichbaren Nicht-Kern-Objekte und der Cluster-Nummerierung).

Der Algorithmus kann mit beliebigen Distanzfunktionen und Ähnlichkeitsmaßen verwendet werden. Im Gegensatz zum K-Means-Algorithmus ist kein geometrischer Raum notwendig, da kein Mittelpunkt berechnet werden muss.

DBSCAN selbst ist von linearer Komplexität. Jedes Objekt wird im Wesentlichen nur einmal besucht. Jedoch ist die Berechnung der $ε$ -Nachbarschaft im Regelfall nicht in konstanter Zeit möglich (ohne entsprechende Vorberechnungen). Ohne die Verwendung von vorberechneten Daten oder einer geeigneten Indexstruktur ist der Algorithmus also von quadratischer Komplexität.

DBSCAN-Algorithmus

Die Originalfassung von DBSCAN kann durch folgenden Pseudocode beschrieben werden:

DBSCAN(D, eps, MinPts)
   C = 0
   for each unvisited point P in dataset D
      mark P as visited
      N = D.regionQuery(P, eps)
      if sizeof(N) < MinPts
         mark P as NOISE
      else
         C = next cluster
         expandCluster(P, N, C, eps, MinPts)

expandCluster(P, N, C, eps, MinPts)
   add P to cluster C
   for each point P' in N
      if P' is not visited
         mark P' as visited
         N' = D.regionQuery(P', eps)
         if sizeof(N') >= MinPts
            N = N joined with N'
      if P' is not yet member of any cluster
         add P' to cluster C
         unmark P' as NOISE if necessary

regionQuery(P, eps)
   return all points within P's eps-neighborhood (including P)

Alternativ könnte DBSCAN auch rekursiv implementiert werden (statt des join von $N$ erfolgt ein rekursiver Aufruf), dies bietet aber keine nennenswerten Vorteile.

DBSCAN (Rekursive Formulierung)

Die rekursive Implementierung zeigt anschaulicher, wie DBSCAN arbeitet. Da die Rekursionstiefe aber sehr hoch werden kann, ist die mengenbasierte normale Formulierung als Implementierung vorzuziehen.

DBSCAN(D, eps, MinPts)
   C = 0
   for each unvisited point P in dataset D
      mark P as visited
      N = getNeighbors(P, eps)
      if sizeof(N) < MinPts
         mark P as NOISE
      else
         C = next cluster
         add P to cluster C
         for P' in N
           if P' is not yet member of any cluster
             recursiveExpandCluster(P', C, eps, MinPts)

recursiveExpandCluster(P, C, eps, MinPts)
   add P to cluster C
   if P is not visited
     mark P as visited
     N = getNeighbors(P, eps)
     if sizeof(N) >= MinPts
       for P' in N
         if P' is not yet member of any cluster
           recursiveExpandCluster(P', C, eps, MinPts)

Generalisierter DBSCAN

Die generalisierte Version von DBSCAN, GDBSCAN abstrahiert hier von der $ε$ -Nachbarschaft und dem $m i n P t s$ -Dichtekriterium. Diese werden ersetzt durch ein Prädikat getNeighbors und einem Prädikat isCorePoint.

GDBSCAN(D, getNeighbors, isCorePoint)
   C = 0
   for each unvisited point P in dataset D
      mark P as visited
      N = getNeighbors(P)
      if isCorePoint(P, N)
         C = next cluster
         expandCluster(P, N, C)
      else
         mark P as NOISE

expandCluster(P, N, C)
   add P to cluster C
   for each point P' in N
      if P' is not visited
         mark P' as visited
         N' = getNeighbors(P')
         if isCorePoint(P', N')
            N = N joined with N'
      if P' is not yet member of any cluster
         add P' to cluster C

Verwendet man eine $ε$ -Bereichsanfrage als getNeighbors und den $m i n P t s$ -Test als isCorePoint-Prädikat, so erhält man offensichtlich den ursprünglichen DBSCAN-Algorithmus.

Zeitkomplexität

DBSCAN durchläuft jeden Punkt der Datenbank, möglicherweise mehrmals, z. B. als Kandidaten für verschiedene Cluster. Aus praktischen Erwägungen wird die Zeitkomplexität jedoch hauptsächlich durch die Anzahl der regionQuery-Aufrufe bestimmt. DBSCAN führt für jeden Punkt genau eine solche Abfrage durch, und wenn eine Indexstruktur verwendet wird, die eine Nachbarschaftsabfrage in $O (\log (n))$ ausführt, ergibt sich eine durchschnittliche Laufzeit von $O (n \cdot \log (n))$ , sofern der Parameter $ε$ sinnvoll gewählt wird, d. h. so, dass im Durchschnitt nur $O (\log (n))$ Punkte zurückgegeben werden.

Ohne die Verwendung einer beschleunigenden Indexstruktur oder bei entarteten Daten, z. B. allen Punkten innerhalb einer Entfernung von weniger als $ε$ , bleibt die Laufzeit im schlimmsten Fall bei $O (n^{2})$ . Das obere Dreieck der Abstandsmatrix der Größe $n$ kann materialisiert werden, um erneute Abstandsberechnungen zu vermeiden, doch dies erfordert $O (n^{2})$ Speicherplatz, während eine nicht matrixbasierte Implementierung von DBSCAN nur $O (n)$ Speicherplatz benötigt.

Erweiterungen von DBSCAN

Auf diesem Algorithmus basieren unter anderem

OPTICS - Ordering Points To Identify the Clustering Structure
Shared-Nearest-Neighbor-Clustering - Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data
PreDeCon - Density Connected Clustering with Local Subspace Preferences
SubClu - Density connected Subspace Clustering for High Dimensional Data
4C - Computing Clusters of Correlation Connected Objects
ERiC - Exploring Complex Relationships of Correlation Clusters
HDBSCAN - Hierarchical Density Based Clustering

Verwendung von DBSCAN

Der Algorithmus DBSCAN ist enthalten in

ELKI (mit flexibler Indizierung und zahlreichen Varianten)
Scikit-learn (mit Index für gängige Metriken)
Weka (jedoch ohne Index-Unterstützung implementiert, sowie ineffizient)
QGIS

Vergleich mit dem k-Means-Algorithmus

Sowohl DBSCAN als auch k-Means sind beliebte Clustering-Algorithmen. Sie weisen sie unterschiedliche Eigenschaften auf, wodurch sie sich für verschiedene Datentypen und Anwendungsfälle eignen.

Folgende Tabelle listet Unterschiede zwischen den beiden Algorithmen auf:


Eigenschaft	DBSCAN	k-Means
Clusterform	kann Cluster beliebiger Form identifizieren	geht davon aus, dass Cluster konvex und annähernd kugelförmig sind
Anzahl der Cluster	erfordert keine vorherige Angabe der Clusteranzahl	erfordert die vorherige Angabe der Clusteranzahl k
Umgang mit Ausreißern	identifiziert Ausreißer als Rauschpunkte	ordnet jeden Punkt einem Cluster zu, was möglicherweise zu Verzerrungen der Clusterformen führt
Empfindlichkeit gegenüber Parametern	empfindlich gegenüber den Parametern epsilon und MinPts	empfindlich gegenüber den anfänglichen Positionen der Zentren und der Wahl von k
Clusterdichte	kann Cluster unterschiedlicher Dichte finden	neigt dazu, Cluster mit ähnlicher räumlicher Ausdehnung und Dichte zu finden
Skalierbarkeit	weniger effizient bei großen Datensätzen, insbesondere bei hochdimensionalen Daten	im Allgemeinen effizienter und besser auf große Datensätze skalierbar
Konsistenz der Ergebnisse	liefert über mehrere Durchläufe hinweg konsistente Ergebnisse	die Ergebnisse können aufgrund der zufälligen Initialisierung der Zentren variieren

Einzelnachweise

↑ Microsoft Academic Search: Meistzitierte Data-Mining-Artikel. Archiviert vom Original (nicht mehr online verfügbar) am 21. April 2010; abgerufen am 10. Mai 2010 (DBSCAN ist ca. Platz 20–25).
↑ Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu: A density-based algorithm for discovering clusters in large spatial databases with noise. In: Evangelos Simoudis, Jiawei Han, Usama M. Fayyad (Hrsg.): Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press, 1996, ISBN 1-57735-004-9, S. 226–231 (Online PDF).
↑ Jörg Sander, Martin Ester, Hans-Peter Kriegel und Xiaowei Xu: Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications. In: Data Mining and Knowledge Discovery. 2. Auflage. Band 2. Springer, Berlin 1998, doi:10.1023/A:1009745219419.
↑ Jörg Sander: Generalized Density-Based Clustering for Spatial Data Mining. Herbert Utz Verlag, München 1998, ISBN 3-89675-469-6.
↑ Shivam Singh: All you need to know about the DBSCAN Algorithm. In: Analytics Vidhya. 1. Februar 2021, abgerufen am 4. Oktober 2026 (englisch).
↑ DBSCAN. Abgerufen am 4. Oktober 2026 (englisch).
↑ Ricardo J. G. B. Campello, Davoud Moulavi, Joerg Sander: Density-Based Clustering Based on Hierarchical Density Estimates. In: Advances in Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, Berlin, Heidelberg 2013, ISBN 978-3-642-37455-5, S. 160–172, doi:10.1007/978-3-642-37456-2_14 (springer.com [abgerufen am 1. August 2018]).
↑ A Guide to the DBSCAN Clustering Algorithm. Abgerufen am 4. Oktober 2026 (englisch).

[1] Microsoft Academic Search: Meistzitierte Data-Mining-Artikel. Archiviert vom Original (nicht mehr online verfügbar) am 21. April 2010; abgerufen am 10. Mai 2010 (DBSCAN ist ca. Platz 20–25).

[2] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu: A density-based algorithm for discovering clusters in large spatial databases with noise. In: Evangelos Simoudis, Jiawei Han, Usama M. Fayyad (Hrsg.): Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press, 1996, ISBN 1-57735-004-9, S. 226–231 (Online PDF).

[3] Jörg Sander, Martin Ester, Hans-Peter Kriegel und Xiaowei Xu: Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications. In: Data Mining and Knowledge Discovery. 2. Auflage. Band 2. Springer, Berlin 1998, doi:10.1023/A:1009745219419.

[4] Jörg Sander: Generalized Density-Based Clustering for Spatial Data Mining. Herbert Utz Verlag, München 1998, ISBN 3-89675-469-6.

[5] Shivam Singh: All you need to know about the DBSCAN Algorithm. In: Analytics Vidhya. 1. Februar 2021, abgerufen am 4. Oktober 2026 (englisch).

[6] DBSCAN. Abgerufen am 4. Oktober 2026 (englisch).

[7] Ricardo J. G. B. Campello, Davoud Moulavi, Joerg Sander: Density-Based Clustering Based on Hierarchical Density Estimates. In: Advances in Knowledge Discovery and Data Mining. Springer Berlin Heidelberg, Berlin, Heidelberg 2013, ISBN 978-3-642-37455-5, S. 160–172, doi:10.1007/978-3-642-37456-2_14 (springer.com [abgerufen am 1. August 2018]).

[8] A Guide to the DBSCAN Clustering Algorithm. Abgerufen am 4. Oktober 2026 (englisch).