El agrupamiento por k-medias es un método de cuantificación vectorial, originalmente del procesamiento de señales, que particiona un conjunto de observaciones en k grupos, donde cada observación pertenece al grupo con la media más cercana, conocida como centroide del grupo. Esto resulta en una partición del espacio de datos en celdas de Voronoi. El algoritmo se utiliza ampliamente en aprendizaje automático para tareas como segmentación de clientes, compresión de imágenes y reconocimiento de patrones, y es una técnica fundamental en inteligencia artificial y análisis de datos.
El objetivo de k-medias es minimizar la suma de cuadrados dentro del grupo (WCSS), que es la suma de las distancias euclidianas al cuadrado entre cada punto y su centroide de grupo. Esto equivale a minimizar las desviaciones cuadráticas por pares de los puntos dentro del mismo grupo. Sin embargo, k-medias minimiza distancias euclidianas al cuadrado, no distancias euclidianas regulares; esto último requeriría resolver el problema de Weber, más difícil. Para la minimización de la distancia euclidiana, alternativas como k-medianas o k-medoides son más apropiadas.
El problema de encontrar el agrupamiento óptimo por k-medias es computacionalmente difícil (NP-difícil), pero los algoritmos heurísticos eficientes convergen rápidamente a un óptimo local. El enfoque más común es el algoritmo de Lloyd, que asigna iterativamente puntos al centroide más cercano y luego actualiza los centroides a la media de los puntos asignados. Este refinamiento iterativo es similar al algoritmo de maximización de expectativas utilizado para modelos de mezclas gaussianas, pero k-medias tiende a encontrar grupos de extensión espacial comparable, mientras que las mezclas gaussianas permiten diferentes formas.
Algoritmo e implementación
El algoritmo estándar de k-medias comienza con un conjunto inicial de k centroides, que pueden elegirse aleatoriamente o mediante métodos como k-medias++ para mejorar la convergencia. El algoritmo repite dos pasos hasta la convergencia: asignación, donde cada observación se asigna al grupo con el centroide más cercano, y actualización, donde cada centroide se recalcula como la media de todos los puntos en su grupo. La convergencia se detecta típicamente cuando las asignaciones ya no cambian o cuando la mejora del WCSS cae por debajo de un umbral.
Existen varias variantes, incluyendo k-medias de mini-lotes para conjuntos de datos grandes y k-medias esféricas para datos de texto. La elección de k a menudo se determina mediante el método del codo, el análisis de silueta o el estadístico de brecha. La complejidad temporal del algoritmo es aproximadamente O(nkd*i), donde n es el número de observaciones, d es la dimensionalidad e i es el número de iteraciones.
Relación con otros métodos
K-medias es un algoritmo no supervisado, lo que significa que no requiere datos etiquetados. Tiene una relación flexible con el clasificador de k vecinos más cercanos (k-NN), una técnica supervisada. Aplicar el clasificador de 1 vecino más cercano a los centros de grupo obtenidos por k-medias clasifica nuevos datos en grupos existentes; esto se conoce como clasificador de centroide más cercano o algoritmo de Rocchio. Esta conexión destaca cómo el agrupamiento no supervisado puede apoyar tareas supervisadas.
K-medias también está relacionado con los modelos de mezclas gaussianas (GMM). Ambos utilizan centros de grupo para modelar datos, pero los GMM permiten que los grupos tengan diferentes formas y tamaños, mientras que k-medias asume grupos esféricos de varianza similar. En consecuencia, k-medias es más simple y rápido, pero menos flexible.
Aplicaciones y limitaciones
K-medias se utiliza en muchos dominios. En Amazon Web Services y Google Cloud, es una herramienta común para analizar el comportamiento del usuario y optimizar la asignación de recursos. En visión por computadora, se utiliza para segmentación de imágenes y cuantificación de color. En marketing, segmenta clientes según patrones de compra. El algoritmo también es un componente básico para métodos más complejos, como la extracción de características en aprendizaje profundo y el preprocesamiento de datos en IA generativa.
Sin embargo, k-medias tiene limitaciones. Requiere que el número de grupos k se especifique de antemano, lo que no siempre se conoce. Es sensible a la selección inicial de centroides, aunque k-medias++ mitiga esto. Asume que los grupos son convexos e isotrópicos, lo que puede no cumplirse en datos del mundo real. Los valores atípicos pueden distorsionar los centroides, y el algoritmo puede converger a óptimos locales. A pesar de estos problemas, su simplicidad y eficiencia lo convierten en una opción popular.
Contexto histórico y desarrollo
El algoritmo de k-medias fue propuesto por primera vez por Hugo Steinhaus en 1956 y refinado posteriormente por Stuart Lloyd en 1957 en Bell Labs (aunque no se publicó hasta 1982). El nombre "k-medias" fue acuñado por James MacQueen en 1967. Desde entonces, se han desarrollado numerosas mejoras, incluyendo k-medias++ para una mejor inicialización y la variante de mini-lotes para escalabilidad. El algoritmo sigue siendo un pilar en los planes de estudio de aprendizaje automático y está implementado en bibliotecas principales como scikit-learn y TensorFlow.