Unterschied zwischen Standard- und sphärischen k-Means-Algorithmen

Ich würde gerne verstehen, was der Hauptunterschied in der Implementierung zwischen Standard- und sphärischen K-Mittel-Clustering-Algorithmen ist.

In jedem Schritt berechnet k-means die Abstände zwischen Elementvektoren und Cluster-Schwerpunkten und ordnet das Dokument diesem Cluster zu, dessen Schwerpunkt der nächste ist. Dann werden alle Zentroide neu berechnet.

Im sphärischen k-Mittel sind alle Vektoren normalisiert, und das Abstandsmaß ist die Kosinusunterschiedlichkeit.

Ist das alles oder gibt es noch etwas anderes?

Die Frage ist:

Was ist der Unterschied zwischen klassischen k-Mitteln und sphärischen k-Mitteln?

Klassisches K-bedeutet:

In klassischen k-Mitteln versuchen wir, einen euklidischen Abstand zwischen dem Clusterzentrum und den Mitgliedern des Clusters zu minimieren. Die Intuition dahinter ist, dass der radiale Abstand vom Clusterzentrum zum Elementstandort für alle Elemente dieses Clusters "gleich" oder "ähnlich" sein sollte.

Der Algorithmus ist:

• Festlegen der Anzahl der Cluster (auch Clusteranzahl genannt)
• Initialisierung durch zufällige Zuweisung von Punkten im Raum zu Cluster-Indizes
• Wiederholen, bis sie zusammenlaufen
  • Suchen Sie für jeden Punkt den nächsten Cluster und weisen Sie dem Cluster einen Punkt zu
  • Ermitteln Sie für jeden Cluster den Mittelwert der Mitgliederpunkte und den Mittelwert des Update Centers
  • Der Fehler ist die Norm der Entfernung von Clustern

Kugelförmiges K-bedeutet:

Bei sphärischen k-Mitteln besteht die Idee darin, den Mittelpunkt jedes Clusters so festzulegen, dass der Winkel zwischen den Komponenten sowohl gleichmäßig als auch minimal wird. Die Intuition ist wie das Betrachten von Sternen - die Punkte sollten einen gleichmäßigen Abstand voneinander haben. Dieser Abstand ist einfacher als "Cosinus-Ähnlichkeit" zu quantifizieren, bedeutet jedoch, dass es keine "Milchstraße" -Galaxien gibt, die große helle Bereiche über dem Himmel der Daten bilden. (Ja, ich versuche in diesem Teil der Beschreibung mit Oma zu sprechen .)

Weitere technische Version:

Denken Sie an Vektoren, die Objekte, die Sie als Pfeile mit Ausrichtung und fester Länge darstellen. Es kann überall übersetzt werden und derselbe Vektor sein. ref

Die Orientierung des Punktes im Raum (sein Winkel von einer Referenzlinie) kann unter Verwendung der linearen Algebra, insbesondere des Punktproduktes, berechnet werden.

Wenn wir alle Daten so verschieben, dass sich ihr Ende am selben Punkt befindet, können wir "Vektoren" nach ihrem Winkel vergleichen und ähnliche Daten in einem einzigen Cluster gruppieren.

Zur Verdeutlichung sind die Längen der Vektoren skaliert, so dass sie leichter mit dem "Augapfel" verglichen werden können.

Man könnte es sich als eine Konstellation vorstellen. Die Sterne in einem einzelnen Cluster sind in gewisser Weise nahe beieinander. Dies sind meine Augapfel als Sternbilder.

Der Wert des allgemeinen Ansatzes besteht darin, dass wir Vektoren konstruieren können, die ansonsten keine geometrische Dimension haben, wie bei der tf-idf-Methode, bei der die Vektoren Worthäufigkeiten in Dokumenten sind. Zwei hinzugefügte "und" Wörter entsprechen nicht einem "das". Wörter sind nicht fortlaufend und nicht numerisch. Sie sind im geometrischen Sinne nicht physisch, aber wir können sie geometrisch erfinden und dann geometrische Methoden anwenden, um sie zu handhaben. Sphärische k-Mittel können verwendet werden, um basierend auf Wörtern Cluster zu bilden.

Die (2d zufälligen, kontinuierlichen) Daten waren also:

$$\begin{bmatrix} x1&y1&x2&y2&group\\ 0&-0.8&-0.2013&-0.7316&B\\ -0.8&0.1&-0.9524&0.3639&A\\ 0.2&0.3&0.2061&-0.1434&C\\ 0.8&0.1&0.4787&0.153&B\\ -0.7&0.2&-0.7276&0.3825&A\\ 0.9&0.9&0.748&0.6793&C\\ \end{bmatrix}$$

Ein paar Punkte:

• Sie projizieren auf eine Einheitskugel, um Unterschiede in der Dokumentlänge zu berücksichtigen.

Lassen Sie uns einen tatsächlichen Prozess durcharbeiten und sehen, wie (schlecht) mein "Augenzwinkern" war.

Das Verfahren ist:

1. (implizit im Problem) Verbinde Vektoren-Schwänze am Ursprung
2. Projizieren auf eine Einheitskugel (um Unterschiede in der Dokumentlänge zu berücksichtigen)
3. Verwenden Sie Clustering, um die " Cosinus-Unähnlichkeit " zu minimieren.

$$J = \sum_{i} d \left( x_{i},p_{c\left( i \right)} \right)$$ wobei
$$d \left( x,p \right) = 1- cos \left(x,p\right) = \frac{\langle x,p \rangle}{\left \|x \right \|\left \|p \right \|}$$

(weitere Änderungen folgen in Kürze)

Links:

1. http://epub.wu.ac.at/4000/1/paper.pdf
2. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.111.8125&rep=rep1&type=pdf
3. http://www.cs.gsu.edu/~wkim/index_files/papers/refinehd.pdf
4. https://www.jstatsoft.org/article/view/v050i10
5. http://www.mathworks.com/matlabcentral/fileexchange/32987-the-spherical-k-meanss-algorithm
6. https://ocw.mit.edu/courses/sloan-school-of-management/15-097-prediction-machine-learning-and-statistics-spring-2012/projects/MIT15_097S12_proj1.pdf