El agrupamiento por k-medias es un método de cuantificación vectorial, originario del procesamiento de señales, que particiona n observaciones en k grupos, donde cada observación pertenece al grupo con la media más cercana (el centro del grupo o centroide). Esto resulta en una partición del espacio de datos en celdas de Voronoi. El algoritmo se usa ampliamente en aprendizaje automático para análisis de datos no supervisado, como segmentación de clientes, compresión de imágenes y reconocimiento de patrones.
K-medias minimiza las varianzas dentro de los grupos, medidas por distancias euclidianas al cuadrado, pero no las distancias euclidianas regulares, lo que sería el problema de Weber, más difícil. La media optimiza los errores al cuadrado, mientras que solo la mediana geométrica minimiza las distancias euclidianas. Por ejemplo, se pueden encontrar mejores soluciones euclidianas usando k-medianas y k-medoides.
El problema es computacionalmente difícil (NP-difícil); sin embargo, los algoritmos heurísticos eficientes convergen rápidamente a un óptimo local. Estos suelen ser similares al algoritmo de maximización de expectativas para mezclas de distribuciones gaussianas mediante un enfoque de refinamiento iterativo empleado tanto por k-medias como por el modelado de mezclas gaussianas. Ambos usan centros de grupo para modelar los datos; sin embargo, el agrupamiento por k-medias tiende a encontrar grupos de extensión espacial comparable, mientras que el modelo de mezclas gaussianas permite que los grupos tengan formas diferentes.
El algoritmo no supervisado de k-medias tiene una relación laxa con el clasificador de k vecinos más cercanos, una técnica popular de aprendizaje automático supervisado para clasificación que a menudo se confunde con k-medias debido al nombre. Aplicar el clasificador de 1 vecino más cercano a los centros de grupo obtenidos por k-medias clasifica nuevos datos en los grupos existentes, conocido como clasificador de centroide más cercano o algoritmo de Rocchio.
Definición Formal
Dado un conjunto de observaciones (x1, x2, ..., xn), donde cada observación es un vector real de d dimensiones, el agrupamiento por k-medias tiene como objetivo particionar las n observaciones en k (≤ n) conjuntos S = {S1, S2, ..., Sk} para minimizar la suma de cuadrados dentro de los grupos (WCSS), es decir, la varianza. Formalmente, el objetivo es encontrar:
argmin sobre S de la suma de i=1 a k de la suma de x en Si de ||x - μi||^2,
donde μi es la media (también llamada centroide) de los puntos en Si, y ||·|| es la norma L2 habitual. Esto es equivalente a minimizar las desviaciones cuadráticas por pares de los puntos en el mismo grupo, como se muestra por la identidad de que la suma de distancias al cuadrado a la media es igual a la distancia cuadrática promedio por pares.
Algoritmo
El algoritmo más común, a menudo llamado algoritmo de Lloyd, utiliza un enfoque de refinamiento iterativo. Comienza con un conjunto inicial de k centroides, luego alterna entre dos pasos: asignación y actualización. En el paso de asignación, cada observación se asigna al grupo cuyo centroide es más cercano, típicamente usando distancia euclidiana. En el paso de actualización, el centroide de cada grupo se recalcula como la media de los puntos asignados. Estos pasos se repiten hasta que las asignaciones ya no cambian, lo que indica convergencia a un óptimo local.
La inicialización es crucial; el método k-medias++, que distribuye los centroides iniciales, es una heurística popular para mejorar la calidad del agrupamiento final. El algoritmo es sensible a la elección de k, y métodos como el método del codo o el análisis de silueta se usan para estimar un número apropiado de grupos.
Propiedades y Limitaciones
K-medias asume que los grupos son esféricos y de tamaño similar, lo que limita su aplicabilidad a datos con formas de grupo complejas. También es sensible a valores atípicos, ya que la media se ve influenciada por valores extremos. El algoritmo converge a un óptimo local, no necesariamente al global, y diferentes inicializaciones pueden producir resultados diferentes. A pesar de estas limitaciones, su simplicidad y escalabilidad lo convierten en una opción popular para conjuntos de datos grandes, especialmente en aumento de datos y pipelines de preprocesamiento.
Aplicaciones
K-medias se usa en varios dominios. En inteligencia artificial, sirve como línea base para tareas de agrupamiento. En visión por computadora, se usa para segmentación de imágenes y cuantización de color. En marketing, ayuda a segmentar clientes según el comportamiento de compra. En procesamiento de lenguaje natural, puede agrupar documentos o incrustaciones de palabras. El algoritmo también es un bloque de construcción para técnicas más avanzadas, como el aprendizaje de características en aprendizaje profundo y modelos de IA generativa.
Relación con Otros Métodos
K-medias está relacionado con los modelos de mezclas gaussianas (GMM), ya que ambos usan refinamiento iterativo y centros de grupo. Sin embargo, GMM permite que los grupos tengan formas y covarianzas diferentes, mientras que k-medias asume grupos isotrópicos. El clasificador de centroide más cercano, derivado de k-medias, es un método de clasificación supervisada simple. K-medias a menudo se confunde con k vecinos más cercanos (k-NN), pero son distintos: k-medias es no supervisado, mientras que k-NN es supervisado.
Historia y Desarrollo
El concepto de k-medias fue propuesto por primera vez por Hugo Steinhaus en 1956, y el término "k-medias" fue acuñado por James MacQueen en 1967. El algoritmo de Lloyd, publicado en 1957 pero no ampliamente conocido hasta 1982, es la implementación estándar. A lo largo de los años, se han desarrollado numerosas variantes, como k-medias de mini-lote para datos a gran escala y c-medias difuso para agrupamiento suave.