Vergleich hierarchischer Cluster-Dendrogramme, die mit unterschiedlichen Entfernungen und Methoden erhalten wurden

28

[Der ursprüngliche Titel "Ähnlichkeitsmessung für hierarchische Clusterbäume" wurde später von @ttnphns geändert, um das Thema besser widerzuspiegeln.]

Ich führe eine Reihe von hierarchischen Clusteranalysen für einen Datenrahmen von Patientenakten durch (z. B. ähnlich wie http://www.biomedcentral.com/1471-2105/5/126/figure/F1?highres=y ).

Ich experimentiere mit verschiedenen Distanzmaßen , verschiedenen Parametergewichten und verschiedenen hierarchischen Methoden , um deren Auswirkungen auf die endgültigen Cluster / Strukturen / Ansichten des Baumes (Dendrogramm) zu verstehen. Meine Frage, ob es eine Standardberechnung / -maß gibt, um den Unterschied zwischen verschiedenen hierarchischen Bäumen zu berechnen, und wie man dies in R umsetzt (z. B. um zu quantifizieren, dass einige Bäume nahezu identisch sind und andere sich drastisch unterscheiden).

Wouter
quelle

Antworten:

44

Um die Ähnlichkeit zweier hierarchischer (baumartiger) Strukturen zu vergleichen, werden Kennzahlen verwendet, die auf der Idee der kophenetischen Korrelation basieren. Aber ist es richtig, Dendrogramme zu vergleichen, um die "richtige" Methode oder das richtige Abstandsmaß in hierarchischen Clustern auszuwählen?

Bei der hierarchischen Clusteranalyse gibt es einige Punkte - versteckte Haken -, die ich für sehr wichtig halte :

  • Niemals Dendrogramme vergleichen ( um die Methode mit der stärkeren Verteilung auszuwählen ), die mit verschiedenen Agglomerationsmethoden visuell erhalten wurden. Es wird nicht gesagt, welche Methode "besser" ist. Jede Methode hat einen eigenen "prototypischen" Baum-Look: Die Bäume unterscheiden sich konsistent, auch wenn die Daten keine Clusterstruktur oder zufällige Clusterstruktur aufweisen. (Und ich glaube nicht, dass es eine Standardisierung oder Maßnahme gibt, die diese inneren Unterschiede beseitigen würde.) Sie können jedoch Dendrogramm-Looks von Ergebnissen vergleichen, die mit derselben Methode, jedoch mit unterschiedlichen Daten erstellt wurden. Maxim: direkt, ein Vergleich des Aussehens von Dendrogrammen nach verschiedenen Methoden ist nicht akzeptabel .
  • 1 Maxim: Die Auswahl einer Schnittstufe durch Betrachtung eines Dendrogrammaussehens ist zwar möglich, aber nicht die beste Methode zur Auswahl der Partition, und für einige Methoden kann dies irreführend sein . Es wird empfohlen, sich stattdessen auf ein formales internes Clustering-Kriterium zu stützen .
  • Obwohl niemand es Ihnen verbieten kann, mit Distanzmaßen oder agglomerativen Methoden zu "experimentieren", ist es besser, die Distanz und die Methode bewusst auszuwählen und nicht blind zu versuchen. Die Entfernung sollte die Aspekte des Unterschieds widerspiegeln, an denen Sie interessiert sind, und die Methode - man muss sich dessen bewusst sein - impliziert einen bestimmten Archetyp eines Clusters (z. B. ist die Metapher eines Ward-Clusters, würde ich sagen, Typ ; Cluster nach vollständiger Verknüpfung wäre sein Kreis [von Hobby oder Handlung]; Cluster nach einmaliger Verknüpfung würde Spektrum [Kette]; Cluster nach Schwerpunktmethode wären die Nähe von Plattformen [Politik]; eine durchschnittliche Verknüpfung Cluster konzeptionell meist undifferenziert ist und wäre im allgemeinen vereint Klasse ).
  • Einige Methoden verlangen richtige Abstand Maßnahmen und / oder richtige Art von Daten. Ward und Centroid zum Beispiel benötigen logischerweise eine (quadratische) euklidische Distanz - weil diese Methoden die Berechnung von Centroiden im euklidischen Raum umfassen. Und die Berechnung von geometrischen Schwerpunkten ist zum Beispiel mit Binärdaten inkongruent. Die Daten sollten skaliert / kontinuierlich sein. Maxim: Daten / Entfernung / Methodenannahmen und Korrespondenz sind sehr wichtig und keine so einfache Frage.
  • Die Vorverarbeitung (wie das Zentrieren, Skalieren und andere Formen der Transformation von Variablen / Merkmalen) vor der Berechnung einer Distanzmatrix und die Durchführung der Clusterbildung ist ebenfalls eine äußerst wichtige Frage. Dies kann die Ergebnisse dramatisch beeinflussen. Überlegen Sie, welche Vorverarbeitung für Sie hilfreich sein kann und aus Sicht der Interpretation Sinn macht. Scheuen Sie sich auch nicht, Ihre Daten sorgfältig grafisch zu untersuchen, bevor Sie versuchen, eine Clusteranalyse durchzuführen.
  • Nicht alle Methoden der agglomerativen Clusterbildung können gleichermaßen als nützlich angesehen werden hierarchische Klassifizierung angesehen werden ... aus philosophischen Gründen. Beispielsweise gibt die Centroid-Methode eine gewisse Hierarchie vor, da das Cluster-Center ein aufstrebendes und definierendes Merkmal eines Clusters als Ganzes ist und das Zusammenführen von Clustern durch dieses Merkmal gesteuert wird. Eine vollständige Verknüpfung "entlässt" andererseits beide Subcluster, wenn sie zusammengeführt werden - aufgrund der Entfernung zwischen einzelnen Objekten der beiden. Somit ist eine vollständige Verknüpfung dendrogram nur eine Geschichte der Sammlung und nicht ein Eltern-Kind - Art Taxonomie .Maxim: Bei der hierarchischen agglomerativen Clusteranalyse wird im Allgemeinen erwartet, dass Sie eine Partition basierend auf dem Ergebnis erstellen, anstatt das Ergebnis als hierarchische Taxonomie zu betrachten.
  • Hierarchisches Clustering ist ein typischer Greedy-Algorithmus , der die beste Wahl unter den Alternativen , die bei jedem Schritt auftreten, in der Hoffnung, am Ende einer optimalen Lösung nahe zu kommen. Es ist jedoch wahrscheinlich, dass die "beste" Auswahl, die in einem Schritt mit hoher Stufe erscheint, schlechter ist als das theoretisch in diesem Schritt mögliche globale Optimum . Je größer die Stufe ist, desto größer ist in der Regel die Suboptimalität. Da wir normalerweise nur wenige Cluster haben möchten, sind die letzten Schritte wichtig. und, wie gerade gesagt, wird erwartet, dass sie relativ schlecht sind, wenn die Anzahl der Stufen hoch ist (sagen wir tausendste Stufe). Aus diesem Grund wird hierarchisches Clustering im Allgemeinen nicht für große Stichproben von Objekten empfohlen (Nummerierung von Tausenden von Objekten), selbst wenn das Programm mit einer so großen Entfernungsmatrix umgehen kann.

Wenn Sie nach den oben genannten Vorsichtsmaßnahmen weiterhin der Meinung sind, dass Sie ein Maß für die Ähnlichkeit zwischen hierarchischen Klassifizierungen wünschen, gehen Sie möglicherweise auf "Vergleichen von Dendrogrammen" und "Vergleichen von hierarchischen Klassifizierungen". Eine Idee, die sich am ehesten anbietet, könnte auf der kophenetischen Korrelation beruhen: Es seien zwei Dendrogramme für denselben Datensatz von n Objekten gegebenXichjKolligationskoeffizient (oder vielleicht sein Rang, die Schrittzahl) zwischen jedem Paar von Objekten ij in einem Dendrogramm sein, undY.ichjauch im anderen Dendrogramm gleich sein. Korrelation oder Cosinus berechnen.


1 Späteres Update zum Problem des Dendrogramms von Wards 's Methode. Verschiedene Clusterprogramme können für das Ward-Verfahren unterschiedlich transformierte Aglomerationskoeffizienten ausgeben. Daher sehen ihre Dendrogramme etwas anders aus, obwohl der Verlauf und die Ergebnisse der Clusterbildung gleich sind . Zum Beispiel nimmt SPSS nicht die Wurzel aus den ultrametrischen Koeffizienten und kumuliert sie in der Ausgabe. Eine andere Tradition (die zum Beispiel in einigen R-Paketen zu finden ist) ist, die Wurzel zu ziehen (sogenanntes "Ward-2").Implementierungen) und nicht zu kumulieren. Um es noch einmal zu wiederholen: Solche Unterschiede wirken sich nur auf die allgemeine Form / das Aussehen des Dendrogramms aus, nicht auf die Clustering-Ergebnisse. Das Aussehen des Dendrogramms kann jedoch Ihre Entscheidung über die Anzahl der Cluster beeinflussen. Die Moral ist, dass es sicher ist, sich überhaupt nicht auf das Dendrogramm in Wards Methode zu verlassen, es sei denn, Sie wissen genau, was diese Koeffizienten aus Ihrem Programm sind und wie Sie sie richtig interpretieren.

ttnphns
quelle
5
Ich kann so ziemlich alles hinter mich bringen. Zwei Punkte, die ich hinzufügen möchte: A) Was Sie zu tun scheinen, ist eine Art Überanpassung . Durch die systematische Bewertung von Maßen, Gewichten und Methoden besteht ein hohes Risiko, dass die Parameter, mit denen Sie enden, für Ihre aktuellen Daten hochspezifisch sind und möglicherweise für andere Daten oder sogar für spätere Daten unbrauchbar werden. B) Was nützt es, die Ähnlichkeit der Dendrogramme zu kennen? Überlegen Sie, was Sie danach mit ihnen machen möchten, und versuchen Sie dann, das Endergebnis zu bewerten. Die Bewertung der Zwischenergebnisse kann irreführend sein.
Anony-Mousse
1
Wenn Sie sich immer noch für das Thema interessieren, dachte ich, dass Sie meine jüngste Antwort auf DS SE hilfreich finden könnten , zumal sie eine, wenn auch eingeschränkte, Abdeckung sowohl von frequentistischen als auch von bayesianischen Ansätzen für hierarchische topische Modelle (mit eingebetteten Klasseninformationen) bietet. und Auswählen von Ähnlichkeitsmaßen .
Aleksandr Blekh
@ttnphns, Könnten Sie bitte näher erläutern, wie Sie mit dem "Kolligierungskoeffizienten" zwei hierarchische Klassifikationen vergleichen können?
Bassir