Hierarchisches Clustering

Hierarchisches Clustering ist ein unüberwachter Machine-Learning-Algorithmus, der Datenpunkte in einem Baum verschachtelter Cluster gruppiert — ohne dass die Anzahl der Cluster vorab angegeben werden muss. Diese Seite erklärt, wie der Algorithmus funktioniert, den Unterschied zwischen agglomerativen und divisiven Ansätzen, wie eine Linkage-Methode gewählt wird und wie hierarchisches Clustering in Python mit scikit-learn und SciPy implementiert und visualisiert wird.

Was ist hierarchisches Clustering?

Hierarchisches Clustering baut eine Hierarchie von Clustern auf, indem Gruppen von Datenpunkten iterativ auf Basis eines Abstands- (oder Ähnlichkeits-)maßes zusammengeführt oder aufgeteilt werden. Das Ergebnis wird als Dendrogramm dargestellt — ein baumartiges Diagramm, bei dem die y-Achse den Abstand zeigt, bei dem Cluster zusammengeführt werden, und die Blätter einzelne Datenpunkte repräsentieren.

Im Gegensatz zu K-Means erfordert hierarchisches Clustering nicht, dass die Anzahl der Cluster vor dem Ausführen des Algorithmus festgelegt wird. Der Algorithmus wird einmal ausgeführt, und anschließend wird das Dendrogramm an einem gewählten Abstandsschwellenwert „geschnitten", um eine beliebige Anzahl von Clustern zu erzeugen.

Wann hierarchisches Clustering einsetzen

Verwenden Sie hierarchisches Clustering, wenn:

• Sie die Anzahl der Cluster nicht im Voraus kennen und mehrere Optionen aus einem einzigen Durchlauf erkunden möchten.
• Ihr Datensatz klein bis mittelgroß ist (Tausende von Zeilen, nicht Millionen) — der O(n²)-Speicherbedarf des Algorithmus macht ihn für sehr große Datensätze unpraktisch.
• Sie interpretierbare Cluster-Beziehungen benötigen (das Dendrogramm zeigt die Zusammenführungshistorie klar).
• Ihre Cluster möglicherweise nicht kugelförmig sind — hierarchische Methoden mit Complete- oder Average-Linkage verarbeiten nicht-globuläre Formen besser als K-Means.

Agglomeratives vs. divisives Clustering

Es gibt zwei Hauptstrategien:

Diese Seite konzentriert sich auf agglomeratives Clustering, was die meisten Praktiker meinen, wenn sie „hierarchisches Clustering" sagen.

Wie der Algorithmus funktioniert

Agglomeratives Clustering folgt diesen Schritten:

1. Jeden der n Datenpunkte als eigenen Cluster behandeln (insgesamt n Cluster).
2. Die Abstandsmatrix berechnen — die paarweisen Abstände zwischen allen Clustern.
3. Die zwei Cluster mit dem kleinsten Abstand zu einem neuen Cluster zusammenführen.
4. Die Abstandsmatrix aktualisieren, um den neuen Cluster widerzuspiegeln.
5. Schritte 3–4 wiederholen, bis nur noch ein Cluster übrig bleibt.

Das endgültige Ergebnis ist ein Dendrogramm, das alle n-1 Zusammenführungsschritte kodiert.

Linkage-Methoden

Die Linkage-Methode steuert, wie der Abstand zwischen zwei Clustern bei jedem Zusammenführungsschritt berechnet wird. Die Wahl beeinflusst erheblich die Form und Qualität der Cluster.

Ward-Linkage ist der am häufigsten verwendete Ausgangspunkt. Wenn Ihre Cluster langgestreckt oder nicht konvex sind, versuchen Sie Average- oder Single-Linkage.

Feature-Skalierung vor dem Clustering

Da hierarchisches Clustering auf Abstandsberechnungen basiert, dominieren Merkmale mit großen numerischen Bereichen die Abstandsmatrix und verzerren die Ergebnisse. Skalieren Sie Ihre Features immer zuerst.

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

StandardScaler zentriert jedes Merkmal auf Mittelwert 0 und Einheitsvarianz. Siehe das Scale-Kapitel für Alternativen wie MinMaxScaler und RobustScaler.

Hierarchisches Clustering mit scikit-learn implementieren

Die Klasse AgglomerativeClustering in scikit-learn passt das Modell an und weist Cluster-Labels in einem Schritt zu. Sie erzeugt kein Dendrogramm — verwenden Sie SciPy (im nächsten Abschnitt gezeigt) dafür.

Schritt 1 — Daten generieren und skalieren

from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler

# 150 points in 3 natural clusters
X, y_true = make_blobs(n_samples=150, centers=3, cluster_std=0.6, random_state=42)

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

make_blobs erstellt einen reproduzierbaren synthetischen Datensatz, sodass dieses Beispiel ohne CSV-Datei ausgeführt werden kann.

Schritt 2 — Agglomeratives Clustering anpassen

from sklearn.cluster import AgglomerativeClustering

hc = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels = hc.fit_predict(X_scaled)

print(labels[:10])
# e.g. [2 2 0 1 0 1 2 2 0 1]

fit_predict passt das Modell an und gibt in einem einzigen Aufruf das Cluster-Label (0, 1 oder 2) für jeden Datenpunkt zurück.

Schritt 3 — Cluster visualisieren

import matplotlib.pyplot as plt

colors = ['red', 'blue', 'green']
for cluster_id in range(3):
    mask = labels == cluster_id
    plt.scatter(X_scaled[mask, 0], X_scaled[mask, 1],
                s=60, label=f'Cluster {cluster_id + 1}')

plt.title('Agglomerative Clustering (Ward linkage, k=3)')
plt.xlabel('Feature 1 (scaled)')
plt.ylabel('Feature 2 (scaled)')
plt.legend()
plt.tight_layout()
plt.show()

