Convergence dans la méthode k-means de Hartigan-Wong et d'autres algorithmes

J'ai essayé de comprendre les différents algorithmes de clustering k-means principalement qui sont implémentés dans le statspackage du Rlangage.

Je comprends l'algorithme de Lloyd et l'algorithme en ligne de MacQueen. La façon dont je les comprends est la suivante:

Algorithme de Lloyd:

Initialement, on choisit des observations aléatoires «k» qui serviront de centroïdes aux clusters «k». Ensuite, les étapes suivantes se produisent dans l'itération jusqu'à ce que les centroïdes convergent.

1. La distance euclidienne entre chaque observation et les centroïdes choisis est calculée.
2. Les observations les plus proches de chaque centroïde sont marquées dans des seaux «k».
3. La moyenne de toutes les observations dans chaque seau sert de nouveaux centroïdes.
4. Les nouveaux centroïdes remplacent les anciens centroïdes et l'itération revient à l'étape 1 si les anciens et les nouveaux centroïdes n'ont pas convergé.

Les conditions de convergence sont les suivantes: l'ancien et le nouveau centroïdes sont exactement identiques, la différence entre les centroïdes est faible (de l'ordre de 10 ^ -3) ou le nombre maximal d'itérations (10 ou 100) est atteint.

Algorithme de MacQueen:

Il s'agit d'une version en ligne où les premières instances «k» sont choisies comme centroïdes.

Ensuite, chaque instance est placée dans des compartiments en fonction du centroïde le plus proche de cette instance. Le centroïde respectif est recalculé.

Répétez cette étape jusqu'à ce que chaque instance soit placée dans le compartiment approprié.

Cet algorithme n'a qu'une seule itération et la boucle continue pour les instances 'x'

Algorithme de Hartigan-Wong:

1. Attribuez tous les points / instances à des compartiments aléatoires et calculez le centroïde respectif.
2. À partir de la première instance, recherchez le centroïde le plus proche et assignez ce compartiment. Si le compartiment a changé, recalculez les nouveaux centroïdes, c'est-à-dire le centroïde du nouveau compartiment affecté et le centroïde de l'ancienne affectation de compartiment, car ce sont deux centroïdes affectés par la modification.
3. Parcourez tous les points et obtenez de nouveaux centroïdes.
4. Effectuez une deuxième itération des points 2 et 3 qui effectue une sorte d'opération de nettoyage et réaffecte les points parasites aux bons compartiments.

Cet algorithme effectue donc 2 itérations avant de voir le résultat de la convergence.

Maintenant, je ne sais pas si ce que je pense au point 4 de l'algorithme Hartigan-Wong est la bonne méthode de l'algorithme. Ma question est, si la méthode suivante pour Hartigan-Wong est la bonne méthode pour implémenter k-means? Y a-t-il seulement deux itérations pour cette méthode? sinon, quelle est la condition de convergence (quand s'arrêter)?

Une autre explication possible de la mise en œuvre est ce que je comprends.

1. Attribuez tous les points / instances à des compartiments aléatoires et calculez le centroïde respectif.
2. À partir de la première instance, recherchez le centroïde le plus proche et affectez ce compartiment. Si le compartiment a changé, recalculez les nouveaux centroïdes, c'est-à-dire le centroïde du nouveau compartiment affecté et le centroïde de l'ancienne affectation de compartiment, car ce sont deux centroïdes affectés par la modification.
3. Une fois qu'il y a un changement dans le compartiment pour n'importe quel point, revenez à la première instance et répétez les étapes à nouveau.
4. L'itération se termine lorsque toutes les instances sont itérées et qu'aucun des points ne change de compartiment.

De cette façon, de nombreuses itérations recommencent depuis le début de l'ensemble de données à chaque fois qu'une instance change de compartiment.

Toutes les explications seraient utiles et veuillez me faire savoir si ma compréhension de l'une de ces méthodes est erronée.

L'algorithme de HW, issu de l'article de 1979, prend en entrée les grappes initiales. Cependant, les auteurs suggèrent une méthode pour les obtenir dans leur dernière section. Ils écrivent qu'il est garanti qu'aucun cluster ne sera vide après l'affectation initiale dans le sous-programme . Il se déroule comme suit:

1. Calculez la moyenne globale .$\bar{x}$
2. Ordonnez les observations par rapport à leur distance à , c'est-à-dire (dans l'ordre croissant, je suppose?).$\bar{x}$$||x_i - \bar{x}||_2$
3. Prenez les points en position , où , comme centroïdes initiaux. ( très probablement référence à la fonction floor, d'où le au début.)$\{ 1 + (L-1) [M/K] \}$$L=1, \dots, K$$[\ \cdot\ ]$$1$

Quant à l'algorithme principal, il est décrit dans un article intitulé K-Means de Hartigan versus K-Means de Lloyd-Est-il temps de changer? par N Slonim, E Aharoni, K Crammer, publié en 2013 par AJCAI . Notez que cette version utilise simplement une partition initiale aléatoire. Cela se passe comme suit.

Pour les vecteurs et un nombre cible de clusters ,$x \in \mathcal{X}$$K$

1. $\mathcal{C}$$\mathcal{X}$$K$$C \in \mathcal{C}$$v_C$

2. $\mathcal{X}$$x \in \mathcal{X}$

   $s = 1$

   $x$$C$$C^{-} = C \setminus \{ x \}$

   $$\begin{align*} C^+ = \Big\{ \mathrm{argmin}_{C^* \in (\mathcal{C} \setminus C) \cup C^{-}}\ \frac{1}{n} d(x,v_C^*) + \frac{1}{n} \sum_{y \in C^*} [d(y,v_{C^* \cup x}) - d(y,v_{C^*})] \Big\} \cup \{ x \} \end{align*}$$

   $C^{+} \neq C$$C \leftarrow C^{-}$$C^* \leftarrow C^{+}$$v_{C}$$v_{C^*}$$s \leftarrow 0$

3. $s=0$

$C^*$$\mathrm{argmin}$$x$$C^*$$d$$v_C$$v_{C^* \cup \{x \}}$

Je pense que les réponses à toutes vos questions sont implicites dans l'algorithme ci-dessus ... Cependant, je dois encore m'assurer que cette implémentation de l'algorithme est standard . En particulier s'il s'agit de celui implémenté dans R. Tous les commentaires / modifications sont les bienvenus.