Warum verwendet der k-means Clustering-Algorithmus nur die euklidische Distanzmetrik?

62

Gibt es einen bestimmten Zweck in Bezug auf Effizienz oder Funktionalität, warum der k-means-Algorithmus zum Beispiel keine Cosinus- (Dis-) Ähnlichkeit als Distanzmetrik verwendet, sondern nur die euklidische Norm verwenden kann? Wird die K-means-Methode im Allgemeinen eingehalten und korrekt sein, wenn andere Abstände als Euklidisch berücksichtigt oder verwendet werden?

[Ergänzung von @ttnphns. Die Frage ist zweifach. "(Nicht-) Euklidische Entfernung" kann die Entfernung zwischen zwei Datenpunkten oder die Entfernung zwischen einem Datenpunkt und einem Clusterzentrum betreffen. Bisher wurde versucht, in den Antworten auf beide Arten zu reagieren.]

neugierig
quelle
Diese Frage wurde ungefähr 10 mal bereits auf stackoverflow und dieser Seite gestellt. Bitte benutzen Sie die Suchfunktion.
Anony-Mousse
3
@ Anony-Mousse: Auch wenn ich Ihnen vollkommen zustimme und kürzlich auf SO ein paar Flaggen gehisst habe, finde ich den Mangel an doppelten Abschlüssen bei den meisten dieser Fragen beunruhigend.
Nikana Reklawyks
4
Dies ist die Seite, die zuerst aufgerufen wird, wenn Sie über dieses Thema googeln.
Haripkannan

Antworten:

62

Das K-Means-Verfahren - eine Vektorquantisierungsmethode, die häufig als Clustering-Methode verwendet wird - verwendet (im Gegensatz zu hierarchischen und einigen anderen Clustern, die willkürliches Näherungsmaß zulassen) überhaupt nicht explizit paarweise Abstände s / w-Datenpunkte . Es läuft darauf hinaus, dem nächstgelegenen Schwerpunkt wiederholt Punkte zuzuweisen, wobei der euklidische Abstand von Datenpunkten zu einem Schwerpunkt verwendet wird . K-Means basiert jedoch implizit auf paarweisen euklidischen Abständen von s / w Datenpunkten, da die Summe der quadratischen Abweichungen vom Schwerpunkt gleich der Summe der paarweisen quadratischen euklidischen Abstände geteilt durch die Anzahl der Punkte ist. Der Begriff "Schwerpunkt" stammt selbst aus der euklidischen Geometrie. Es ist ein multivariates Mittel im euklidischen Raum. Im euklidischen Raum geht es um euklidische Entfernungen. Nichteuklidische Entfernungen erstrecken sich im Allgemeinen nicht über den euklidischen Raum. Deshalb gilt K-Means nur für euklidische Entfernungen.

Ein euklidischer Abstand zwischen zwei Datenpunkten kann jedoch auf verschiedene Weise dargestellt werden . Beispielsweise ist es eng mit dem Kosinus- oder Skalarprodukt s / w der Punkte verknüpft . Wenn Sie Kosinus, Kovarianz oder Korrelation haben, können Sie diese immer (1) in (quadratische) euklidische Distanz transformieren und dann (2) Daten für diese Matrix von euklidischen Distanzen erstellen (mithilfe von Hauptkoordinaten oder anderen Formen von Metriken) Multidimensionales Skalieren), um (3) diese Daten in das K-Means-Clustering einzugeben. Daher ist es möglich , K-Mittel mit paarweisen Kosinussen oder dergleichen "arbeiten" zu lassen; Tatsächlich existieren solche Implementierungen von K-Means-Clustering. Siehe auch zur Implementierung von "K-means for distance matrix".

