Herramienta de Clustering K-Means

Pseudocódigo

Dos pasos que se alternan hasta que nada cambia: asignar cada punto al centroide más cercano, y después mover cada centroide al promedio de los puntos que le fueron asignados.

KMedias(puntos, k):
    inicializar k centroides (aleatorio, o k-means++)

    repetir hasta que las asignaciones no cambien:
        // Paso de asignación
        para cada punto p:
            grupo[p] = argmin sobre c de distancia(p, c)

        // Paso de actualización
        para cada centroide c:
            c = media de todos los puntos con grupo[p] == c

    devolver grupos y centroides

Cada paso reduce la suma de cuadrados dentro de los grupos, o la deja igual, y solo hay un número finito de asignaciones posibles, así que el algoritmo termina siempre. Lo que no garantiza es terminar en el óptimo global: converge a un mínimo local que depende por completo de la inicialización, y esa es la limitación práctica que hay que gestionar.

Ejemplo resuelto, paso a paso

Agrupa cuatro puntos en dos grupos partiendo deliberadamente de una inicialización mala, con ambos centroides dentro del mismo grupo real.

Grafo de ejemplo: Puntos en (1,1), (2,1), (8,8) y (9,8). Centroides iniciales colocados en (1,1) y (2,1), es decir los dos dentro del grupo inferior izquierdo.

1. Iteración 1, asignación. El punto (1,1) va al primer centroide. Los otros tres, (2,1), (8,8) y (9,8), quedan más cerca del segundo. La partición es claramente mala: un grupo con un punto y otro con tres.
2. Iteración 1, actualización. El primer centroide se queda en (1,1). El segundo se mueve al promedio de (2,1), (8,8) y (9,8), es decir (6,33, 5,67). La suma de cuadrados dentro de los grupos es 61,333.
3. Iteración 2, asignación. Con el segundo centroide desplazado hacia arriba a la derecha, el punto (2,1) queda ahora más cerca del primero. La partición pasa a ser (1,1) y (2,1) frente a (8,8) y (9,8), que es la correcta.
4. Iteración 2, actualización. Los centroides se mueven a (1,5, 1) y (8,5, 8). La suma de cuadrados dentro de los grupos cae de 61,333 a 1,0.
5. Iteración 3, convergencia. Las asignaciones no cambian y los centroides tampoco. El algoritmo se detiene.

La convergencia llega en dos iteraciones y la suma de cuadrados dentro de los grupos cae de 61,333 a 1,0. Fíjate en que el algoritmo se recuperó de una inicialización deliberadamente mala, con ambos centroides dentro del mismo grupo real. Eso no está garantizado: con otros datos, una inicialización así puede dejarte atrapado en un mínimo local. Por eso k-means++ elige los centroides iniciales bien separados y por eso conviene ejecutar el algoritmo varias veces con inicializaciones distintas.

Complejidad y de dónde sale

Tiempo: O(n · k · i · d) · Espacio: O(n + k·d)

Cada iteración asigna n puntos comparándolos con k centroides en d dimensiones, lo que da O(n por k por d), y el paso de actualización recorre los puntos una vez más con el mismo coste. Con i iteraciones el total es O(n por k por i por d). En la práctica i suele ser pequeño, del orden de decenas, aunque en el peor caso puede crecer de forma superpolinómica. El espacio es la asignación de grupo por punto más los k centroides. Hallar el agrupamiento óptimo por suma de cuadrados es NP-difícil incluso con k igual a 2, así que el algoritmo de Lloyd que se usa universalmente es una heurística: rápido y bueno en la práctica, sin garantía de optimalidad.

Cuándo usar Agrupamiento K-Means y cuándo no

Elige según la forma que esperes en los grupos y según si conoces k de antemano.

Errores frecuentes

• Inicializar al azar sin k-means++. Una inicialización mala puede converger a un mínimo local claramente peor. K-means++ elige los centros iniciales con probabilidad proporcional a la distancia al cuadrado respecto de los ya escogidos, lo que los separa y mejora mucho el resultado esperado con muy poco coste extra.
• No normalizar las variables. K-medias usa distancia euclídea, así que una variable medida en miles domina a otra medida entre 0 y 1. Si las escalas difieren, normaliza antes de agrupar o los grupos reflejarán solo la variable de mayor rango.
• Elegir k mirando solo la suma de cuadrados. La suma de cuadrados dentro de los grupos siempre decrece al aumentar k, hasta llegar a cero cuando k iguala al número de puntos. Usa el método del codo, la silueta o el gap statistic, no el mínimo absoluto.
• Aplicarlo a grupos no esféricos. K-medias particiona el espacio en celdas de Voronoi, así que solo puede producir fronteras convexas. Con grupos en forma de media luna o anidados fallará por construcción, por muchas veces que lo ejecutes. DBSCAN o el agrupamiento espectral son las alternativas.
• Ejecutarlo una sola vez. Dado que el resultado depende de la inicialización, una única ejecución no dice si has caído en un mínimo local. Ejecuta varias veces con semillas distintas y quédate con la de menor suma de cuadrados.

Preguntas frecuentes

¿Qué es el agrupamiento k-medias?

K-medias divide un conjunto de puntos en k grupos alternando dos pasos: asignar cada punto al centroide más cercano y después mover cada centroide al promedio de sus puntos asignados. Se repite hasta que las asignaciones dejan de cambiar, minimizando la suma de distancias al cuadrado dentro de cada grupo.

¿Cuál es la complejidad temporal de k-medias?

O(n por k por i por d), donde n son los puntos, k los grupos, i las iteraciones y d las dimensiones. En la práctica i suele ser del orden de decenas. Hallar el agrupamiento óptimo por suma de cuadrados es NP-difícil incluso con k igual a 2, así que el algoritmo estándar es una heurística sin garantía de optimalidad.

¿Converge siempre k-medias?

Sí, siempre termina, porque cada paso reduce o mantiene la suma de cuadrados dentro de los grupos y solo hay un número finito de asignaciones posibles. Pero converge a un mínimo local, no necesariamente al global, y a cuál llega depende por completo de la inicialización.

¿Por qué importa la inicialización en k-medias?

Porque el algoritmo solo puede mejorar localmente desde donde arranca. Unos centros iniciales mal colocados pueden dejarlo atrapado en una partición claramente peor que la óptima. K-means++ mitiga esto eligiendo centros iniciales bien separados, y ejecutar varias veces con semillas distintas y quedarse con el mejor resultado es la práctica habitual.

¿Cómo se elige el valor de k?

No hay una respuesta única. El método del codo representa la suma de cuadrados frente a k y busca el punto donde la mejora se aplana. El coeficiente de silueta mide cuán bien separados quedan los grupos. El gap statistic compara con datos aleatorios de referencia. Con frecuencia el conocimiento del dominio manda por encima de todos ellos.