Warum wird bei der Clustering-Methode (K-Mittelwert) nur der Mittelwert verwendet?

8

Bei Clustering-Methoden wie K-means ist der euklidische Abstand die zu verwendende Metrik. Daher berechnen wir nur die Mittelwerte innerhalb jedes Clusters. Anschließend werden die Elemente anhand ihres Abstands zu jedem Mittelwert angepasst.

Ich habe mich gefragt, warum die Gaußsche Funktion nicht als Metrik verwendet wird. Anstatt zu verwenden xi -mean(X), können wir verwenden exp(- (xi - mean(X)).^2/std(X).^2). Somit wird nicht nur die Ähnlichkeit zwischen den Clustern gemessen (Mittelwert), sondern auch die Ähnlichkeit innerhalb des Clusters berücksichtigt (Standard). Entspricht dies auch dem Gaußschen Mischungsmodell ?

Es ist hier jenseits meiner Frage, aber ich denke , dass eine Mittelwertverschiebung dieselbe Frage wie oben aufwerfen kann.

lennon310
quelle
1
Dieser Thread kann hilfreich sein. stats.stackexchange.com/questions/76866/… Durchsuchen Sie Ihre Tags nach anderen relevanten Fragen.
DL Dahly
@ DLLahahly Danke Dahly. Können wir EM-basiertes GMM als gewichtetes k-Mittel betrachten (mit unterschiedlichen Gewichten für Varianzen)?
Lennon310
Es ist nicht so, wie ich es mir vorstellen würde. Ich sehe k-means eher als GMM, bei dem die Varianzen auf Null beschränkt sind.
DL Dahly

Antworten:

5

Es gibt buchstäblich Tausende von k-Mittel-Variationen . Einschließlich weicher Zuordnung, Varianz und Kovarianz (normalerweise als Gaußsche Mischungsmodellierung oder EM-Algorithmus bezeichnet).

Ich möchte jedoch auf einige Dinge hinweisen:

  • K-means basiert nicht auf der euklidischen Entfernung. Es basiert auf der Varianzminimierung . Da die Varianz die Summe der euklidischen Quadratabstände ist, ist die minimale Varianzzuweisung diejenige mit dem kleinsten euklidischen Quadrat, und die Quadratwurzelfunktion ist monoton. Aus Effizienzgründen ist es tatsächlich klüger, die euklidische Entfernung nicht zu berechnen (sondern die Quadrate zu verwenden).

  • Wenn Sie eine andere Distanzfunktion in k-means einstecken, hört die Konvergenz möglicherweise auf. Sie müssen in beiden Schritten dasselbe Kriterium minimieren . Der zweite Schritt ist die Neuberechnung der Mittel. Das Schätzen des Zentrums unter Verwendung des arithmetischen Mittels ist ein Schätzer der kleinsten Quadrate und minimiert die Varianz. Da beide Funktionen die Varianz minimieren, müssen k-Mittel konvergieren. Wenn Sie die Konvergenz mit anderen Entfernungen sicherstellen möchten, verwenden Sie PAM (Partitionierung um Medoide. Das Medoid minimiert die Entfernungen innerhalb des Clusters für beliebige Entfernungsfunktionen.)

Aber am Ende sind k-means und alle seine Variationen meiner Meinung nach eher eine Optimierung (oder genauer gesagt ein Vektorquantisierungsalgorithmus ) als tatsächlich ein Clusteranalysealgorithmus. Sie werden die Struktur nicht wirklich "entdecken". Sie werden Ihre Daten in k Partitionen massieren. Wenn Sie ihnen einheitliche Daten ohne Struktur geben, die über die Zufälligkeit hinausgeht, findet k-means immer noch so viele "Cluster", wie Sie möchten. k-means gibt gerne Ergebnisse zurück, die im Wesentlichen zufällig sind .

