Gibt es Fälle, in denen es in k-means kein optimales k gibt?

11

Das ist mir seit mindestens ein paar Stunden in den Sinn gekommen. Ich habe versucht, ein optimales k für die Ausgabe des k-means-Algorithmus (mit einer Kosinus-Ähnlichkeitsmetrik ) zu finden, also habe ich die Verzerrung als Funktion der Anzahl der Cluster aufgetragen. Mein Datensatz ist eine Sammlung von 800 Dokumenten in einem 600-dimensionalen Raum.

Soweit ich weiß, sollte mir das Finden des Knie- oder Ellbogenpunkts auf dieser Kurve mindestens ungefähr die Anzahl der Cluster mitteilen, in die ich meine Daten einfügen muss. Ich habe die Grafik unten platziert. Der Punkt, an dem die rote vertikale Linie gezeichnet wurde, wurde unter Verwendung des Tests der maximalen zweiten Ableitung erhalten . Nachdem ich das alles getan hatte, blieb ich bei etwas viel Einfacherem hängen: Was sagt mir diese Grafik über den Datensatz?

Sagt es mir, dass es sich nicht lohnt, Cluster zu erstellen, und dass meine Dokumente nicht strukturiert sind oder dass ich ein sehr hohes k festlegen muss? Eine seltsame Sache ist jedoch, dass selbst bei niedrigem k ähnliche Dokumente in Gruppen zusammengefasst werden, sodass ich nicht sicher bin, warum ich diese Kurve erhalte. Irgendwelche Gedanken?

Geben Sie hier die Bildbeschreibung ein

machine-learning clustering k-means Legende
quelle
2
Was ich ehrlich gesagt nicht verstehe, ist, wie Sie k-means Clustering mit Proximity-Matrix-Eingabe einsetzen konnten (und das ist Cosinus!). K-means Clustering benötigt die Eingabe von Rohdaten (Objekte X Variablen) und arbeitet intern mit der euklidischen Distanz.
ttnphns
2
@ttnphns: Ich hoffe, ich habe Ihren Standpunkt verstanden, aber nach meinem besten Wissen können wir jede Distanzmetrik mit k-means verwenden, nicht wahr? Ich mache das in Python, aber es sieht so aus, als ob sogar eine Bibliothek für R verfügbar ist: cran.r-project.org/web/packages/skmeans/index.html Die Eingabe war keine Proximity-Matrix, sondern eine, terms x documentdie nach dem Ausführen eines einzelnen Vektors erhalten wurde Zersetzung. Bitte korrigieren Sie mich, wenn ich mich irre.
Legende
Das sphärische k-means- Clustering, basierend auf dem Kosinusmaß, ist für mich neu, muss ich zugeben. Ich hoffe, eines Tages mehr darüber zu lesen.
ttnphns
@ttnphns: Danke, dass du zurückgekommen bist. Ich wollte nur sicherstellen, dass ich nicht Äpfel und Orangen zusammen benutze :)
Legende
L.p

Antworten:

12

In den meisten Situationen hätte ich gedacht, dass ein solches Diagramm im Grunde bedeutet, dass die Daten keine Clusterstruktur enthalten. Das Clustering in sehr hohen Dimensionen wie dieser ist jedoch schwierig, da bei der euklidischen Abstandsmetrik alle Abstände mit zunehmender Anzahl von Dimensionen gleich sind. Auf dieser Wikipedia-Seite finden Sie Verweise auf einige Artikel zu diesem Thema. Kurz gesagt, möglicherweise ist nur die hohe Dimensionalität des Datensatzes das Problem.

Dies ist im Wesentlichen "der Fluch der Dimensionalität", siehe auch diese Wikipedia-Seite.

Ein Artikel, der von Interesse sein könnte, ist Sanguinetti, G., "Dimensionality Reduction of Clustered Datsets", IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 30 nr. 3, S. 535-540, März 2008 ( www ). Das ist ein bisschen wie eine unbeaufsichtigte Version von LDA, die einen niedrigdimensionalen Raum sucht, der die Clusterstruktur betont. Vielleicht könnten Sie das als Merkmalsextraktionsmethode verwenden, bevor Sie k-means ausführen?

Dikran Beuteltier
quelle
Ups, Entschuldigung. Ich hätte erwähnen sollen, dass ich Kosinusähnlichkeit verwende.
Legende
Ich denke, es ist sehr wahrscheinlich, dass der Fluch der Dimensionalität auch für die Kosinusähnlichkeit gilt. Grundsätzlich heißt es, dass Sie (im schlimmsten Fall) exponentiell mehr Muster benötigen, um eine Verteilung zu definieren, wenn die Anzahl der Dimensionen zunimmt. Beim Clustering identifizieren Sie effektiv Verteilungen, die Teilpopulationen darstellen. Daher ist das Clustering in hohen Dimensionen wahrscheinlich von Natur aus schwierig.
Dikran Beuteltier
+1 Danke für den Link. Ich werde es durchgehen und zurückkommen. Ich habe SVD auf meine ursprüngliche Matrix angewendet, bevor ich k-means angewendet habe, um die Anzahl der Dimensionen zu reduzieren.
Legende
3

