Clustering im Machine Learning: 5 unverzichtbare Clustering-Algorithmen

Clustering ist kein einzelner Algorithmus, sondern eine Aufgabenstellung. Du kannst sie mit verschiedenen Algorithmen lösen, die sich stark darin unterscheiden, was sie als Cluster verstehen und wie sie diese effizient finden. 

Intuition für Clustering aufbauen

Bevor wir in Details einsteigen, bauen wir ein Gefühl für Clustering mit einem einfachen Obst-Beispiel auf. Angenommen, wir haben eine große Bildsammlung mit drei Obstsorten: (i) Erdbeeren, (ii) Birnen und (iii) Äpfeln. 

Im Datensatz sind alle Bilder vermischt, und deine Aufgabe ist es, ähnliche Früchte zusammenzufassen — also drei Gruppen zu bilden, die jeweils eine Obstsorte enthalten. Genau das macht ein Clustering-Algorithmus. 

Erfolgskriterien für Clustering-Analysen

Clustering lässt sich — anders als überwachte Use-Cases wie Klassifikation oder Regression — nicht vollständig End-to-End automatisieren. Es ist ein iterativer Entdeckungsprozess, der Domänenwissen und menschliches Urteilsvermögen erfordert, um Daten und Modellparameter gezielt anzupassen, bis das gewünschte Ergebnis erreicht ist. 

Vor allem gilt: Weil Clustering unüberwachtes Lernen ist und keine gelabelten Daten nutzt, können wir Performance-Metriken wie Accuracy, AUC, RMSE etc. nicht berechnen, um Algorithmen oder Preprocessing-Varianten direkt zu vergleichen. Das macht die Beurteilung von Clustering-Modellen anspruchsvoll und subjektiv. 

Die wichtigsten Erfolgskriterien für Clustering-Modelle sind:

• Ist das Ergebnis interpretierbar?
• Stiftet das Clustering einen klaren geschäftlichen Nutzen?
• Hast du neue Informationen oder Muster entdeckt, die vor dem Clustering nicht sichtbar waren?

Clustering-Qualität messen

Ohne gelabelte Daten kannst du keine Accuracy oder AUC berechnen. Zwei Metriken helfen, die Trennschärfe deiner Cluster zu quantifizieren. Häufig genutzt sind:

• Der Silhouette-Score misst, wie ähnlich ein Punkt seinem eigenen Cluster im Vergleich zum nächstgelegenen Nachbarcluster ist. Werte liegen zwischen -1 und 1; über 0,5 deutet auf gut getrennte Cluster hin.
• Der Davies-Bouldin-Index misst die durchschnittliche Ähnlichkeit jedes Clusters mit seinem ähnlichsten Cluster — je niedriger, desto besser.

Beide sind in scikit-learn verfügbar: sklearn.metrics.silhouette_score(X, labels) und sklearn.metrics.davies_bouldin_score(X, labels).

1. K-Means

K-Means ist der am häufigsten genutzte Algorithmus für Clustering-Aufgaben, vor allem weil die Schritte leicht nachvollziehbar und die Implementierung in scikit-learn unkompliziert ist. Es ist ein zentroidbasierter Algorithmus, bei dem du die gewünschte Anzahl an Clustern vorgeben musst. 

Diese ergibt sich meist aus dem Business-Use-Case oder durch Ausprobieren verschiedener Clusterzahlen und anschließender Bewertung der Ergebnisse. 

K-Means ist ein iterativer Algorithmus, der nicht überlappende Cluster erzeugt — jede Instanz im Datensatz gehört genau zu einem Cluster. Die Intuition hinter K-Means lässt sich am besten über die einzelnen Schritte und das folgende Diagramm erfassen. Eine ausführliche Beschreibung findest du in unseren Tutorials K-Means Clustering in Python und K-Means Clustering in R. 

