Clusteranalyse einfach erklärt: Data Science für Anfänger

Die Clusteranalyse oder auch Clustering ist ein beliebtes Verfahren zur Segmentierung von Daten. Im folgenden Artikel erkläre ich dir alle wichtigen Begriffe im Zusammenhang mit der Clusteranalyse, gebe dir einen Überblick über verschiedene Distanzmaße und Clustering-Algorithmen und außerdem einige Beispiele, damit du das Verfahren wirklich verstehst und auch selbst anwenden kannst.

Einführung in die Clusteranalyse

Die Clusteranalyse ist genau wie die Assoziationsanalyse (mehr dazu hier: Einführung in die Assoziationsanalyse) ein exploratives Verfahren – das bedeutet, dass sie vor allem eingesetzt wird, um Datensätze zu erforschen und Strukturen oder Ähnlichkeiten zu entdecken, die nicht von vornherein festgelegt sind. In explorativen Verfahren gibt es daher keine vorgefertigten Hypothesen; man versucht vielmehr, durch die Analyse unbekannte Zusammenhänge, Gruppen oder Strukturen aufzudecken.

Das Ergebnis einer Clusteranalyse sind Cluster von Objekten, die beschrieben (und oft auch verglichen) werden – wie beispielsweise Lebensstilgruppen oder Konsumentensegmente. Dabei ist das Ziel einer Clusteranalyse immer, dass die Gruppen in sich möglichst homogen sind, während die Gruppen untereinander sich möglichst stark voneinander unterscheiden sollen. Beispielsweise könnte ein Clustering von Kundendaten ergeben,  das Cluster A eher junge, urbane Konsumenten enthält, die technologieaffin sind und oft online einkaufen, während Cluster B aus älteren Kunden besteht, die Wert auf persönlichen Service legen und traditionelle Kaufgewohnheiten haben.

Durch die Einteilung in verschiedene Cluster können diese dann gezielter und passender angesprochen werden. Wie das erreicht wird, hängt unter anderem von dem gewählten Distanzmaß und dem Clustering-Algorithmus ab. Davon gibt es ganz schön viele (siehe weiter unten) wodurch das Thema zu Beginn ganz schön erschlagend sein kann.

Beispielfragen für eine Clusteranalyse könnten sein:

• Können mittels Jahreseinkommen, Alter und Berufserfahrung Cluster gebildet werden?
• Können Personen anhand ihres Markenbewusstseins, ihres Umweltbewusstseins und ihrer politischen Orientierung gruppiert werden?

Ein kurzes Beispiel zur Einführung ins Clustering

Damit du besser verstehst, worum es geht, fangen wir mit einem einfachen Beispiel an:

Wie könnte man diese Gruppe Sportler:innen clustern? Eine Vorgehensweise wäre, zu sagen: „Jede Person in der Tabelle ist ein/e Sportler:in, somit gibt es nur die eine Gruppe der Sportler:innen“. Genau so einfach, aber auch nicht zielführend, wäre es, zu sagen: „Jede Person ist seine eigene Gruppe, es gibt n=3 Personen und somit 3 Gruppen.“ Beides bringt uns nicht wirklich weiter, denn wir wollen viel mehr wissen, wie sich die Gruppe so einteilen lässt, das wir Untergruppen bilden, in denen die dort zugehörigen sich ähnlicher sind, als zum Rest.

Die Frage ist also:
Welche dieser Sportler:innen sind sich am ähnlichsten? Oder anders ausgedrückt: Welche dieser Sportler:innen sind sich „am nächsten“?

Für jedes Paar lassen sich Ähnlichkeiten finden, sie sind sich in bestimmten Dingen nah; es kommt nur darauf an, wie wir „nah“ definieren, d.h., welchem „Feature“ (Liegestütze, Ruhepuls oder 1.600m Zeit) wir besonderes Gewicht zuweisen oder wie wir diese miteinander in Relation setzen:

• Aaron und Beatrix sind sich bei Liegestützen und Ruhepuls nah.
• Aaron und Clemens sind sich nahe, weil beide in einer Diszipin die besten Ergebnisse haben (Aaron beim Laufen und Clemens bei den Liegestützen)
• Beatrix und Clemens sind sich ähnlich, weil sie beide deutlich langsamer sind als Aaron.

Jetzt haben wir schon ein paar Dinge angesprochen, die für eine Clusteranalyse wichtig sind:

Beim Clustern geht es darum, zu bestimmen, welche Datenpunkte sich nah oder ähnlich sind. Dafür gibt es verschiedene „Distanzmaße“, die wir gleich noch näher betrachten. Ausschlaggebend ist außerdem, welcher Clustering-Algoritmus verwendet wird. Sowohl die Wahl des Distanzmaßes als auch der verwendete Clustering-Algorithmus (das angewandte Verfahren) hat einen wesentlichen Einfluss auf das Ergebnis, weshalb sie mit bedacht gewählt werden sollen.

Wie läuft eine Clusteranalyse ab?

Um eine Clusteranalyse durchzuführen, sind 3 wesentliche Schritte notwendig: Die Distanzmessung, das Clustering und die Bestimmung oder Optimierung der Cluster. Vorab steht die Vorbereitung der Daten.

Clustering-Algorithmen: Eine Gesamt-Übersicht

Der Clustering-Algorithmus nimmt die eigentliche Gruppierung vor. Hierfür gibt es eine Vielzahl an verschiedenen Verfahren, über die ich der Vollständigkeit halber einen kurzen Überblick geben möchte:

Wir schauen uns weiter unten ein komplettes Beispiel für den Entferntester Nachbar („complete linkage“) Algorithmus an. Doch zuvor noch ein paar Worte zu den Distanzmaßen.

Distanzmaße in der Clusteranalyse

Der Begriff „Distanzmaß“ wird häufig synonym für „Proximitätsmaß“ verwendet, tatsächlich ist „Proximitätsmaß“ aber der Oberbegriff, unter den sowohl die Distanzmaße als auch die Ähnlichkeitsmaße fallen. Beide werden genutzt, um festzustellen, welche Datenpunkte innerhalb eines Clusters sich ähnlicher sind als andere. Distanzmaße werden tendenziell kleiner, je ähnlicher zwei Punkte sich sind. Bei Ähnlichkeitsmaßen ist es andersherum: Bei größerer Ähnlichkeit zwischen zwei Punkten steigt ihr Wert.

Distanz- und Ähnlichkeitsmaße in der Clusteranalyse sind nichts anderes, als mathematische Methoden zur Berechnung der Ähnlichkeit oder Unähnlichkeit (=Distanz) zwischen zwei (oder mehr) Datenpunkten oder Objekten. Die Wahl des Distanzmaßes hat dabei einen großen Einfluss auf das Ergebnis der Clusteranalyse!

Ein gut gewähltes Distanzmaß sorgt dafür, dass ähnliche Objekte zuverlässig in demselben Cluster landen und somit Cluster gebildet werden, die die Strukturen im Datensatz sinnvoll wiedergeben. Doch woher soll man wissen, welches Distanzmaß das richtige ist?

Distanz- oder Ähnlichkeitsmaß bestimmen – wann kommt was zum Einsatz?

Welches Distanz- oder Ähnlichkeitsmaß das richtige ist, hängt von verschiedenen Faktoren ab, die sich aus den Eigenschaften (genauer gesagt der Art und dem Skalenniveau) der Daten, der Zielsetzung der Analyse und den Anforderungen des gewählten Algorithmus ergeben. Beim k-means Algorithmus wird zum Beispiel typischerweise die euklidische Distanz verwendet. Andere Algorithmen und ihr dazu passendes Distanzmaß findest du weiter unten in der Tabelle.

Distanzmaße nach Datentyp

Einen Anhaltspunkt zur Wahl des Distanzmaß liefert zum Beispiel der untersuchte Datentyp:

• Für metrische Daten (z.B. Körpergröße, Alter, Einkommen) sind die euklidische und die Manhattan-Distanz üblich, da sie direkte Abstände zwischen numerischen Werten messen.
• Für kategorische oder binäre Daten (z.B. Geschlecht, Ja/Nein-Antworten) eignet sich die Hamming-Distanz, da sie die Anzahl der Unterschiede zwischen den Einträgen zählt.
• Für Textdaten oder Vektordaten (z.B. Dokumentähnlichkeit, Vektordarstellungen) wird gern die Kosinus-Ähnlichkeit verwendet, da sie die Winkel zwischen Vektoren misst und somit die Richtung der Daten berücksichtigt, statt ihrer absoluten Größe.

Distanzmaße in Abhängigkeit vom Clustering-Algorithmus

Einige Clustering-Algorithmen setzen bestimmte Maße voraus:

• Der k-Means Algorithmus benötigt ein metrisches Maß, z. B. die Euklidische Distanz.
• Hierarchische Clustering Algorithmen unterstützen sowohl Distanz- als auch Ähnlichkeitsmaße.
• DBSCAN (Dichtebasiertes Clustering) ist flexibel in der Wahl des Maßes (benutzerdefiniert möglich).

Distanzmaße in Abhängigkeit von derClusterform

• Wenn Cluster kompakt und kugelförmig sind:
  • Euklidische Distanz (z. B. für k-Means).
