Wie können Sie feststellen, ob die Daten so „geclustert“ sind, dass Clustering-Algorithmen aussagekräftige Ergebnisse liefern?

Woher wissen Sie, ob Ihre (hochdimensionalen) Daten genügend Clustering aufweisen, sodass Ergebnisse von kmeans oder anderen Clustering-Algorithmen tatsächlich von Bedeutung sind?

Wie stark sollte die Varianz innerhalb eines Clusters reduziert werden, damit die tatsächlichen Cluster-Ergebnisse aussagekräftig (und nicht unecht) sind?

Sollte Clustering sichtbar sein, wenn eine dimensionsreduzierte Form der Daten gezeichnet wird, und sind die Ergebnisse von kmeans (oder anderen Methoden) bedeutungslos, wenn das Clustering nicht visualisiert werden kann?

Über k-means können Sie speziell die Lückenstatistik verwenden. Grundsätzlich besteht die Idee darin, die Güte des Clustering-Maßes basierend auf der durchschnittlichen Streuung im Vergleich zu einer Referenzverteilung für eine zunehmende Anzahl von Clustern zu berechnen. Weitere Informationen finden Sie im Original:

Tibshirani, R., Walther, G. und Hastie, T. (2001). Schätzung der Anzahl von Clustern in einem Datensatz über die Lückenstatistik . JR Statist. Soc. B, 63 (2): 411 & ndash; 423.

Die Antwort, die ich auf eine verwandte Frage gegeben habe, hebt andere allgemeine Gültigkeitsindizes hervor, anhand derer überprüft werden kann, ob ein gegebener Datensatz eine Art Struktur aufweist.

Wenn Sie keine Ahnung haben, was Sie erwarten würden, wenn nur Rauschen vorhanden wäre, ist es ein guter Ansatz, Resampling zu verwenden und die Stabilität von Clustern zu untersuchen. Mit anderen Worten, nehmen Sie eine erneute Abtastung Ihrer Daten vor (per Bootstrap oder durch Hinzufügen von Rauschen) und berechnen Sie die "Nähe" der resultierenden Partitionen, gemessen an Jaccard- Ähnlichkeiten. Kurz gesagt, es ermöglicht die Abschätzung der Häufigkeit, mit der ähnliche Cluster in den Daten wiederhergestellt wurden. Diese Methode ist im fpc R-Paket als verfügbar clusterboot(). Es verwendet entweder Rohdaten oder eine Distanzmatrix als Eingabe und ermöglicht die Anwendung einer Vielzahl von Clustering-Methoden (hierarchische, k-Means-, Fuzzy-Methoden). Die Methode wird in den verlinkten Quellen beschrieben:

Hennig, C. (2007) Clusterbasierte Bewertung der Clusterstabilität . Computational Statistics and Data Analysis , 52, 258 & ndash; 271.

Hennig, C. (2008) Auflösungspunkt und Isolationsrobustheit: Robustheitskriterien für allgemeine Methoden der Clusteranalyse . Journal of Multivariate Analysis , 99, 1154 & ndash; 1176.

Unten sehen Sie eine kleine Demonstration mit dem k-means-Algorithmus.

sim.xy <- function(n, mean, sd) cbind(rnorm(n, mean[1], sd[1]),
rnorm(n, mean[2],sd[2]))
xy <- rbind(sim.xy(100, c(0,0), c(.2,.2)),
            sim.xy(100, c(2.5,0), c(.4,.2)),
            sim.xy(100, c(1.25,.5), c(.3,.2)))
library(fpc)
km.boot <- clusterboot(xy, B=20, bootmethod="boot",
                       clustermethod=kmeansCBI,
                       krange=3, seed=15555)

Die Ergebnisse in diesem künstlichen (und gut strukturierten) Datensatz sind recht positiv, da keiner der drei Cluster ( krange) über die Proben hinweg aufgelöst wurde und die durchschnittliche clusterweise Jaccard-Ähnlichkeit für alle Cluster> 0,95 beträgt.

Unten sehen Sie die Ergebnisse für die 20 Bootstrap-Beispiele. Wie zu sehen ist, bleiben statistische Einheiten in der Regel in demselben Cluster zusammengefasst, mit wenigen Ausnahmen für die dazwischen liegenden Beobachtungen.

Sie können diese Idee natürlich auf jeden Gültigkeitsindex erweitern: Wählen Sie eine neue Reihe von Beobachtungen durch Bootstrap (mit Ersetzung) aus, berechnen Sie Ihre Statistik (z. B. Silhouette-Breite, kophenetische Korrelation, Huberts Gamma, innerhalb der Quadratsumme) für einen Bereich von Cluster-Nummern (z. B. 2 bis 10) wiederholen Sie 100 oder 500 Mal und sehen Sie sich das Boxplot Ihrer Statistik als Funktion der Cluster-Nummer an.

Folgendes erhalte ich mit demselben simulierten Datensatz, jedoch unter Verwendung der hierarchischen Clustering-Methode von Ward und unter Berücksichtigung der kophenetischen Korrelation (mit der beurteilt wird, wie gut Abstandsinformationen in den resultierenden Partitionen reproduziert werden) und der Silhouette-Breite (ein Kombinationsmaß zur Beurteilung der Homogenität und Inter-Cluster-Homogenität). Cluster-Trennung).

Die cophenetische Korrelation reicht von 0,6267 bis 0,7511 mit einem Medianwert von 0,7031 (500 Bootstrap-Samples). Die Silhouette scheint maximal zu sein, wenn wir 3 Cluster betrachten (Median 0,8408, Bereich 0,7371-0,8769).

Eine Möglichkeit, schnell zu visualisieren, ob hochdimensionale Daten genügend Cluster aufweisen, ist die Verwendung von t-Distributed Stochastic Neighbor Embedding ( t-SNE ). Es projiziert die Daten in einen Raum mit geringen Dimensionen (z. B. 2D, 3D) und leistet gute Arbeit bei der Beibehaltung der Clusterstruktur, falls vorhanden.

ZB MNIST-Datensatz :

Olivetti stellt Datensatz gegenüber:

Die Fähigkeit, die Cluster in einer darstellbaren Anzahl von Dimensionen visuell zu erkennen, ist sicherlich ein zweifelhaftes Kriterium für die Nützlichkeit eines Clustering - Algorithmus, insbesondere wenn diese Dimensionsreduktion unabhängig von der Clusterung selbst durchgeführt wird (dh vergeblich, um herauszufinden, ob Clustering wird funktionieren).

Tatsächlich haben Clustering-Methoden den höchsten Wert, wenn es darum geht, Cluster zu finden, bei denen das menschliche Auge / der menschliche Verstand die Cluster nicht sehen kann.

Die einfache Antwort lautet: Clustering durchführen und dann herausfinden, ob es funktioniert hat (mit einem der Kriterien, die Sie interessieren, siehe auch die Antwort von @ Jeff).

Wann sind Ergebnisse überhaupt sinnvoll ? Insbesondere k-means Ergebnisse?

Fakt ist, dass k-means eine bestimmte mathematische Statistik optimiert. Damit ist kein "Sinn" verbunden.

Insbesondere bei hochdimensionalen Daten sollte die erste Frage lauten: Ist der euklidische Abstand noch sinnvoll ? Wenn nicht, verwende kein k-means. Die euklidische Distanz ist in der physischen Welt von Bedeutung, verliert jedoch schnell an Bedeutung, wenn Sie über andere Daten verfügen. Gibt es einen Grund, warum Daten, die Sie künstlich in einen Vektorraum transformieren, euklidisch sein sollten?

Wenn Sie den klassischen "altgetreuen" Datensatz nehmen und k-means ohne Normalisierung darauf ausführen , aber mit reinem euklidischen Abstand, ist er bereits nicht mehr aussagekräftig. EM, das tatsächlich eine Form der "cluster local" Mahalanobis-Distanz verwendet, wird viel besser funktionieren. Insbesondere passt es sich den Achsen mit sehr unterschiedlichen Maßstäben an.

Übrigens ist eine wesentliche Stärke von k-means, dass es die Daten eigentlich immer partitioniert, egal wie sie aussehen. Sie können k-means verwenden, um gleichmäßiges Rauschen in k Cluster zu unterteilen . Man kann behaupten, dass k-Mittel-Cluster offensichtlich nicht aussagekräftig sind. Oder man kann dies akzeptieren als: Der Benutzer wollte die Daten partitionieren, um die quadratischen euklidischen Abstände zu minimieren, ohne dass die Cluster "aussagekräftig" sein müssen.

