Abst�nde zwischen Objekten im multidimensionalen Raum bilden die Grundlage vieler multivariater Methoden der Datenanalyse. Unterschiedliche Methoden zur Berechnung der Abst�nde zu verwenden, kann die Ergebnisse einer Methode betr�chtlich beeinflussen. Die �hnlichkeiten von Objekten und deren Abst�nde sind nahe miteinander verwandt und werden oft verwechselt. W�hrend der Ausdruck "Abstand" pr�ziser und im mathematischen Sinn verwendet wird, h�ngt die genaue Bedeutung des Begriffs "�hnlichkeit" oft von den Umst�nden und dem Gebiet der Anwendung ab. Show Allgemein kann der Abstand dij zwischen zwei Punkten im n-dimensionalen Raum durch die Gleichung von Minkowski berechnet werden: mit k als dem Index der Koordinaten und p f�r die Art des Abstands. Es gibt drei Spezialf�lle des Minkowski-Abstands:
Die Mahalanobis-Distanz ist mit der euklidischen Distanz verwandt; f�r unkorrelierte, standardisierte Daten sind die beiden gleich. Sie kann leicht durch Einbeziehen der inversen Kovarianzmatrix C-1 in die Distanzberechnung errechnet werden: Ein anderes Abstandsma�, das eher ein Ma� f�r die �hnlichkeit zwischen zwei Objekten ist, wurde von Jaccard ( ) vorgeschlagen (es wird manchmal auch Tanimoto-Koeffizient genannt):,mit (x.y), als inneres Produkt der zwei Vektoren x und y. Man beachte, dass der Jaccard-Koeffizient f�r Objekte ohne Abstand gleich 1,0 wird. Au�erdem kann der Tanimoto-Koeffizient auch auf bin�re Daten angewendet werden: Die Linien in rot, blau und gelb sind drei Beispiele für die Manhattan-Distanz zwischen den zwei schwarzen Punkten (je 12 Einheiten lang); die grüne Linie stellt zum Vergleich den Euklidischen Abstand dar, der eine Länge von 6·√2 ≈ 8,5 hat. Die Manhattan-Metrik (auch Mannheimer, Taxi- oder Cityblock-Metrik) ist eine Metrik, in der die Distanz zwischen zwei Punkten als die Summe der absoluten Differenzen ihrer Einzelkoordinaten definiert wird: Die zugrundeliegende Geometrie wurde zuerst von Hermann Minkowski untersucht. Ihren Namen hat diese Distanzdefinition von der Schachbrettmuster-artigen Anlage der Gebäudeblöcke Manhattans, die einen Taxifahrer zwingen, die Entfernung zwischen zwei Adressen durch Aneinanderreihung „vertikaler“ und „horizontaler“ Wegstücke zu überwinden. Die Stadt Mannheim weist eine vergleichbare Struktur auf. Ein Taxifahrer, der seine Route durch ein derartiges System plant, legt auf der Fahrt zu seinem Ziel immer die gleiche Streckenlänge zurück, sofern er nur Wege benutzt, die ihn seinem Ziel näher bringen. Dabei verlässt er niemals ein am Raster ausgerichtetes Rechteck, dessen gegenüberliegende Ecke auf dem Start- und dem Zielpunkt liegen. In diesem Tutorial werden die Grundlagen der Clusteranalyse beschrieben und die hierarchische Clusteranalyse mit der Ward-Methode in Python umgesetzt. GrundlagenDie Clusteranalyse ist ein exploratives Verfahren um Ähnlichkeitsstrukturen in Daten zu erkennen. Bei den Untersuchungsobjekten einer Clusteranalyse kann es sich sowohl um Personen, Produkte oder um beliebige andere Einheiten wie Filme, Länder oder Unternehmen handeln. Durch die Anwendung der Clusteranalyse können diese Objekte anhand ihrer Eigenschaftsausprägungen zu Clustern zusammengefasst werden. Dabei soll jedes Cluster in sich möglichst gleichartig (homogen) sein und sich gleichzeitig von den anderen Clustern möglichst stark unterscheiden (heterogen). Beispielsweise erfasst der Streaminganbieter Netflix die Sehgewohnheiten seiner Abonnenten und hat auf dieser Grundlage über 2000 Mikro-Cluster, sogenannte “Taste Communities”, gebildet (New York Magazine, 2018). Den Mitgliedern der jeweiligen Clustern sollen anhand der jeweiligen Clusterzugehörigkeit möglichst passende Inhalte vorgeschlagen werden. Die Filme können dabei ebenfalls anhand unterschiedlicher Merkmale geclustert und im Anschluss mit aussagekräftigen Bezeichnungen versehen werden (Netflix, 2017): Wichtige Voraussetzungen, die bei der Durchführung der Analyse beachtet werden sollten (Universität Zürich, 2018):
Bei der Berechnung der Cluster wird nach bestimmten Regeln entschieden, wie die Objekte zu Clustern zusammengefasst werden. Das Ergebnis dieses Prozesses hängt nicht nur von der Wahl des Clustering-Algorithmus ab, sondern auch davon, wie die Distanz oder Ähnlichkeit zwischen den Objekten bestimmt wird. Zu Beginn der Clusteranalyse wird daher in Abhängigkeit von den vorliegenden Datentypen ein sogenanntes Proximitätsmaß gewählt. ProximitätsmaßMit Hilfe des Proximitätsmaßes wird die Distanz zwischen den Objekten berechnet. In Abhängigkeit von dem Skalenniveau der Variablen wird eine Distanzfunktion zur Bestimmung des Abstandes (Distanz) zweier Elemente oder eine Ähnlichkeitsfunktion zur Bestimmung der Ähnlichkeit verwendet:
In diesem Tutorial behandeln wir die Distanzmaße “euklidische Distanz” (auch $L_2$ genannt), “quadrierte euklidische Distanz” und die “L1-Distanz” (auch Manhattan-Metrik, Manhattan-Distanz, Mannheimer Metrik, Taxi- oder Cityblock-Metrik geannt). Euklidische DistanzMit Hilfe der euklidischen Distanz kann der Abstand zwischen zwei Punkten als gerade Linie in einem Raum berechnet werden (“Luftliniendistanz”). Anders formuliert ist der euklidische Abstand zweier Punkte die mit einem Lineal gemessene Länge einer Strecke, die diese zwei Punkte verbindet. Ein Distanzwert von Null bedeutet dabei, dass die Objekte einen Abstand von Null aufweisen, also identisch sind. Die Formel für die Berechnung der euklidischen Distanz für $n$ verschiedenen Variablen lautet: $$d(A,B) = \sqrt{\sum_{i=1}^{n}(A_i - B_i)^2}$$ Die Formel kann in einem zweidimensionalen Koordinatensystem mit den beiden Variablen $X$ und $Y$ (d.h. n = 2) wie folgt visualisiert werden (Korstanje, 2019): Wie aus dem Punktediagramm entnommen werden kann, gelten für die Punkte A und B:
Da wir in diesem Beispiel nur 2 Variablen vorliegen haben (n = 2), gilt hier ein bekannter Spezialfall der Berechnung des euklidischen Abstandes: der Satz des Pythagoras. Für die Berechnung der euklidischen Distanz werden daher lediglich die (X,Y)-Koordinaten benötigt um mit Hilfe der Formel von Pythagoras die Distanz zu berechnen: $$d(A,B) = \sqrt{(x_A-x_B)^2 + (y_A-y_B)^2}$$ $$d(A,B) = \sqrt{(70-330)^2 + (40-228)^2}$$ $$d(A,B) = \sqrt{(-260)^2 + (-188)^2}$$ $$d(A,B) = \sqrt{(76600 + 35344) }$$ $$d(A,B) = \sqrt{(112225) }$$ $$d(A,B) = 335$$ Quadrierte euklidische DistanzAnstelle der einfachen euklidischen Distanz kann auch die quadrierte euklidische Distanz als Distanzmaß genutzt werden. Dadurch werden größere Abweichungen stärker gewichtet. Die Formel der quadrierten euklidischen Distanz lautet: $$d^2(A,B) = \sum_{i=1}^{n}(A_i - B_i)^2$$ Für unser Datenbeispiel gilt daher: $$d^2(A,B) = (x_A-x_B)^2 + (y_A-y_B)^2$$ $$d^2(A,B) = (70-330)^2 + (40-228)^2$$ $$d^2(A,B) = 112225$$ $L_1$-DistanzDie $L_1$-Distanz (auch Manhattan-Metrik, Manhattan-Distanz, Mannheimer Metrik, Taxi- oder Cityblock-Metrik) ist eine Metrik, in der die Distanz $d$ zwischen zwei Punkten $A$ und $B$ als die Summe der absoluten Differenzen ihrer Einzelkoordinaten definiert wird. Dies ist insbesondere bei der Berechnung von geografischen Abständen relevant, bei welchen der Abstand zwischen zwei Punkten über vordefinierte Wege (bspw. Straßen in einer Stadt mit einer blockartigen Struktur wie in Manhattan oder Mannheim) zurückgelegt werden muss (Korstanje, 2019) Wie aus der Abbildung ersichtlich wird, existieren mehrere Möglichkeiten, den Abstand zwischen den Punkten A und B zu berechnen. Wichtig ist jedoch, dass die “Straßen” nicht verlassen werden dürfen. D.h. es können bspw. zwei Blöcke nach oben (Norden) und dann drei Blöcke nach rechts (Osten) auf der Fahrbahn zurückgelegt werden, um von Punkt A aus Punkt B zu erreichen. Unabhängig von dem gewählten Pfad ist die Distanz aufgrund der blockartigen Struktur immer die gleiche. Allgemein lautet die Formel für die Berechnung des L1-Abstands wie folgt: $$d(A,B) = \sum_{i} |A_i - B_i|$$ In unserem Fall gilt: $$d(A,B) = |x_A - x_B| + |y_A - y_B |$$ $$d(A,B) = |70 - 330| + |40 - 228 |$$ $$d(A,B) = |-260 | + |-188|$$ $$d(A,B) = 260 + 188$$ $$d(A,B) = 448 $$ Clustering-AlgorithmusIst das Proximitätsmaß berechnet, so wird anhand eines Clustering-Algorithmus die eigentliche Gruppierung der Daten vorgenommen. In dieser Abbildung sind beispielhaft einige Clustering-Algorithmen aufgeführt (Universität Zürich, 2018): Bei den hier dargestellten Algorithmen wird zwischen hierarchischen und nicht-hierarchischen Algorithmen unterschieden. Im Rahmen dieses Tutorials werden ausschließlich hierarchische Algorithmen behandelt. Diese werden weiter in agglomerative und divisive Verfahren unterteilt. Bei divisiven Verfahren wird zunächst ein Cluster gebildet, welches alle Datenpunkte enthält. Dieses wird dann schrittweise in kleinere Cluster zerteilt, bis jeder Fall ein eigenes Cluster bildet. Bei agglomerativen Verfahren werden die Datenpunkte zuerst einzeln betrachtet (d.h. jeder Fall ist ein eigenes Cluster) und dann schrittweise zu größeren Clustern zusammengefasst. Die agglomerativen Verfahren werden in Linkage-Methoden und Varianz-Methoden unterteilt. Linkage-MethodenBei den Linkage-Methoden wird in jedem Schritt nach einer bestimmten Logik geprüft, welche Cluster den geringsten Abstand zueinander aufweisen. Diese Cluster werden dann zu einem neuen Cluster fusioniert. Je nach Linkage-Methode wird diese Distanz zwischen den Clustern unterschiedlich bestimmt (Universität Zürich, 2018):
Ward-MethodeNeben den Linkage-Methoden exisiteren noch weitere Methoden. Die Ward-Methode ist eine beliebte Varianz-basierte-Methode. Dabei werden die Cluster, die den kleinsten Zuwachs der totalen Varianz aufweisen, fusioniert. Die Methode ist daher eine Erweiterung der empirischen Varianz einer Variablen auf den multivariaten Fall. Formel der empirischen Varianz: $$s^2 = \frac{1}{n} \sum_{i=1}^{n}(x_i - \bar{x})^2$$ Formel der totalen Varianz (Streuung eines multivariaten Datensatzes mit $p$ Variablen $X_j$): $T = \frac{1}{n}\sum_{j=1}^{p}\sum_{i=1}^{n}(x_{ij}-\bar{x_j})^2$ In den Formeln wird ersichtlich, dass $(x_i-\bar{x})^2$ mit der bereits bekannten quadrierten euklidischen Distanz $d^2(x_i,\bar{x})$ übereinstimmt. Es wird also für jedes Cluster die Summe der quadrierten Distanzen der Einzelfälle vom jeweiligen Cluster-Mittelwert berechnet. Diese Werte werden dann über alle Variablen $p$ aufsummiert. Im nächsten Schritt werden jeweils jene zwei Cluster fusioniert, deren Zusammenfügen die geringste Erhöhung der Gesamtsumme der quadrierten Distanzen zur Folge hat. In dieser Abbildung sind die Ergebnisse der verschiedenen Clustering-Algorithmen für unterschiedliche Datensätze exemplarisch dargestellt (Quelle: scikit-learn): Bei den agglomerativen Verfahren führt das single linkage Verfahren in einigen Fällen zu einer sehr einseitigen Verteilung der Cluster. Die Ward Methode führt dagegen in den meisten Fällen zu einer relativ ausgeglichenen Aufteilung. Im folgenden Beispiel wird daher die Ward-Methode genutzt. Clusteranalyse in PythonFür die Durchführung der hierarchischen Clusteranalyse mit der Ward-Methode nutzen wir die Daten des World Happiness Reports aus dem Jahr 2020. Der World Happiness Report ist ein jährlich vom Sustainable Development Solutions Network der Vereinten Nationen veröffentlichter Bericht. Der Bericht enthält Ranglisten zur Lebenszufriedenheit in verschiedenen Ländern der Welt und Datenanalysen aus verschiedenen Perspektiven (siehe Helliwell et al., 2020). Import der Daten:
In dieser Analyse nutzen wir die landesspezifischen Informationen zu der Lebenserwartung in Jahren ( 0) und das logarithmierte Bruttoinlandsprodukt pro Einwohner ( 1):
Damit die Vorgehensweise des hierarchischen Clustering-Algorithmus besser nachvollzogen werden kann, ziehen wir zufällig 20 Länder aus dem Datensatz. Um eine Reproduzierbarkeit der Ergebnisse sicherzustellen (d.h., dass immer die gleichen 20 Länder “zufällig” gezogen werden) nutzen wir die Funktion 2 mit einer belieben Zahlenfolge (in unserem Beispiel 12).
Darstellung der Länder in einem Punktediagramm:
DatenvorbereitungVariablenauswahlWir erzeugen einen neuen Datensatz 3, in welchem nur die Variablen enthalten sind, die für die Clusteranalyse genutzt werden sollen. Zusätzlich nutzen wir die Variable 4, um in einem späteren Schritt die Daten sinnvoll beschriften zu können.
Fehlende WerteWir prüfen, ob in den Daten fehlende Werte vorliegen:
In diesem Datensatz liegen keine fehlenden Werte vor. Falls dies in einem anderen Projekt jedoch der Fall sein sollte, könnten wir diese fehlenden Werte mit dem Befehl 5 entfernen, wobei sich 6 auf die Zeilen des dataframes bezieht:
StandardisierungDamit die Werte der Variablen in einem einheitlichen Werteintervall vorliegen, nutzen wir für die Standardisierung der Daten die z-Transformation. Mit Hilfe dieser Standardisierung wird der Mittelwert auf 0 und die Standardabweichung der Variablen auf 1 gesetzt. Die Formel dafür lautet: $$z = \frac{x - \bar{x}}{s}$$
Wir führen die Standardisierung für unsere numerischen Variablen mit Hilfe des 7 durch. Dafür erstellen wir zunächst eine Kopie des Datensatzes und nennen diese 8:
Wie in der Abbildung nachvollzogen werden kann, ändert sich nicht die Position der Länder, sondern lediglich die Einheiten auf der X- und Y-Achse: 0Da wir die Variable 4 nicht mit in die Berechnung einbeziehen möchten, verwenden wir diese als Index: 1
DendrogrammWir beginnen unsere Cluster-Analyse mit der Erstellung eines Dendrogramms, mit dessen Hilfe die Vorgehensweise bei der Erstellung der Cluster dargestellt werden kann. Die Abbbildung ist uns insbesondere bei der Bestimmmung der optimalen Clusteranazahl behilflich, da die Anzahl nicht von dem Cluster-Algorithmus bestimmt wird. Das Dendrogramm liest sich in unserem Beispiel von links nach rechts und beschreibt in diese Richtung den Prozess des Clusterings:
Die “optimale” Anzahl der Cluster sollte insbesondere anhand inhalticher Interpretationen in Hinblick einer größtmöglichen Plausibilität der gebildeten Cluster geschehen. Zusätzlich kann der größte (bzw. ein großer) Zuwachs der Heterogenität in dem Dendrogramm als Entscheidungskriterium genutzt werden. Bei unseren Daten entsteht der größte Heterogenitätszuwachs zwischen einer 2-Cluster und 1-Cluster-Lösung. Der Heterogenitätszuwachs zwischen einer 4-Cluster und 2-Cluster-Lösung ist ebenfalls relativ groß. Wir entscheiden uns hier für eine Clusteranzahl von 4, hätten jedoch auch die 2-Cluster-Lösung wählen können. Wie bereits erwähnt existiert bei diesem Verfahren oftmals keine eindeutige “optimale” Lösung, da jeweils auch die Interpretiertbarkeit der Cluster auf Grundlage inhaltlicher Überlegungen eine wichtige Rolle spielt. 3Im nächsten Schritt wird die hierarchische Clusteranalyse angewendet. Dafür nutzen wir die Funktion 0 mit dem Verfahren 1, der euklidischen Distanz ( 2) als Proximitätsmaß. Die Anzahl der zu erstellenden Cluster setzen wir hier auf 4. Im Anschluss nutzen wir die Funktion 3 4 5Wir übergeben die Ergebnisse in den Datensatz 3 (da wir im Anschluss nicht mit den z-standardisierten Werten arbeiten möchten) 6
In der letzten Abbildung werden die Cluster dargestellt:
8Alternativ besteht auch die Möglichkeit, die Ländernamen gemeinsamen mit den Clustern als Symbole anzeigen zu lassen: |