Cómo entender los inconvenientes de K-means

K-means es un método ampliamente utilizado en el análisis de conglomerados. Según tengo entendido, este método NO requiere NINGUNA suposición, es decir, dame un conjunto de datos y un número predeterminado de clústeres, k, y simplemente aplico este algoritmo que minimiza la suma de los errores al cuadrado (SSE), dentro del clúster al cuadrado error.

Entonces k-means es esencialmente un problema de optimización.

Leí algo de material sobre los inconvenientes de k-means. La mayoría de ellos dice que:

• k-means asume que la varianza de la distribución de cada atributo (variable) es esférica;
• todas las variables tienen la misma varianza;
• la probabilidad previa para todos los k grupos es la misma, es decir, cada grupo tiene aproximadamente el mismo número de observaciones;

Si se viola cualquiera de estos 3 supuestos, entonces k-means fallará.

No pude entender la lógica detrás de esta declaración. Creo que el método k-means esencialmente no hace suposiciones, solo minimiza el SSE, por lo que no puedo ver el vínculo entre minimizar el SSE y esos 3 "supuestos".

Si bien me gusta mucho la respuesta de David Robinson aquí, aquí hay una crítica adicional de k-means.

Agrupación de datos no agrupados

Ejecute k-means en datos uniformes, ¡y aún obtendrá grupos! No le dice cuándo los datos simplemente no se agrupan, y puede llevar su investigación a un callejón sin salida de esta manera.

Sensible a la escala

Cambiar la escala de sus conjuntos de datos cambiará completamente los resultados. Si bien esto en sí mismo no es malo, no te das cuenta de que tienes que dedicar más atención a escalar tus datos . Los factores de escala son adicionales parámetros ocultos en k-significa que "por defecto" a 1 y por lo tanto son fácilmente pasados por alto, sin embargo, tener un impacto importante (pero por supuesto esto se aplica a muchos otros algoritmos, también).$d$

Esto es probablemente lo que usted denominó "todas las variables tienen la misma varianza". Excepto que idealmente, también consideraría la escala no lineal cuando sea apropiado.

También tenga en cuenta que es solo una heurística escalar cada eje para tener varianza unitaria . Esto no asegura que k-means funcione. El escalado depende del significado de su conjunto de datos. Y si tiene más de un clúster, desearía que cada clúster (independientemente) también tenga la misma varianza en cada variable.

Aquí hay un contraejemplo clásico de conjuntos de datos que k-means no puede agrupar. Ambos ejes están en cada grupo, por lo que sería suficiente hacer esto en 1 dimensión. Pero los grupos tienen diferentes variaciones, y k-means los divide de manera incorrecta.

No creo que este contraejemplo para k-means esté cubierto por sus puntos:

• Todos los grupos son esféricos (iid gaussiano).
• Todos los ejes tienen la misma distribución y, por lo tanto, varianza.
• Ambos grupos tienen 500 elementos cada uno.

Sin embargo, k-means todavía falla gravemente (y empeora si aumento la varianza más allá de 0.5 para el grupo más grande) Pero: no es el algoritmo el que falló. Son los supuestos, que no se sostienen . K-means está funcionando perfectamente, solo está optimizando el criterio equivocado.

Incluso en conjuntos de datos perfectos, puede atascarse en un mínimo local

A continuación se muestra la mejor de las 10 ejecuciones de k-means en el clásico conjunto de datos A3. Este es un conjunto de datos sintéticos, diseñado para k-means . 50 racimos, cada uno de forma gaussiana, razonablemente bien separados. Sin embargo, solo con k-means ++ y 100 iteraciones obtuve el resultado esperado ... (a continuación se muestran 10 iteraciones de k-means normales, por ejemplo).

Encontrará rápidamente muchos grupos en este conjunto de datos, donde k-means no pudo encontrar la estructura correcta. Por ejemplo, en la parte inferior derecha, un grupo se dividió en tres partes. Pero no hay manera, k-means va a mover uno de estos centroides a un lugar completamente diferente del conjunto de datos: está atrapado en un mínimo local (¡y esta ya fue la mejor de 10 carreras!)

Y hay muchos de esos mínimos locales en este conjunto de datos. Muy a menudo, cuando obtiene dos muestras del mismo clúster, se atascará en un mínimo donde este clúster permanece dividido, y otros dos clústeres se fusionaron en su lugar. No siempre, pero muy a menudo. Por lo tanto, necesita muchas iteraciones para tener una elección afortunada. Con 100 iteraciones de k-means, aún conté 6 errores, y con 1000 iteraciones lo reduje a 4 errores. K-means ++ por la forma en que pesa las muestras aleatorias, funciona mucho mejor en este conjunto de datos.

