Hierarchisches Clustering, auch als hierarchische Clusteranalyse (HCA) bekannt, ist eine Methode der Clusteranalyse im Data Mining und in der Statistik, die darauf abzielt, eine Hierarchie von Clustern zu erstellen. Im Gegensatz zu partitionierenden Verfahren wie k-means, bei denen die Anzahl der Cluster im Voraus festgelegt werden muss, erzeugt das hierarchische Clustering eine verschachtelte Struktur, die auf jeder Ebene geschnitten werden kann, um unterschiedliche Anzahlen von Clustern zu erhalten. Die Ergebnisse werden typischerweise in einem Dendrogramm dargestellt, einem baumartigen Diagramm, das die Abfolge von Verschmelzungen oder Teilungen veranschaulicht. Dieser Ansatz wird häufig in Bereichen wie Biologie, Sozialwissenschaften und maschinellem Lernen für die explorative Datenanalyse eingesetzt.
Der Hauptvorteil des hierarchischen Clusterings ist seine Flexibilität: Jedes gültige Distanzmaß kann verwendet werden, und die Beobachtungen selbst sind nicht erforderlich, sondern nur eine Distanzmatrix. Mit Ausnahme des Sonderfalls der Single-Linkage-Distanz kann jedoch keiner der Algorithmen garantieren, die optimale Lösung ohne erschöpfende Suche zu finden, die eine Zeitkomplexität von O(2^n) aufweist.
Agglomerative und divisive Strategien
Die Strategien des hierarchischen Clusterings fallen im Allgemeinen in zwei Kategorien: agglomerativ und divisiv. Agglomeratives Clustering, oft als "Bottom-up"-Ansatz bezeichnet, beginnt mit jedem Datenpunkt als individuellem Cluster. In jedem Schritt verschmilzt der Algorithmus die beiden ähnlichsten Cluster basierend auf einer gewählten Distanzmetrik (z. B. euklidische Distanz) und einem Linkage-Kriterium (z. B. Single-Linkage, Complete-Linkage). Dieser Prozess wird fortgesetzt, bis alle Datenpunkte zu einem einzigen Cluster zusammengefasst sind oder ein Abbruchkriterium erfüllt ist. Agglomerative Methoden werden aufgrund ihrer Einfachheit und rechnerischen Effizienz für kleine bis mittelgroße Datensätze häufiger verwendet.
Divisives Clustering, bekannt als "Top-down"-Ansatz, beginnt mit allen Datenpunkten in einem einzigen Cluster und teilt das Cluster rekursiv in kleinere auf. In jedem Schritt wählt der Algorithmus ein Cluster aus und teilt es in zwei oder mehr Teilmengen, oft unter Verwendung eines Kriteriums wie der Maximierung der Distanz zwischen den resultierenden Clustern. Divisive Methoden sind weniger verbreitet, können aber nützlich sein, wenn das Ziel darin besteht, zunächst große, deutlich getrennte Cluster zu identifizieren. Im Allgemeinen werden die Verschmelzungen und Teilungen auf gierige Weise bestimmt, was bedeutet, dass der Algorithmus in jedem Schritt lokal optimale Entscheidungen trifft, ohne die globale Struktur zu berücksichtigen.
Komplexität und Algorithmen
Der Standardalgorithmus für hierarchisches agglomeratives Clustering (HAC) hat eine Zeitkomplexität von O(n^3) und benötigt Ω(n^2) Speicher, was ihn für selbst mittlere Datensätze zu langsam macht. Für einige Sonderfälle sind jedoch optimale effiziente agglomerative Methoden mit einer Komplexität von O(n^2) bekannt: SLINK für Single-Linkage und CLINK für Complete-Linkage-Clustering. Mit einem Heap kann die Laufzeit des allgemeinen Falls auf O(n^2 log n) anstelle von O(n^3) reduziert werden, allerdings auf Kosten zusätzlicher Speicheranforderungen. In vielen Fällen sind die Speicher-Overheads dieses Ansatzes zu groß, um ihn praktisch nutzbar zu machen. Es existieren Methoden, die Quadtrees verwenden und eine Gesamtlaufzeit von O(n^2) mit O(n) Speicher nachweisen.
Divisives Clustering mit erschöpfender Suche ist O(2^n), aber es ist üblich, schnellere Heuristiken zur Auswahl von Teilungen zu verwenden, wie z. B. k-means. Diese Heuristiken tauschen Optimalität gegen rechnerische Machbarkeit, sodass divisive Methoden auf größere Datensätze angewendet werden können.
Distanzmetriken
Während das Linkage-Kriterium bestimmt, wie die Unähnlichkeit zwischen Mengen von Beobachtungen berechnet wird, bestimmt die zugrunde liegende Distanzmetrik, wie die Unähnlichkeit zwischen einzelnen Beobachtungen gemessen wird. Da das hierarchische Clustering jedes gültige Distanzmaß zulässt, wird die Wahl der Metrik durch die Art der Daten geleitet und kann einen erheblichen Einfluss auf das resultierende Clustering haben.
Die euklidische Distanz ist die am weitesten verbreitete Metrik für kontinuierliche numerische Daten. Sie entspricht der geradlinigen Distanz zwischen zwei Punkten im euklidischen Raum und ist die Standardwahl in den meisten Statistiksoftware. Die Manhattan-Distanz (auch City-Block- oder L1-Distanz genannt) summiert die absoluten Differenzen über die Merkmale. Sie wird oft bevorzugt, wenn Merkmale auf unterschiedlichen Skalen gemessen werden oder wenn die Daten Ausreißer enthalten, da sie weniger empfindlich auf große Abweichungen reagiert als die euklidische Distanz. Die Kosinus-Distanz misst die winklige Unähnlichkeit zwischen zwei Nicht-Null-Vektoren und wird häufig in der Textanalyse und anderen hochdimensionalen Umgebungen verwendet.
Linkage-Kriterien
Das Linkage-Kriterium bestimmt, wie die Distanz zwischen zwei Clustern aus den Distanzen zwischen ihren einzelnen Mitgliedern berechnet wird. Single-Linkage (oder Nearest-Neighbor) verwendet die minimale Distanz zwischen zwei beliebigen Punkten in den beiden Clustern, was tendenziell lange, kettenartige Cluster erzeugt. Complete-Linkage (oder Farthest-Neighbor) verwendet die maximale Distanz, was tendenziell kompakte, kugelförmige Cluster erzeugt. Average-Linkage verwendet die mittlere Distanz zwischen allen Punktpaaren und bietet einen Kompromiss zwischen den beiden. Wards Methode minimiert die gesamte Varianz innerhalb der Cluster, was sie für kontinuierliche Daten beliebt macht. Die Wahl des Linkage-Kriteriums kann die Form und Interpretation des resultierenden Dendrogramms erheblich verändern.
Anwendungen und Einschränkungen
Hierarchisches Clustering wird in vielen Bereichen eingesetzt. In der Biologie wird es zur Konstruktion phylogenetischer Bäume auf der Grundlage genetischer Ähnlichkeit verwendet. Im Marketing hilft es, Kunden in Gruppen mit ähnlichem Verhalten zu segmentieren. In der Bildanalyse kann es Pixel oder Merkmale gruppieren. In der künstlichen Intelligenz wird hierarchisches Clustering häufig als unüberwachte Lerntechnik für die explorative Datenanalyse und als Vorverarbeitungsschritt für andere Algorithmen verwendet.
Trotz seiner Vorteile hat das hierarchische Clustering Einschränkungen. Die gierige Natur der Algorithmen bedeutet, dass eine einmal durchgeführte Verschmelzung oder Teilung nicht rückgängig gemacht werden kann, was zu suboptimalen Ergebnissen führen kann. Die rechnerische Komplexität des Standardalgorithmus beschränkt seine Verwendung auf Datensätze mittlerer Größe, obwohl optimierte Implementierungen für spezifische Linkage-Kriterien existieren. Darüber hinaus kann die Interpretation eines Dendrogramms subjektiv sein, und die Wahl der Distanzmetrik und des Linkage-Kriteriums erfordert Fachwissen.