Hierarchische Clusteranalyse

Die hierarchische Clusteranalyse erstellt eine verschachtelte Abfolge von Clustern, die als Dendrogramm visualisiert wird, indem Gruppen gemäß einem Verknüpfungskriterium sukzessive zusammengeführt oder geteilt werden.

Definition

Die hierarchische Clusteranalyse ist ein Clustering-Ansatz, der einen Baum verschachtelter Partitionen erzeugt, indem die ähnlichsten Cluster iterativ kombiniert oder die am wenigsten kohäsiven geteilt werden, basierend auf einer gewählten Distanz zwischen den Clustern.

Scope

Dieses Thema behandelt agglomeratives (Bottom-up) und divisives (Top-down) hierarchisches Clustering, die gängigen Verknüpfungsregeln wie Single-Linkage, Complete-Linkage, Average-Linkage und Ward-Linkage (Minimum-Varianz-Verknüpfung), die Konstruktion und Interpretation des Dendrogramms sowie das Schneiden des Baumes zur Erzeugung einer flachen Partition.

Core questions

• Wie kann eine verschachtelte Familie von Clusterings aus paarweisen Unähnlichkeiten konstruiert werden?
• Wie beeinflussen verschiedene Verknüpfungsregeln die resultierenden Cluster?
• Wie wird das Dendrogramm gelesen und wo sollte es geschnitten werden?
• Wann ist eine hierarchische Struktur informativer als eine einzelne flache Partition?

Key theories

Verknüpfungsdefinierte Zusammenführung

Agglomeratives Clustering führt wiederholt die beiden Cluster zusammen, die unter einer Verknüpfungsdefinition am nächsten liegen; Single-Linkage, Complete-Linkage, Average-Linkage und Ward-Linkage kodieren unterschiedliche Vorstellungen von Distanz zwischen Clustern und erzeugen charakteristisch unterschiedliche Clusterformen.

Dendrogramm-Darstellung

Die Abfolge der Zusammenführungen wird als Dendrogramm kodiert, dessen Zusammenführungshöhen die Unähnlichkeit aufzeichnen, wodurch eine beliebige Anzahl von Clustern durch Schneiden des Baumes in einer gewählten Höhe erhalten werden kann.

Clinical relevance

Hierarchisches Clustering wird häufig eingesetzt, wenn eine verschachtelte Gruppierung natürlich oder informativ ist, wie z. B. bei der Erstellung von Taxonomien, der Organisation von Genexpressions-Heatmaps und der Untersuchung von Dokumenten- oder Organismenähnlichkeiten.

History

Hierarchische Gruppierungsmethoden wurden in den frühen 1960er Jahren formalisiert, einschließlich des Ward-Kriteriums der Minimum-Varianz, und wurden zu festen Bestandteilen der numerischen Taxonomie und der explorativen Datenanalyse, da die Computer die Dendrogramm-Erstellung routinemäßig ermöglichten.

Debates

Wahl der Verknüpfung

Single-Linkage kann Cluster miteinander verketten, während Complete-Linkage dazu neigt, kompakte Gruppen zu erzeugen, und die Ward-Methode bevorzugt gleich große sphärische Cluster, sodass die Wahl der Verknüpfung die Ergebnisse stark prägt und selten eindeutig korrekt ist.

Key figures

• Joe Ward
• Peter Rousseeuw

Seminal works

• everitt2011
• kaufman1990
• wardjr1963

Frequently asked questions

Was ist der Unterschied zwischen agglomerativem und divisivem Clustering?

Agglomeratives Clustering beginnt mit jedem Objekt als eigenem Cluster und führt nach oben zusammen, während divisives Clustering mit einem Cluster beginnt und nach unten teilt; agglomerative Methoden sind in der Praxis weitaus häufiger.

Wie wähle ich die Anzahl der Cluster aus einem Dendrogramm aus?

Indem der Baum in einer gewählten Höhe geschnitten wird, oft dort, wo die Zusammenführungshöhen stark ansteigen, was der Kombination von Gruppen entspricht, die wesentlich unähnlicher sind als die darunter zusammengeführten.