Wie kann man die Nachteile von Hierarchical Clustering verstehen?

19

Kann jemand die Vor- und Nachteile von Hierarchical Clustering erklären?

  1. Hat hierarchisches Clustering die gleichen Nachteile wie K?
  2. Was sind die Vorteile von Hierarchical Clustering gegenüber K?
  3. Wann sollten wir K-Mittel anstelle von Hierarchical Clustering verwenden und umgekehrt?

Antworten auf diesen Beitrag erklären die Nachteile von k sehr gut. Wie man die Nachteile von K-means versteht

GeorgeOfTheRF
quelle
2
In dieser Antwort habe ich einige potenziell problematische Aspekte der hierarchischen agglomerativen Clusteranalyse angesprochen. Der Hauptnachteil ist, dass es sich um einen nicht-iterativen Single-Pass-Greedy-Algorithmus handelt. Mit einem gierigen Algorithmus optimieren Sie die Aufgabe des aktuellen Schritts, was - für die meisten HC-Methoden - nicht unbedingt die beste Partition in einem entfernten zukünftigen Schritt garantiert. Der Hauptvorteil von HC besteht darin, dass es hinsichtlich der Wahl des zu verwendenden Annäherungsmaßes flexibel ist. @Mic hat unten bereits eine gute Antwort gegeben, also stimme ich nur zu.
TTNPHNS

Antworten:

13

Während means versucht, ein globales Ziel (Varianz der Cluster) zu optimieren und ein lokales Optimum zu erreichen, zielt die agglomerative hierarchische Clusterbildung darauf ab, bei jeder Clusterfusion den besten Schritt zu finden (Greedy-Algorithmus), der exakt ausgeführt wird, aber zu einer potenziell suboptimalen Lösung führt .k

Man sollte hierarchisches Clustering verwenden, wenn die zugrunde liegenden Daten eine hierarchische Struktur haben (wie die Korrelationen an den Finanzmärkten) und Sie die Hierarchie wiederherstellen möchten. Sie können dazu immer noch Mittel anwenden , es kann jedoch vorkommen, dass Partitionen (von den gröbsten (alle Datenpunkte in einem Cluster) bis zu den feinsten (jeder Datenpunkt ist ein Cluster)) nicht verschachtelt sind keine richtige Hierarchie.k

Wenn Sie sich mit feineren Clustering-Eigenschaften befassen möchten, sollten Sie flache Clustering- Methoden wie Mittel nicht mit hierarchischen Clustering-Methoden wie Single, Average, Complete Linkages vergleichen. Beispielsweise sind alle diese Cluster platzsparend, dh wenn Sie Cluster erstellen, verzerren Sie den Raum nicht, wohingegen hierarchische Cluster wie Ward nicht platzsparend sind, dh bei jedem Zusammenführungsschritt wird der metrische Raum verzerrt.k

Zusammenfassend kann gesagt werden, dass die Nachteile der hierarchischen Clustering-Algorithmen sehr unterschiedlich sein können. Einige haben möglicherweise ähnliche Eigenschaften wie : Ward zielt darauf ab, die Varianz zu optimieren, Single Linkage jedoch nicht. Sie können aber auch andere Eigenschaften haben: Ward erweitert den Raum, während Single Linkage wie Mittel platzsparend ist.kkk

- Bearbeiten, um die platzsparenden und den Raum erweiternden Eigenschaften zu präzisieren

Platzsparend: wobei der Abstand zwischen den Clustern und Sie zusammenführen möchten, und der Abstand zwischen den Datenpunkten ist. D i j C i C j d

Dichj[MindestxCich,yCjd(x,y),maxxCich,yCjd(x,y)]
DichjCichCjd

: dh durch Zusammenführen von und der Algorithmus den Cluster weiter .

D(CiCj,Ck)max(Dik,Djk),
CiCjCk
mic
quelle
Können Sie noch einige Beispiele für Daten mit hierarchischer Struktur nennen? Dem Beispiel des Finanzmarktes nicht gefolgt.
GeorgeOfTheRF
Sicher. vgl. arxiv.org/pdf/cond-mat/9802256.pdf oder einfach Abbildung 7 in arxiv.org/pdf/1506.00976.pdf, die eine Korrelationsmatrix darstellt, die eine (verrauschte) hierarchische Korrelationsblockstruktur aufweist: Sie können Blöcke auf dem Hauptbild erkennen Diagonale, die in mehrere Blöcke unterteilt ist, wobei jeder in noch mehr Blöcke unterteilt ist. Dies entspricht in etwa einer Unterteilung in Regionen (Europa, USA, Asien ohne Japan, Japan). Anschließend wird jede Region durch die Qualität der Vermögenswerte (beispielsweise hohe Qualität vs. Junk) und anschließend durch die großen Industriesektoren (Einzelhandel, Industrie, media), weiter unterteilt in (aerospace, auto ...)
mic
3
+1. Allerdings should use hierarchical clustering when underlying data has a hierarchical structure... and you want to recover the hierarchynicht unbedingt. Meistens eher im Gegenteil. Die Hierarchie von HC ist eher eine Geschichte des Algo als eine Struktur der Daten . Dennoch ist diese Frage letztendlich philosophisch / logisch, nicht so statistisch.
TTNPHNS
Ward is not space-conserving, i.e. at each merging step it will distort the metric space. Kannst du mehr darüber schreiben? Das ist nicht sehr klar.
TTNPHNS
Ward is space-dilating, whereas Single Linkage is space-conserving like k-means. Wollten Sie Space-Contracting für Single Linkage sagen?
TTNPHNS
13

