Wie bestimme ich die richtige Anzahl von Clustern?

54

Wir finden die Cluster-Zentren und weisen k verschiedenen Cluster-Klassen Punkte zu. Dies ist ein sehr bekannter Algorithmus, der fast in jedem maschinellen Lernpaket im Netz zu finden ist. Aber der fehlende und wichtigste Teil meiner Meinung nach ist die Wahl eines korrekten k. Was ist der beste Wert dafür? Und was ist mit am besten gemeint ?

Ich verwende MATLAB für wissenschaftliche Berechnungen, bei denen das Betrachten von Silhouetten-Plots als Entscheidungsgrundlage für das hier diskutierte k dient . Ich würde mich jedoch mehr für Bayes'sche Ansätze interessieren. Anregungen sind willkommen.

Petrichor
quelle
2
Schöne Frage ...
Unter Visualization-for-Clustering gibt es (ähm) eine Möglichkeit, k-Cluster mit MSTs in einer Aufnahme darzustellen und den Effekt verschiedener k zu sehen.
Denis
Ich habe in dieser Frage mit einem halben Dutzend Methoden beantwortet Rüber hier
Ben
1
Die Entscheidung über die "beste" Anzahl k von Clustern impliziert den Vergleich von Clusterlösungen mit verschiedenen k - welche Lösung "besser" ist. In dieser Hinsicht ähnelt die Aufgabe dem Vergleich von Clustering- Methoden - was für Ihre Daten "besser" ist. Die allgemeinen Richtlinien finden Sie hier .
TTNPHNS

Antworten:

28

Dies wurde einige Male beim Stackoverflow gefragt: hier , hier und hier . Sie können sich ansehen, was die Menge dort über diese Frage (oder eine kleine Variante davon) denkt.

Lassen Sie mich auch meine eigene Antwort auf diese Frage auf stackoverflow.com kopieren:

Leider gibt es keine Möglichkeit, das "richtige" K automatisch zu setzen, und es gibt auch keine Definition dessen, was "richtig" ist. Es gibt keine einfache oder komplexe prinzipielle statistische Methode, die das "richtige K" setzen kann. Es gibt Heuristiken, Faustregeln, die manchmal funktionieren, manchmal nicht.

Die Situation ist allgemeiner, da viele Clustering-Methoden diese Art von Parametern haben, und ich denke, dies ist ein großes offenes Problem in der Clustering- / unbeaufsichtigten Lernforschungsgemeinschaft.

carlosdc
quelle
+1 Nachdem ich das gelesen habe, scheint es mir so intuitiv .... aber ich muss sagen, dass ich noch nie darüber nachgedacht habe. dass tatsächlich das Problem der Auswahl der Anzahl der PCs in PCA entspricht dem Problem der Auswahl der Anzahl der Cluster in K-Mittelwert ...
Dov
2
@Dov diese beiden Dinge sind nicht ganz gleichwertig. Es gibt spezielle Maßnahmen, mit denen die Qualität einer PCA-Lösung überprüft werden kann (insbesondere Rekonstruktionsfehler, aber auch Prozentsätze der erfassten Varianz usw.). Diese sind in der Regel (meistens) konsistent. Beim Clustering gibt es jedoch häufig keine "richtige Antwort" - ein Clustering ist möglicherweise um eine Metrik besser als ein anderes, und umgekehrt kann es bei Verwendung einer anderen Metrik zutreffen. In einigen Situationen können zwei verschiedene Cluster unter derselben Metrik gleich wahrscheinlich sein.
tdc
@tdc aber nicht diese en.wikipedia.org/wiki/... ist mehr oder weniger wie dieser improvedoutcomes.com/docs/WebSiteDocs/PCA/... ?
Dov
2
@Dov Ja, sie sind sich "mehr oder weniger" ähnlich, aber ich habe lediglich gesagt, dass das Problem der Auswahl der Anzahl der Cluster viel schwerer ist als die Auswahl der Anzahl der PCs - dh sie sind nicht "gleichwertig".
tdc
1
+1 Du hast recht. Wir führen ein anderes Modell oder eine andere Annahme ein, um über das beste k zu entscheiden, aber dann stellt sich die Frage, warum dieses Modell oder diese Annahme das beste ist ...
petrichor
19