1. Du gibst die Anzahl der Cluster vor.
2. Initialisiere die Zentroiden zufällig basierend auf der Clusterzahl. Im Diagramm unten siehst du in Iteration 1 drei zufällig gesetzte Zentroiden (blau, rot, grün).
3. Berechne die Distanz zwischen Datenpunkten und jedem Zentroid und weise jeden Punkt dem nächstgelegenen Zentroid zu.
4. Berechne den Mittelwert des Zentroids anhand aller zugewiesenen Punkte neu; dadurch verschiebt sich seine Position (siehe Iteration 2–9), bis das Verfahren konvergiert.
5. Es wird iteriert, bis sich der Mittelwert eines Zentroids nicht mehr ändert oder max_iter erreicht ist — die maximale Iterationszahl, die du beim Training festlegst. In scikit-learn ist der Standardwert 300.

Image Source: Learnbymarketing.com

2. MeanShift

Im Gegensatz zu K-Means erfordert der MeanShift-Algorithmus keine Angabe der Clusteranzahl. Er bestimmt die Anzahl der Cluster automatisch — ein klarer Vorteil, wenn du nicht weißt, wie viele Cluster in den Daten stecken. 

MeanShift ist ebenfalls zentroidbasiert und ordnet Datenpunkte iterativ Clustern zu. Ein häufiger Use-Case ist die Bildsegmentierung.

MeanShift beruht auf Kerndichteschätzung. Ähnlich wie K-Means weist MeanShift jeden Punkt iterativ dem nächstgelegenen Cluster-Zentroid zu (initial zufällig) und verschiebt Punkte im Raum in Richtung der höchsten Punktedichte, also der Mode (im Kontext von MeanShift: Bereich mit maximaler Dichte). 

Darum ist MeanShift auch als Mode-seeking-Algorithmus bekannt. Die Schritte sind:

• Wähle einen zufälligen Punkt und lege ein Fenster um ihn herum.
• Berechne den Mittelwert aller Punkte in diesem Fenster.
• Verschiebe das Fenster in Richtung der Mode. 
• Wiederhole die Schritte bis zur Konvergenz.

Image Source: ResearchGate

Einen praxisnahen Walkthrough findest du im Mean Shift Clustering Tutorial.

3. DBSCAN

DBSCAN, kurz für Density-Based Spatial Clustering of Applications with Noise, ist ein unüberwachter Clustering-Algorithmus, der davon ausgeht, dass Cluster dichte Regionen sind, getrennt durch Bereiche geringerer Dichte. 

Der größte Vorteil gegenüber K-Means und MeanShift: Er ist robust gegenüber Ausreißern — Ausreißer werden keinem Cluster zugeordnet. 

DBSCAN benötigt nur zwei Parameter: 

• Den Radius des Kreises um jeden Punkt, genannt epsilon

• minPoints — die minimale Punktzahl in diesem Kreis, damit der Punkt als Kernpunkt (Core) gilt.

Jeder Punkt wird von einem Kreis mit Radius epsilon umgeben, und DBSCAN klassifiziert ihn als Kernpunkt, Randpunkt (Border) oder Rauschen (Noise). Ein Punkt ist Kernpunkt, wenn der umgebende Kreis mindestens minPoints enthält. 

Liegt die Punktzahl darunter, ist er Randpunkt; gibt es innerhalb eines Epsilon-Radius’ keine weiteren Punkte, gilt er als Rauschen. Rauschpunkte gehören zu keinem Cluster (sprich: Ausreißer).

Typische Use-Cases für DBSCAN sind:

• Sehr gute Trennung von Bereichen hoher und niedriger Dichte
• Funktioniert gut auf nichtlinearen Datensätzen
• Eignet sich für Anomalieerkennung, da Rauschpunkte isoliert werden

DBSCAN vs. K-Means

Im Vergleich zu K-Means zeigen sich vor allem diese Unterschiede: 

• K-Means weist alle Instanzen einem Cluster zu, DBSCAN ordnet Rauschpunkte (Ausreißer) keinem gültigen Cluster zu
• K-Means tut sich mit nicht-globularen Clustern schwer, DBSCAN bewältigt das problemlos
• K-Means setzt implizit normalverteilte Daten voraus, DBSCAN macht keine Annahmen über die Verteilung

Mehr dazu im DBSCAN-Guide mit Parametertuning und Beispielen. 

Image Source: Medium

4. Hierarchical Clustering

