Hierarchische Clusteranalyse

Als hierarchische Clusteranalyse bezeichnet man eine bestimmte Familie von distanzbasierten Verfahren zur Clusteranalyse (Strukturentdeckung in Datenbeständen). Cluster bestehen hierbei aus Objekten, die zueinander eine geringere Distanz (oder umgekehrt: höhere Ähnlichkeit) aufweisen als zu den Objekten anderer Cluster. Man kann die Verfahren in dieser Familie nach den verwendeten Distanz- bzw. Proximitätsmaßen (zwischen Objekten, aber auch zwischen ganzen Clustern) und nach ihrer Berechnungsvorschrift unterscheiden.

Untergliedert man nach der Berechnungsvorschrift, so unterscheidet man zwei wichtige Typen von Verfahren:

die divisiven Clusterverfahren, in denen zunächst alle Objekte als zu einem Cluster gehörig betrachtet und dann schrittweise die bereits gebildeten Cluster in immer kleinere Cluster aufgeteilt werden, bis jeder Cluster nur noch aus einem Objekt besteht. (Auch bezeichnet als „Top-down-Verfahren“) die agglomerativen Clusterverfahren, in denen zunächst jedes Objekt einen Cluster bildet und dann schrittweise die bereits gebildeten Cluster zu immer größeren zusammengefasst werden, bis alle Objekte zu einem Cluster gehören. (Auch bezeichnet als „Bottom-up-Verfahren“)

Für beide Verfahren gilt, dass einmal gebildete Cluster nicht mehr verändert werden können. Die Struktur wird entweder stets nur verfeinert („divisiv“) oder nur vergröbert („agglomerativ“), so dass eine strikte Cluster-Hierarchie entsteht. An der entstandenen Hierarchie kann man nicht mehr erkennen, wie sie berechnet wurde.

Vorteile und Nachteile

Die Vorteile der hierarchischen Clusteranalyse sind die Flexibilität durch Verwendung komplexer Distanzmaße, dass das Verfahren außer der Distanzfunktion und der Fusionierungsmethode keine eigenen Parameter hat und dass das Ergebnis eine Cluster-Hierarchie ist, die auch Unterstrukturen erlaubt.

Der Nachteil ist der Analyseaufwand des Ergebnisses. Andere Verfahren, wie z. B. der k-Means-Algorithmus, DBSCAN oder der ebenfalls hierarchische OPTICS-Algorithmus, liefern eine einzelne Partitionierung der Daten in Cluster. Eine hierarchische Clusteranalyse liefert zahlreiche solcher Partitionierungen, und der Anwender muss sich entscheiden, wie er partitioniert. Dies kann aber auch ein Vorteil sein, da dem Anwender so eine Zusammenfassung des qualitativen Verhaltens des Clusterings gegeben wird. Diese Erkenntnis ist grundlegend für die topologische Datenanalyse im Allgemeinen, und persistenter Homologie im Speziellen.

Ein weiterer Nachteil der hierarchischen Clusteranalyse ist die Laufzeit-Komplexität. Eine agglomerative Berechnung kommt in der Praxis und Forschung sehr viel häufiger vor, da es in jedem Schritt Möglichkeiten gibt, Cluster zusammenzufassen, was zu einer naiven Gesamtkomplexität von führt. In speziellen Fällen sind jedoch Verfahren mit einer Gesamtkomplexität von bekannt. Divisiv gibt es aber naiv in jedem Schritt Möglichkeiten, den Datensatz zu teilen.

Als weiterer Nachteil der hierarchischen Clusteranalyse gilt, dass sie keine Clustermodelle liefert. So entstehen beispielsweise je nach verwendeten Maßen Ketteneffekte ("single-link effekt") und es werden aus Ausreißern oft winzige Cluster erzeugt, die nur aus wenigen Elementen bestehen. Die gefundenen Cluster müssen daher meist nachträglich analysiert werden, um Modelle zu erhalten.

Dendrogramm

Zur Visualisierung der bei einer hierarchischen Clusterung entstehenden Baumstruktur kann das Dendrogramm (griech. δένδρον (dendron) = Baum) genutzt werden. Das Dendrogramm ist ein Baum, der die hierarchische Zerlegung der Datenmenge in immer kleinere Teilmengen darstellt. Die Wurzel repräsentiert ein einziges Cluster, das die gesamte Menge enthält. Die Blätter des Baumes repräsentieren Cluster, in denen sich je ein einzelnes Objekt der Datenmenge befindet. Ein innerer Knoten repräsentiert die Vereinigung aller seiner Kindknoten. Jede Kante zwischen einem Knoten und einem seiner Kindknoten hat als Attribut noch die Distanz zwischen den beiden repräsentierenden Mengen von Objekten.