Es ist natürlich möglich , K-Mittel so zu programmieren, dass es direkt auf der Quadratmatrix der paarweisen euklidischen Abstände berechnet. Es funktioniert jedoch nur langsam, und daher ist es effizienter, Daten für diese Entfernungsmatrix zu erstellen (Konvertieren der Entfernungen in Skalarprodukte usw. - der im vorherigen Absatz beschriebene Durchgang) und dann das Standardverfahren mit K-Mitteln anzuwenden zu diesem Datensatz.

Bitte beachten Sie, dass ich über das Thema diskutiert habe, ob die euklidische oder die nichtuklidische Ungleichheit zwischen Datenpunkten mit K-means kompatibel ist. Es hängt mit der Frage zusammen, ob nicht-nuklidische Abweichungen vom Schwerpunkt (im weiteren Sinne, Zentrum oder Quasizentrum) in K-Mittel oder modifizierte "K-Mittel" aufgenommen werden können.

Siehe verwandte Frage K-means: Warum maximiert die Minimierung von WCSS den Abstand zwischen Clustern? .

ttnphns
quelle
Können Sie einige Beispiele für den Ansatz anführen, den Sie erwähnen?
neugierig
4
@Douglas, bitte. Ich sagte , dass k-Mittel nicht nicht verwenden paarweise Distanzen. Es ist klar angegeben. Dabei werden Abstände zum Schwerpunkt verwendet. Das bedeutet aber automatisch, dass es implizit mit der Aufgabe verbunden ist, paarweise Abstände innerhalb von Clustern zu optimieren.
ttnphns
1
@ttnphns: In der Anzahl der Zeichen, die Sie geschrieben haben But a Euclidean distance b/w two data points can be represented in a number of alternative ways. For example, it is closely tied with cosine or scalar product b/w the points. If you have cosine, or covariance, or correlation, you can always (1) transform it to (squared) Euclidean distance, könnten Sie genauso leicht geschrieben haben: distance(x,y) = 1 - cosine_sim(x,y)oder etwas ähnlich Markiges und Informatives.
Stackoverflowuser2010
1
Dies sieht nach berechtigter und konstruktiver Kritik aus: Es ist besser, Informationen direkt in Ihren Beitrag aufzunehmen, als sich auf einen Link zu verlassen. und es ist normalerweise besser, explizit als vage zu sein. (cc @stackoverflowuser)
whuber
3
Was streiten Sie? Dass es in diesem Fall besser ist, sich auf einen Link zu verlassen oder vage zu sein oder beides? Und warum?
Whuber
46

Siehe auch @ttnphns answer für eine Interpretation von k-Mitteln, die tatsächlich punktweise euklidische Abstände beinhalten.

Die Art und Weise, wie k-means konstruiert ist , basiert nicht auf Entfernungen .

K-means minimiert die Varianz innerhalb des Clusters. Betrachtet man nun die Definition der Varianz, so ist sie identisch mit der Summe der quadrierten euklidischen Abstände vom Zentrum. (@ttnphns Antwort bezieht sich auf paarweise euklidische Entfernungen!)

Die Grundidee von k-means besteht darin , quadratische Fehler zu minimieren . Es gibt hier keine "Distanz".

Warum es nicht richtig ist, willkürliche Abstände zu verwenden: weil k-means möglicherweise aufhört, mit anderen Abstandsfunktionen zusammenzuarbeiten . Der allgemeine Konvergenznachweis lautet wie folgt: Der Zuweisungsschritt und der mittlere Aktualisierungsschritt optimieren beide dasselbe Kriterium. Es ist eine endliche Anzahl von Zuordnungen möglich. Daher muss es nach einer endlichen Anzahl von Verbesserungen konvergieren. Um diesen Beweis für andere Abstandsfunktionen zu verwenden, müssen Sie zeigen, dass der Mittelwert (Anmerkung: k- bedeutet ) auch Ihre Abstände minimiert.

Wenn Sie nach einer Manhattan-Distanz-Variante von k-means suchen, gibt es k-Mediane. Weil der Median ein bekannter bester L1-Schätzer ist.

Wenn Sie beliebige Distanzfunktionen wünschen, schauen Sie sich k-medoids an (auch bekannt als: PAM, Partitionierung um Medoids). Das Medoid minimiert beliebige Abstände (weil es als Minimum definiert ist ) und es gibt auch nur eine begrenzte Anzahl möglicher Medoide. Es ist jedoch viel teurer als der Durchschnitt.

Anony-Mousse
quelle
Aber im ersten Schritt von k-means wird jeder Punkt mit der nächsten euklidischen Entfernung zum Schwerpunkt des Clusters in den Cluster gesetzt ... Es gibt also eine Entfernungsmetrik
neugierig,
@AnonyMousse @ttnphns answer refers to pairwise Euclidean distances!In meiner Antwort, 1. Absatz, verweise ich eindeutig sowohl auf „SS - Fehler“ (direkt) und „paarweise d ^ 2“ (implizite) Interpretationen.
TTNPHNS
3
Ich stimme deiner Antwort zu. Beachten Sie, dass Ihr Betriebskonto k-means may stop converging with other distance functionsmeiner Theorie entspricht Non-euclidean distances will generally not span euclidean space.
TTNPHNS
sehr gute erklärung. Ich habe nie einen zweiten Gedanken über die euklidische Distanz gemacht und nicht bemerkt, dass dies tatsächlich die Summe der Quadrate des Withing Clusters minimiert.
Verena Haunschmid
Ich kann immer noch nicht verstehen, warum der Mittelwert Entfernungen in Bezug auf euklidische Entfernungen minimiert und in Bezug auf den Kosinus nicht als Teil des Beweises
neugierig am
9

Ich mag hier etwas umständlich sein, aber K-means ist der Name eines bestimmten Algorithmus, der Datenpunkten Bezeichnungen zuweist, so dass innerhalb von Clustern Abweichungen minimiert werden, und es ist nicht der Name für eine "allgemeine Technik".

Der K-Means-Algorithmus wurde unabhängig von mehreren Feldern vorgeschlagen, wobei starke Interpretationen auf das Feld anwendbar sind. Es stellt sich nur schön heraus, dass es auch eine euklidische Entfernung zum Zentrum gibt. Für eine kurze Geschichte von K-means lesen Sie bitte Data Clustering: 50 Jahre jenseits von K-means

Es gibt eine Vielzahl anderer Cluster-Algorithmen, die andere Metriken als Euklidisch verwenden. Der allgemeinste mir bekannte Fall ist die Verwendung von Bregman-Divergenzen zur Clusterbildung, wobei Euklidisch ein Sonderfall ist.

user1669710
quelle
"andere Metriken als euklidische" Ich bin vielleicht etwas pedantischer, aber diese Abweichungen sind im Allgemeinen keine Metriken :)
mic
wahr :); Ich sollte wahrscheinlich die Antwort bearbeiten.
user1669710
8

Da dies anscheinend jetzt eine kanonische Frage ist und hier noch nicht erwähnt wurde:

Rdφ:RpHdd(X,y)=φ(X)-φ(y)H{φ(Xich)}φk(X,y)=φ(X),φ(y)H

