DBSCAN-Clustering

DBSCAN (Dichtebasierte räumliche Clusteranalyse von Anwendungen mit Rauschen) ist ein beliebter dichtebasierter Algorithmus im maschinellen Lernen und Data Mining. Er ist besonders nützlich, um Cluster beliebiger Form in Daten mit Rauschen oder Ausreißern zu identifizieren. Der Algorithmus funktioniert, indem er Cluster als dichte Regionen von Punkten definiert, die durch weniger dichte Regionen getrennt sind. Der DBSCAN-Algorithmus verwendet zwei Hauptparameter: Epsilon (eps) und min_samples. Epsilon definiert den Radius um jeden Punkt, und min_samples definiert die Mindestanzahl von Punkten, die erforderlich sind, um eine dichte Region zu bilden.

Der Algorithmus arbeitet mit drei verschiedenen Arten von Punkten:

Kernpunkt hat mindestens min_samples Punkte in seinem eps-Radius;
Randpunkt hat weniger als min_samples Punkte in seinem eps-Radius, aber mindestens einer dieser Punkte innerhalb des Radius ist der Kernpunkt;
Rauschpunkt ist dasselbe wie der Randpunkt, hat jedoch keinen Kernpunkt in seinem eps-Radius.

Durch die Klassifizierung von Punkten als Kern-, Rand- oder Rauschpunkte kann der DBSCAN-Algorithmus Cluster von Rauschpunkten identifizieren und trennen.

Um DBSCAN zu verstehen, müssen wir auch zwei Definitionen erwähnen:

Erreichbarkeit in Bezug auf Dichte legt fest, dass ein Punkt von einem anderen erreichbar ist, wenn er innerhalb einer bestimmten Entfernung (eps) von ihm liegt. Aber Erreichbarkeit wurde auch im Mean-Shift-Clustering verwendet: In den vorherigen Kapiteln haben wir festgestellt, dass dieser Algorithmus nicht mit beliebig geformten Clustern arbeiten konnte.

Um Cluster mit beliebiger Form zu erkennen, benötigen wir Konnektivität: Es beinhaltet einen auf Transitivität basierenden Ansatz, um festzustellen, ob Punkte in einem bestimmten Cluster liegen. Zum Beispiel könnten die Punkte p und q verbunden sein, wenn q->p1->p2->p3->p, wobei x->y bedeutet, dass y von x erreichbar ist.

Um DBSCAN zu implementieren, müssen Sie die folgenden Schritte ausführen:

Schritt 1. Klassifizieren Sie die Punkte als Kern, Grenze und Rauschen;

Schritt 2. Rauschen verwerfen (oder Rauschen in einen separaten Cluster einordnen);

Schritt 3. Weisen Sie einem Kernpunkt einen Cluster zu;

Schritt 4. Verbinden Sie alle verbundenen Kernpunkte eines in Schritt 3 gewählten Punktes mit dem Cluster dieses Punktes;

Schritt 5. Besuchen Sie den nächsten nicht zugeordneten Kernpunkt und wiederholen Sie die Schritte 3-4, bis es keine nicht zugeordneten Kernpunkte im Datensatz mehr gibt;

Schritt 6. Verbinden Sie Randpunkte mit dem nächstgelegenen Kernpunkt-Cluster.

Schauen wir uns an, wie man DBSCAN in Python implementiert:


              1234567891011121314
            
from sklearn.datasets import make_blobs
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
# Create blobs dataset for clustering
X, y = make_blobs(n_samples=500, centers=3)
# Specify eps and min_samples paremeters of DBSCAN model and train model
clustering = DBSCAN(eps=0.85, min_samples=20).fit(X)
# Visualize results
fig, axes = plt.subplots(1, 2)
axes[0].scatter(X[:, 0], X[:, 1], c=y, cmap='tab20b')
axes[0].set_title('Real clusters')
axes[1].scatter(X[:, 0], X[:, 1], c=clustering.labels_, cmap='tab20b')
axes[1].set_title('Clusters with DBSCAN')
print('Clustering labels are: ', set(clustering.labels_))

Hinweis

Der DBSCAN-Algorithmus weist Rauschen einem separaten Cluster mit dem Label -1 zu.

Im obigen Code haben wir die DBSCAN-Klasse aus dem sklearn.cluster-Modul verwendet, um den DBSCAN-Algorithmus zu implementieren. Wir haben auch zwei Parameter angegeben:

Der eps-Parameter bestimmt den Erreichbarkeitsradius;
Der min_samples-Parameter bestimmt die Mindestanzahl von Proben im Erreichbarkeitsradius, um Punkte als Kern, Rand oder Rauschen zu klassifizieren;
wir verwenden die .fit()-Methode, um das Clustering bereitzustellen.

Hinweis

Die DBSCAN-Klasse hat keine Implementierung für die .predict()-Methode, daher können wir kein Clustering für neue Punkte bereitstellen, ohne das Modell neu zu trainieren.

War alles klar?

Danke für Ihr Feedback!

Abschnitt 2. Kapitel 6