• Wenn Cluster länglich oder unregelmäßig geformt sind:
  • Manhattan-Distanz oder DBSCAN mit benutzerdefiniertem Maß.

Zusammenfassung der Kriterien

Die Wahl sollte immer von einer Voruntersuchung der Daten begleitet werden, z. B. durch Visualisierung oder Analyse von Korrelationen und Streuungen.

Praxisbeispiel: Hierachsiche Clusteranalyse nach dem Complete-Linkage-Verfahren

Hinweis: In diesem Beispiel gehen wir davon aus, dass die Daten, mit denen wir arbeiten, als zwei-dimensionale Koordinaten (X, Y) vorliegen und verwenden als Distanzmaß die euklidische Distanz. Das sollte in Prüfungssituationen in der Regel der Fall sein und war auch in meiner Modulprüfung so.

Das Vorgehen

1. Daten vorbereiten:
   • Datenpunkte in Form von Vektoren oder Koordinaten sammeln (metrische oder numerische Daten) und in eine übersichtliche Form birngen.
   • Optional: Daten standardisieren, falls sie unterschiedliche Maßeinheiten haben (z. B. Zentimeter und Kilogramm).
2. Distanzmatrix berechnen:
   • Wir berechnen die Paarweise-Distanzen zwischen allen Datenpunkten mit einem geeigneten Distanzmaß (z. B. euklidische Distanz).
   • Das Ergebnis ist eine Distanzmatrix, die alle Abstände enthält.
   • Aus dieser können wir ablesen, welche Cluster die geringsten Abstände zueinander haben.
3. Clusterbildung:
   • Zu Beginn bildet jeder Datenpunkt ein eigenes Cluster, wodurch wir n Cluster haben.
   • Als nächstes identifizieren wir die beiden Cluster mit der geringsten maximalen Distanz und fassen diese Cluster zusammen. Dabei ist nach dem Complete Linkage immer die größte Distanz zwischen den beiden Punkten in den Clustern ausschlaggebend. (Es gibt andere Algorithmus, bei denen zum Beispiel nicht einer der Punkte des Clusters für die Bestimmung der Distanz herangezogen wird, sondern das jeweilige Zentrum eines Clusters). Da dies hier NICHT der Fall ist, sondern sich die maximale Distanz immer auf einen Punkt im Cluster bezieht, lassen sich alle Distanzen aus der einmal berechneten Distanzmatrix ablesen.
4. Distanzmatrix aktualisieren bzw. Distanzen ablesen:
   • Wie oben erwähnt können wir beim Complete Linkage Verfahren direkt aus der Distanzmatrix ablesen, welche Cluster als nächstes zusammengefasst werden müssen und müssen nichts neu berechen. Bei anderen Algorithmen wird die Distanzmatrix an dieser Stelle neu berechnet, um herauszufinden, welche Cluster das Kriterium erfüllen (zum Beispiel kleinster Abstand der Mittelpunkte zweier Cluster zueinander) und als nächstes zusammengefasst werden müssen.
   • Dieser Schritt wird so lange wiederholt, bis alle Datenpunkte in einem einzigen Cluster zusammengefasst sind oder die gewünschte Anzahl von Clustern erreicht ist.
5. Visualisierung und Interpretation:
   • Zur Visualisierung der Hierachie der Cluster wird in der Regel (bei hierachischen Clusteralgorithmen) ein Dendrogramm erstellt.
   • Durch die Analyse der Dendrogrammhöhen oder anderen Validierungsmetriken, wie z. B. dem Silhouettenkoeffizient lässt sich die optimale Anzahl von Clustern bestimmen.

Das Complete-Linkage (Entferntester Nachbar)-Verfahren ist ein hierarchischer Clustering-Algorithmus, der damit beginnt, das jeder Datenpunkt ein eigenes Cluster bildet. Danach werden schrittweise immer die beiden Cluster mit der kleinsten maximalen Distanz kombiniert. Die kleinste maximale Distanz kann man für die erste Fusion ganz einfach in der Distanzmatrix, die wir gleich berechnen werden, ablesen. Für das weitere Vorgehen passiert dann folgendes:

Alle Distanzen zwischen den Clustern werden neu ermittelt, um die nächst kleinere Distanz zwischen den verschiedenen Clustern zu ermitteln. Beim Complete Linkage Verfahren ist dabei die größte Distanz zwischen den beiden Punkten in den Clustern ausschlaggebend. Wie wir dabei Vorgehen, erläutere ich weiter unten.

Als erstes berechnen wir daher die Distanzmatrix für die angegebenen Datenpunkte, basierend auf der euklidischen Distanz, die sich gut für solche metrischen Daten eignet.

Schritt 1: Datenpunkte ordnen

Angenommen, wir haben folgende Werte gegeben:

Schritt 2: Berechnung der euklidischen Distanz

Formel:

Für zwei Punkte (x1 ,x2, … xn) und (y1, y2, … yn) in einem $n$-dimensionalen Raum lautet die Formel der euklidischen Distanz:

Wenn die Punkte in einem zwei-dimensionalen-Raum liegen, wie in unserem Beispiel, reduziert sich die Formel zu:

Hier ein Rechenbeispiel für unsere ersten beiden Punkte X1 (1,2) und X2 (2,3)

Auf diese Weise berechnen wir die folgende Distanzmatrix für unsere Werte X1 bis X9.

Schritt 3: Clusterbildung

Zu Beginn bildet jeder Datenpunkt ein eigenes Cluster, wodurch wir 9 Cluster haben. Als nächstes identifizieren wir die beiden Cluster mit der geringsten maximalen Distanz und fassen diese Cluster zusammen. Das sind in diesem Fall die Cluster X4 und X5, die eine Distanz von 1 zueinander haben.

Schritt 4: Clusterbildung schrittweise wiederholen

1. Geringste Distanz finden

Die geringste Distanz ist die Distanz zwischen X4 und X5: d (X4,X5) = 1.00
Aktion: Cluster (X4) und (X5) werden zu einem neuen Cluster (X4, X5) zusammengefasst.

Schritt 2: Aktualisierung der Distanzen

Die neue Distanz zwischen dem Cluster (X4, X5) und jedem anderen Cluster wird berechnet, indem die maximale Distanz zwischen den Punkten des Clusters (X4, X5) und den anderen Punkten ermittelt wird. Es werden also die Distanzen beider Punkte (X4 und X5) mit den jeweils anderen Punkten verglichen, wobei die größere Distanz ausschlaggebend ist.
Beispiel: d ((X4, X5) X1)=max ⁡(d (X4, X1) ,d (X5, X1) ) = max ⁡(3.00, 4.00) = 4.00

Schritt 3: Nächste geringste Distanz ermitteln

Nach Aktualisierung der Matrix wird die nächstkleinere Distanz ermittelt:

Diese ist mit 1,41 zwischen Cluster X1 und X2 sowie ebenfalls mit 1,41 zwischen Cluster X6 und X7
Aktion: Cluster (X1) und (X2) werden zu einem neuen Cluster (X1, X2) zusammengefasst.
Cluster (X6) und (X7) werden ebenfalls zu einem neuen Cluster (X6, X7) zusammengefasst.

Wie beim ersten Cluster werden nun die neuen Distanzen der Cluster zueinander ermittelt, in dem die maximale Distanz zwischen den Punkten (X1, X2) bzw. (X6, X7) und den anderen Punkten ermittelt wird.

Dabei ergibt sich für Cluster (X6, X7) und Cluster (X8):
d ((X6, X7) X8)=max ⁡(d (X6, X8) ,d (X7, X8) ) = max ⁡(3.00, 2,24) = 3.00

Die nächstkleinere maximale Distanz zwischen zwei Punkten ist also mit 3,00 die Distanz zwischen den Clustern (X6, X7) und (X8).
Warum nicht 2,24? Weil wir den Complete Linkage Algorithmus anwenden und dabei immer der Punkt ausschlaggebend ist, der weiter entfernt ist, eben die maximale Distanz zwischen den nächstgelegenen Clustern.

Schritt 4: Prozess wiederholen, bis alle Cluster zu einem einzigen Cluster zusammengefasst sind

Nächstkleinere Distanz ermitteln:

Die Distanzen zwischen (X1, X2) und (X3) ergeben:
d ((X1, X2) ,X3) = max ⁡(d (X1,X3) ,d(X2,X3)) = max ⁡(3.16, 2.83) =3.16
Aktion: Cluster (X1, X2) und (X3) werden zu einem neuen Cluster (X1, X2, X3) zusammengefasst.

Danach wird das Cluster von X5 und X4 mit dem Cluster von X6, X7 und X8 vereinigt und bildet das sechste Cluster.
Das siebte Cluster bilden die Cluster von X9, X1, X2 und X3.
Das letzte und siebte Cluster bilden alle Cluster zusammen.

Schritt 5: Visualisierung und Interpretation

Hier ist das Dendrogramm der agglomerativen hierarchischen Clusteranalyse mit dem Complete-Linkage-Verfahren.

Interpretation:

1. Die x-Achse zeigt die Datenpunkte (X1 bis X9).
2. Die y-Achse gibt die euklidische Distanz an, bei der die Cluster zusammengeführt werden.
3. Die Höhe der Verzweigung (Verbindungen) zeigt die Distanzen, bei denen Cluster zusammengeführt wurden.

Quellen: