Ventajas y desventajas de los k-medios

El método K-means es útil y eficiente en muchos contextos de aprendizaje automático, pero tiene algunas debilidades distintivas.

Ventajas del método k-means

Son relativamente fáciles de implementar.

Se escala a grandes conjuntos de datos.

Siempre converge.

Permite el inicio en caliente de las posiciones de los centroides.

Se adapta sin problemas a ejemplos nuevos.

Se puede generalizar a clústeres de diferentes formas y tamaños, como los clústeres elípticos.

Generalización de k-means

Una implementación directa de k-means puede tener problemas con clústeres de diferentes densidades y tamaños. El lado izquierdo de la Figura 1 muestra los clústeres que esperaríamos ver, mientras que el lado derecho muestra los clústeres propuestos por k-means.

Dos gráficos uno al lado del otro. El primero muestra un conjunto de datos con clústeres algo obvios. El segundo muestra una agrupación extraña de ejemplos después de ejecutar k-means.
Figura 1: Ejemplo de k-means no generalizado.

Para obtener un mejor rendimiento en clústeres desequilibrados como los que se muestran en la Figura 1, puedes generalizar, es decir, adaptar, k-means. En la Figura 2, se muestran tres conjuntos de datos diferentes agrupados con dos generalizaciones diferentes. El primer conjunto de datos muestra el método k-means sin generalización, mientras que el segundo y el tercero permiten que los clústeres varíen en ancho.

Tres gráficos que muestran el método k-means sin generalización, luego el método k-means que permite anchos variables y, luego, el método k-means que permite anchos variables en las dimensiones.
Figura 2: Agrupamiento en clústeres de k-means con y sin generalización.

En este curso, no se explica cómo generalizar el algoritmo k-means, pero quienes estén interesados deberían consultar Clustering: modelos de mezcla Gaussiana de k-means, de Carlos Guestrin, de la Universidad Carnegie Mellon.

Desventajas del método k-means

k se debe elegir de forma manual.

Los resultados dependen de los valores iniciales.

Para kbajo, puedes mitigar esta dependencia ejecutando k-means varias veces con diferentes valores iniciales y elegir el mejor resultado. A medida que k aumenta, necesitas inicializar k-means para elegir mejores centroides iniciales. Para obtener una explicación completa de la inicialización de k-means, consulta "A Comparative Study of Efficient Initialization Methods for the K-means Clustering Algorithm", de M. Emre Celebi, Hassan A. Kingravi y Patricio A. Vela.

Tiene dificultades para agrupar datos de diferentes tamaños y densidades sin generalización.

Dificultad para agrupar valores extremos.

Los valores atípicos pueden arrastrar los centroides, o bien los valores atípicos pueden obtener su propio clúster en lugar de ignorarse. Considera quitar o recortar los valores atípicos antes de agruparlos.

La dificultad de escalamiento aumenta con la cantidad de dimensiones.

A medida que aumenta la cantidad de dimensiones en los datos, una medida de similitud basada en la distancia converge a un valor constante entre cualquier ejemplo determinado. Reduce la dimensionalidad con PCA en los datos de atributos o con el agrupamiento espectral para modificar el algoritmo de agrupamiento.

Maldición de la dimensionalidad y el agrupamiento espectral

En estos tres gráficos, observa cómo, a medida que aumentan las dimensiones, la desviación estándar en la distancia entre los ejemplos se reduce en relación con la distancia promedio entre los ejemplos. Esta convergencia significa que k-means se vuelve menos eficaz para distinguir entre ejemplos a medida que aumenta la dimensionalidad de los datos. Esto se conoce como maldición de la dimensionalidad.

Tres gráficos que muestran cómo la desviación estándar de la distancia entre los ejemplos disminuye a medida que aumenta la cantidad de dimensiones
Figura 3: Una demostración de la maldición de la dimensionalidad. Cada gráfico muestra las distancias por pares entre 200 puntos aleatorios.

Puedes evitar esta disminución en el rendimiento con el clúster espectral, que agrega pasos previos al clúster al algoritmo. Para realizar el agrupamiento espectral, haz lo siguiente:

  1. Reduce la dimensionalidad de los datos de atributos con el PCA.
  2. Proyecta todos los datos en el subespacio de menor dimensión.
  3. Agrupa los datos en este subespacio con el algoritmo que elijas.

Consulta A Tutorial on Spectral Clustering de Ulrike von Luxburg para obtener más información sobre el clúster espectral.