Einführung in hierarchisches Clustering in Python

Motivation

Stell dir vor, du bist Data Scientist in einem Einzelhandelsunternehmen. Deine Chefin bittet dich, Kundinnen und Kunden anhand ihres Ausgabeverhaltens für zielgerichtetes Marketing und Produktempfehlungen in folgende Gruppen zu segmentieren: Low, Average, Medium oder Platinum.

Da es zu diesen Kundinnen und Kunden keine entsprechenden historischen Labels gibt, wie lässt sich eine sinnvolle Einteilung vornehmen?

Hier kommt Clustering ins Spiel. Es ist eine Methode des unüberwachten Lernens, mit der unbeschriftete Daten in ähnliche Gruppen zusammengefasst werden.

In diesem Tutorial konzentrieren wir uns auf hierarchisches Clustering, eine von vielen Techniken im unüberwachten Lernen. Wir starten mit einem Überblick, was hierarchisches Clustering ist, und vergleichen es anschließend mit anderen Verfahren.

Danach führen wir dich Schritt für Schritt durch die Umsetzung in Python mit der beliebten Scipy-Bibliothek.

Definition von hierarchischem Clustering

Beim hierarchischen Clustering werden sukzessive Cluster gebildet, die auf zuvor definierten Clustern aufbauen. Ziel ist es, die Daten als Baumstruktur von Clustern (Dendrogramm) zu organisieren, die die hierarchischen Beziehungen zwischen den zugrunde liegenden Clustern grafisch darstellt.

Vergleich: Hierarchisches Clustering und andere Verfahren

Hierarchisches Clustering ist ein leistungsfähiger Ansatz, aber nicht der einzige. Jedes Clustering-Verfahren bringt eigene Stärken und Schwächen mit.

Schauen wir uns an, wie es im Vergleich zu K-Means und modellbasiertem Clustering abschneidet. Es gibt viele weitere Methoden, doch diese beiden sind neben hierarchischem Clustering weit verbreitet und helfen, die anderen besser einzuordnen.

Mehr zu Clustering im Machine Learning erfährst du in unserem separaten Artikel mit fünf wichtigen Clustering-Algorithmen.

Hierarchisches Clustering vs. K-Means

Im Unterschied zum hierarchischen Verfahren teilt K-Means die ursprünglichen Datenpunkte in „K“ Gruppen bzw. Cluster ein, wobei „K“ im Vorfeld festgelegt wird.

Die Grundidee: Es werden Cluster gesucht, die die quadrierte euklidische Distanz aller Punkte zu ihren Zentren über alle Merkmale hinweg minimieren. Die Zuordnung erfolgt iterativ.

Unser Tutorial K-means Clustering in Python mit Scikit-learn erklärt dir die inneren Abläufe von K-Means anhand einer spannenden Fallstudie.

Vorteile

• Rechnerisch effizienter als hierarchisches Clustering und dadurch für große Datensätze geeignet.
• K-Means ist einfacher zu verstehen und umzusetzen.

Nachteile

• Weniger flexibel als hierarchisches Clustering, da die Anzahl der Cluster vorab festgelegt werden muss, was oft nicht offensichtlich ist.
• Die Ergebnisse sind instabil und können sich zwischen Läufen auf demselben Datensatz unterscheiden.
• Empfindlicher gegenüber Ausreißern, da diese den Cluster-Mittelwert beeinflussen.
• Sowohl K-Means als auch hierarchisches Clustering können kategoriale Daten nicht direkt verarbeiten und funktionieren bei nicht kontinuierlichen Daten oder sehr hoher Varianz oft schlechter.

Trotz seiner Grenzen ist K-Means wegen der einfachen Nutzung und Effizienz weiterhin sehr beliebt und dient häufig als Referenz zum Vergleich anderer Clustering-Techniken.

Modellbasiertes Clustering

Sowohl K-Means als auch hierarchisches Clustering arbeiten mit Distanzmatrizen, die die Abstände zwischen allen Punkten im Datensatz abbilden. Modellbasiertes Clustering nutzt dagegen statistische Modelle, um Cluster in den Daten zu identifizieren. Der grobe Ablauf:

• Statistisches Modell wählen und die Anzahl der Cluster festlegen.
• Modell auf die Daten fitten.
• Cluster anhand der Modellparameter bestimmen.

Vorteile

• Flexibler als hierarchisches Clustering, da unterschiedliche Modelle für verschiedene Clustertypen einsetzbar sind.
• Besser geeignet für Daten mit komplexen Formen oder Strukturen.

Nachteile

• Rechnerisch aufwendiger als hierarchisches Clustering, besonders bei großen Datenmengen.
• Erfordert ein gutes Verständnis statistischer Modellierung, da die Modellwahl das Ergebnis stark beeinflusst.
• Wie K-Means muss auch hier die Anzahl der Cluster vorab festgelegt werden.

Anwendungsfelder des hierarchischen Clustering

Hierarchisches Clustering findet in vielen Bereichen unseres Alltags Anwendung, unter anderem in Biologie, Bildverarbeitung, Marketing, Volkswirtschaft und der Analyse sozialer Netzwerke.

Biologie

Die Clusterung von DNA-Sequenzen zählt zu den größten Herausforderungen in der Bioinformatik.

Biologinnen und Biologen können hierarchisches Clustering nutzen, um genetische Beziehungen zwischen Organismen zu analysieren und diese in taxonomische Gruppen einzuordnen. Das erleichtert die schnelle Analyse und Visualisierung der zugrunde liegenden Zusammenhänge.

Bildverarbeitung

In der Bildverarbeitung lässt sich hierarchisches Clustering einsetzen, um ähnliche Regionen oder Pixel eines Bildes nach Farbe, Intensität oder anderen Merkmalen zu gruppieren. Das ist nützlich für Aufgaben wie Segmentierung, Klassifikation und Objekterkennung.

Marketing

Marketing-Teams können mit hierarchischem Clustering eine Hierarchie verschiedener Kundentypen nach Kaufverhalten ableiten und so bessere Strategien und Empfehlungen entwickeln. Beispielsweise lassen sich je nach Ausgabenniveau unterschiedliche Produkte empfehlen.

Analyse sozialer Netzwerke

Soziale Netzwerke sind bei richtiger Auswertung eine wertvolle Informationsquelle. Hierarchisches Clustering hilft, Gruppen oder Communities zu erkennen, ihre Beziehungen zu verstehen und die Struktur des Netzwerks als Ganzes zu analysieren.

Der Algorithmus des hierarchischen Clustering

In diesem Abschnitt betrachten wir drei Kernaspekte: die einzelnen Schritte des Algorithmus, die beiden Varianten (agglomerativ und divisiv) sowie die Wahl der passenden Distanzmaße.

Schritte im hierarchischen Clustering

Der Algorithmus basiert auf Distanzen, um Cluster zu erzeugen. Der Prozess umfasst im Wesentlichen:

Bereite die Daten auf, indem du fehlende Werte entfernst und weitere Bereinigungsschritte vornimmst. Dieser Schritt ist bei den meisten Machine-Learning-Aufgaben üblich.

1. Berechne die Distanzmatrix mit den Abständen zwischen allen Datenpunkt-Paaren anhand eines Distanzmaßes wie euklidische Distanz, Manhattan-Distanz oder Kosinus-Ähnlichkeit. Standard ist meist die euklidische Distanz.

2. Fasse die beiden Cluster mit der geringsten Distanz zusammen.

3. Aktualisiere die Distanzmatrix in Bezug auf die neuen Cluster.

4. Wiederhole die Schritte 1, 2 und 3, bis alle Cluster zu einem einzigen Cluster verschmolzen sind.

Beispiele für hierarchisches Clustering

Agglomeratives und divisives Clustering sind gewissermaßen Spiegelbilder. Schauen wir uns an, wie beide arbeiten, mit Beispiel und Visualisierung.

Agglomeratives hierarchisches Clustering

Dieses Szenario entspricht dem oben beschriebenen Ansatz. Zunächst gilt jede Beobachtung als eigener Singleton-Cluster (nur ein Datenpunkt). Anschließend werden Cluster iterativ zusammengeführt, bis ein einziger Cluster entsteht. Man spricht auch vom Bottom-up-Ansatz.

Wie in der folgenden Abbildung gezeigt:

• Wir starten damit, jedes Tier als eigenen Cluster zu betrachten.
• Dann bilden wir anhand von Ähnlichkeiten drei Cluster aus diesen Einzeltieren:
• Vögel: Adler und Pfau
• Säugetiere: Löwe und Bär
• Mehr als drei Beine: Spinne und Skorpion.
• Wir führen die beiden ähnlichsten Cluster zusammen und bilden so die Wirbeltiere: Vögel und Säugetiere.
• Zum Schluss werden die verbleibenden Cluster Wirbeltiere und Mehr als drei Beine zu einem einzigen Cluster Tiere zusammengeführt.

Dendrogramm des agglomerativen Ansatzes

Divisives Clustering

Das divisive Clustering arbeitet Top-down: Es beginnt mit allen Datenpunkten in einem einzigen Cluster und teilt diesen schrittweise, bis nur noch Einzelpunkte übrig sind.

In der Grafik zum divisiven Ansatz:

• Der gesamte Tierdatensatz wird zunächst als ein Block betrachtet.
• Dann teilen wir in zwei Cluster: Wirbeltiere und Mehr als 3 Beine.
• Die Teilung wird iterativ auf die neu entstandenen Cluster angewandt, bis einzelne Tiere entstehen.

Dendrogramm des divisiven Ansatzes

Die richtige Distanz wählen

Die Wahl des Distanzmaßes ist entscheidend und hängt von deiner Problemstellung ab. Beispiel: Wir könnten Studierende anhand folgender Merkmale clustern:

• Herkunftsland
• Geschlecht
• Vorheriger akademischer Hintergrund

All diese Cluster sind valide, unterscheiden sich aber in ihrer Bedeutung.

Obwohl die euklidische Distanz am weitesten verbreitet ist, gibt es weitere Maße wie Manhattan- oder Canberra-Distanz, Pearson- oder Spearman-Korrelation und die Minkowski-Distanz.

Wie man Cluster vor dem Mergen misst

Die genannten Distanzen beziehen sich auf einzelne Items. Hier betrachten wir drei gängige Methoden, um die „nächsten“ Cluster vor dem Zusammenführen zu bestimmen: (1) Single Linkage, (2) Complete Linkage und (3) Average Linkage.

Single Linkage

Aus allen paarweisen Distanzen zwischen Items in den Clustern C1 und C2 ist die Clusterdistanz das Minimum.

Distance (C1, C2) = Min { d(i, j), wobei Item i in C1 und Item j in C2 liegt }

Unter allen Item-Paaren aus beiden Clustern haben die grün markierten den geringsten Abstand.

Single-Linkage-Illustration

Complete Linkage

Aus allen paarweisen Distanzen zwischen Items in C1 und C2 ist die Clusterdistanz hier das Maximum.

Distance (C1, C2) = Max { d(i, j), wobei Item i in C1 und Item j in C2 liegt }

Unter allen Item-Paaren aus beiden Clustern haben die grün markierten den größten Abstand.

Complete-Linkage-Illustration

Average Linkage

Bei Average Linkage entspricht die Distanz zwischen zwei Clustern C1 und C2 dem Durchschnitt aller paarweisen Distanzen zwischen den Items beider Cluster.

Distance (C1, C2) = Sum{ d(i, j) } / Anzahl der Distanzen

Average-Linkage-Illustration

Dann ergibt sich die Average-Linkage-Distanz wie folgt:

d(a,j) + d(a,h) + d(a,n) + d(d,j) + d(d,h) + d(d,n)

—-----------------------------------------------------------, wobei die Anzahl der Distanzen = 6

Anzahl der Distanzen

Hierarchisches Clustering in Python umsetzen

Jetzt kennst du die Grundlagen. In diesem Abschnitt geht es um die technische Umsetzung in Python.

Wenn du die Implementierung lieber in R nachvollziehen möchtest, starte mit unserem Hierarchical clustering in R Tutorial.

Umgebung einrichten

Du brauchst eine installierte Python-Version sowie die folgenden Bibliotheken:

• Pandas zum Laden von DataFrames.
• Scikit-learn für die Normalisierung.
• Seaborn und matplotlib für Visualisierungen.
• Scipy für das Clustering.

Du kannst sie mit dem Paketmanager pip wie folgt installieren:

pip install scikit-learn
pip install pandas

pip install matplotlib seaborn

pip install scipy

Als Nächstes importieren wir die benötigten Module und laden den Datensatz. Wir verwenden das integrierte Iris-Dataset aus scikit-learn, das Informationen zu verschiedenen Iris-Arten enthält.

Um den Anwendungsfall greifbarer zu machen, nutzen wir die Loan Data aus DataLab. Den gesamten Code findest du in diesem DataLab-Workbook. Du kannst es im Browser kopieren und ausführen, ohne Software lokal installieren zu müssen.

Die Daten verstehen

Der Datensatz enthält 9.500 Kredite mit Informationen zur Kreditstruktur, zu Kreditnehmenden und dazu, ob der Kredit vollständig zurückgezahlt wurde. Um den unüberwachten Charakter zu wahren, entfernen wir die Zielspalte not.fully.paid.

import pandas as pd
loan_data = pd.read_csv("loan_data.csv")
loan_data.head()

Die ersten fünf Zeilen der Daten

Die folgende Ausgabe zeigt: Die Daten haben 9.578 Zeilen und 14 Spalten numerischer Typen, außer purpose (Objekt), das den Zweck als Text beschreibt.

loan_data.info()

Informationen zum Datensatz

Daten vorverarbeiten

Vor dem Clustering müssen die Daten bereinigt werden: fehlende Werte prüfen, Spaltenwerte normalisieren und irrelevante Spalten entfernen.

Mit fehlenden Werten umgehen

Wie die folgende Ausgabe zeigt, gibt es keine fehlenden Werte.

percent_missing =round(100*(loan_data.isnull().sum())/len(loan_data),2)
percent_missing

Prozentsatz fehlender Werte

Unerwünschte Spalten entfernen

Wir analysieren alle Spalten mit Ausnahme von:

• purpose
• not.fully.paid, da dies das Label ist, ob vollständig zurückgezahlt wurde.

cleaned_data entspricht den Daten ohne diese Spalten.

cleaned_data = loan_data.drop(['purpose', 'not.fully.paid'], axis=1)
cleaned_data.info()

Das folgende Bild zeigt die Informationen zu den bereinigten Daten.

Neue Daten ohne die entfernten Spalten

Ausreißer analysieren

Eine Schwäche des hierarchischen Clustering ist die Empfindlichkeit gegenüber Ausreißern. Die Verteilung jeder Variablen zeigt der Boxplot.

def show_boxplot(df):
plt.rcParams['figure.figsize'] = [14,6]
sns.boxplot(data = df, orient="v")
plt.title("Outliers Distribution", fontsize = 16)
plt.ylabel("Range", fontweight = 'bold')
plt.xlabel("Attributes", fontweight = 'bold')
   
show_boxplot(cleaned_data)

Boxplot aller Variablen

Der revolvierende Saldo der Kreditnehmenden (revol_bal) ist die einzige Variable mit deutlich entfernten Punkten.

Mit dem Interquartilsabstand (IQR) können wir Punkte entfernen, die außerhalb des Bereichs Quartile ± 1,5 × IQR liegen.

Das leistet die folgende Hilfsfunktion.

def remove_outliers(data):
   
df = data.copy()
   
for col in list(df.columns):
 
      Q1 = df[str(col)].quantile(0.05)
      Q3 = df[str(col)].quantile(0.95)
      IQR = Q3 - Q1
      lower_bound = Q1 - 1.5*IQR
      upper_bound = Q3 + 1.5*IQR
 
      df = df[(df[str(col)] >= lower_bound) & 

        (df[str(col)] <= upper_bound)]
   
return df

Anschließend wenden wir die Funktion auf den Datensatz an.

without_outliers = remove_outliers(cleaned_data)

Jetzt prüfen wir den neuen Boxplot und vergleichen ihn mit dem vor der Ausreißerentfernung.

show_boxplot(without_outliers)

Es liegen keine Punkte mehr außerhalb des Interquartilsbereichs.

without_outliers.shape

Die Daten haben nun 9.319 Zeilen und 12 Spalten. Das heißt, 259 Beobachtungen wurden als Ausreißer entfernt.

Daten skalieren

Da hierarchisches Clustering häufig die euklidische Distanz nutzt, die empfindlich auf unterschiedlich skalierte Variablen reagiert, sollten alle Variablen vor der Distanzberechnung skaliert werden.

Das erledigen wir mit StandardScaler aus sklearn.

from sklearn.preprocessing import StandardScaler

data_scaler = StandardScaler()

scaled_data = data_scaler.fit_transform(without_outliers)
scaled_data.shape

Die Form bleibt gleich (9.319 Zeilen, 12 Spalten), denn die Normalisierung ändert die Dimensionen nicht.

Den Algorithmus anwenden

Alle Voraussetzungen sind erfüllt, um die Implementierung zu starten.

Über den Parameter method der Funktion linkage() wählen wir die Linkage-Variante. In diesem Abschnitt betrachten wir alle drei Techniken mit euklidischer Distanz.

Nach dem Import der benötigten Bibliotheken setzen wir Folgendes um:

from scipy.cluster.hierarchy import linkage, dendrogram

complete_clustering = linkage(scaled_data, method="complete", metric="euclidean")
average_clustering = linkage(scaled_data, method="average", metric="euclidean")
single_clustering = linkage(scaled_data, method="single", metric="euclidean")

Nach der Berechnung der drei Clusterings visualisieren wir die entsprechenden Dendrogramme, beginnend mit Complete Linkage.

dendrogram(complete_clustering)
plt.show()

Dendrogramm: Complete Linkage

dendrogram(average_clustering)
plt.show()

Dendrogramm: Average Linkage

dendrogram(single_clustering)
plt.show()

Dendrogramm: Single Linkage

Ergebnisse interpretieren (Dendrogramm visualisieren, Clusteranzahl bestimmen)

Für jede Linkage-Variante zeigt das Dendrogramm, wie die Zusammenführung erfolgt, bis alle Punkte in einem Cluster enden.

• Die x-Achse stellt die Stichproben dar.
• Die y-Achse zeigt die Distanzen. Je höher die Linie, desto unähnlicher sind die Cluster.
• Die passende Clusterzahl erhältst du, indem du eine horizontale Linie durch die höchste vertikale Linie ohne Schnitt mit anderen Clustern ziehst. Die Anzahl der Schnittpunkte entspricht der Clusteranzahl.

Die optimale Zahl an Clustern findet sich über die höchste vertikale Linie, die keine anderen Cluster (horizontale Linien) schneidet. In den Abbildungen ist sie rot markiert.

• Bei Complete Linkage ist es die blaue Linie rechts und es ergeben sich drei Cluster.

Optimale Clusterzahl ohne Schnittpunkte (Complete Linkage)

• Bei Average Linkage ist es die erste blaue Vertikallinie und es ergeben sich zwei Cluster.

Optimale Clusterzahl ohne Schnittpunkte (Average Linkage)

• Bei Single Linkage ist es die erste Vertikallinie, was nur einen Cluster nahelegt.

Optimale Clusterzahl ohne Schnittpunkte (Single Linkage)

Aus diesen Beobachtungen liefert Average Linkage die stimmigsten Cluster, während Single und Complete Linkage jeweils einen bzw. drei Cluster nahelegen. Zudem passt die optimale Anzahl von zwei Clustern zu unserem Vorwissen über den Datensatz: zwei Typen von Kreditnehmenden.

Nachdem wir die optimale Clusterzahl bestimmt haben, schauen wir uns die Bedeutung der Cluster anhand des Kreditscores an.

cluster_labels = cut_tree(average_clustering, n_clusters=2).reshape(-1, )
without_outliers["Cluster"] = cluster_labels

sns.boxplot(x='Cluster', y='fico', data=without_outliers)

Aus dem Boxplot lässt sich ablesen:

• Kreditnehmende in Cluster 0 haben die höheren Kreditscores.
• Kreditnehmende in Cluster 1 haben niedrigere Scores.

Cluster Analysis in Python ist ein guter nächster Schritt, um mit Scipy tiefer in K-Means und hierarchisches Clustering einzusteigen.

Fazit

In diesem Beitrag hast du gelernt, was hierarchisches Clustering ist, welche Stärken und Schwächen es hat und wie es sich gegenüber K-Means und modellbasiertem Clustering einordnet.

Wir hoffen, du hast jetzt das nötige Rüstzeug, um unbeschriftete Daten effektiv zu clustern und daraus tragfähige Entscheidungen abzuleiten.