Skalierbarkeit

k means ist hier klarer Sieger. ist viel besser als die (in einigen Fällen ) Skalierbarkeit der hierarchischen Clusterbildung, da normalerweise sowohl als auch und sind klein (leider neige dazu, mit zu wachsen , daher gilt normalerweise nicht ). Außerdem ist der Speicherverbrauch im Gegensatz zu quadratisch linear (normalerweise gibt es lineare Sonderfälle).Ö(nkdich)O(n3d)O(n2d)kidinO(n)

Flexibilität

k Mittel ist in seiner Anwendbarkeit äußerst begrenzt. Es ist im Wesentlichen auf euklidische Entfernungen beschränkt (einschließlich euklidischer in Kernelräumen und Bregman-Divergenzen, aber diese sind ziemlich exotisch und niemand verwendet sie tatsächlich mit Mitteln). Schlimmer noch, mean funktioniert nur mit numerischen Daten (die eigentlich stetig und dicht sein sollten, damit sie gut zu mean passen ).kkk

Hier ist das hierarchische Clustering der klare Gewinner. Es ist nicht einmal ein Abstand erforderlich - jedes Maß kann verwendet werden, einschließlich Ähnlichkeitsfunktionen, indem einfach hohe Werte niedrigen Werten vorgezogen werden. Kategoriale Daten? benutze einfach zB Jaccard. Streicher? Versuchen Sie Levenshtein Abstand. Zeitfolgen? sicher. Gemischte Typdaten? Gower Abstand. Es gibt Millionen von Datensätzen, in denen Sie hierarchisches Clustering verwenden können, in denen Sie jedoch keine Mittel verwenden können.k

Modell

Kein Gewinner hier. Mittel erzielt hohe Punktzahlen, da es eine große Datenreduktion ergibt. Centroids sind einfach zu verstehen und zu benutzen. Hierarchisches Clustering erzeugt dagegen ein Dendrogramm. Ein Dendrogramm kann auch sehr hilfreich sein, um Ihren Datensatz zu verstehen.k

Anony-Mousse - Setzen Sie Monica wieder ein
quelle
Scheitert Hierarchisch wie k bedeutet, wenn Cluster 1) nicht kugelförmig 2) unterschiedliche Radien haben 3) unterschiedliche Dichte haben?
GeorgeOfTheRF
2
Beide können funktionieren und beide können scheitern. Deshalb sind Dinge wie Dendrogramme nützlich. Vertraue niemals darauf, dass ein Clustering-Ergebnis jemals "korrekt" ist.
Anony-Mousse
Hierarchisches Clustering kann lokal optimierte Cluster ergeben, da es auf einem gierigen Ansatz basiert, aber K bedeutet, dass global optimierte Cluster vorliegen. Ich habe auch erfahren, dass es für Geschäftsleute relativ einfach ist, hierarchische Cluster zu erklären, wenn man sie mit K-Mitteln vergleicht.
Arpit Sisodia
7

Ich wollte den anderen Antworten nur etwas hinzufügen, wie es in gewisser Weise einen starken theoretischen Grund gibt, bestimmte hierarchische Clustering-Methoden zu bevorzugen.

Bei der Clusteranalyse wird häufig davon ausgegangen, dass die Daten aus einer zugrunde liegenden Wahrscheinlichkeitsdichte abgetastet werden , auf die wir keinen Zugriff haben. Aber nehmen wir an, wir hätten Zugang dazu. Wie würden wir die Cluster von f definieren ?ff

Ein sehr natürlicher und intuitiver Ansatz besteht darin, zu sagen, dass die Cluster von Regionen mit hoher Dichte sind. Betrachten Sie beispielsweise die folgende Dichte mit zwei Spitzen:f

Bildbeschreibung hier eingeben

Indem wir eine Linie über den Graphen ziehen, induzieren wir eine Menge von Clustern. Wenn wir zum Beispiel bei eine Linie zeichnen , erhalten wir die beiden gezeigten Cluster. Wenn wir jedoch die Linie bei λ 3 zeichnen , erhalten wir einen einzelnen Cluster.λ1λ3

Um dies genauer zu machen, nehmen wir an, dass wir ein willkürliches . Was sind die Cluster von f auf der Ebene λ ? Sie sind die verbundene Komponente der Superlevelmenge { x : f ( x ) λ } .λ>0fλ{x:f(x)λ}

λ λff

fXC1{x:f(x)λ1}C2{x:f(x)λ2}C1λ1C2λ2λ2<λ1C1C2C1C2=

Jetzt habe ich einige Daten aus einer Dichte abgetastet. Kann ich diese Daten so gruppieren, dass der Clusterbaum wiederhergestellt wird? Insbesondere möchten wir, dass eine Methode in dem Sinne konsistent ist, dass unsere empirische Schätzung des Clusterbaums mit zunehmender Datenerfassung immer näher an den tatsächlichen Clusterbaum heranreicht.

ABfnfXnXnEINnEINXnBnBXnPr(EINnBn)=1nEINB

Im Wesentlichen besagt die Hartigan-Konsistenz, dass unsere Clustering-Methode Regionen mit hoher Dichte angemessen trennen sollte. Hartigan untersuchte, ob Einzelverknüpfungscluster konsistent sein könnten, und stellte fest, dass sie in Dimensionen> 1 nicht konsistent sind. Das Problem, eine allgemeine, konsistente Methode zur Schätzung des Clusterbaums zu finden, lag erst vor wenigen Jahren vor, als Chaudhuri und Dasgupta einführten Robuste Einfachverbindung , die nachweislich konsistent ist. Ich würde vorschlagen, über ihre Methode zu lesen, da sie meiner Meinung nach ziemlich elegant ist.

Um Ihre Fragen zu beantworten, ist es in gewisser Weise richtig, hierarchische Cluster zu verwenden, wenn Sie versuchen, die Struktur einer Dichte wiederherzustellen. Beachten Sie jedoch die erschreckenden Anführungszeichen um "richtig" ... Letztendlich tendieren dichtebasierte Clustering-Methoden aufgrund des Fluches der Dimensionalität dazu, in hohen Dimensionen schlecht zu funktionieren, obwohl eine Definition von Clustering basierend auf Clustern Regionen mit hoher Wahrscheinlichkeit sind ist recht übersichtlich und intuitiv, wird jedoch häufig zugunsten von Methoden ignoriert, die in der Praxis eine bessere Leistung erbringen. Das heißt nicht, dass eine robuste Einfachverbindung nicht praktikabel ist - sie funktioniert tatsächlich recht gut bei Problemen in niedrigeren Dimensionen.

Abschließend möchte ich sagen, dass die Hartigan-Konsistenz in gewissem Sinne nicht unserer Intuition der Konvergenz entspricht. Das Problem ist , dass Hartigan Konsistenz ein Clusterverfahren zu stark ermöglicht über Segment Cluster , so dass ein Algorithmus Hartigan sein kann , konsistente, noch produzieren Clusterungen , die sehr unterschiedlich sind als der wahre Cluster Baum. Wir haben in diesem Jahr Arbeiten zu einem alternativen Konvergenzbegriff verfasst, der sich mit diesen Fragen befasst. Die Arbeit wurde in COLT 2015 unter "Beyond Hartigan Consistency: Verzerrungsmetrik für hierarchisches Clustering zusammenführen" veröffentlicht.

jme
quelle
Dies ist eine interessante Art, über hierarchische Clustering nachzudenken. Ich finde, dass es stark an Clustering durch nichtparametrische Dichteschätzung ( pdf ) erinnert, die Rim pdfCluster- Paket implementiert ist . (Ich diskutiere es hier .)
gung - Setzen Sie Monica wieder ein
HDBSCAN * verwendet einen ähnlichen Ansatz.
Anony-Mousse
3

k

BEARBEITEN dank ttnphns: Ein Merkmal, das hierarchisches Clustering mit vielen anderen Algorithmen gemeinsam hat, ist die Notwendigkeit, ein Entfernungsmaß zu wählen. Dies hängt häufig stark von der jeweiligen Anwendung und den jeweiligen Zielen ab. Dies kann als zusätzliche Komplikation angesehen werden (ein weiterer zu wählender Parameter ...), aber auch als Aktivposten - mehr Möglichkeiten. Im Gegensatz dazu verwendet der klassische K-Mittelwert-Algorithmus speziell den euklidischen Abstand.

Jacek Podlewski
quelle
3
Ich nehme an, "Problem" in Ihrem letzten Absatz würde positiv als Aktivposten angesehen. K-means basiert jedoch implizit nur auf der euklidischen Distanz .
TTNPHNS
Viele mögliche Entscheidungen können sowohl ein Problem als auch ein Vorteil sein :) Vielen Dank für den Kommentar zu k-means, ich werde diesen Absatz verbessern.
Jacek Podlewski
kk
Ich glaube, die ursprüngliche Frage bezog sich auf "klassische" K-Mittel und nicht die geringste Absicht, sich mit Bregman-Divergenzen zu befassen. Eine nette Bemerkung, ich werde diese Abhandlung jedoch genauer untersuchen.
Jacek Podlewski
@mic nobody benutzt Bregman-Divergenzen jenseits von Variationen der euklidischen Distanz ... es ist nur eine winzige Klasse. Aber die Leute möchten zB Manhattan-Distanz, Gower usw. verwenden, die nach meinem Wissen keine Bregman-Divergenzen sind.
Anony-Mousse