~2025-30445-74: /* Verwendung von DBSCAN */

2025-10-29T08:33:00Z

Verwendung von DBSCAN

Neue Seite

'''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 (Informatiker)|Jörg Sander]] und Xiaowei Xu entwickelter [[Data-Mining]]-Algorithmus zur [[Clusteranalyse]]. Er ist einer der meistzitierten<ref>{{Internetquelle | url=http://academic.research.microsoft.com/CSDirectory/paper_category_7.htm | titel=Meistzitierte Data-Mining-Artikel | autor=Microsoft Academic Search | kommentar=DBSCAN ist ca. Platz 20–25 | zugriff=10.5.2010 | offline=ja | archiv-url=https://web.archive.org/web/20100421170848/http://academic.research.microsoft.com/CSDirectory/paper_category_7.htm | archiv-datum=2010-04-21 }}</ref> Algorithmen in diesem Bereich.
Der [[Algorithmus]] arbeitet [[Dichte|dichtebasiert]] und ist in der Lage, mehrere Cluster zu erkennen. Rauschpunkte werden dabei ignoriert und separat zurückgeliefert.

== Übersicht ==
[[Datei:DBSCAN-Illustration.svg|mini|Punkte bei A sind Kernpunkte. Punkte B und C sind ''dichte-erreichbar'' von A und dadurch ''dichte-verbunden'' und gehören zum selben Cluster. Punkt N ist weder ein Kernpunkt noch dichte-erreichbar, also Rauschen. (<math>minPts=3</math>)]]

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 <math>minPts</math> 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 <math>\varepsilon</math> und <math>minPts</math>.
* Dabei definiert <math>\varepsilon</math> die ''Nachbarschaftslänge'' eines Punktes: Von einem Punkt erreichbar ist ein zweiter Punkt genau dann, wenn sein Abstand kleiner als <math>\varepsilon</math> ist.
* <math>minPts</math> definiert dagegen, wann ein Objekt ''dicht'' (d. h. ein ''Kernobjekt'') ist: wenn es mindestens <math>minPts</math> <math>\varepsilon</math>-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 [[Transitive Relation|transitiv]] ist; ''Dichte-Erreichbarkeit'' ist nicht [[Symmetrische Relation|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 [[Determiniertheit (Algorithmus)|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 [[Distanzfunktion]]en 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 (Informatik)|Komplexität]]. Jedes Objekt wird im Wesentlichen nur einmal besucht. Jedoch ist die Berechnung der <math>\varepsilon</math>-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<ref>{{Literatur
| Autor = Martin Ester, [[Hans-Peter Kriegel]], Jörg Sander, Xiaowei Xu
| Titel = A density-based algorithm for discovering clusters in large spatial databases with noise
| Seiten = 226–231
| Herausgeber = Evangelos Simoudis, Jiawei Han, Usama M. Fayyad
| Sammelwerk = Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96)
| Verlag = AAAI Press
| Jahr = 1996
| ISBN = 1-57735-004-9
| Online = [http://www.dbs.ifi.lmu.de/Publikationen/Papers/KDD-96.final.frame.pdf Online] PDF
}}</ref> 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 [[Rekursion|rekursiv]] implementiert werden (statt des ''join'' von <math>N</math> 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<ref>{{Literatur
| Autor = Jörg Sander, Martin Ester, [[Hans-Peter Kriegel]] und Xiaowei Xu
| Titel = Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications
| Sammelwerk = Data Mining and Knowledge Discovery
| Band = 2
| Auflage = 2.
| Ort = Berlin
| Verlag = Springer
| Jahr = 1998
| DOI = 10.1023/A:1009745219419}}</ref><ref>{{Literatur | Autor = Jörg Sander | Titel = Generalized Density-Based Clustering for Spatial Data Mining | ISBN=3896754696 | Jahr=1998 | Ort = München | Verlag = Herbert Utz Verlag }}</ref> abstrahiert hier von der <math>\varepsilon</math>-Nachbarschaft und dem <math>minPts</math>-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 <math>\varepsilon</math>-Bereichsanfrage als getNeighbors und den <math>minPts</math>-Test als isCorePoint-Prädikat, so erhält man offensichtlich den ursprünglichen DBSCAN-Algorithmus.

== 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<ref>{{Literatur |Autor=Ricardo J. G. B. Campello, Davoud Moulavi, Joerg Sander |Titel=Density-Based Clustering Based on Hierarchical Density Estimates |Sammelwerk=Advances in Knowledge Discovery and Data Mining |Verlag=Springer Berlin Heidelberg |Ort=Berlin, Heidelberg |Datum=2013 |ISBN=9783642374555 |DOI=10.1007/978-3-642-37456-2_14 |Seiten=160–172 |Online=http://link.springer.com/10.1007/978-3-642-37456-2_14 |Abruf=2018-08-01}}</ref>

== Verwendung von DBSCAN ==
Der Algorithmus DBSCAN ist enthalten in
* [[Environment for DeveLoping KDD-Applications Supported by Index-Structures|ELKI]] (mit flexibler Indizierung und zahlreichen Varianten)
* [[Scikit-learn]] (mit Index für gängige Metriken)
* [[Waikato Environment for Knowledge Analysis|Weka]] (jedoch ohne Index-Unterstützung implementiert, sowie ineffizient)
* [[QGIS]]

== Einzelnachweise ==
<references />

{{SORTIERUNG:Dbscan}}
[[Kategorie:Clusteranalyse]]
[[Kategorie:Abkürzung]]

DBSCAN - Versionsgeschichte

~2025-30445-74: /* Verwendung von DBSCAN */