Hat aufgehört - Anony-Mousse
quelle
1
+1. Die Behauptung, dass K-means kein Clustering ist, scheint jedoch zu radikal und zu "Data-Mining" zu sein. Historisch gesehen ist K-means eine klassische Partitionierungsclusteranalyse. Die Tatsache, dass "unstrukturierte" Daten glücklich partitioniert werden, schließt sie nicht aus dem Bereich des Clusters aus: Viele Arten von Analysen können sozusagen missbraucht werden und zu dummen Ergebnissen führen.
ttnphns
Noch ein Punkt: K-means is not based on Euclidean distanceIst nicht genug klarer Platz in Ihrer Antwort. Du und ich hatte Diskussionen darüber in der Vergangenheit , und ich zeigte , dass Varianz Minimierung wird auf die Summe der im Cluster paarweise euklidische d ^ 2 bezogen.
ttnphns
Ich stelle die Beziehung zur euklidischen Distanz durch Varianz klar dar. Die Sache ist, Sie müssen die Varianz durch eine andere Kennzahl ersetzen (dann Zuordnung auswählen und entsprechend aktualisieren), nicht euklidisch austauschen und hoffen, dass der Mittelwert weiterhin aussagekräftig bleibt.
Hat aufgehört - Anony-Mousse
Historisch gesehen wurde k-means von Lloyd als " Quantisierung der kleinsten Quadrate in PCM" veröffentlicht. Ebenso hatte Steinhaus den Wunsch, eine Quantisierung durchzuführen. Das erklärt gut, warum SSQ verwendet wird, da SSQ der quadratische Fehler der Diskretisierung ist. MacQueen erwähnt die Clusteranalyse als Anwendung des Algorithmus, schlägt jedoch vor, eine modifizierte Version des Algorithmus zu verwenden, mit der Cluster nach Wunsch hinzugefügt oder entfernt werden können (ab diesem Zeitpunkt ist sie tatsächlich mehr als nur eine Quantifizierung).
Hat aufgehört - Anony-Mousse
Der Punkt, den ich am Ende ansprechen möchte , ist die Vektorquantisierung , nicht nur das "Clustering", da die Clusterforschung in jüngster Zeit von Data-Mining-Gesichtspunkten dominiert wird (und die meiste Zeit nicht mehr auf k-Mitteln basiert ). . Die Vektorquantisierung kann der viel bessere (weil viel präzisere) Suchbegriff sein .
Hat aufgehört - Anony-Mousse
3

Es gibt viele verschiedene Clustering-Techniken, und K-means ist nur ein Ansatz. Wie DL Dahly kommentierte, können EM-Algorithmen auf die von Ihnen beschriebene Weise zum Clustering verwendet werden. Es ist erwähnenswert, dass der Hauptunterschied zwischen K-Mittelwerten und der Verwendung von EM mit einem Guassian-Mischungsmodell für die Clusterbildung die Form der Cluster ist: Der Schwerpunkt nähert sich immer noch dem Mittelwert der Punkte in der Gruppe an, aber K-Mittelwerte ergeben a sphärischer Cluster, während ein Gaußscher Kern ein Ellipsoid ergibt.

Hierarchisches Clustering verwendet einen völlig anderen Ansatz. Dichtebasiertes Clustering wird durch eine ähnliche Heuristik wie mittelbasiertes Clustering motiviert, liefert jedoch offensichtlich unterschiedliche Ergebnisse. Es gibt viele Clustering-Techniken, die keinen Mittelwert berücksichtigen.

Wirklich, wenn es darauf ankommt, ist die Wahl des Algorithmus eine Funktion der Problemdomäne und des Experimentierens (dh zu sehen, was funktioniert).

David Marx
quelle
Danke David. Ich denke, Hierarchical liefert unterschiedliche Ergebnisse von kmeans, da die Definitionen der Entfernung zwischen zwei Clustern nicht gleich sind. Es ist möglicherweise nicht einfach zu bestimmen, welche Metrik verwendet werden soll und ob die Varianz einbezogen werden soll. Es scheint, als hätten verschiedene Personengruppen ihre eigenen Metriken für ihr eigenes Problem entwickelt. Die Methode lieferte einem solchen Problem nur ein gutes Ergebnis, es fehlte jedoch die theoretische Unterstützung für die Option von Clustering-Methoden.
Lennon310