Convergencia en el método k-means de Hartigan-Wong y otros algoritmos

He estado tratando de entender los diferentes algoritmos de agrupación de k-means que se implementan principalmente en el statspaquete del Rlenguaje.

Entiendo el algoritmo de Lloyd y el algoritmo en línea de MacQueen. La forma en que los entiendo es la siguiente:

Algoritmo de Lloyd:

Inicialmente, se eligen observaciones aleatorias 'k' que servirán como centroides de los grupos 'k'. Luego, los siguientes pasos ocurren en iteración hasta que los centroides convergen.

1. Se calcula la distancia euclidiana entre cada observación y los centroides elegidos.
2. Las observaciones más cercanas a cada centroide están etiquetadas dentro de los cubos 'k'.
3. La media de todas las observaciones en cada segmento sirve como nuevos centroides.
4. Los nuevos centroides reemplazan a los antiguos centroides y la iteración vuelve al paso 1 si los viejos y nuevos centroides no han convergido.

Las condiciones para converger son las siguientes: los centroides antiguos y nuevos son exactamente idénticos, la diferencia entre los centroides es pequeña (del orden de 10 ^ -3) o se alcanza el número máximo de iteraciones (10 o 100).

Algoritmo de MacQueen:

Esta es una versión en línea donde las primeras instancias 'k' se eligen como centroides.

Luego, cada instancia se coloca en cubos según el centroide más cercano a esa instancia. El centroide respectivo se recalcula.

Repita este paso hasta que cada instancia se coloque en el cubo apropiado.

Este algoritmo solo tiene una iteración y el ciclo continúa para instancias 'x'

Algoritmo de Hartigan-Wong:

1. Asigne todos los puntos / instancias a cubos aleatorios y calcule el centroide respectivo.
2. A partir de la primera instancia, encuentre el centroide más cercano y evalúe ese cubo. Si el depósito cambió, vuelva a calcular los nuevos centroides, es decir, el centroide del nuevo depósito asignado y el centroide de la asignación anterior del recipiente, ya que esos son dos centroides que se ven afectados por el cambio
3. Recorre todos los puntos y obtén nuevos centroides.
4. Realice una segunda iteración de los puntos 2 y 3 que realice una especie de operación de limpieza y reasigne puntos perdidos para corregir los cubos.

Entonces este algoritmo realiza 2 iteraciones antes de que veamos el resultado de convergencia.

Ahora, no estoy seguro de si lo que pienso en el punto 4 del algoritmo Hartigan-Wong es el método correcto del algoritmo. Mi pregunta es, si el siguiente método para Hartigan-Wong es el método correcto para implementar k-means? ¿Hay solo dos iteraciones para este método? Si no, ¿cuál es la condición para la convergencia (cuándo parar)?

Otra posible explicación de implementación es lo que entiendo.

1. Asigne todos los puntos / instancias a cubos aleatorios y calcule el centroide respectivo.
2. A partir de la primera instancia, encuentre el centroide más cercano y asigne ese depósito. Si el depósito cambió, recalcule los nuevos centroides, es decir, el centroide del nuevo depósito asignado y el centroide de la asignación anterior del depósito, ya que esos son dos centroides afectados por el cambio.
3. Una vez que haya un cambio en el depósito para cualquier punto, regrese a la primera instancia y repita los pasos nuevamente.
4. La iteración finaliza cuando se repiten todas las instancias y ninguno de los puntos cambia los depósitos.

De esta manera, hay muchas iteraciones que comienzan desde el principio del conjunto de datos una y otra vez cada vez que una instancia cambia de bucket.

Cualquier explicación sería útil y avíseme si entiendo que alguno de estos métodos es incorrecto.

El algoritmo de HW, del artículo de 1979, toma como entrada los grupos iniciales. Sin embargo, los autores sugieren un método para obtenerlos en su última sección. Escriben que se garantiza que ningún clúster estará vacío después de la asignación inicial en la subrutina . Va de la siguiente manera:

1. $\bar{x}$
2. $\bar{x}$$||x_i - \bar{x}||_2$
3. $\{ 1 + (L-1) [M/K] \}$$L=1, \dots, K$$[\ \cdot\ ]$$1$

En cuanto al algoritmo principal, se describe en un artículo llamado K-Means de Hartigan versus K-Means de Lloyd: ¿es hora de un cambio? por N Slonim, E Aharoni, K Crammer, publicado en 2013 por AJCAI . Tenga en cuenta que esta versión simplemente usa una partición inicial aleatoria. Va de la siguiente manera.

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

Creo que las respuestas a todas sus preguntas están implícitas en el algoritmo anterior ... Sin embargo, todavía tengo que asegurarme de que esta implementación del algoritmo sea estándar . En particular, si es el implementado en R. Cualquier comentario / edición es bienvenida.