Los medios son continuos

Si bien puede ejecutar k-means en datos binarios (o datos categóricos codificados en caliente), los resultados ya no serán binarios. Así que obtienes un resultado, pero es posible que al final no puedas interpretarlo porque tiene un tipo de datos diferente al de tus datos originales.

Supuesto oculto: vale la pena minimizar SSE

Básicamente, esto ya está presente en la respuesta anterior, bien demostrado con regresión lineal. Hay algunos casos de uso en los que k-means tiene mucho sentido. Cuando Lloyd tuvo que decodificar señales PCM, él sabía la cantidad de tonos diferentes, y el error de mínimos cuadrados minimiza la posibilidad de errores de decodificación. Y en la cuantización del color de las imágenes, también minimiza el error de color al reducir la paleta. Pero en sus datos, ¿es la suma de las desviaciones al cuadrado un criterio significativo para minimizar?

En el contraejemplo anterior, no vale la pena minimizar la varianza , porque depende del clúster. En cambio, un modelo de mezcla gaussiana debe ajustarse a los datos, como en la figura a continuación:

(Pero este tampoco es el método definitivo. Es igual de fácil construir datos que no satisfacen los supuestos de la "mezcla de distribuciones k gaussianas", por ejemplo, agregando mucho ruido de fondo)

Demasiado fácil de usar mal

Con todo, es demasiado fácil arrojar k-means en sus datos y, sin embargo, obtener un resultado (que es bastante aleatorio, pero no lo notará). Creo que sería mejor tener un método que pueda fallar si no ha entendido sus datos ...

K-medias como cuantización

Si desea un modelo teórico de lo que significa k-means, considérelo un enfoque de cuantificación , no un algoritmo de agrupamiento.

El objetivo de k-means (minimizar el error al cuadrado) es una opción razonable si reemplaza cada objeto por su centroide más cercano. (Tiene mucho menos sentido si inspecciona los datos originales de los grupos en mi humilde opinión).

Hay muy buenos casos de uso para esto. Me viene a la mente el caso de uso original de PCM de Lloyd, o por ejemplo, la cuantización del color (Wikipedia) . Si desea reducir una imagen para k colores, que no desea reemplazar cada píxel con el centroide más cercano. Al minimizar la desviación de color al cuadrado , se mide la optimización de L2 en la aproximación de la imagen utilizando solo colores.$k$

Esta cuantización es probablemente bastante similar al ejemplo de regresión lineal. La regresión lineal encuentra el mejor modelo lineal . Y k-means encuentra (a veces) la mejor reducción a los valores k de un conjunto de datos multidimensional. Donde "mejor" es el error de menor cuadrado.

En mi humilde opinión, k-means es un buen algoritmo de cuantificación (vea la primera imagen en esta publicación; si desea aproximar el conjunto de datos a dos puntos, ¡esta es una opción razonable!). Si desea hacer un análisis de conglomerados como en la estructura de descubrimiento, k-means es, en mi humilde opinión, no la mejor opción. Tiende a agruparse cuando no hay agrupaciones, y no puede reconocer varias estructuras que sí ve mucho en los datos.

Letra pequeña: todas las imágenes se generaron con ELKI . Los datos se generaron utilizando el .xmlformato de generación de datos, pero son tan básicos que no vale la pena compartirlos.

Qué gran pregunta: es una oportunidad para mostrar cómo se inspeccionarían los inconvenientes y los supuestos de cualquier método estadístico. A saber: invente algunos datos y pruebe el algoritmo!

Consideraremos dos de sus supuestos, y veremos qué sucede con el algoritmo k-means cuando esos supuestos se rompen. Nos atendremos a los datos bidimensionales ya que es fácil de visualizar. (Gracias a la maldición de la dimensionalidad , agregar dimensiones adicionales probablemente hará que estos problemas sean más graves, no menos). Trabajaremos con el lenguaje de programación estadística R: puede encontrar el código completo aquí (y la publicación en forma de blog aquí ).

Desvío: Cuarteto de Anscombe

Primero, una analogía. Imagine que alguien argumentó lo siguiente:

Leí algo de material sobre los inconvenientes de la regresión lineal: que espera una tendencia lineal, que los residuos se distribuyen normalmente y que no hay valores atípicos. Pero todo lo que está haciendo la regresión lineal es minimizar la suma de los errores al cuadrado (SSE) de la línea pronosticada. Ese es un problema de optimización que se puede resolver sin importar la forma de la curva o la distribución de los residuos. Por lo tanto, la regresión lineal no requiere suposiciones para funcionar.

Bueno, sí, la regresión lineal funciona minimizando la suma de los residuos al cuadrado. Pero eso en sí mismo no es el objetivo de una regresión: lo que estamos tratando de hacer es dibujar una línea que sirva como un predictor confiable e imparcial de y basado en x . El teorema de Gauss-Markov nos dice que minimizar el SSE logra ese objetivo, pero ese teorema se basa en algunos supuestos muy específicos. Si esas suposiciones se rompen, aún puede minimizar el SSE, pero podría no funcionar .cualquier cosa. Imagínese diciendo "Conduce un automóvil presionando el pedal: conducir es esencialmente un 'proceso de presionar el pedal'. El pedal se puede presionar sin importar la cantidad de gasolina en el tanque. Por lo tanto, incluso si el tanque está vacío, aún puede presionar el pedal y conducir el automóvil ".

Pero hablar es barato. Veamos los datos fríos y duros. O en realidad, datos inventados.

De hecho, esta es mi información inventada favorita : Anscombe's Quartet . Creada en 1973 por el estadístico Francis Anscombe, esta deliciosa mezcla ilustra la locura de confiar ciegamente en métodos estadísticos. Cada uno de los conjuntos de datos tiene la misma pendiente de regresión lineal, intersección, valor p y , y sin embargo, de un vistazo podemos ver que solo uno de ellos, I , es apropiado para la regresión lineal. En II sugiere la forma incorrecta, en III está sesgada por un solo valor atípico, ¡y en IV claramente no hay tendencia en absoluto!$R^2$

Se podría decir "La regresión lineal todavía funciona en esos casos, porque está minimizando la suma de los cuadrados de los residuos". ¡Pero qué victoria pírrica ! La regresión lineal siempre dibujará una línea, pero si es una línea sin sentido, ¿a quién le importa?

Así que ahora vemos que solo porque se puede realizar una optimización no significa que estemos logrando nuestro objetivo. Y vemos que inventar datos y visualizarlos es una buena manera de inspeccionar los supuestos de un modelo. Aférrate a esa intuición, la necesitaremos en un minuto.

Suposición rota: datos no esféricos

Usted argumenta que el algoritmo k-means funcionará bien en grupos no esféricos. Racimos no esféricos como ... ¿estos?

Tal vez esto no sea lo que esperabas, pero es una forma perfectamente razonable de construir clústeres. Al observar esta imagen, los humanos reconocemos inmediatamente dos grupos naturales de puntos: no hay que confundirlos. Entonces, veamos cómo lo hace k-means: las asignaciones se muestran en color, los centros imputados se muestran como X.

Bueno, eso no está bien. K-means estaba tratando de colocar una clavija cuadrada en un agujero redondo , tratando de encontrar centros agradables con esferas ordenadas a su alrededor, y falló. Sí, sigue minimizando la suma de cuadrados dentro del grupo, pero al igual que en el Cuarteto de Anscombe anterior, ¡es una victoria pírrica!

Podría decir: "Ese no es un ejemplo justo ... ningún método de agrupación podría encontrar correctamente agrupaciones que sean tan extrañas". ¡No es verdad! Pruebe el agrupamiento jerárquico de enlace único :

¡Dado en el clavo! Esto se debe a que la agrupación jerárquica de enlace único hace las suposiciones correctas para este conjunto de datos. (Hay otra clase de situaciones en las que falla).

Podría decir "Ese es un caso único, extremo y patológico". ¡Pero no lo es! Por ejemplo, puede hacer que el grupo externo sea un semicírculo en lugar de un círculo, y verá que k-means todavía funciona terriblemente (y la agrupación jerárquica todavía funciona bien). Podría encontrar otras situaciones problemáticas fácilmente, y eso es solo en dos dimensiones. Cuando agrupa datos en 16 dimensiones, puede surgir todo tipo de patologías.

Por último, debo tener en cuenta que k-means todavía es salvable. Si comienza transformando sus datos en coordenadas polares , la agrupación ahora funciona:

Es por eso que comprender los supuestos subyacentes a un método es esencial: no solo te dice cuándo un método tiene inconvenientes, sino que te dice cómo solucionarlos.

Suposición rota: grupos de tamaño desigual

¿Qué pasa si los grupos tienen un número desigual de puntos? ¿Eso también rompe el grupo k-significa? Bueno, considere este conjunto de grupos, de tamaños 20, 100, 500. He generado cada uno de un gaussiano multivariante:

Parece que k-means probablemente podría encontrar esos grupos, ¿verdad? Todo parece generarse en grupos limpios y ordenados. Entonces intentemos k-means:

Ay. Lo que sucedió aquí es un poco más sutil. En su búsqueda para minimizar la suma de cuadrados dentro del grupo, el algoritmo k-means da más "peso" a los grupos más grandes. En la práctica, eso significa que es feliz dejar que ese grupo pequeño termine lejos de cualquier centro, mientras usa esos centros para "dividir" un grupo mucho más grande.

Si juegas un poco con estos ejemplos (¡ código R aquí! ), Verás que puedes construir muchos más escenarios en los que k-means se equivoca vergonzosamente.

Conclusión: sin almuerzo gratis

Hay una construcción encantadora en el folklore matemático, formalizada por Wolpert y Macready , llamada el "Teorema de no almuerzo gratis". Probablemente sea mi teorema favorito en la filosofía de aprendizaje automático, y disfruto cualquier posibilidad de plantearlo (¿mencioné que me encanta esta pregunta?) La idea básica se plantea (sin rigor) como esta: "Cuando se promedia en todas las situaciones posibles, cada algoritmo funciona igual de bien ".

¿Suena contraintuitivo? Considere que para cada caso donde funciona un algoritmo, podría construir una situación en la que falla terriblemente. La regresión lineal supone que sus datos caen a lo largo de una línea, pero ¿y si sigue una onda sinusoidal? Una prueba t supone que cada muestra proviene de una distribución normal: ¿qué pasa si arroja un valor atípico? Cualquier algoritmo de ascenso de gradiente puede quedar atrapado en los máximos locales, y cualquier clasificación supervisada puede ser engañada para ajustarse en exceso.

¿Qué significa esto? ¡Significa que las suposiciones son de donde proviene tu poder! Cuando Netflix te recomienda películas, se supone que si te gusta una película, te gustarán películas similares (y viceversa). Imagina un mundo donde eso no fuera cierto, y tus gustos están perfectamente dispersos al azar en géneros, actores y directores. Su algoritmo de recomendación fallaría terriblemente. ¿Tendría sentido decir "Bueno, todavía está minimizando algunos errores al cuadrado esperados, por lo que el algoritmo sigue funcionando"? No puede hacer un algoritmo de recomendación sin hacer algunas suposiciones sobre los gustos de los usuarios, al igual que no puede hacer un algoritmo de agrupación sin hacer algunas suposiciones sobre la naturaleza de esos grupos.

Así que no solo acepte estos inconvenientes. Conózcalos para que puedan informarle su elección de algoritmos. Comprenderlos, para que pueda ajustar su algoritmo y transformar sus datos para resolverlos. Y ámalos, porque si tu modelo nunca puede estar equivocado, eso significa que nunca estará bien.

Solo me gustaría agregar a la respuesta de @ DavidRobinson que el agrupamiento a una varianza mínima total del clúster es en realidad un problema de optimización combinatoria , del cual k-Means es solo una técnica, y dada la naturaleza de "un disparo" local, "descenso más pronunciado" de este último, uno bastante malo también. Además, tratar de mejorar sustancialmente los k-medias de "huesos desnudos" de alguna manera (¡pero rápidamente!) Descubriendo dónde deberían estar las semillas del racimo, está condenado desde el principio: dado que las semillas impactan (drásticamente) los racimos finales, asciende para "saber" cuál es el óptimo ... antes de calcularlo realmente.

Sin embargo, como la mayoría de los problemas de optimización, puede ser útil para algunas técnicas de optimización serias . Uno de ellos se ajusta muy bien a la estructura del problema (¡como lo requiere la NFL!), Y ciertamente se nota en sus resultados. No quiero hacer ningún anuncio aquí (sería, y con razón, contra la etiqueta), así que si está interesado, léalo aquí y haga su propio juicio.

Dicho esto, estoy de acuerdo con @ttnphns en que k-Means ciertamente no identifica una mezcla gaussiana: las funciones de costo de los dos problemas son completamente diferentes. Resulta que encontrar el mejor ajuste (en términos de probabilidad del modelo dado los datos) de la Mezcla Gaussiana también es un problema de optimización combinatoria , y para el cual también existe una técnica de optimización seria . Una vez más, no hay anuncios: puede llegar a su propia conclusión aquí : solo diré que el algoritmo discutido allí puede, de hecho, identificar correctamente los grupos como la última imagen en la publicación de @ DavidRobinson . Incluso correctamente (es decir, de una manera matemáticamente bien definida) resuelve el problema perenne de los valores atípicos, es decir, puntos de datos que no pertenecen a ninguno de los clústeres porque son completamente aleatorios (notoriamente, descarrilan completamente k-Means, por ejemplo). Esto se logra haciendo que una distribución adicional y uniforme compita con los gaussianos ... y el espléndido resultado es que en los datos distribuidos uniformemente, de hecho informa que no hay nada allí (nunca he visto eso en ningún otro lugar).

