Cómo entender los inconvenientes de K-means

Question

K-means es un método muy utilizado en el análisis de conglomerados. A mi entender, este método no requiere NINGUNA suposición, es decir, dame un conjunto de datos y un número preestablecido de conglomerados, k, y simplemente aplico este algoritmo que minimiza la suma de errores al cuadrado (SSE), el error al cuadrado dentro del conglomerado.

Así que k-means es esencialmente un problema de optimización.

He leído algo sobre los inconvenientes de k-means. La mayoría de ellos dicen 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 a priori para todos los k clusters es la misma, es decir, cada cluster tiene aproximadamente el mismo número de observaciones;

Si se incumple alguno de estos 3 supuestos, k-means fallará.

No pude entender la lógica de esta afirmación. Creo que el método de k-means no hace esencialmente ninguna suposición, sólo minimiza el SSE, así que no puedo ver el vínculo entre la minimización del SSE y esas 3 "suposiciones".

Answer 1

Qué gran pregunta: es una oportunidad para mostrar cómo se inspeccionan los inconvenientes y los supuestos de cualquier método estadístico. A saber: inventar algunos datos y probar el algoritmo con ellos.

Consideraremos dos de sus supuestos, y veremos qué ocurre con el algoritmo de k-means cuando se rompen esos supuestos. Nos ceñiremos a los datos bidimensionales, ya que son fáciles de visualizar. (Gracias a la maldición de la dimensionalidad Si no se puede hacer nada, es probable que la adición de dimensiones adicionales haga que estos problemas sean más graves, no menos). Trabajaremos con el lenguaje de programación estadística R: puedes encontrar el código completo aquí (y la entrada en forma de blog aquí ).

Desvío: El cuarteto de Anscombe

Primero, una analogía. Imagina que alguien argumenta lo siguiente:

He leído algún 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 lo único que hace la regresión lineal es minimizar la suma de errores al cuadrado (SSE) de la línea predicha. Ese es un problema de optimización que puede resolverse sin importar la forma de la curva o la distribución de los residuos. Por lo tanto, la regresión lineal no requiere ninguna suposición para funcionar.

Pues sí, la regresión lineal funciona minimizando la suma de los residuos al cuadrado. Pero ése no es en sí mismo el objetivo de una regresión: lo que estamos probando hacer es trazar una línea que sirva como predictor fiable e imparcial de y basado en x . El Teorema de Gauss-Markov nos dice que la minimización de la SSE cumple ese objetivo, pero ese teorema se basa en algunas suposiciones muy específicas. Si esas suposiciones se rompen, todavía se puede minimizar la SSE, pero puede que no hacer cualquier cosa. Imagínese que dice "Se conduce un coche pisando el pedal: conducir es esencialmente un "proceso de pisar el pedal". Se puede pisar el pedal independientemente de la cantidad de gasolina que haya en el depósito. Por lo tanto, aunque el depósito esté vacío, se puede pisar el pedal y conducir el coche".

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

De hecho, este es mi favorito datos inventados: Cuarteto de Anscombe . Creado en 1973 por el estadístico Francis Anscombe, este delicioso brebaje ilustra la locura de confiar ciegamente en los métodos estadísticos. Cada uno de los conjuntos de datos tiene la misma pendiente de regresión lineal, intercepción, valor p y $R^2$ - y, sin embargo, a simple vista podemos ver que sólo uno de ellos I es apropiado para la regresión lineal. En II sugiere la forma incorrecta, en III está sesgada por un único valor atípico- y en IV es evidente que no hay ninguna tendencia.

Se podría decir que "la regresión lineal sigue siendo trabajando en esos casos, porque está minimizando la suma de cuadrados de los residuos". Pero lo que es un 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 el hecho de que se pueda realizar una optimización no significa que estemos cumpliendo nuestro objetivo. Y vemos que inventar datos, y visualizarlos, es una buena manera de inspeccionar los supuestos de un modelo. Agarraos a esa intuición, la vamos a necesitar en un minuto.

Supuesto roto: Datos no esféricos

Usted sostiene que el algoritmo k-means funcionará bien en clusters no esféricos. ¿Grupos no esféricos como... estos?

