DBSCAN-Clustering

Was ist DBSCAN-Clustering?

DBSCAN gruppiert eng beieinanderliegende Datenpunkte und markiert Punkte in Regionen geringer Dichte als Ausreißer. Im Gegensatz zu K-Means muss die Clusteranzahl nicht vorgegeben werden.

Zwei Parameter: Epsilon (eps) — maximaler Nachbarschaftsabstand, MinSamples — Mindestanzahl Punkte für eine dichte Region. Punkte: Kern-, Rand- oder Rauschpunkte.

DBSCAN ist effektiv bei unterschiedlichen Dichten, nicht-konvexen Formen und signifikantem Rauschen. Bei sehr unterschiedlichen Clusterdichten stößt es an Grenzen.

Formula: Kernpunkt: |N_eps(p)| ≥ minSamples Randpunkt: |N_eps(p)| < minSamples, aber innerhalb von eps eines Kernpunkts Rauschen: weder Kern- noch Randpunkt N_eps(p) = {q : dist(p,q) ≤ eps}

Berechnungsbeispiel

Punkte: (1,1), (1.1,1.2), (0.9,0.8), (5,5), (5.1,5.2), (4.9,4.8), (10,10). eps=1.0, minSamples=2. Cluster 1: 3 Punkte, Cluster 2: 3 Punkte, Rauschen: (10,10).

Wann diesen Rechner verwenden

• Ein Data Scientist, der Anomalieerkennung durchführt, bei der Ausreißer explizit als Rauschpunkte getrennt von Clustern identifiziert werden müssen
• Ein Geodatenanalyst, der geografische Daten clustert (z. B. Kriminalitätsschwerpunkte, Lieferorte), bei denen die Clusterformen unregelmäßig und die Anzahl der Gruppen unbekannt ist
• Ein Forscher, der Daten mit natürlichem Rauschen analysiert, bei denen das Erzwingen jedes Punkts in ein Cluster (wie bei K-Means) die Analyse verfälschen würde
• Ein Ingenieur, der Sensormesswerte gruppiert, die nicht-sphärische Muster (Ringe, Halbmonde, langgestreckte Formen) bilden, die K-Means nicht erkennen kann

Häufige Fehler vermeiden

• Epsilon zu groß wählen — dadurch verschmelzen unterschiedliche Cluster zu einem; verwenden Sie das k-Distanz-Diagramm, um den geeigneten eps-Wert am Knick der Kurve zu finden
• Epsilon zu klein wählen — dadurch werden die meisten Punkte als Rauschen klassifiziert und wenige oder keine Cluster gefunden; wenn der Großteil Ihrer Daten als Rauschen markiert wird, ist eps vermutlich zu klein
• Merkmale vor dem Clustering nicht skalieren — DBSCAN verwendet die euklidische Distanz, daher dominieren Merkmale mit größeren Skalen die Distanzberechnung; standardisieren Sie zuerst alle Merkmale
• DBSCAN verwenden, wenn Cluster sehr unterschiedliche Dichten haben — ein einzelner eps-Wert kann dichte und dünn besetzte Cluster nicht gleichzeitig abdecken; ziehen Sie stattdessen HDBSCAN oder OPTICS in Betracht

Ergebnisse interpretieren

• Rauschpunkte (als Ausreißer markiert) sind Datenpunkte in Regionen geringer Dichte — sie können echte Anomalien, Messfehler oder Übergangsdaten zwischen Clustern darstellen
• Die Anzahl der Cluster wird automatisch durch die Daten und Parameter bestimmt und nicht im Voraus festgelegt — das ist ein entscheidender Vorteil gegenüber K-Means
• Findet der Algorithmus nur ein Cluster oder klassifiziert alles als Rauschen, passen Sie eps und minSamples an — die Parameter müssen auf die Dichtestruktur Ihrer Daten abgestimmt werden

Verwandte Normen und Referenzen

• Ester, Kriegel, Sander & Xu (1996), 'A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise', Proc. KDD-96 — die ursprüngliche DBSCAN-Veröffentlichung
• Schubert, Sander, Ester, Kriegel & Xu (2017), 'DBSCAN Revisited, Revisited', ACM Transactions on Database Systems — moderne Hinweise zur Parameterwahl und zur k-Distanz-Heuristik

Häufig gestellte Fragen

Wie wählt man eps und minSamples?

minSamples: typisch 2 × Dimensionsanzahl. eps: k-nächste-Nachbar-Distanzkurve plotten, 'Knie' wählen.

Wann DBSCAN statt K-Means?

Bei unbekannter Clusteranzahl, unregelmäßigen Formen oder signifikantem Rauschen. K-Means ist schneller für sphärische Cluster.