Wie genau verwenden Sie die Kosinusähnlichkeit? Wird dies als sphärisches K-Mittel bezeichnet? Ihr Datensatz ist ziemlich klein, daher würde ich versuchen, ihn als Netzwerk zu visualisieren. Hierzu ist es selbstverständlich, eine Ähnlichkeit zu verwenden (z. B. die Kosinusähnlichkeit oder die Pearson-Korrelation), einen Grenzwert anzuwenden (nur Beziehungen über einer bestimmten Ähnlichkeit zu berücksichtigen) und das Ergebnis beispielsweise in Cytoscape oder BioLayout als Netzwerk anzuzeigen . Dies kann sehr hilfreich sein, um ein Gefühl für die Daten zu bekommen. Zweitens würde ich die Singularwerte für Ihre Datenmatrix oder die Eigenwerte einer entsprechend transformierten und normalisierten Matrix (einer Dokument-Dokument-Matrix, die in irgendeiner Form erhalten wurde) berechnen. Die Clusterstruktur sollte (erneut) als Sprung in die geordnete Liste der Eigenwerte oder Singularwerte angezeigt werden.

micans
quelle
+1 Danke für die Hinweise. Cytoscape war mir nicht bekannt. Ich werde das versuchen. Und ja, es sieht so aus, als würde k-Mittel mit Kosinusähnlichkeit als sphärisches k-Mittel bezeichnet. Ich habe dieses k-Mittel angewendet, nachdem ich SVD angewendet und die Anzahl der Dimensionen reduziert habe. Die Art und Weise, wie ich die Anzahl der Dimensionen reduzierte, bestand darin, die Varianzregel zu verwenden (wählen Sie die Singularwerte aus, die zu 95% der Varianz in den Originaldaten beitragen).
Legende
Wenn es Ihnen nichts ausmacht, können Sie auf ein Tutorial verweisen, in dem erklärt wird, wie das geht (oder zumindest so etwas). Wenn ich die Matrix generiert habe, exportiere ich sie einfach und importiere sie dann in Cytoscape und führe das aus, was Sie vorgeschlagen haben? Ich bin gespannt, ob Cytoscape integrierte Methoden für die Kosinusähnlichkeit hat oder ob ich ein Datenformat vorberechnen und als Eingabe angeben muss.
Legende
Wenn ich mit diesen Programmen arbeite, berechne ich alle paarweisen Ähnlichkeiten extern, filtere nach Schwellenwerten und erstelle eine Datei mit dem Format <label1> <label2> <ähnlichkeit>. Beide sollten diese Eingabe lesen können. In BioLayout muss es ein .txt-Suffix haben, denke ich; Verwenden Sie in CytoScape 'Import from table'.
Micans
Verstanden. Ich werde das tun und bald zurückkommen. Vielen Dank noch mal.
Legende
Entschuldigen Sie die dumme Frage, aber ich habe meine Daten als <label1> <label2> <ähnlichkeit> formatiert, kann aber nicht genau herausfinden, wie sie importiert werden sollen. Ich habe Datei-> Importieren-> Netzwerk aus Tabelle ausgeführt und meine Quell- und Zielspalten ausgewählt. Ich habe die Interaktion standardmäßig verlassen. Aber wie soll ich Kantengewichte zusammen mit den Kanten importieren? Haben Sie bitte Vorschläge?
Legende
2

Im Allgemeinen können k-Mittel zu sehr unterschiedlichen Lösungen konvergieren, die als ungeeignet beurteilt werden können. Dies gilt insbesondere für Cluster mit unregelmäßigen Formen.

Um mehr Intuition zu erlangen, können Sie auch einen anderen Visualisierungsansatz ausprobieren: Für k-means können Sie mehrere Läufe mit k-means mithilfe von Graphgrams visualisieren (siehe das WEKA-Graphgram-Paket - am besten vom Paketmanager oder hier erhalten . Eine Einführung und Beispiele können ebenfalls sein hier gefunden .

Johannes Schneider
quelle
1

Wenn ich den Graphen richtig verstehe, ist es eine grafische Darstellung der Anzahl der Cluster, K auf der x-Achse und des Abstands innerhalb der Cluster auf der y-Achse?

Da Ihre K-Mittel-Zielfunktion darin besteht, das WCSS zu minimieren, sollte dieses Diagramm immer monoton abnehmen. Wenn Sie weitere Cluster hinzufügen, verringert sich der Abstand zwischen den Punkten im Cluster immer. Dies ist das grundlegende Problem der Modellauswahl, daher müssen Sie etwas mehr Raffinesse einsetzen.

Versuchen Sie es vielleicht mit der Gap-Statistik: www-stat.stanford.edu/~tibs/ftp/gap.ps oder ähnlichen.

Darüber hinaus stellen Sie möglicherweise fest, dass K-means nicht das richtige Werkzeug für den Job ist. Wie viele Cluster erwarten Sie zu finden? Die Verwendung der Varianzregel zur Dimensionsreduzierung für das Clustering ist nicht geeignet. In diesem Dokument erfahren Sie, wann die Projektion auf die ersten K-1-PCs eine geeignete Vorverarbeitungsmaßnahme darstellt: http://people.csail.mit.edu/gjw/papers/jcss.ps

Sie können schnell feststellen, ob dies das Richtige ist, indem Sie die Projektion auf die ersten beiden Hauptkomponenten auftragen. Wenn es eine klare Trennung gibt, sollte K-means in Ordnung sein, wenn nicht, müssen Sie sich mit etwas anderem befassen. Möglicherweise K-Subspaces oder andere Subspace-Clustering-Methoden. Beachten Sie jedoch, dass diese Methoden für die euklidische Distanz gelten. Ich bin mir nicht sicher, wie sich das für Cosinus ändert.

bmc
quelle