In dieser Situation können wir im Standard (Lloyd's) k-means-Algorithmus ihren Clustern leicht Punkte zuweisen, aber wir repräsentieren die Clusterzentren implizit (als lineare Kombinationen der Eingabepunkte im Hilbert-Raum). Um die beste Darstellung im Eingaberaum zu finden, müsste ein Fréchet-Mittelwert gefunden werden , was ziemlich teuer ist. So ist es einfach, Cluster-Zuweisungen mit einem Kernel zu erhalten, und schwieriger, die Mittel dafür zu finden.

In der folgenden Abhandlung wird dieser Algorithmus erörtert und auf die spektrale Clusterbildung bezogen:

I. Dhillon, Y. Guan und B. Kulis. Kernel k-means, Spectral Clustering und Normalized Cuts. KDD 2005.

Dougal
quelle
Ich verstehe nicht, wie der Kernel-Trick mit Lloyd's Algorithmus verwendet werden kann. Es scheint mir, dass wir zur Berechnung eines Schwerpunkts (auch implizit im Hilbert-Raum) die explizite Abbildung φ (x_i) benötigen werden. Für die Zuweisung von Punkten zu Clustern benötigen wir nur den Kernel, aber für die Neuberechnung von Zentroiden kommen wir nicht nur mit dem Kernel durch, da der Schwerpunkt der Mittelwert des diesem Cluster zugewiesenen {φ (x_i)} ist. Vermisse ich etwas?
user2428107
1nichjCichφ(Xj)Xφ(X)-1nichjCichφ(Xj)2=k(X,X)+1nich2j,jk(Xj,Xj)-2nichjk(X,Xj)
5

Ich habe hier viele interessante Kommentare gelesen, aber lassen Sie mich hinzufügen, dass Matlabs "persönliche" Implementierung von k-means 4 nicht-euklidische Abstände [zwischen Datenpunkten und Clusterzentren] unterstützt. Der einzige Kommentar aus der Dokumentation, den ich dazu sehen kann, ist:

Abstandsmaß im p-dimensionalen Raum, das zur Minimierung verwendet wird und als durch Kommas getrenntes Paar aus 'Abstand' und einer Zeichenfolge angegeben wird.

kmeans berechnet die Schwerpunktcluster für die verschiedenen unterstützten Entfernungsmessungen unterschiedlich. Diese Tabelle fasst die verfügbaren Abstandsmaße zusammen. In den Formeln ist x eine Beobachtung (dh eine Reihe von X) und c ist ein Schwerpunkt (ein Reihenvektor).

Dann folgt eine Liste der Funktionen von cund x. Wenn man bedenkt, dass dies pdie Dimensionalität der Eingabedaten ist, scheint es, dass keine euklidische Einbettung im Voraus durchgeführt wird.

Übrigens habe ich in der Vergangenheit Matlabs k-means mit Korrelationsabstand verwendet und es hat (nicht überraschend) das getan, was es tun sollte.

Francesco Napolitano
quelle
2
cosinecorrelationcityblockL1hammingcityblock
@Dougal, Wie wird der Median im Algorithmus berücksichtigt? Ändert es k- means nicht in ein grundsätzlich anderes Algo?
TTNPHNS
1
Beachten Sie auch, dass für Binärdaten "Hamming-Abstand" = Stadtblock = Quadratischer euklidischer Abstand.
TTNPHNS
1
=L22=L1
1
@Dougal, Beachten Sie, dass die mit verknüpfte Matlab-Prozedur verschiedene Abstände zwischen einem Datenpunkt und dem Clusterzentrum angibt. Das ist nicht dasselbe wie paarweise Entfernungen.
TTNPHNS
2

Von hier :

Bildbeschreibung hier eingeben

Betrachten wir zwei Dokumente A und B, die durch die Vektoren in der obigen Abbildung dargestellt werden. Der Kosinus behandelt beide Vektoren als Einheitsvektoren, indem er sie normalisiert. Auf diese Weise erhalten Sie ein Maß für den Winkel zwischen den beiden Vektoren. Es liefert zwar ein genaues Maß für die Ähnlichkeit, jedoch ohne Rücksicht auf die Größe. Die Größenordnung ist jedoch ein wichtiger Faktor bei der Berücksichtigung von Ähnlichkeiten.

DL Dahly
quelle
Dies ist eine allgemeine Antwort. Es erklärt nicht, warum es in k-means keine Kosinusähnlichkeit gibt. Zum Beispiel in hierarchischen Clustern wird es häufig verwendet
neugierig am
3
@DLDahly: Manchmal ist die Größe wichtig, manchmal ist es das Rauschen. Es hängt vom Forschungsgebiet ab und ist ein Thema der Datenstandardisierung.
TTNPHNS