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

Das Grundprinzip von DBSCAN (Density-Based Spatial Clustering of Applications with Noise) basiert auf der Idee, Cluster anhand ihrer Dichte zu identifizieren. Hierbei werden Datenpunkte in Gruppen (Cluster) zusammengefasst, die in dichten Regionen liegen, während Punkte in weniger dichten Bereichen als Noise oder Ausreißer betrachtet werden. Dieser Ansatz ermöglicht es DBSCAN, Cluster verschiedener Formen und Größen effektiv zu erkennen und ist besonders nützlich in Datensätzen mit Rauschen. Hier sind die Kernaspekte des Algorithmus:

1. Eps und MinPts festlegen: Zwei Hauptparameter - Eps (der Radius um einen Punkt, um Nachbarn zu suchen) und MinPts (die minimale Anzahl von Punkten, die einen dichten Bereich bilden) - werden definiert.

2. Kernpunkte identifizieren: Punkte, die mindestens MinPts Nachbarn innerhalb des Radius Eps haben, werden als Kernpunkte klassifiziert.

3. Randpunkte und Noise bestimmen: Punkte, die weniger als MinPts Nachbarn haben, aber einem Kernpunkt nahe sind, gelten als Randpunkte. Punkte, die weder Kern- noch Randpunkte sind, werden als Noise betrachtet.

4. Cluster bilden: Kernpunkte und die ihnen zugeordneten Randpunkte bilden Cluster, während als Noise deklarierte Punkte ignoriert werden.

5. Ergebnisanalyse: Die entstandenen Cluster können analysiert und für weitere Datenanalysen verwendet werden.

In Abbildung 12 wird DBSCAN visualisiert. Die gestrichelten Kreise um die Punkte zeigen den Radius Eps an, in welchem Nachbarn gesucht werden.

Abbildung 12: Bestandteile und Funktion des DBSCAN-Algorithmus

DBSCAN eignet sich besonders für Datensätze, in denen die Anzahl der Cluster nicht bekannt ist und in denen Noise und Ausreißer vorhanden sind. Es erfordert keine Annahme über die Form der Cluster, was es vielseitig und robust in unterschiedlichen Anwendungsfällen macht. Im folgenden Abschnitt werden die Vor- und Nachteile von DBSCAN behandelt:

Vorteile:

• Robust gegenüber Rauschen und Ausreißern: DBSCAN ist in der Lage, Ausreißer zu erkennen und zu ignorieren, was ihn besonders robust gegenüber Rauschen in den Daten macht.

• Automatische Bestimmung der Anzahl von Clustern: Im Gegensatz zu k-Means muss die Anzahl der Cluster bei DBSCAN nicht im Voraus festgelegt werden, da der Algorithmus automatisch Cluster identifiziert.

• Erkennung von Clustern verschiedener Formen und Größen: DBSCAN kann Cluster mit unterschiedlichen Formen und Größen effektiv erkennen, da er auf der Dichte basiert und nicht auf geometrischen Formen.

Nachteile:

• Abhängigkeit von den Parametern Eps und MinPts: Die Leistung von DBSCAN hängt stark von der Auswahl der Parameter Eps (Radius um einen Punkt) und MinPts (minimale Anzahl von Punkten in einem dichten Bereich) ab, was die Anpassung des Algorithmus an verschiedene Datensätze erschweren kann.

• Schwierigkeit bei der Behandlung von Clustern unterschiedlicher Dichte: DBSCAN kann Schwierigkeiten haben, Cluster zu identifizieren, die unterschiedliche Dichten aufweisen, insbesondere wenn die Parameter nicht optimal gewählt wurden.

• Rechenintensität: DBSCAN kann rechenintensiv sein, hauptsächlich für große Datensätze oder wenn die Datenpunkte hochdimensional sind, da für jeden Punkt die Distanz zu anderen Punkten berechnet werden muss.

Im gegebenen Code wird die DBSCAN-Clustering-Technik angewendet, um nicht lineare Cluster in synthetischen Daten zu erkennen. Anschließend werden die Kernpunkte (Core Samples) identifiziert und den zugehörigen Clustern zugewiesen.

import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons

# Generiere Beispieldaten
X, _ = make_moons(n_samples=500, noise=0.1, random_state=42)

# DBSCAN Clustering
dbscan = DBSCAN(eps=0.2, min_samples=10)
dbscan.fit(X)

# Cluster-Zuweisungen
labels = dbscan.labels_

# Identifiziere Core Samples
core_samples_mask = np.zeros_like(dbscan.labels_, dtype=bool)
core_samples_mask[dbscan.core_sample_indices_] = True
core_samples = X[core_samples_mask]
core_samples_labels = labels[core_samples_mask]

Mehr erfahren: KDnuggets/DBSCAN Clustering Algorithm in Machine Learning, GeeksforGeeks/DBSCAN Clustering in ML | Density based clustering