Hierarchisches Clustering baut eine Hierarchie von Clustern auf. Es gibt zwei Varianten. 

• Agglomerativ: Bottom-up — jede Beobachtung startet als eigenes Cluster, dann werden zunächst Beobachtungen zu Paaren, anschließend Paare zu Clustern zusammengeführt. 
• Divisiv: Top-down — alle Beobachtungen starten in einem Cluster und werden schrittweise rekursiv aufgeteilt.

Bei der Analyse von Social-Network-Daten ist hierarchisches Clustering mit Abstand die gängigste Methode. Knoten (Äste) im Graphen werden je nach Ähnlichkeit verglichen; durch das Verbinden kleinerer, verwandter Knotengruppen entstehen größere Gruppen.

Der größte Vorteil: Es ist leicht zu verstehen und zu implementieren. Das Ergebnis wird meist als Dendrogramm visualisiert.

Mehr dazu im Tutorial zum hierarchischen Clustering, inklusive Aufbau und Interpretation von Dendrogrammen in Python. 

Image Source: ResearchGate

5. BIRCH

BIRCH steht für Balanced Iterative Hierarchical Based Clustering. Es wird für sehr große Datensätze eingesetzt, bei denen K-Means praktisch nicht skaliert. BIRCH teilt große Daten in kleine Cluster und versucht, dabei möglichst viele Informationen zu bewahren. Die kleineren Gruppen werden anschließend zu einem Endergebnis geclustert, statt den gesamten großen Datensatz direkt zu clustern. 

BIRCH dient oft als Vorstufe für andere Clustering-Algorithmen, indem es eine kompakte Zusammenfassung erzeugt, die diese Algorithmen weiterverwenden können. Wie bei K-Means musst du auch hier die Anzahl der Cluster für das Training vorgeben.

Ein Vorteil von BIRCH ist die schrittweise, dynamische Clusterbildung für mehrdimensionale Datenpunkte — mit dem Ziel, unter gegebenen Speicher- und Zeitbudgets möglichst hochwertige Cluster zu erzeugen. In vielen Fällen genügt ein einziger Durchlauf über die Datenbank — das macht BIRCH skalierbar. 

Der häufigste Use-Case: eine speichereffiziente Alternative zu K-Means, um sehr große Datensätze zu clustern, die aufgrund von Speicher- oder Rechenlimits nicht mit K-Means bearbeitet werden können.

Business-Anwendungen von Clustering

Clustering hat breite Anwendung in Medien, Gesundheitswesen, Fertigung, Handel — überall dort, wo große Mengen ungelabelter Daten vorliegen. Hier einige Praxisbeispiele.

Kundensegmentierung

Kundinnen und Kunden werden anhand ihres Kaufverhaltens oder ihrer Interessen geclustert, um zielgenaue Marketingkampagnen zu entwickeln. 

Stell dir vor, du hast 10 Mio. Kunden und möchtest personalisierte Kampagnen fahren. 10 Mio. Kampagnen sind unrealistisch — also clusterst du die 10 Mio. in z. B. 25 Gruppen und entwickelst 25 Kampagnen statt 10 Mio.

Image Source: Medium

Retail-Clustering

Im Handel gibt es viele Clustering-Chancen. Du kannst z. B. Filialdaten sammeln und auf Filialebene clustern, um zu erkennen, welche Standorte sich ähneln — etwa nach Frequenz, Durchschnittsumsatz, SKU-Anzahl usw. 

Ein weiteres Beispiel ist Clustering auf Kategorieebene. Im Diagramm unten gibt es acht Filialen. Unterschiedliche Farben stehen für verschiedene Cluster — insgesamt vier. 

Beachte: Die Kategorie Deodorants ist in Filiale 1 rot (Cluster A), in Filiale 2 jedoch blau (Cluster B). Das zeigt, dass beide Filialen für Deodorants völlig unterschiedliche Zielgruppen haben.

Image source: dotactiv.com

Clustering in der klinischen Versorgung / Krankheitsmanagement

Im Gesundheitswesen gibt es besonders starke Clustering-Anwendungen. Ein Beispiel ist die Studie von Komaru & Yoshida et al. 2020: Demografie- und Labordaten von 101 Patientinnen und Patienten wurden erhoben und in drei Cluster segmentiert. 

