Hierarchisches Clustering

Was ist hierarchisches Clustering?

Hierarchisches Clustering baut ein Dendrogramm durch iteratives Zusammenführen der zwei nächsten Cluster. Im Gegensatz zu K-Means muss K nicht vorab festgelegt werden.

Verknüpfungsmethoden: Single (Minimum-Distanz, Kettenbildung), Complete (Maximum, kompakt), Average (Mittelwert), Ward (Varianzminimierung, meist ausgeglichenste Ergebnisse).

Die Zusammenführungstabelle protokolliert Distanzen je Schritt. Große Sprünge deuten auf natürliche Clustergrenzen hin.

Formula: Single Linkage: d(A,B) = min{d(a,b) : a∈A, b∈B} Complete Linkage: d(A,B) = max{d(a,b) : a∈A, b∈B} Average Linkage: d(A,B) = (1/|A||B|) ΣΣ d(a,b) Ward: ΔV = (nₐnᵦ)/(nₐ+nᵦ) ‖μₐ − μᵦ‖²

Berechnungsbeispiel

Punkte: A(0,0), B(1,0), C(4,0), D(5,0). Single: Schritt 1 A+B (Dist=1), Schritt 2 C+D (1), Schritt 3 {A,B}+{C,D} (3). Schnitt bei Distanz 2 → 2 Cluster.

Wann diesen Rechner verwenden

• Ein Forscher, der natürliche Gruppierungen in Daten erkundet, ohne sich auf eine feste Clusteranzahl festzulegen — das Dendrogramm offenbart die Struktur auf allen Granularitätsebenen
• Ein Bioinformatiker, der Genexpressionsprofile oder Proteinsequenzen anhand von Ähnlichkeitsmaßen clustert
• Ein Marktforscher, der Produkte oder Kunden in eine Taxonomie mit verschachtelten Unterkategorien einordnet
• Ein Datenanalyst, der vergleichen muss, wie sich verschiedene Linkage-Methoden auf Clusterzusammensetzung und -struktur auswirken

Häufige Fehler vermeiden

• Single Linkage auf verrauschte Daten anwenden — Single Linkage neigt zum 'Verkettungseffekt', bei dem Rauschpunkte unterschiedliche Cluster überbrücken und vorzeitig verschmelzen; verwenden Sie Ward oder Complete für die meisten Anwendungen
• Merkmale nicht standardisieren — hierarchisches Clustering verwendet skalensensitive Distanzmaße; Variablen mit großen Wertebereichen dominieren, sofern nicht alle Merkmale standardisiert sind
• Die Clusteranzahl wählen, ohne das Muster der Verschmelzungsdistanzen zu betrachten — willkürliche Schnitte erzeugen bedeutungslose Cluster; untersuchen Sie stets das Dendrogramm oder die Historie der Verschmelzungsdistanzen auf natürliche Bruchpunkte
• Hierarchisches Clustering ohne Teilstichprobenbildung auf sehr große Datensätze anwenden — die Speicherkomplexität O(n2) und Zeitkomplexität O(n3) machen es für Datensätze über ~10.000 Punkten unpraktikabel; verwenden Sie K-Means oder Mini-Batch-Ansätze für große Daten

Ergebnisse interpretieren

• Große Sprünge in den Verschmelzungsdistanzen in der Verschmelzungshistorie zeigen natürliche Clustergrenzen an — die Cluster unmittelbar vor einem großen Sprung sind aussagekräftige Gruppierungen
• Liefern die Ward-Methode und Complete Linkage ähnliche Cluster, ist die Gruppierung robust; weichen sie deutlich voneinander ab, ist die Clusterstruktur möglicherweise mehrdeutig
• Cluster mit sehr unterschiedlichen Größen (z. B. ein Cluster mit 90 % der Punkte) können darauf hindeuten, dass die Daten auf dieser Schnittebene keine starken natürlichen Gruppierungen aufweisen — versuchen Sie eine andere Clusteranzahl

Verwandte Normen und Referenzen

• Ward, J. H. (1963), 'Hierarchical Grouping to Optimize an Objective Function', Journal of the American Statistical Association — Ursprung der Ward-Linkage mit minimaler Varianz
• Lance & Williams (1967), 'A General Theory of Classificatory Sorting Strategies', The Computer Journal — einheitliche Rekursionsformel, die Single-, Complete- und Average-Linkage abdeckt
• Everitt, Landau, Leese & Stahl, Cluster Analysis (Wiley) — Standardlehrbuch zu agglomerativen Verfahren und Dendrogramm-Interpretation

Häufig gestellte Fragen

Welche Verknüpfungsmethode verwenden?

Ward ist der beliebteste Standard — kompakte, gleichmäßige Cluster. Single-Linkage wegen Ketteneffekt vermeiden.

Wo das Dendrogramm schneiden?

Größte Lücke in Zusammenführungsdistanzen suchen, Fachwissen nutzen oder Inkonsistenzkoeffizienten anwenden.