Dendrogramme mit SciPy

Das Dendrogramm ist die markanteste Ausgabe des hierarchischen Clusterings. Es ermöglicht Ihnen, die Anzahl der Cluster visuell zu wählen, indem der Baum bei verschiedenen Höhen geschnitten wird. Das Modul scipy.cluster.hierarchy von SciPy bietet sowohl linkage (zum Aufbau des Baums) als auch dendrogram (zum Plotten).

Dendrogramm erstellen und plotten

from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt

# Use a smaller dataset so the dendrogram is readable
X, _ = make_blobs(n_samples=30, centers=3, cluster_std=0.6, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Build the linkage matrix
Z = linkage(X_scaled, method='ward')

# Plot
plt.figure(figsize=(12, 5))
dendrogram(Z, leaf_rotation=90, leaf_font_size=8)
plt.title('Dendrogram (Ward linkage)')
plt.xlabel('Sample index')
plt.ylabel('Merge distance')
plt.tight_layout()
plt.show()

Das Dendrogramm lesen

• Blätter (unten) repräsentieren einzelne Datenpunkte.
• Horizontale Linien repräsentieren Zusammenführungen. Die Höhe einer Linie entspricht dem Abstand zwischen den zwei zusammengeführten Clustern.
• Den Baum schneiden bei einer bestimmten Höhe ergibt die Anzahl der Cluster unterhalb dieses Schnitts.

Um k zu wählen, suchen Sie nach der längsten vertikalen Linie, die nicht von einer horizontalen Linie gekreuzt wird — diese Lücke deutet auf die natürlichste Anzahl von Clustern hin.

Das Dendrogramm schneiden, um Labels zuzuweisen

Nachdem die Linkage-Matrix Z erstellt wurde, verwenden Sie fcluster, um den Baum bei einer gewünschten Anzahl von Clustern zu schneiden:

from scipy.cluster.hierarchy import linkage, fcluster
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import numpy as np

X, _ = make_blobs(n_samples=150, centers=3, cluster_std=0.6, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

Z = linkage(X_scaled, method='ward')

# Cut the tree to get exactly 3 clusters
labels = fcluster(Z, t=3, criterion='maxclust')

print('Unique cluster IDs:', np.unique(labels))   # [1 2 3]  (1-indexed)
print('Sizes:', np.bincount(labels[labels > 0]))   # [50 50 50]

Beachten Sie, dass fcluster-Labels 1-indiziert sind (beginnen bei 1), im Gegensatz zu den 0-indizierten Labels von scikit-learn.

Linkage-Methoden vergleichen

Die Linkage-Methode verändert die Cluster-Formen und -Größen erheblich. Hier ist, wie alle vier Methoden auf demselben Datensatz verglichen werden können:

from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt
import numpy as np

X, _ = make_blobs(n_samples=150, centers=3, cluster_std=0.6, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

methods = ['ward', 'complete', 'average', 'single']
fig, axes = plt.subplots(1, 4, figsize=(16, 4))

for ax, method in zip(axes, methods):
    hc = AgglomerativeClustering(n_clusters=3, linkage=method)
    labels = hc.fit_predict(X_scaled)
    ax.scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels, cmap='Set1', s=30)
    ax.set_title(f'{method.capitalize()} linkage')
    ax.set_xticks([])
    ax.set_yticks([])

plt.suptitle('Linkage method comparison (k=3)', y=1.02)
plt.tight_layout()
plt.show()

Hierarchisches Clustering vs. K-Means

Verwenden Sie hierarchisches Clustering für explorative Analysen kleinerer Datensätze; wechseln Sie zu K-Means (oder DBSCAN), wenn Sie Millionen von Zeilen haben oder die Anzahl der Cluster bereits kennen.

Häufige Fehler

Features nicht skalieren. Ohne Feature-Skalierung dominiert ein Merkmal, das in Tausenden gemessen wird (z. B. Einkommen), eines, das in einstelligen Zahlen gemessen wird (z. B. Altersfreigabe), und erzeugt irreführende Cluster.

Ward-Linkage mit nicht-euklidischen Abständen verwenden. Ward-Linkage ist nur mit euklidischem Abstand gültig. Für andere Abstandsmetriken (z. B. Kosinus, Manhattan) verwenden Sie Complete- oder Average-Linkage und übergeben Sie metric= explizit.

Dendrogramme bei sehr großen Datensätzen interpretieren. Ein Dendrogramm mit 10.000 Blättern ist unleserlich. Verwenden Sie p= und truncate_mode='lastp' in SciPys dendrogram(), um nur die letzten p Zusammenführungen anzuzeigen.

Cluster-IDs als stabil behandeln. Cluster-IDs (0, 1, 2) sind willkürliche Labels. Wenn zwei Durchläufe verglichen werden, Cluster nach Inhalt abgleichen, nicht nach Nummer.

Fazit

Hierarchisches Clustering ist ein flexibler, interpretierbarer Algorithmus, der nicht erfordert, dass k vorab gewählt wird. Das vollständige Dendrogramm wird einmal erstellt und kann dann auf jeder Ebene geschnitten werden. Ward-Linkage mit StandardScaler-Vorverarbeitung ist die sicherste Standardwahl. Für sehr große Datensätze bevorzugen Sie K-Means aus Leistungsgründen.

Verwandte Kapitel:

• Scale — warum und wie Features vor dem Clustering standardisiert werden
• K-Means — die flache Clustering-Alternative für große Datensätze
• SciPy Tutorial — mehr zur wissenschaftlichen Bibliothek SciPy
• Scatter Plot — mehrdimensionale Daten mit Matplotlib visualisieren