Warum wird k-means nicht mit Gradientenabstieg optimiert?

14

Ich weiß, dass k-means normalerweise mit Expectation Maximization optimiert wird . Wir könnten jedoch die Verlustfunktion genauso optimieren wie alle anderen!

Ich habe einige Artikel gefunden, die tatsächlich eine stochastische Gradientenabnahme für großräumige k-Mittelwerte verwenden, aber ich konnte meine Frage nicht beantworten.

Weiß jemand, warum das so ist? Liegt es daran, dass die Expectation Maximization schneller konvergiert ? Hat es eine besondere Garantie? Oder ist es ein historischer Grund ?

elsonidoq
quelle
Der Maximierungsschritt steigt bereits auf den Wahrscheinlichkeitsgradienten (abhängig von den vom Erwartungsschritt gewählten Werten), richtig?
David J. Harris
@ DavidJ.Harris Ich glaube nicht, dass das OP bestreitet, dass EM sich so verhält, sondern fragt, warum eine Methode weit verbreitet zu sein scheint und eine andere Methode nicht so häufig. Ihr Kommentar scheint nicht direkt zu sagen, warum EM bevorzugt werden könnte.
Glen_b
1
Hallo @ DavidJ.Harris, es ist wie bei Glen_b, ich verstehe, dass beide Algorithmen entweder die Wahrscheinlichkeit (EM) oder die Log-Wahrscheinlichkeit (Gradientenabstieg) optimieren. Nachdem ich mich bei Google und Freunden umgesehen hatte, kam ich zu diesem Papierlink , ob diese Frage angesprochen wird. Wenn ich es nicht verpasst habe zu verstehen, kommt EM zu einer besseren Lösung als der Gefälleabstieg.
Elsonidoq
Was ist die Zielfunktion für k-means zur Optimierung? Ist es differenzierbar?
Vladislavs Dovgalecs
3
Es ist in den Parametern (Clustermittel) glatt unterscheidbar, aber sicher nicht in den Clusterzuordnungen (die multinomiale Indikatorvariablen sind)?
Ruben van Bergen

Antworten:

7

Wie in der OP erwähnt, ist es möglich, k-Mittelwerte mit Gradientenabstieg zu lösen, und dies kann bei großen Problemen hilfreich sein.

Es gibt sicherlich historische Gründe für die Verbreitung von EM-Algorithmen zur Lösung von k-Mitteln (dh Lloyd's Algorithmus). Lloyd's Algorithmus ist so populär, dass die Leute ihn manchmal "den k-Means-Algorithmus" nennen und vielleicht gar nicht wissen, dass es andere Ansätze gibt. Diese Popularität ist jedoch nicht unbegründet.

Bottou und Bengio (1995) zeigten, dass der Lloyd-Algorithmus der Optimierung der k-Mittelwert-Kostenfunktion nach der Newton-Methode entspricht. Bei allgemeinen Optimierungsproblemen können Methoden zweiter Ordnung wie die Newtonsche Methode schneller konvergieren als Methoden erster Ordnung wie der Gradientenabstieg, da sie Informationen über die Krümmung der Zielfunktion ausnutzen (und Methoden erster Ordnung nicht). In einem Experiment mit dem bekannten Iris-Datensatz zeigten sie, dass der Lloyd-Algorithmus tatsächlich schneller konvergierte als der Gradientenabstieg. Es wäre interessant, diesen Vergleich auf einer größeren Vielfalt von Datensätzen zu sehen.

Verweise:

Bottou und Bengio (1995) . Konvergenzeigenschaften der k-means Algorithmen.

user20160
quelle
2

K bedeutet, dass das Clustering nicht überwacht wird, und die nächste nicht überwachte Technik, die EM verwendet, ist das modellbasierte Clustering (Gaußsche Mischungsmodelle, GMM). Ein ärgerliches Problem mit GMM-modellbasiertem Clustering tritt auf, wenn viele der Merkmale korreliert sind, was in der merkmalsbasierten Kovarianzmatrix (Korrelationsmatrix) nahezu Singularität verursacht. In dieser Situation wird die Likelihood-Funktion instabil, wobei die Zustandsindizes unendlich sind, was dazu führt, dass GMM vollständig zusammenbricht.

Lassen Sie daher die Idee von EM und kNN fallen, da sie auf Kovarianzmatrizen (Korrelationsmatrizen) für unbeaufsichtigte Analysen basiert. Ihre Anfrage zur Optimierung ähnelt stark Sammon-Mapping und klassischer metrischer und nichtmetrischer multidimensionaler Skalierung (MDS). Sammon-Mapping basiert auf Derivaten und Iterationen, während verschiedene Formen von MDS häufig iterative oder einstufige Eigendezusammensetzungen sind, die sich jedoch während einer einstufigen Matrixoperation optimieren lassen.

Rückblick auf Ihre Anfrage: Die Antwort lautet: Es wurde bereits in Sammon-Mapping durchgeführt.

JoleT
quelle