Hierarchisches clustering¶

In diesem Tutorial werden die Grundlagen der Clusteranalyse beschrieben und die hierarchische Clusteranalyse mit der Ward-Methode in Python umgesetzt.

Die 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):

Voraussetzungen¶

Wichtige Voraussetzungen, die bei der Durchführung der Analyse beachtet werden sollten (Universität Zürich, 2018):

Die Analyse kann für unterschiedliche Datentypen (kategoriale und metrische Daten) genutzt werden.
Fehlende Werte und Ausreißerwerte sollten vorab beseitigt werden.
Weisen die verwendeten Variablen große Unterschiede bezüglich ihres Wertebereichs auf (bspw. wenn eine Variable in cm und die andere in km gemessen wurde), so sollten diese auf ein einheitliches Niveau transformiert werden. Üblicherweise wird dafür die z-Transformation genutzt.

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:

Bei kategorialen (nominalen und ordinalen) Variablen werden Ähnlichkeitsmaße benutzt.
Bei metrischen Variablen werden Distanzmaße genutzt.

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 Distanz¶

Mit 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:

\(x_A\) = 70
\(x_B\) = 330
\(y_A\) = 40
\(y_B\) = 228

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 Distanz¶

Anstelle 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\)-Distanz¶

Die \(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-Algorithmus¶

Ist 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):

Clustering-Algortihmen

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-Methoden¶

Bei 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):

Nächstgelegener Nachbar (engl. “single linkage”): Das Minimum aller möglichen Distanzen zwischen den Datenpunkten in Cluster 1 und jenen in Cluster 2 wird betrachtet (Sigbert, 2011):

Entferntester Nachbar (engl. “complete linkage”): Das Maximum aller möglichen Distanzen zwischen den Datenpunkten in Cluster 1 und jenen in Cluster 2 wird betrachtet (Sigbert, 2011):

Linkage zwischen Gruppen (engl. “average linkage”): Der Mittelwert aller möglichen Distanzen zwischen den Datenpunkten in Cluster 1 und jenen in Cluster 2 wird betrachtet (Sigbert, 2011):

Other Linkage: Dies umfasst verschiedene Methoden. Beispielsweise wird die Distanz zwischen dem Median (Median-Clustering) von Cluster 1 und dem Median von Cluster 2 betrachtet (Sigbert, 2011):

Ward-Methode¶

Neben 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.