Jedes Cluster weist andere Charakteristika auf. Beispielsweise enthält Cluster 1 Patienten mit niedrigem WBC & CRP, Cluster 2 mit hohem BMP & Serum und Cluster 3 mit niedrigem Serum. Jedes Cluster zeigt eine eigene Überlebenskurve in Bezug auf die 1-Jahres-Mortalität nach Hämodialyse.

Image source: elsevierhealth.com

Bildsegmentierung

Bildsegmentierung klassifiziert ein Bild in verschiedene Gruppen. In diesem Bereich gibt es viel Forschung mit Clustering. Ziel ist, Objekte im Bild zu isolieren, um sie separat zu analysieren. 

Im Beispiel unten siehst du links das Originalbild, rechts das Clustering-Ergebnis. Es sind klar vier Cluster erkennbar — vier Objekte, bestimmt anhand der Pixel (Tiger, Gras, Wasser, Sand).

Clustering-Algorithmen im Vergleich

In scikit-learn, einer beliebten Machine-Learning-Bibliothek für Python, sind 10 unüberwachte Clustering-Algorithmen implementiert. Sie unterscheiden sich grundlegend darin, wie sie Cluster erkennen und zuweisen. 

Diese Unterschiede lassen sich auf vier Aspekte herunterbrechen, anhand derer wir vergleichen können:

• Erforderliche Modellparameter 
• Skalierbarkeit 
• Use-Cases 
• Geometrie, d. h. verwendete Distanzmaße 

Im Diagramm unten steht jede Spalte für den Output eines anderen Clustering-Algorithmus, z. B. K-Means, Affinity Propagation, MeanShift usw. Insgesamt wurden 10 Algorithmen auf demselben Datensatz trainiert.

Einige Algorithmen liefern identische Ergebnisse. Beachte: Agglomeratives Clustering, DBSCAN, OPTICS und Spectral Clustering ergeben hier dieselben Cluster. 

Vergleichst du K-Means mit MeanShift, siehst du unterschiedliche Ergebnisse: K-Means erzeugt zwei Gruppen (blau und orange), MeanShift hingegen drei (blau, grün, orange). 

Image Source: scikit-learn

Leider (oder zum Glück) gibt es im Clustering nicht die eine richtige Antwort. Es wäre schön, einfach sagen zu können: „Algorithmus X ist hier der beste.“ 

Das ist nicht möglich — und gerade deshalb ist Clustering so herausfordernd. 

Am Ende hängt die Wahl weniger von leicht messbaren Metriken ab als von der Interpretation und dem konkreten Nutzen des Ergebnisses für den Use-Case.

So wählst du den richtigen Clustering-Algorithmus

Jeder Algorithmus passt zu anderen Datenbedingungen. Nutze diese Tabelle als Startpunkt — teste dann mindestens zwei Algorithmen mit deinen echten Daten, bevor du dich festlegst.

Ein praktischer Einstieg: Probiere zuerst K-Means wegen der Geschwindigkeit. Wechsle zu DBSCAN, wenn deine Daten unregelmäßige Formen oder Ausreißer haben. Nutze hierarchisches Clustering, wenn du die Clusterstruktur vor der Wahl von k visuell per Dendrogramm erkunden willst.

Abschluss

Clustering ist in der Praxis schwieriger anzuwenden als überwachte Verfahren wie Klassifikation und Regression — aus zwei Gründen: Es gibt keine Zielwerte zum Gegenprüfen, und Parameter wie die Clusteranzahl erfordern Domänenurteil statt einer rein algorithmischen Wahl. 

Clustering ist für viele Rollen wertvoll: Data Scientists, ML Engineers und Analysten stoßen regelmäßig auf Probleme, die sich damit lösen lassen. 

Wenn du Clustering und unüberwachtes Lernen vertiefen und die Umsetzung in Python und R lernen möchtest, helfen dir diese Kurse weiter: 

• Cluster Analysis in Python
• Cluster Analysis in R
• Unsupervised Learning in Python
• Unsupervised Learning in R