4 · K-Means: intuición + algoritmo de Lloyd
El algoritmo de clustering canónico — alterna entre asignar puntos a centroides y mover centroides a las medias de los clusters hasta converger.
K-Means particiona los puntos en K clusters alternando: asigna cada punto al centroide más cercano, luego mueve cada centroide a la media de sus puntos asignados.
Sin esto:
Sin K-Means carecerías del algoritmo de clustering canónico — el equivalente no supervisado de la regresión lineal.
El clustering es la tarea de agrupar puntos similares juntos — sin ninguna etiqueta. Donde el aprendizaje supervisado dice "predice la clase de este punto dadas las etiquetas", el clustering dice "descubre agrupaciones naturales en los datos solo por su estructura."
K-Means es el algoritmo de clustering más utilizado, con tres ideas claras en su núcleo:
-
Objetivo — minimizar la suma de cuadrados dentro del cluster (WCSS), también llamada inercia:
WCSS = Σₖ Σ_{x ∈ Cₖ} ||x − μₖ||²
donde Cₖ es el conjunto de puntos en el cluster k y μₖ es su media (el centroide). Menor WCSS = clusters más compactos y ajustados.
-
Algoritmo de Lloyd — una minimización alternada simple que provablemente disminuye el WCSS en cada paso:
- (1) Inicializar K centroides (aleatoriamente o vía k-means++).
- (2) Asignar cada punto al centroide más cercano (partición de Voronoi).
- (3) Actualizar cada centroide a la media de todos sus puntos asignados.
- (4) Repetir los pasos 2–3 hasta que las asignaciones dejen de cambiar.
-
Garantía de convergencia — dado que hay finitas asignaciones posibles y el WCSS disminuye en cada paso, el algoritmo de Lloyd está garantizado a converger. Sin embargo, converge a un mínimo local del WCSS, no necesariamente al mínimo global. La solución depende de los centroides iniciales.
Por qué K-Means es tan fundamental: es sin duda el equivalente no supervisado de la regresión lineal — fácil de interpretar, rápido de ejecutar y el punto de referencia con el que todo otro método de clustering se compara.
Python (in browser)
K-Means en datos de 4 blobs — puntos coloreados por cluster, marcas X negras son los centroides finales.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
Algoritmo de Lloyd a mano — posiciones de centroides en las iteraciones 0, 1, 2, 3, 5. Los centroides dejan de moverse entre la iteración 3 y 5: convergencia.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
Verificando que model.inertia_ de sklearn es igual a la fórmula manual de WCSS — coinciden exactamente.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
Python (in browser)
Sensibilidad a la inicialización — cada semilla aleatoria da una inercia diferente, mostrando que K-Means encuentra mínimos locales cuya calidad depende de las condiciones iniciales.
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
K-Means como un algoritmo EM restringido — entender esto revela exactamente cuándo y por qué falla.
K-Means está garantizado a converger, pero solo a...
- K-Means minimiza WCSS (inercia) = Σₖ Σ_{x∈Cₖ} ||x−μₖ||² — la suma de distancias al cuadrado de cada punto a su centroide de cluster.
- El algoritmo de Lloyd alterna: asignar puntos al centroide más cercano (paso E) → recomputar centroides como medias de cluster (paso M) → repetir hasta convergencia.
- La convergencia está garantizada a un MÍNIMO LOCAL — diferentes inicializaciones aleatorias pueden dar diferentes inercias; n_init=10 de sklearn mitiga esto.
- K-Means es EM restringido a Gaussianas isótropas de igual varianza — asume clusters esféricos de tamaño similar.
- Para clusters elongados o de formas irregulares, prefiere DBSCAN o Modelos de Mezcla Gaussiana sobre K-Means.
Segmentación de clientes (agrupar clientes similares), clustering de documentos (agrupar textos similares), cuantización de imágenes (reducir paleta de colores), inicialización en caliente de algoritmos más complejos como los modelos de mezcla gaussiana.
Si lo quitas: Carecerías de la herramienta de clustering canónica — y la mayoría de los otros algoritmos de clustering se construyen sobre la intuición de K-Means o se comparan con él.