Optimización global frente a optimización local

Donde:

     - n es el número total de ejemplos.

     - xi es el ejemplo de datos iº.

     - cj es el centroide jº.

Por lo tanto, yendo de derecha a izquierda, se toma la distancia entre un ejemplo de datos y un centroide (dist). A continuación, se toma el centroide con la distancia mínima (más cercana) al ejemplo (min). Por último, se calcula la suma de todas las distancias más cercanas. En última instancia, esto ayuda a encontrar los centroides que minimizan esta distancia total. Sin embargo, normalmente no es factible aplicar esta optimización globalmente. Si intentara todas las asignaciones posibles de ejemplos de datos n a cada clúster, terminaría con muchas, muchas combinaciones posibles, incluso si el tamaño de la muestra y el número de clústeres son bajos. Por ejemplo, con un n de 25 y 4 como el número de clústeres, hay aproximadamente 47 billones de asignaciones posibles.

Esta es la razón por la que la agrupación en clústeres k-means es un algoritmo iterativo que requiere optimización local. El proceso es el siguiente:

     1. Comienza tomando el número de clústeres deseados, luego asigna aleatoriamente centroides para cada clúster.
     2. Luego, asigna cada ejemplo de datos a cualquier centroide que sea más cercano actualmente. Esto es efectivamente lo mismo que minimizar el costo de estas asignaciones.
     3. A continuación, el algoritmo mueve cada centroide para que esté en el centro de los ejemplos de datos que se le asignaron. Esto es efectivamente lo mismo que minimizar el costo de los centroides.
     4. El proceso se repite hasta la convergencia o hasta que se cumple un máximo de iteración.

Por lo tanto, esta minimización iterativa de costos es un enfoque más eficiente para la optimización. Sin embargo, no siempre logra la optimización global perfecta, especialmente si los centroides iniciales seleccionados aleatoriamente se colocaron en ubicaciones subóptimas. Puede volver a inicializar el algoritmo de k-means con diferentes centroides elegidos aleatoriamente para superar esto.