Agrupamiento K-medias
- Propuesto por
- MacQueen, J. B.; Lloyd, S. P.
- Año
- 1967 (formalized 1982)
- Tipo
- Partitional clustering
- Familia
- Machine learning
Este texto es una traducción automática y aún no se ha revisado. Leer el original en inglés
¿Qué hace?
K-medias es un algoritmo clásico de agrupamiento particional no supervisado que divide un conjunto de datos en K grupos no superpuestos, asignando iterativamente cada observación a su centroide más cercano y actualizando los centroides como la media de sus puntos asignados.
Es una de las herramientas exploratorias más utilizadas en aprendizaje automático y análisis de datos.
La intuición detrás del método
Imagine que deja caer K imanes sobre un mapa de puntos de datos. Cada punto es atraído por su imán más cercano, y luego cada imán se mueve al centro de gravedad de los puntos que atrajo. Repita este ciclo de atracción y movimiento hasta que nada se mueva: los imanes han encontrado K agrupaciones naturales. K-medias formaliza exactamente esta idea, minimizando la distancia total al cuadrado desde cada punto a su centro de clúster, llamada suma de cuadrados dentro del clúster (WCSS o inercia).
Historia
La idea de k-medias fue introducida independientemente por MacQueen en 1967, quien acuñó el término, y formalizada como un algoritmo iterativo eficiente por Stuart Lloyd en Bell Labs en la década de 1950 (publicado en 1982). La mejora de la inicialización k-means++ por Arthur y Vassilvitskii en 2007 abordó el problema de la sensibilidad al mínimo local. Hoy en día, k-medias sigue siendo un método fundamental de aprendizaje no supervisado enseñado en prácticamente todos los planes de estudio de ciencia de datos.
Cuándo usarlo
K-medias es adecuado para el agrupamiento exploratorio de conjuntos de datos numéricos grandes y puramente numéricos cuando necesita particionamiento rápido y escalable y se siente cómodo especificando K de antemano o buscándolo con el método del codo o de silueta. Funciona bien para la segmentación de clientes, la compresión de imágenes, la agrupación de temas de documentos y el preprocesamiento antes del aprendizaje supervisado. Evítelo cuando los clústeres no son esféricos, tienen tamaños o densidades muy variables, cuando las características son categóricas u ordinales (use k-modes o k-prototypes en su lugar), cuando el número de clústeres es completamente desconocido y los experimentos con K variable no son factibles, o cuando los datos contienen muchos valores atípicos (use DBSCAN o variantes robustas en su lugar).
Limitaciones y consideraciones
- Requiere que K se especifique de antemano; elegir mal K produce clústeres sin sentido.
- Asume clústeres esféricos y de tamaño similar; los clústeres alargados, irregulares o de escala diferente se dividen o fusionan incorrectamente.
- Sensible a valores atípicos: un solo punto extremo puede alejar un centroide del grueso del clúster.
- Solo funciona con características numéricas continuas; los datos categóricos requieren un algoritmo diferente (k-modes).
- Converge a un mínimo local; los resultados pueden variar entre ejecuciones con diferentes semillas aleatorias a menos que se utilicen k-means++ o múltiples reinicios.
Las condiciones de la fuente no sustituyen una revisión científica independiente ni la validación por un motor de análisis.
Fortalezas
- Rápido y escalable: O(nKdi) por iteración, práctico en millones de observaciones con K y dimensiones moderadas.
- Simple de implementar, ampliamente disponible en todos los principales marcos de ML y fácil de explicar a audiencias no técnicas.
- Funciona bien en clústeres grandes, bien separados, aproximadamente esféricos y de tamaño similar.
- La inicialización k-means++ reduce sustancialmente la sensibilidad a las condiciones de inicio en comparación con la inicialización aleatoria.
- Determinista dentro de una semilla aleatoria fija, lo que hace que los resultados sean reproducibles.
Aplicaciones
- Segmentación de clientes para marketing y personalización basada en características conductuales o demográficas.
- Compresión de imágenes mediante la cuantificación de colores de píxeles a K valores representativos (cuantificación de color).
- Agrupamiento de documentos y textos como un paso en los flujos de trabajo de modelado de temas después de la vectorización.
- Preprocesamiento de detección de anomalías: los puntos lejanos a cualquier centroide son posibles valores atípicos.
- Paso de inicialización para algoritmos más complejos como modelos de mezcla gaussiana o agrupamiento jerárquico.
- Análisis de expresión génica para agrupar genes o muestras con perfiles de expresión similares.
Cómo funciona
Cómo funciona
Se colocan K centroides de clúster en el espacio de características, ya sea seleccionando aleatoriamente K puntos de datos (Forgy) o mediante la estrategia más inteligente k-means++ que distribuye los centroides iniciales para reducir la posibilidad de mínimos locales deficientes. La elección de la inicialización importa: k-means++ típicamente produce una convergencia más rápida y mejores soluciones finales.
Cada observación se asigna al clúster cuyo centroide es el más cercano según la distancia euclidiana. Esta asignación dura crea K particiones de datos no superpuestas. Formalmente, cada punto x_i se asigna al clúster c_i = argmin_k ||x_i - mu_k||^2.
Fórmula
c_i = \arg\min_k \|x_i - \mu_k\|^2
Cada centroide se recalcula como la media aritmética de todos los puntos actualmente asignados a ese clúster: mu_k = (1/|C_k|) veces la suma de todos los x_i en C_k. Este paso garantiza que el nuevo centroide minimiza la WCSS dentro de cada clúster dada la asignación actual.
Fórmula
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_iLos pasos de asignación y actualización se alternan hasta que las posiciones de los centroides dejan de cambiar (o cambian menos de un umbral de tolerancia) o se alcanza un número máximo de iteraciones. Se garantiza que el algoritmo converge a un mínimo local de WCSS, aunque no necesariamente al mínimo global.
La calidad de la solución se evalúa con la WCSS total (inercia) J = suma sobre clústeres de suma sobre puntos asignados de ||x_i - mu_k||^2. La elección de K es una preocupación separada abordada por el método del codo, las puntuaciones de silueta o las estadísticas de brecha, ya que el algoritmo en sí requiere que K se especifique de antemano.
Fórmula
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2Errores comunes
- Olvidar estandarizar las características antes del agrupamiento: las variables en grandes escalas dominarán los cálculos de distancia.
- Seleccionar K inspeccionando solo la WCSS dentro de la muestra sin el gráfico del codo o la validación de silueta, lo que lleva a un K trivialmente pequeño o grande.
- Ejecutar solo una inicialización y aceptar el primer resultado sin múltiples reinicios para protegerse contra mínimos locales deficientes.
- Incluir variables categóricas u ordinales en la matriz de características sin una codificación apropiada o cambiar a k-modes.
- Tratar las etiquetas de clúster como identidades de grupo significativas sin validación externa, especialmente cuando los clústeres no están bien separados.
Preguntas frecuentes
¿Cómo elijo el número correcto de clústeres K?
Ejecute k-medias para un rango de valores de K, trace la suma de cuadrados dentro del clúster frente a K y busque un 'codo' donde la tasa de disminución se ralentiza bruscamente. Complemente esto con puntuaciones de silueta, que miden cuán similar es cada punto a su propio clúster frente a los clústeres vecinos; una silueta promedio más alta indica clústeres mejor definidos.
¿Por qué obtengo resultados diferentes en cada ejecución?
K-medias es sensible a la inicialización y converge a un mínimo local en lugar de global de WCSS. Use la inicialización k-means++ y establezca una semilla aleatoria fija para la reproducibilidad. Ejecutar el algoritmo varias veces con diferentes semillas y quedarse con la solución con la inercia más baja es una buena práctica.
¿Funciona k-medias con datos categóricos?
No. K-medias se basa en la distancia euclidiana y las medias de los centroides, que no están definidas para variables categóricas. Para datos puramente categóricos use k-modes; para datos mixtos numéricos y categóricos use k-prototypes.
¿Cuándo debería preferir DBSCAN o GMM sobre k-medias?
Use DBSCAN cuando los clústeres tengan formas irregulares o necesite detección automática de valores atípicos sin especificar K. Use Modelos de Mezcla Gaussiana (GMM) cuando desee asignaciones de clústeres suaves (probabilísticas) o clústeres de diferentes tamaños y orientaciones, a costa de una mayor complejidad computacional.
¿Necesito escalar mis características?
Sí, casi siempre. K-medias utiliza la distancia euclidiana, por lo que las características con rangos numéricos grandes dominarán el agrupamiento. Aplique estandarización de puntuación z o escalado de min-max antes de ajustar k-medias, a menos que todas las características ya estén en la misma escala.
Métodos relacionados
Fuentes
Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.
Abrir referencia DOICopiado.MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
Abrir referencia de la publicaciónCopiado.