Tal vez no sea lo que esperabas, pero es una forma perfectamente razonable de construir clusters. Mirando esta imagen, los humanos inmediatamente reconocer dos grupos naturales de puntos, no hay que confundirlos. Veamos cómo lo hace k-means: las asignaciones se muestran en color, los centros imputados se muestran como X.

Bueno, que no está bien. K-means estaba tratando de encajar un una clavija cuadrada en un agujero redondo - tratando de encontrar centros bonitos con esferas ordenadas alrededor de ellos- y falló. Sí, sigue minimizando la suma de cuadrados dentro del clúster, pero al igual que en el Cuarteto de Anscombe, es una victoria pírrica.

Usted podría decir "Ese no es un ejemplo justo... no método de clustering podría encontrar correctamente clusters así de raros". ¡No es cierto! Pruebe con enlace único agrupación jerárquica :

Lo he clavado. Esto se debe a que la agrupación jerárquica de enlace único hace que el a la derecha supuestos para este conjunto de datos. (Hay todo un otros clase de situaciones en las que falla).

Podrías decir: "Es un caso único, extremo y patológico". ¡Pero no lo es! Por ejemplo, puedes hacer que el grupo exterior sea un semicírculo en lugar de un círculo, y verás que k-means sigue haciéndolo fatal (y el clustering jerárquico sigue haciéndolo bien). Se me ocurren otras situaciones problemáticas fácilmente, y eso sólo en dos dimensiones. Cuando se agrupan datos de 16 dimensiones, pueden surgir todo tipo de patologías.

Por último, debo señalar que k-means todavía es salvable. Si se empieza por transformar los datos en coordenadas polares La agrupación ahora funciona:

Por eso es esencial comprender los supuestos en los que se basa un método: no sólo te dice cuando un método tiene inconvenientes, sino que te dice cómo solucionarlos.

Supuesto roto: Agrupaciones de tamaño desigual

¿Qué pasa si los clusters tienen un número desigual de puntos - eso también rompe el clustering de k-means? Bien, consideremos este conjunto de clusters, de tamaños 20, 100, 500. He generado cada uno de ellos a partir de una gaussiana multivariante:

Parece que k-means podría encontrar esos grupos, ¿no? Todo parece generarse en grupos limpios y ordenados. Así que probemos con k-means:

Ouch. Lo que ocurrió aquí es un poco más sutil. En su búsqueda por minimizar la suma de cuadrados dentro del cluster, el algoritmo k-means da más "peso" a los clusters más grandes. En la práctica, eso significa que está contento de dejar que ese pequeño clúster acabe lejos de cualquier centro, mientras utiliza esos centros para "dividir" un clúster 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: No hay almuerzo gratis

Hay una construcción encantadora en el folclore matemático, formalizada por Wolpert y Macready El teorema del almuerzo gratis". Es probablemente mi teorema favorito en la filosofía del aprendizaje automático, y disfruto de cualquier oportunidad para sacarlo a colación (¿he mencionado que me encanta esta pregunta?) La idea básica se enuncia (sin rigor) así: "Cuando se promedia en todas las situaciones posibles, todos los algoritmos funcionan igual de bien".

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

¿Qué significa esto? Significa que los supuestos ¡son de donde viene tu poder! Cuando Netflix te recomienda películas, está asumiendo que si te gusta una película, te gustarán otras similares (y viceversa). Imagina un mundo en el que eso no fuera cierto, y tus gustos fueran perfectamente aleatorios, dispersos al azar entre géneros, actores y directores. Su algoritmo de recomendación fallaría terriblemente. ¿Tendría sentido decir "Bueno, sigue minimizando un error cuadrático esperado, así que el algoritmo sigue funcionando"? No se puede hacer un algoritmo de recomendación sin hacer algunas suposiciones sobre los gustos de los usuarios, al igual que no se puede hacer un algoritmo de agrupación sin hacer algunas suposiciones sobre la naturaleza de esos grupos.

Así que no aceptes sin más estos inconvenientes. Conócelos, para que te sirvan de base para elegir los algoritmos. Entiéndelos, para que puedas ajustar tu algoritmo y transformar tus datos para resolverlos. Y ámalos, porque si tu modelo no puede equivocarse nunca, significa que nunca estará bien.

---

Answer 2

Aunque me gusta Respuesta de David Robinson aquí mucho, aquí hay una crítica adicional de k-means.

