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.
Antworten:
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 .
quelle
K-means is not based on Euclidean distance
Ist 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.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).
quelle