Ich habe gerade erst angefangen, Clustering-Algorithmen zu verwenden, sodass hoffentlich jemand, der über mehr Kenntnisse verfügt, eine vollständigere Antwort liefern kann. Hier sind jedoch einige Gedanken:

"Sinnvoll" ist, wie Sie sicher wissen, sehr subjektiv. Ob das Clustering gut genug ist, hängt ganz davon ab, warum Sie überhaupt ein Clustering durchführen müssen. Wenn Sie versuchen, eine Gruppenzugehörigkeit vorherzusagen, ist es wahrscheinlich, dass Clustering besser als der Zufall ist (und nicht schlechter), daher sollten die Ergebnisse bis zu einem gewissen Grad aussagekräftig sein.

Wenn Sie wissen möchten, wie zuverlässig dieses Clustering ist, benötigen Sie eine Metrik, mit der Sie es vergleichen können. Wenn Sie über eine Reihe von Entitäten mit bekannten Mitgliedschaften verfügen, können Sie mithilfe der Diskriminanzanalyse feststellen, wie gut die Vorhersagen waren. Wenn Sie keine Gruppe von Entitäten mit bekannten Mitgliedschaften haben, müssen Sie wissen, welche Varianz für Cluster in Ihrem Bereich typisch ist. Physische Attribute von Entitäten mit starren Kategorien haben wahrscheinlich eine viel geringere Varianz innerhalb der Gruppe als psychometrische Daten über Menschen, aber das macht die Clusterbildung nicht notwendigerweise "schlimmer".

Ihre zweite Frage spielt auf "Welchen Wert von k soll ich wählen?" An. Auch hier gibt es keine eindeutige Antwort. In Ermangelung einer Gruppe von Kategorien von vornherein möchten Sie wahrscheinlich die Anzahl der Cluster minimieren und gleichzeitig die durchschnittliche Varianz der Cluster minimieren. Ein einfacher Ansatz könnte darin bestehen, die "Anzahl der Cluster" gegen die "durchschnittliche Cluster-Varianz" zu zeichnen und nach dem "Winkel" zu suchen - wobei das Hinzufügen weiterer Cluster keinen signifikanten Einfluss auf Ihre Cluster-Varianz hat.

Ich würde nicht sagen, dass die Ergebnisse von k-means bedeutungslos sind, wenn sie nicht visualisiert werden können, aber es ist auf jeden Fall ansprechend, wenn die Cluster visuell sichtbar sind. Dies führt wiederum nur zu der Frage zurück: Warum müssen Sie Clustering durchführen und wie zuverlässig müssen Sie sein? Letztendlich ist dies eine Frage, die Sie beantworten müssen, je nachdem, wie Sie die Daten verwenden werden.

Um festzustellen, ob ein Cluster sinnvoll ist, können Sie einen Algorithmus ausführen, um die Anzahl der Cluster zu ermitteln und festzustellen, ob ein Wert größer als 1 ausgegeben wird.

Wie gesagt, ein Algorithmus zur Clusterzählung ist der Algorithmus zur Lückenstatistik. Grob berechnet dies die Gesamtvarianz der Cluster unter Berücksichtigung Ihrer tatsächlichen Daten und vergleicht sie mit der Gesamtvarianz der Cluster von Daten, die überhaupt keine Cluster haben sollten (z. B. ein Datensatz, der durch gleichmäßiges Abtasten innerhalb derselben Grenzen wie Ihre tatsächlichen Daten gebildet wird). Die Anzahl der Cluster wird dann so gewählt, dass die größte "Lücke" zwischen diesen beiden Clustervarianzen ergibt.$k$$k$

Ein anderer Algorithmus ist der Vorhersagekraftalgorithmus (der der restlichen Antwort von chl ähnelt). In etwa führt dies eine Reihe von k-Means-Clustern durch und berechnet den Anteil der Punkte, die im selben Cluster verbleiben. wird dann als das kleinste , das einen Anteil ergibt, der höher als eine Schwelle ist (z. B. eine Schwelle von 0,8).$k$$k$