Erstens eine Einschränkung. Beim Clustering gibt es häufig keine "richtige Antwort" - ein Clustering ist möglicherweise um eine Metrik besser als das andere, und umgekehrt kann es bei Verwendung einer anderen Metrik zutreffen. In einigen Situationen können zwei verschiedene Cluster unter derselben Metrik gleich wahrscheinlich sein.

Dennoch möchten Sie vielleicht einen Blick auf Dirichlet-Prozesse werfen . Siehe auch dieses Tutorial .

Wenn Sie mit einem Gaußschen Mischungsmodell beginnen, haben Sie das gleiche Problem wie bei k-means - Sie müssen die Anzahl der Cluster wählen. Sie können Modellnachweise verwenden, diese sind in diesem Fall jedoch nicht zuverlässig. Der Trick besteht also darin, vor den Mischungskomponenten einen Dirichlet-Prozess zu verwenden, der es Ihnen ermöglicht, eine möglicherweise unendliche Anzahl von Mischungskomponenten zu haben. Das Modell findet jedoch (normalerweise) automatisch die "richtige" Anzahl von Komponenten (unter den Voraussetzungen von) das Model).

αα

tdc
quelle
1
Ein Dirichlet-Prozess unter welchem ​​Konzentrationsparameter? Es ist eine Art Äquivalent zu der gleichen ursprünglichen Frage, k-bedeutet unter welcher k? Obwohl ich damit einverstanden bin, dass wir die Direchlet-Verteilung besser verstehen als das Verhalten eines komplexen Algorithmus auf einigen realen Daten.
Carlosdc
@carlosdc guter Punkt, ich habe die Antwort aktualisiert, um ein wenig Diskussion über den Konzentrationsparameter aufzunehmen
tdc
1
Nach meiner Erfahrung ist es viel einfacher, einen kontinuierlichen Konzentrationsparameter wie Alpha zu lernen, als die Anzahl der Cluster in einem Modell mit endlichen Gemischen zu bestimmen. Wenn Sie sich an ein Modell mit endlicher Mischung halten und eine Bayes'sche
1
Gute Antwort. Ich würde die Arbeit Revisiting K-Means: New Algorithms via Bayesian Nonparametrics hinzufügen . Dies gibt einen einfachen "kontinuierlichen" Ansatz für K-Mittel. Dann ist es einfach, mithilfe der Optimierung den optimalen Wert zu finden.
Royi
9

Ich benutze die Elbow-Methode :

  • Beginnen Sie mit K = 2 und erhöhen Sie es in jedem Schritt um 1, indem Sie Ihre Cluster und die mit dem Training verbundenen Kosten berechnen. Bei einem bestimmten Wert für K sinken die Kosten dramatisch, und danach erreicht es ein Plateau, wenn Sie es weiter erhöhen. Dies ist der gewünschte K-Wert.

Das Grundprinzip ist, dass Sie danach die Anzahl der Cluster erhöhen, aber der neue Cluster ist sehr nahe an einigen der vorhandenen.

vonPetrushev
quelle
Das klingt nach dem Prinzip, das die L-Methode (siehe meine Antwort) auswertet.
Winwaed
6

Die Clustergröße hängt stark von Ihren Daten ab und davon, wofür Sie die Ergebnisse verwenden. Wenn Sie Ihre Daten zum Aufteilen von Dingen in Kategorien verwenden, versuchen Sie sich vorzustellen, wie viele Kategorien Sie zuerst möchten. Wenn es sich um eine Datenvisualisierung handelt, konfigurieren Sie sie so, dass die Benutzer sowohl die großen als auch die kleineren Cluster sehen können.

Wenn Sie es automatisieren müssen, möchten Sie möglicherweise eine Strafe für die Erhöhung von k hinzufügen und auf diese Weise den optimalen Cluster berechnen. Und dann wiegen Sie nur k, je nachdem, ob Sie eine Tonne Cluster oder nur sehr wenige möchten.

Neuron
quelle
5

Ich habe es geschafft, die "L-Methode" zu verwenden, um die Anzahl von Clustern in einer geografischen Anwendung zu bestimmen (dh im Wesentlichen ein 2d-Problem, obwohl technisch nicht euklidisch).

Die L-Methode wird hier beschrieben: Bestimmen der Anzahl der Cluster / Segmente in hierarchischen Cluster- / Segmentierungsalgorithmen Stan Salvador und Philip Chan