mini|Dendrogramm Das Dendrogramm wird informativer, wenn eine Achse zur Darstellung der Distanz oder (Un-)ähnlichkeit verwendet wird. Wenn zwei Cluster zusammengefügt werden, dann haben diese Cluster eine bestimmte Distanz oder (Un-)ähnlichkeit zueinander. Auf dieser Höhe wird der Verbindungsstrich gezeichnet. Im nebenstehenden Beispiel wurden z. B. die Objekte RR1 und RR4 bei einem Wert des Ähnlichkeitsmaßes von ca. 62 zusammengefügt. Die „Höhe“ ist hier die horizontale Achse.

In dieser Darstellung kann man eine gewünschte Zahl von Clustern auswählen, indem man das Dendrogramm auf einer geeigneten Höhe durchschneidet. Typischerweise sucht man eine Stelle, wo es zwischen zwei Fusionierungen einen großen Sprung der Distanz oder (Un-)ähnlichkeit gibt, z. B. im rechten Dendrogramm auf der Höhe 40. Dann ergeben sich vier Cluster, von denen 2 nur einzelne Objekte enthalten (RR2, RR5), ein Cluster enthält zwei Objekte (RR3 und RR6) und das letzte Cluster enthält alle übrigen Objekte. Gibt es hierarchische Cluster mit deutlich unterschiedlichen Größen, so kann es notwendig sein, auf unterschiedlichen Höhen zu zerlegen: während ein Cluster auf einer Höhe noch mit seinen Nachbarn verbunden ist, zerfällt ein anderer ("dünnerer") Cluster auf dieser Höhe schon in einzelne Objekte.

Distanz- und Ähnlichkeitsmaße

Sowohl in der agglomerativen als auch bei den divisiven hierarchischen Clusteranalysen ist es notwendig, Abstände bzw. (Un-)ähnlichkeiten zwischen zwei Objekten, einem Objekt und einem Cluster oder zwei Clustern zu berechnen. Je nach Skalenniveau der zugrunde liegenden Variablen kommen verschiedene Maße zum Einsatz:

Bei kategorialen (nominalen und ordinalen) Variablen werden Ähnlichkeitsmaße benutzt, d. h. ein Wert von Null bedeutet, dass die Objekte eine maximale Unähnlichkeit haben. Diese können in Distanzmaße umgewandelt werden. Bei metrischen Variablen werden Distanzmaße benutzt, d. h. ein Wert von Null bedeutet, dass die Objekte einen Abstand von Null, also maximale Ähnlichkeit haben.

Die folgende Tabelle zeigt einige Ähnlichkeits- bzw. Distanzmaße für binäre und metrische Variablen. Kategorielle Variablen mit mehr als zwei Kategorien können in mehrere binäre Variablen umgewandelt werden. Die Gower Distanz kann auch für nominal skalierte Variablen definiert werden.

Ähnlichkeitsmaß Distanzmaß Jaccard Tanimoto Euklidisch Simple Matching Pearson mit die Standardabweichung der Variable Russel Rao City-BlockManhattan Dice Gower mit die Spannweite der Variable Kulczynski Mahalanobis mit die Kovarianzmatrix der Variablen

Beispiele

Ein Internetbuchhändler weiß für zwei Besucher, welche Buch-Webseiten sie sich angesehen haben, für jede der Webseiten wird also eine 0=nicht angesehen oder 1=angesehen gespeichert. Welches Ähnlichkeitsmaß bietet sich an, um zu erfahren, wie ähnlich die beiden Besucher sind? Die Anzahl der Buch-Webseiten, die sich keiner der beiden Besucher angesehen hat (), von denen es viele gibt, sollten in die Berechnung nicht einfließen. Ein möglicher Koeffizient wäre der Jaccard-Koeffizient, d. h. die Anzahl der Buch-Webseiten, die sich beide Besucher angesehen haben (), dividiert durch die Anzahl der Buch-Webseiten, die sich mindestens einer der beiden Besucher angesehen hat ( Anzahl der Buch-Webseiten, die sich nur der erste Besucher angesehen hat, und Anzahl der Buch-Webseiten, die sich nur der zweite Besucher angesehen hat). In den ALLBUS Daten wird u. a. nach der Einschätzung der aktuellen Wirtschaftslage mit den Antwortmöglichkeiten Sehr gut, Gut, Teils-Teils, Schlecht und Sehr Schlecht gefragt. Für jede der möglichen Antworten wird nun eine binäre Variable gebildet, so dass die binären Ähnlichkeitsmaße verwendet werden können. Zu beachten ist, dass bei mehreren Variablen mit unterschiedlichen Kategorienzahlen noch eine Gewichtung bzgl. der Kategorienzahl stattfinden sollte. Im Iris Datensatz werden die vier () Abmessungen von Schwertlilienblütenblättern betrachtet. Um Abstände zwischen zwei Blütenblättern und zu berechnen, kann z. B. der euklidische Abstand benutzt werden.