Agrupación de datos no agrupados

Ejecute k-means en datos uniformes, y usted todavía ¡consigue racimos! No te dice cuando los datos sólo lo hacen no cluster, y puede llevar su investigación a un callejón sin salida de esta manera.

Sensible a la escala

Reescalar los conjuntos de datos cambiará completamente los resultados. Aunque esto en sí no es malo, no darse cuenta de que hay que prestar más atención al escalado de los datos es malo. Los factores de escala son extra $d$ parámetros ocultos en k-means que "por defecto" son 1 y, por lo tanto, se pasan por alto fácilmente, aunque tienen un gran impacto (pero, por supuesto, esto también se aplica a muchos otros algoritmos).

Esto es probablemente lo que se refiere a que "todas las variables tienen la misma varianza". Excepto que, idealmente, también considerarías el escalamiento no lineal cuando sea apropiado.

También hay que tener en cuenta que es sólo una heurística para escalar cada eje para tener una varianza unitaria . Esto no asegura que k-means funcione. El escalamiento depende del significado de su conjunto de datos. Y si tiene más de un cluster, querrá que cada cluster (independientemente) tenga la misma varianza en cada variable, también.

He aquí un contraejemplo clásico de conjuntos de datos que k-means no puede racimo. Ambos ejes son i.i.d. en cada clúster, por lo que bastaría con hacerlo en 1 dimensión. Pero los clústeres tienen variantes distintas y, por tanto, k-means los divide incorrectamente.

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

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

Sin embargo, k-means sigue fallando mucho (y empeora si aumento la varianza más allá de 0,5 para el cluster más grande) Pero: no es el algoritmo el que ha fallado. Son las suposiciones, que no se sostienen . K-means funciona perfectamente, sólo está optimizando el criterio equivocado.

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

A continuación se muestra el mejor de 10 ejecuciones de k-means en el conjunto de datos clásico A3. Se trata de un conjunto de datos sintéticos, diseñado para k-means . 50 clusters, cada uno de ellos con forma gaussiana, razonablemente bien separados. Sin embargo, sólo con k-means++ y 100 iteraciones obtuve el resultado esperado... (abajo hay 10 iteraciones de k-means normal, para ilustrar).

Encontrará rápidamente muchos clusters en este conjunto de datos, en los que k-means no encontró la estructura correcta. Por ejemplo, en la parte inferior derecha, un clúster se dividió en tres partes. Pero no hay manera de que k-means mueva uno de estos centroides a un lugar completamente diferente del conjunto de datos - está atrapado en un mínimo local (y esto ya era el mejor de 10 carreras)

Y hay muchos de tales mínimos locales en este conjunto de datos. Muy a menudo, cuando se obtienen dos muestras del mismo clúster, se atascará en un mínimo en el que este clúster permanece dividido, y otros dos clústeres fusionados en su lugar. No siempre, pero sí muy a menudo. Así que se necesitan muchas iteraciones para tener una selección afortunada. Con 100 iteraciones de k-means, todavía conté 6 errores, y con 1000 iteraciones lo bajé a 4 errores. K-means++ por la forma en que pondera las muestras aleatorias, funciona mucho mejor en este conjunto de datos.

Los medios son continuos

Aunque se puede ejecutar k-means sobre datos binarios (o datos categóricos codificados con un punto) los resultados ya no serán binarios. Por lo tanto, se obtiene un resultado, pero puede ser incapaz de interpretarlo al final, porque tiene un tipo de datos diferente al de los datos originales.

Supuesto oculto: La ESS es vale minimizar

Esto ya está presente en la respuesta anterior, muy bien demostrada con la regresión lineal. Hay algunos casos de uso en los que k-means tiene mucho sentido. Cuando Lloyd tenía que decodificar señales PCM, conocía el número de tonos diferentes, y el error mínimo cuadrático minimiza la posibilidad de errores de decodificación. Y en la cuantificación del color de las imágenes, también se minimiza el error de color al reducir la paleta. Pero en sus datos, ¿es la suma de desviaciones al cuadrado un criterio significativo para minimizar?

En el contraejemplo anterior, la varianza es no que vale la pena minimizar, ya que depende de la agrupación. En su lugar, debe ajustarse a los datos un modelo de mezcla gaussiana, como en la figura siguiente:

(Pero esto es no el método definitivo tampoco. Es igual de fácil construir datos que no satisfagan los supuestos de "mezcla de k distribuciones gaussianas", por ejemplo, añadiendo mucho ruido de fondo)

Demasiado fácil de usar mal

En definitiva, es demasiado fácil lanzar k-means sobre tus datos y, sin embargo, sacar un resultado (que es bastante aleatorio, pero no se nota). Creo que sería mejor tener un método que pueda fallar si no has entendido tus datos...

K-means como cuantificación

Si quieres un modelo teórico de lo que hace k-means, considéralo un cuantificación y no un algoritmo de agrupación.

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

Hay muy buenos casos de uso para esto. Me viene a la mente el caso de uso original del PCM de Lloyd, o por ejemplo cuantificación del color (Wikipedia) . Si desea reducir una imagen a k colores, debe hacer quiere reemplazar cada píxel con el centroide más cercano. Minimizando la desviación de color al cuadrado entonces hace medida de optimalidad L2 en la aproximación de imágenes mediante $k$ sólo colores.

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

En mi opinión, k-means es un buen cuantificación (ver la primera imagen de este post - si quieres aproximar el conjunto de datos a dos puntos, esta es una opción razonable). Si quieres hacer un análisis de cluster como en descubrir la estructura entonces k-means no es, en mi opinión, la mejor opción. Tiende a agrupar cuando no hay clusters, y no puede reconocer varias estructuras que sí se ven mucho en los datos.

---

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

Answer 3

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

• necesita separabilidad lineal de las agrupaciones
• necesita especificar el número de grupos
• Algoritmo : El procedimiento de Loyds no converge a la verdadera máximo mundial incluso con una buena inicialización cuando hay muchos puntos o dimensiones

Pero K-means es mejor de lo que solemos pensar. Me he entusiasmado con él después de probarlo frente a otros métodos de agrupación (espectral, de densidad...) y LDA en la clasificación de un millón de textos en la vida real: K-means tuvo una precisión mucho mayor que LDA, por ejemplo (88% frente a 59%). Algunos otros métodos de clustering 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. Tampoco digo que K-means sea universalmente mejor, sólo que no hay un superhéroe de clustering universal hasta donde yo sé. Muchos artículos, muchos métodos, no una verdadera revolución (en mi limitada experiencia personal de probar algunos de ellos).

La razón principal por la que los inconvenientes lógicos de K-means suelen ser sólo aparentes es que la agrupación de puntos 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 vectoriales más bien de alta dimensión o abstractos (como bolsa de palabras, vector de variables...)

Separabilidad lineal : Rara vez hay que enfrentarse a clusters circulares en los datos de la vida real. Incluso es mejor suponer que no existen en estos casos. Permitir que su algoritmo los busque le permitiría encontrar clusters circulares Impares en el ruido. La suposición lineal en K-means lo hace a menudo más robusto.

Número de racimos : A menudo no hay un número ideal de racimos que se desee ver. Para la clasificación de textos, por ejemplo, puede haber 100 categorías, 105, 110... todo es bastante subjetivo. Especificar el número de clusters equivale a especificar una granularidad global. Todos los métodos de clustering necesitan una especificación de granularidad de todos modos.

Máximo global : Creo que es un problema real. El verdadero K-means abstracto que consistiría en encontrar el mínimo global para el S.O.D es fundamentalmente NP-Hard. Sólo Lloyd es asequible y es... muy imperfecto. Realmente hemos visto que estar cerca del mínimo real (gracias a las réplicas) mejoraba claramente la calidad de los resultados. La replicación de los K-means es una mejora pero no una solución perfecta. Para un gran conjunto de datos se necesitaría $10^{\text{a lot}}$ réplicas para tener una pequeña posibilidad de encontrar el verdadero mínimo. Otros métodos como el de "acabar con la búsqueda codiciosa" (propuesto en Matlab) son astronómicamente costosos en conjuntos de datos grandes.

Pero todos los algoritmos de clustering tienen estas limitaciones. Por ejemplo, en el clustering espectral: no se pueden encontrar los verdaderos vectores propios, sólo aproximaciones.

Para el mismo tiempo de cálculo, una biblioteca LDA bastante optimizada lo hizo menos bien que nuestro K-means casero (no perfectamente optimizado). Desde entonces, pienso un poco diferente.

Answer 4

Sólo me gustaría añadir a la respuesta de @DavidRobinson que agrupación para minimizar la varianza total de los clústeres es en realidad un optimización combinatoria de los cuales k-Means es sólo una técnica - y dada la naturaleza de este último de "una sola vez", de "descenso más pronunciado", una bastante malo uno también. Además, intentar mejorar sustancialmente el k-Means "básico" averiguando de alguna manera (¡pero rápidamente!) dónde deben estar las semillas de los clusters, está condenado desde el principio: como las semillas afectan (¡drásticamente!) a los clusters finales, equivale a "saber" cuál es el óptimo... antes de computándolo realmente.

Sin embargo, como la mayoría de los problemas de optimización, puede ser susceptible de algunas optimización seria técnica. Una de ellas se ajusta muy bien a la estructura del problema (¡como exige la NFL!), y ciertamente se nota en sus resultados. No quiero hacer ningún anuncio aquí (iría -y con razón- en contra de la etiqueta), así que si te interesa, léelo aquí y hacer su propio juicio.

Dicho esto, estoy de acuerdo con @ttnphns en que k-Means ciertamente no identificar una Mezcla Gaussiana - las funciones de coste de los dos problemas son completamente diferentes. Resulta que encontrar la Mezcla Gaussiana que mejor se ajusta (en términos de probabilidad del modelo dados los datos) es también un optimización combinatoria problema - y uno para el cual un optimización seria también existe la técnica. Una vez más, no hay anuncios: usted puede llegar a su propia conclusión aquí - Sólo diré que el algoritmo discutido allí puede, efectivamente, identificar correctamente clusters como la última imagen del post de @DavidRobinson . Incluso resuelve correctamente (es decir, de forma matemáticamente bien definida) el eterno problema de valores atípicos es decir, los puntos de datos que no no pertenecer a cualquiera de las agrupaciones porque son completamente aleatorias (notoriamente descarrilar completamente k-Means por ejemplo). Esto se hace teniendo una adicional, distribución uniforme competir con los gaussianos... y el espléndido resultado es que en datos uniformemente distribuidos, efectivamente informa hay nada ahí dentro (Nunca he visto eso en ningún otro sitio).

Ahora, obviamente, según la NFL, y como su señaló acertadamente Incluso las mezclas gaussianas globalmente óptimas con identificación de valores atípicos se basan en una suposición previa, a saber, que los datos se distribuyen normalmente. Pero, afortunadamente, gracias a la Ley de los Grandes Números, numerosos fenómenos naturales hacer cumplir con ese supuesto.

DISCLAIMER: con mis más sinceras disculpas, yo escribí los dos artículos anteriores y los algoritmos que discuten.

P.D. Una vez conocí a Macready en una conferencia - ¡un tipo extremadamente brillante y agradable!

Answer 5

Para entender los inconvenientes de K-means, me gusta pensar en el modelo que hay detrás.

K-means es un caso especial de los modelos de mezcla gaussiana (GMM). El GMM asume que los datos provienen de una mezcla de $K$ Distribuciones gaussianas. En otras palabras, hay una cierta probabilidad de que los datos provengan de una de $K$ de las distribuciones gaussianas.

Si hacemos que la probabilidad de estar en cada uno de los $K$ Gaussianos iguales y hacer que las matrices de covarianza sean $\sigma^2 \mathbf{I}$ , donde $\sigma^2 $ es la misma constante fija para cada uno de los $K$ Gaussianos, y tomar el límite cuando $\sigma^2 \rightarrow 0$ entonces obtenemos K-means.

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

1. K-means conduce a clusters que parecen gaussianos multivariados.
2. Dado que la varianza de las variables es la misma, K-means da lugar a clusters de aspecto esférico.
3. No sólo los conglomerados parecen esféricos, sino que, como la matriz de covarianza es la misma en todas las $K$ grupos, K-means conduce a clusters que se parecen a la misma esfera.
4. K-means tiende a los grupos de igual tamaño.

K-means es en realidad un algoritmo bastante restrictivo. La ventaja es que, con los supuestos anteriores, se 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.