Ahora, obviamente, según la NFL, y como señaló correctamente , incluso las mezclas gaussianas globalmente óptimas con identificación atípica se basan en una suposición previa, a saber, que los datos se distribuyen normalmente. Afortunadamente, sin embargo, gracias a la Ley de los Grandes Números, numerosos fenómenos naturales no cumplen con esa suposición.

DESCARGO DE RESPONSABILIDAD: con mis más sinceras disculpas, escribí los dos documentos anteriores y los algoritmos que discuten.

PD: Una vez conocí a Macready en una conferencia, ¡un tipo extremadamente brillante y agradable!

Lógicamente hablando, los inconvenientes de K-means son:

• necesita separabilidad lineal de los grupos
• necesita especificar el número de grupos
• Algoritmos: el procedimiento de Loyds no converge al máximo global verdadero incluso con una buena inicialización cuando hay muchos puntos o dimensiones

Pero K-means es mejor de lo que generalmente pensamos. Me entusiasmé al respecto después de probarlo con otros métodos de agrupamiento (espectral, densidad ...) y LDA en la clasificación de textos de la vida real de un millón de textos: K-means tenía una precisión mucho mejor que LDA, por ejemplo (88% vs 59%). Algunos otros métodos de agrupamiento eran buenos, pero K-means estaba cerca de la cima ... y más asequible en términos de complejidad.

Nunca he leído sobre un método de agrupación que sea universalmente mejor en una amplia gama de problemas. No decir que K-means es universalmente mejor tampoco, solo que, hasta donde yo sé, no hay un superhéroe de agrupación universal. Muchos artículos, muchos métodos, no una verdadera revolución (en mi experiencia personal limitada de probar algunos de ellos).

La razón principal por la cual los inconvenientes lógicos de K-means a menudo solo son evidentes es que los puntos de agrupación en un plano 2D es algo que rara vez se hace en el aprendizaje automático. Muchas cosas de la intuición geométrica que son ciertas en 2D, 3D ... son irrelevantes en espacios de vectores abstractos o de dimensiones bastante altas (como bolsa de palabras, vector de variables ...)

Separación lineal: rara vez tiene que lidiar con grupos circulares en los datos de la vida real. Es incluso mejor suponer que no existen en estos casos. Permitir que su algoritmo los busque le permitiría encontrar grupos circulares extraños en el ruido. La suposición lineal en K-means lo hace a menudo más robusto.

Número de grupos: a menudo no hay un verdadero número ideal de grupos que desee ver. Para la clasificación de texto, por ejemplo, puede haber 100 categorías, 105, 110 ... todo es bastante subjetivo. Especificar el número de clústeres se convierte en equivalente a especificar una granularidad global. Todos los métodos de agrupación necesitan una especificación de granularidad de todos modos.

$10^{\text{a lot}}$

Pero todos los algoritmos de agrupamiento tienen tales limitaciones. Por ejemplo, en el agrupamiento espectral: no puede encontrar los vectores propios verdaderos, solo aproximaciones.

Por el mismo tiempo de cálculo, una biblioteca LDA bastante optimizada funcionó menos que nuestros medios K caseros (no perfectamente optimizados). Desde entonces, pienso un poco diferente.

Para comprender los inconvenientes de K-means, me gusta pensar cuál es el modelo detrás de él.

$K$$K$

$K$$\sigma^2 \mathbf{I}$$\sigma^2$$K$$\sigma^2 \rightarrow 0$

Entonces, ¿qué nos dice esto sobre los inconvenientes de K-means?

1. K-means conduce a grupos que parecen gaussianos multivariados.
2. Como la varianza entre las variables es la misma, K-means conduce a grupos que parecen esféricos.
3. $K$
4. K-means tiende hacia grupos de igual tamaño.

K-means es en realidad un algoritmo bastante restrictivo. La ventaja es que con los supuestos anteriores, puede realizar el algoritmo con bastante rapidez. Pero si el rendimiento de la agrupación es su principal preocupación, K-means suele ser demasiado restrictivo en situaciones reales.