Im Wesentlichen bewertet dies die Anpassung für verschiedene Werte von k. Ein "L" -förmiges Diagramm wird mit dem optimalen k-Wert angezeigt, der durch das Knie im Diagramm dargestellt wird. Eine einfache Berechnung der kleinsten Quadrate mit zwei Linien wird verwendet, um den Kniepunkt zu finden.

Ich fand die Methode sehr langsam, da das iterative k-Mittel für jeden Wert von k berechnet werden muss. Außerdem fand ich, dass k-means am besten mit mehreren Läufen funktioniert und am Ende das Beste auswählt. Obwohl jeder Datenpunkt nur zwei Dimensionen aufwies, konnte kein einfacher pythagoreischer Abstand verwendet werden. Das ist also eine Menge Rechenaufwand.

Ein Gedanke ist, jeden anderen Wert von k (sagen wir) zur Hälfte der Berechnungen zu überspringen und / oder die Anzahl der Iterationen der k-Mittelwerte zu verringern und dann die resultierende Kurve leicht zu glätten, um eine genauere Anpassung zu erzielen. Ich habe diesbezüglich bei StackOverflow - IMHO nachgefragt , die Glättungsfrage bleibt eine offene Forschungsfrage.

winwaed
quelle
4

k

Aber was ist, wenn Ihr Datensatz nicht in das Voronoi-Schema passt?

kk

k

Anony-Mousse
quelle
3
Obwohl die Beschreibung von K-means im ersten Absatz nicht falsch ist, kann es einige Leute irreführen, diese Methode mit der Voronoi-Partitionierung basierend auf den Originaldaten gleichzusetzen . Dies ist nicht der Fall: Die Partition basiert auf den Positionen der Clustermittel, die möglicherweise nicht mit den ursprünglichen Daten übereinstimmen (und in der Regel auch nicht).
whuber
3

Insgesamt können Sie die Anzahl der Cluster in zwei verschiedenen Pfaden auswählen.

  1. Wissensgetrieben: Sie sollten einige Ideen haben, wie viele Cluster Sie aus geschäftlicher Sicht benötigen. Wenn Sie beispielsweise Kunden gruppieren, sollten Sie sich fragen, was ich als Nächstes tun soll, nachdem Sie diese Kunden erhalten haben? Vielleicht werden Sie für verschiedene Cluster unterschiedlich behandelt? (zB Werbung per E-Mail oder Telefon). Wie viele mögliche Behandlungen planen Sie dann? In diesem Beispiel wählen Sie aus, dass 100 Cluster nicht sehr sinnvoll sind.

  2. Datengesteuert: Mehr Cluster sind überpasst und weniger Cluster sind unterpasst. Sie können Daten jederzeit in zwei Hälften teilen und eine Kreuzvalidierung durchführen, um festzustellen, wie viele Cluster gut sind. Beachten Sie, dass Sie beim Clustering immer noch die Verlustfunktion haben, ähnlich wie bei der überwachten Einstellung.

Schließlich sollten Sie in der realen Welt immer wissensbasiert und datenbasiert miteinander kombinieren.

Haitao Du
quelle
2

Da noch niemand darauf hingewiesen hat, dachte ich, ich würde dies teilen. Es gibt eine Methode namens X-means ( siehe diesen Link ), die die richtige Anzahl von Clustern unter Verwendung des Bayesian Information Criterion (BIC) schätzt. Dies wäre im Wesentlichen so, als würde man versuchen, K mit unterschiedlichen Ks zu versuchen, den BIC für jedes K zu berechnen und das beste K auszuwählen. Dieser Algorithmus erledigt dies effizient.

Es gibt auch eine weka- Implementierung, deren Details hier zu finden sind .

Rivu
quelle
0

Ein anderer Ansatz ist die Verwendung eines Evolutionsalgorithmus, dessen Individuen Chromosomen unterschiedlicher Länge aufweisen. Jedes Individuum ist eine Kandidatenlösung: Jedes Individuum trägt die Schwerpunktkoordinaten. Die Anzahl der Zentroide und ihre Koordinaten werden entwickelt, um eine Lösung zu erhalten, die die beste Punktzahl für die Clusterbewertung ergibt.

In diesem Artikel wird der Algorithmus erläutert.

felipeduque
quelle