K-Means Clustering

El agrupamiento k-means es un algoritmo de aprendizaje no supervisado que divide los datos en k grupos, cada uno representado por su centroide, la media de los puntos asignados. Busca la partición con la menor suma de distancias cuadráticas dentro de los clústeres, una cantidad llamada inercia, de modo que los puntos de un clúster queden cerca de su centroide. El procedimiento estándar es el algoritmo de Lloyd, que Stuart Lloyd desarrolló en Bell Labs en 1957 para cuantizar señales; el nombre «k-means» procede de un artículo de James MacQueen de 1967. Como es sencillo, rápido y escala a millones de puntos, k-means es una herramienta predeterminada para la minería de datos, la compresión y la exploración de la estructura de los datos sin etiquetar.

Cómo funciona el algoritmo#

Tras elegir los centroides iniciales, el algoritmo de Lloyd alterna entre una etapa de asignación y otra de actualización hasta que los clústeres dejan de cambiar:

1. Inicialización: Elige k centroides iniciales. El método predeterminado de Scikit-learn, k-means++, elige el primer centroide al azar y cada uno de los siguientes con una probabilidad proporcional a su distancia cuadrática al centroide elegido más cercano, lo que separa las semillas.
2. Asignación: Asigna cada punto a su centroide más cercano, normalmente según la distancia euclídea.
3. Actualización: Desplaza cada centroide hasta la media de los puntos que tiene asignados en ese momento.
4. Repetición: Vuelve a la etapa de asignación hasta que ningún punto cambie de clúster o los centroides se desplacen menos que una tolerancia.

Ninguno de los dos pasos puede aumentar la inercia, por lo que el ciclo siempre converge, pero solo a un mínimo local que depende de los centroides iniciales. Encontrar el óptimo global es NP-hard, así que las implementaciones ejecutan varias inicializaciones y se quedan con la de menor inercia. En KMeans de scikit-learn, el valor predeterminado de n_init="auto" ejecuta el algoritmo una vez con la inicialización k-means++ y 10 veces con una inicialización aleatoria.

Elección del número de clústeres#

K-means necesita conocer k de antemano. La inercia siempre disminuye a medida que aumenta k, porque más centroides quedan más cerca de los puntos. Por eso, el método del codo representa la inercia en función de k y busca el punto en que la reducción se aplana. La puntuación de silueta compara, para cada punto, la distancia media a su propio clúster con la distancia media al clúster más cercano, y va de -1 a 1; los valores más altos indican clústeres compactos y bien separados. En este ejemplo, se calcula la puntuación para valores de k entre 2 y 6 en datos generados alrededor de cuatro centros:

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.metrics import silhouette_score

# 600 unlabeled points drawn around 4 hidden centers
X, _ = make_blobs(n_samples=600, centers=4, cluster_std=1.0, random_state=7)

# Fit k-means for several k and score each partition
for k in range(2, 7):
    kmeans = KMeans(n_clusters=k, n_init="auto", random_state=0)
    labels = kmeans.fit_predict(X)
    print(f"k={k}  inertia={kmeans.inertia_:8.0f}  silhouette={silhouette_score(X, labels):.3f}")

La inercia baja de 18.363 con k=2 a 5.241 con k=3 y 1.127 con k=4, y después solo baja a 1.039 con k=5 y 922 con k=6, así que el codo está en k=4. La puntuación de silueta coincide: alcanza su máximo, 0,811, con k=4 y cae a 0,687 con k=5, lo que recupera los cuatro centros en torno a los que se generaron los datos.

Supuestos y variantes#

K-means funciona mejor cuando los clústeres son más o menos esféricos, tienen tamaños similares y están separados en el espacio euclídeo. Las características de mayor escala dominan la distancia, por lo que normalmente se estandarizan primero los datos. Cada punto se asigna a algún clúster, y unos pocos valores atípicos extremos pueden arrastrar un centroide lejos de su grupo. Varias variantes relajan estas limitaciones:

• K-means por mini lotes: Actualiza los centroides a partir de pequeños lotes aleatorios, lo que sacrifica algo de precisión a cambio de un entrenamiento mucho más rápido en conjuntos de datos grandes.
• K-medoides: Usa puntos de datos reales como centros de los clústeres, lo que le da más resistencia a los valores atípicos y permite utilizar cualquier medida de distancia.
• C-medias difusas: Asigna a cada punto un grado de pertenencia a cada clúster, siguiendo el enfoque de la lógica difusa, en lugar de una única asignación estricta.
• Modelos de mezclas gaussianas: Ajustan una distribución de probabilidad por clúster, lo que permite clústeres elípticos de distintos tamaños y devuelve asignaciones probabilísticas flexibles.

Aplicaciones en IA y visión artificial#

• Cuantización de colores: Agrupar los colores de los píxeles de una imagen y sustituir cada píxel por su centroide reduce una foto con miles de colores a una paleta de k colores, lo que comprime la imagen y también ofrece una forma rápida y aproximada de segmentación de imágenes.
• Libros de códigos y cuantización vectorial: Los centroides forman un libro de códigos, y cada vector se almacena como el índice de su centroide más cercano. La recuperación de imágenes clásica basada en bolsas de palabras visuales construía sus vocabularios de este modo a partir de descriptores locales de imágenes.
• Diseño de cajas de anclaje: YOLOv2 aplicaba k-means a los anchos y altos de las cajas de entrenamiento, usando 1 menos IoU como distancia, para elegir sus cajas de anclaje.
• Paletización de pesos: Al exportar YOLO26 a Core ML con quantize=8, se agrupan los valores de cada tensor de pesos grande mediante k-means en 256 centroides, de modo que el modelo exportado almacena un índice de 8 bits por peso y una pequeña tabla de búsqueda.
• Segmentación de clientes: los comercios agrupan a los clientes según la frecuencia de compra, el tamaño de la cesta y la antigüedad de la última compra para adaptar las ofertas a cada segmento.

K-Means frente a algoritmos relacionados#

• K vecinos más cercanos (KNN): La «k» compartida causa confusión. KNN es un algoritmo supervisado que asigna una etiqueta a un punto nuevo a partir de sus k ejemplos etiquetados más cercanos, mientras que k-means es no supervisado y k representa el número de grupos que crea.
• DBSCAN: Agrupa puntos por densidad, encuentra por sí mismo el número de grupos, admite grupos de cualquier forma y etiqueta los puntos dispersos como ruido en lugar de forzarlos a formar parte de un grupo.
• Agrupamiento jerárquico: Construye un árbol de grupos anidados fusionando repetidamente los grupos más cercanos, de modo que k puede elegirse después cortando el árbol a cualquier nivel, a costa de un crecimiento como mínimo cuadrático con el número de puntos.