Différence entre les algorithmes k-moyennes standard et sphériques

Je voudrais comprendre quelle est la principale différence de mise en œuvre entre les algorithmes de clustering k-means standard et sphérique.

À chaque étape, k-means calcule les distances entre les vecteurs d'éléments et les centroïdes de cluster, et réaffecte le document à ce cluster, dont le centroïde est le plus proche. Ensuite, tous les centroïdes sont recalculés.

Dans les moyennes k sphériques, tous les vecteurs sont normalisés et la mesure de distance est la dissimilarité du cosinus.

C'est tout, ou il y a autre chose?

La question est:

Quelle est la différence entre les k-moyennes classiques et les k-moyennes sphériques?

K classique signifie:

Dans les k-moyennes classiques, nous cherchons à minimiser une distance euclidienne entre le centre du cluster et les membres du cluster. L'intuition derrière cela est que la distance radiale du centre du cluster à l'emplacement de l'élément devrait "avoir la même similitude" ou "être similaire" pour tous les éléments de ce cluster.

L'algorithme est:

• Définir le nombre de clusters (aka nombre de clusters)
• Initialiser en attribuant au hasard des points dans l'espace aux indices de cluster
• Répétez jusqu'à ce que convergent
  • Pour chaque point, trouvez le cluster le plus proche et attribuez un point au cluster
  • Pour chaque cluster, trouvez la moyenne des points membres et la moyenne du centre de mise à jour
  • L'erreur est la norme de distance des clusters

K sphérique signifie:

Dans les moyennes k sphériques, l'idée est de définir le centre de chaque groupe de sorte qu'il rend à la fois uniforme et minimal l'angle entre les composants. L'intuition est comme regarder les étoiles - les points doivent avoir un espacement constant entre eux. Cet espacement est plus simple à quantifier en tant que "similitude cosinus", mais cela signifie qu'il n'y a pas de galaxies "voie lactée" formant de grandes bandes lumineuses à travers le ciel des données. (Oui, j'essaie de parler à grand-mère dans cette partie de la description.)

Version plus technique:

Pensez aux vecteurs, aux éléments que vous représentez sous forme de flèches d'orientation et de longueur fixe. Il peut être traduit n'importe où et être le même vecteur. ref

L'orientation du point dans l'espace (son angle par rapport à une ligne de référence) peut être calculée en utilisant l'algèbre linéaire, en particulier le produit scalaire.

Si nous déplaçons toutes les données de façon à ce que leur queue soit au même point, nous pouvons comparer les "vecteurs" par leur angle et regrouper ceux-ci en un seul cluster.

Pour plus de clarté, les longueurs des vecteurs sont mises à l'échelle, afin qu'elles soient plus faciles à comparer.

On pourrait y voir une constellation. Les étoiles d'un même cluster sont proches les unes des autres dans un certain sens. Ce sont mes globes oculaires considérés comme des constellations.

La valeur de l'approche générale est qu'elle nous permet de créer des vecteurs qui autrement n'ont pas de dimension géométrique, comme dans la méthode tf-idf, où les vecteurs sont des fréquences de mots dans les documents. Deux mots "et" ajoutés ne correspondent pas à un "le". Les mots sont non continus et non numériques. Ils ne sont pas physiques au sens géométrique, mais nous pouvons les concevoir géométriquement, puis utiliser des méthodes géométriques pour les manipuler. Les k-moyennes sphériques peuvent être utilisées pour se regrouper en fonction des mots.

Ainsi, les données (2d aléatoires, continues) étaient les suivantes:

$$\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}$$

Quelques points:

• Ils se projettent dans une sphère unitaire pour tenir compte des différences de longueur de document.

Travaillons à travers un processus réel et voyons à quel point (mauvais) mon "globe oculaire" était.

La procédure est la suivante:

1. (implicite dans le problème) connecter les queues des vecteurs à l'origine
2. projet sur la sphère unitaire (pour tenir compte des différences de longueur de document)
3. utiliser le clustering pour minimiser la " dissemblance cosinus "

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

(d'autres modifications seront bientôt disponibles)

Liens:

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-means-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