Welches Ähnlichkeits- bzw. Distanzmaß verwendet wird, hängt letztlich von der gewünschten inhaltlichen Interpretation des Ähnlichkeits- bzw. Distanzmaßes ab.

Agglomerative Berechnung

Die agglomerative Berechnung einer hierarchischen Clusteranalyse ist der einfachste und flexibelste Fall. Zu Beginn wird zunächst jedes Objekt als ein eigener Cluster aufgefasst. Nun werden in jedem Schritt die jeweils einander nächsten Cluster zu einem Cluster zusammengefasst. Besteht ein Cluster aus mehreren Objekten, dann muss angegeben werden, wie die Distanz zwischen Clustern berechnet wird. Hier unterscheiden sich die einzelnen agglomerativen Verfahren. Das Verfahren kann beendet werden, wenn alle Cluster eine bestimmte Distanz/Ähnlichkeit zueinander überschreiten/unterschreiten oder wenn eine genügend kleine Zahl von Clustern ermittelt worden ist. Dies ist bei Clustern mit nur einem Objekt, wie sie zu Anfang vorgegeben sind, trivial.

Für die Durchführung einer agglomerativen Clusteranalyse müssen ein Distanz- oder Ähnlichkeitsmaß zur Bestimmung des Abstandes zwischen zwei Objekten und ein Fusionierungsalgorithmus zur Bestimmung des Abstandes zwischen zwei Clustern ausgewählt werden.

Dabei ist die Wahl des Fusionierungsalgorithmus oft wichtiger als die des Distanz- oder Ähnlichkeitsmaßes.

Fusionierungsalgorithmen

Die folgende Tabelle zeigt eine Übersicht über gängige Fusionierungsalgorithmen. Der Abstand zwischen Cluster und dem neuen Cluster wird oft über den Abstand oder die Unähnlichkeit von zwei Objekten berechnet. Der neue Cluster B entsteht aus der Fusion des "grünen" und "blauen" Clusters.

Single-LinkageK. Florek, J. Łukasiewicz, J. Perkal, H. Steinhaus, S. Zubrzycki: Taksonomia wrocławska. In: Przegląd Antropol. 17, 1951, S. 193–211.K. Florek, J. Łukaszewicz, J. Perkal, H. Steinhaus, S. Zubrzycki: Sur la liaison et la division des points d’un ensemble fini. In: Colloquium Mathematicae. Vol. 2, No. 3–4, 1951, S. 282–285. Institute of Mathematics Polish Academy of Sciences.L. L. McQuitty: Elementary linkage analysis for isolating orthogonal and oblique types and typal relevancies. Educational and Psychological Measurement. 1957.P. H. Sneath: The application of computers to taxonomy. In: Journal of general microbiology. 17(1), 1957, S. 201–226. 150px Minimaler Abstand aller Elementpaare aus den beiden Clustern. Dieses Verfahren neigt zur Kettenbildung. Complete-LinkageP. N. M. Macnaughton-Smith: Some Statistical and Other Numerical Techniques for Classifying Individuals. Research Unit Report 6. London: Her Majesty’s Stationery Office, 1965 150px Maximaler Abstand aller Elementpaare aus den beiden Clustern. Dieses Verfahren neigt zur Bildung kleiner Gruppen. Average-Linkage, Weighted Pair-Group Method using arithmetic Averages (WPGMA)R. R. Sokal, C. D. Michener: A statistical method for evaluating systematic relationships. In: University of Kansas Science Bulletin 38, 1958, S. 1409–1438. 150px Durchschnittlicher Abstand aller Elementpaare aus den beiden Clustern Average-Group-Linkage, McQuitty, Unweighted Pair-Group Method using arithmetic Averages (UPGMA) 150px Durchschnittlicher Abstand aller Elementpaare aus der Vereinigung von A und B Centroid-Method, Unweighted Pair-Group Method using Centroids (UPGMC) 150px Abstand der Zentren der beiden Cluster wobei das Zentrum des Clusters sei, das des Clusters . Median-Method, Weighted Pair-Group Method using Centroids (WPGMC)J. C. Gower: A Comparison of Some Methods of Cluster Analysis. In: Biometrics 23.4, 1967, S. 623. 150px Abstand der Zentren der beiden Cluster wobei das Zentrum des Clusters sei, der Mittelwert aus den Clusterzentren des grünen und blauen Clusters.

Weitere Methoden sind: