341 votos

Cómo entender los inconvenientes de K-means

K-means es un método ampliamente utilizado en el análisis de cluster. A mi entender, este método NO requiere NINGÚN tipo de supuestos, es decir, me dan un conjunto de datos y un número preestablecido de clusters, k, y acabo de aplicar este algoritmo que minimiza la ESS, el plazo de clúster error cuadrado.

Por lo que k-means es esencialmente un problema de optimización.

He leído algunos de los materiales sobre los inconvenientes de k-means. La mayoría de ellos dicen que:

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

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

Yo no podía entender la lógica detrás de esta afirmación. Creo que el k-means método hace que en esencia, no de suposiciones, sólo minimiza la ESS, así que no puedo ver el vínculo entre la reducción al mínimo de la ESS y los 3 "supuestos".

431voto

mdahlman Puntos 5700

Qué gran pregunta - es una oportunidad para mostrar la manera de inspeccionar las desventajas y los supuestos de cualquier método estadístico. A saber: hacer algunos datos y probar el algoritmo en él!

Vamos a considerar dos de sus supuestos, y vamos a ver qué pasa con el k-means el algoritmo cuando esos supuestos están rotos. Nos ceñiremos a 2-dimensional de datos, ya que es fácil de visualizar. (Gracias a la maldición de la dimensionalidad, la adición de dimensiones adicionales es probable que estos problemas más graves, no menos). Vamos a trabajar con la estadística lenguaje de programación R: usted puede encontrar el código completo aquí (y en el post en el blog de la forma aquí).

Desviación: Cuarteto de Anscombe

En primer lugar, una analogía. Imagina a alguien argumentó lo siguiente:

He leído algunos de los materiales sobre los inconvenientes de regresión lineal - que se espera una tendencia lineal, que los residuos están normalmente distribuidos, y que no hay valores atípicos. Pero todos los que la regresión lineal está haciendo es minimizar la suma de los cuadrados de los errores (SSE) a partir de la predicción de la línea. Eso es un problema de optimización que puede ser solucionado no importa cuál sea la forma de la curva o la distribución de los residuos es. Por lo tanto, la regresión lineal no requiere de hipótesis de trabajo.

Bueno, sí, la regresión lineal funciona mediante la minimización de la suma de los cuadrados de los residuales. Pero que por sí misma no es el objetivo de una regresión: ¿qué estamos tratando de hacer es dibujar una línea que sirve como un confiable, imparcial predictor de y basado en x. El de Gauss-Markov teorema nos dice que la minimización de la ESS logra ese objetivo -, sino que el teorema descansa sobre algunos supuestos concretos. Si estos supuestos se rompe, usted todavía puede minimizar la ESS, pero no podría hacer nada. Imagino diciendo: "Usted conduce un coche empujando el pedal: la conducción es esencialmente un pedal de empujar proceso". El pedal puede ser empujado no importa la cantidad de gas en el tanque. Por lo tanto, incluso si el tanque está vacío, usted todavía puede empujar el pedal y el coche."

Pero hablar es barato. Veamos el frío, duro, de datos. O, en realidad, hecha de seguridad de los datos.

center

De hecho, esta es mi favorita hecho de que los datos de: Cuarteto de Anscombe. Creado en 1973 por el estadístico Francisco Anscombe, este delicioso brebaje ilustra la locura de confiar en los métodos estadísticos a ciegas. Cada uno de los conjuntos de datos tiene la misma regresión lineal la pendiente, el intercepto, p-valor y $R^2$- y, sin embargo, de un vistazo podemos ver que sólo uno de ellos, yo, es apropiado para la regresión lineal. En II sugiere la forma equivocada, en III es sesgada por un único valor atípico - y en el IV hay, claramente, no hay una tendencia en todo!

Uno podría decir que "la regresión Lineal, se sigue trabajando en esos casos, porque es minimizar la suma de los cuadrados de los residuos." Pero lo que es una victoria Pírrica! Regresión lineal siempre dibujará una línea, pero si es un sin sentido de la línea, a quién le importa?

Así que ahora vemos que sólo porque una optimización puede realizarse no significa que estamos logrando nuestro objetivo. Y vemos que hacer de la seguridad de los datos, y visualizando, es una buena manera de inspeccionar los supuestos de un modelo. Aferrarse a esa intuición, de que vamos a necesitar en un minuto.

Roto Suposición: No Esférica De Datos

Alegan que el k-means el algoritmo funciona bien en no esférica grupos. No esférica clusters... como estas?

center

Tal vez esto no es lo que esperaba - pero es perfectamente razonable camino para la construcción de clusters. Mirando esta imagen, nosotros, los humanos, inmediatamente reconocer dos grupos naturales de puntos - no hay duda de ellos. Así que vamos a ver como k-means: las asignaciones se muestran en color, imputado centros se muestra como X.

enter image description here

Bueno, que's no es correcto. K-means estaba tratando de encajar una clavija cuadrada en un agujero redondo- tratando de encontrar agradable centros con pequeñas esferas alrededor de ellos - y fracasó. Sí, todavía minimizar el plazo de un clúster de suma de cuadrados - pero, igual que en Anscombe Cuarteto de arriba, es una victoria Pírrica!

Usted podría decir: "Eso no es un ejemplo justo... no hay método de agrupación podría encuentren correctamente los clústeres que raro". No es cierto! Trate solo de vinculación hierachical la agrupación:

enter image description here

Dado en el clavo! Esto es debido solo a la vinculación de la agrupación jerárquica hace que el derecho supuestos de este conjunto de datos. (Hay otra clase de situaciones en las que se produce un error).

Usted podría decir: "el Que un solo extremo, caso patológico." Pero no lo es! Por ejemplo, puede hacer que el grupo exterior de un semi-círculo en lugar de un círculo, y verás k-means sigue terriblemente (y la agrupación jerárquica todavía hace bien). Yo podría llegar a otras situaciones problemáticas fácilmente, y que sólo en dos dimensiones. Cuando estás agrupación 16-dimensional de datos, hay todo tipo de patologías que puedan surgir.

Por último, debo señalar que la k-means es todavía salvagable! Si usted comienza por transformar los datos en coordenadas polares, la agrupación ahora funciona:

center

Es por eso que la comprensión de los supuestos en que un método es esencial: no sólo te dicen cuando un método tiene sus inconvenientes, lo que te dice cómo solucionarlos.

Roto Asunción: De Manera Desigual Tamaño De Los Clústeres

Lo que si los grupos tienen un número impar de puntos hace que también rompe k-means clustering? Así, considere la posibilidad de este conjunto de agrupaciones, de los tamaños de 20, 100, 500. He generado cada uno de un multivariante de Gauss:

center

Esto se ve como k-means probablemente podría encontrar esos grupos, derecho? Todo parece ser generados en limpio y ordenado grupos. Así que vamos a intentar k-means:

enter image description here

Ouch. Lo que sucedió aquí es un poco más sutil. En su afán de minimizar el plazo de un clúster de suma de cuadrados, el k-means el algoritmo da más "peso" a las grandes agrupaciones. En la práctica, eso significa que es feliz de dejar que pequeños grupos terminan lejos de cualquier centro, mientras que utiliza los centros para "dividir" un grupo más grande.

Si usted juega con estos ejemplos un poco (R código de aquí!), usted verá que usted puede construir mucho más escenarios donde k-means se pone terriblemente mal.

Conclusión: No Hay Almuerzo Gratis

Hay un encantador de la construcción en matemática folclore, formalizado por Wolpert y Macready, llamado el "No hay Almuerzo Gratis Teorema." Es probablemente mi favorito teorema de la máquina de aprendizaje de la filosofía, y me entusiasma cualquier oportunidad para llevar (¿he mencionado que me encanta esta pregunta?) La idea básica es la indicada (no rigurosamente) como este: "Cuando promediado a través de todas las situaciones posibles, cada algoritmo funciona igual de bien."

Sonar contradictorio? Considerar que para cada caso donde un algoritmo funciona, yo podría construir una situación en la que se falla terriblemente. Regresión lineal supone que sus datos caídas a lo largo de una línea -, pero lo que si se sigue una onda sinusoidal? Una prueba t se supone que cada muestra procede de una distribución normal: lo que si te meten en un valor atípico? Cualquier gradiente de ascenso algoritmo puede quedar atrapada en los máximos locales, y cualquier clasificación supervisada puede ser engañado en el sobreajuste.

¿Qué significa esto? Esto significa que los supuestos son donde su poder proviene de! Cuando Netflix recomienda películas, suponiendo que si te gusta una película, te va a gustar similares (y viceversa). Imagina un mundo donde eso no era cierto, y sus gustos son perfectamente aleatoria dispersa al azar a través de géneros, actores y directores. Su algoritmo de recomendación de fallar terriblemente. Tendría sentido decir "Bueno, todavía minimizar algunos esperado del error cuadrado, de manera que el algoritmo sigue trabajando"? Usted no puede hacer una recomendación algoritmo sin hacer algunas suposiciones acerca de los gustos del usuario - al igual que usted no puede hacer que un algoritmo de clustering sin hacer algunas suposiciones acerca de la naturaleza de esos grupos.

Así que no sólo aceptan estos inconvenientes. Saben ellos, para que puedan informar a su elección de algoritmos. Entiende, entonces usted puede ajustar su algoritmo y transformar los datos para resolverlos. Y el amor, porque si el modelo podría nunca estar equivocados, que significa que nunca será correcto.


253voto

Amadiere Puntos 5606

Aunque me gusta David Robinsons respuesta por encima de un montón, he aquí algunos adicionales crítica de k-means.

La agrupación no agrupados datos

Ejecutar k-means en el uniforme de los datos, y usted todavía obtener racimos! No se lo dirá a usted cuando los datos de la misma ¿ no clúster, y puede llevar su investigación en un punto muerto de esta manera.

K-means on uniform data

Sensibles a la escala

Reescalando los conjuntos de datos va a cambiar completamente los resultados. Aunque esto en sí no es malo, sin darse cuenta de que usted tiene que gastar más de atención a la ampliación de sus datos es malo. Los factores de escala son extra $d$ parámetros ocultos en k-significa que "por defecto" a 1 y por lo tanto son fácilmente pasados por alto, sin embargo, tienen un impacto importante (pero por supuesto, esto se aplica a muchos otros algoritmos, también).

Esto es probablemente lo que usted se refiere como "todas las variables tienen la misma varianza". Excepto que lo ideal sería que también considere la posibilidad de no-lineal de la escala, cuando corresponda.

También ser conscientes de que es sólo una heurística para la escala de cada eje para tener la unidad de la varianza. Esto no garantiza que k-means obras. De escala depende del significado de su conjunto de datos. Y si usted tiene más de un grupo, usted quisiera que cada clúster (de forma independiente) para tener la misma varianza en cada una de las variables, también.

Aquí es un clásico contraejemplo de conjuntos de datos que k-means no clúster. Ambos ejes se yo.yo.d. en cada grupo, por lo que sería suficiente para hacer esto en 1 dimensión. Pero los clusters tienen diferentes variaciones, y k-means lo divide de forma incorrecta.

K-means cannot cluster this data set

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

  • Todos los grupos son esféricos (he.yo.d. De gauss).
  • Todos los ejes tienen la misma distribución y por lo tanto la varianza.
  • Ambos grupos han 500 elementos de cada uno.

Sin embargo, k-means todavía no mal (y se pone peor si puedo aumentar la varianza más allá de 0,5 para el grupo más grande) Pero: no es el algoritmo que ha fallado. Se trata de la hipótesis, que no se mantenga. K-significa que está trabajando perfectamente, es sólo la optimización del mal criterio.

Incluso en perfecto conjuntos de datos, se puede quedar atrapado en un mínimo local

A continuación es el mejor de 10 carreras de k-means en el clásico A3 conjunto de datos. Esta es una síntesis de conjunto de datos, diseñado para k-means. 50 grupos, cada uno de forma Gaussiana, razonablemente bien separados. Sin embargo, sólo con k-means++ y 100 iteraciones me hizo conseguir el resultado esperado... (a continuación es de 10 iteraciones de regular k-means, para la ilustración).

k-means on A3 data set

Encontrarás rápidamente muchos grupos de este conjunto de datos, donde k-means no se pudo encontrar la estructura correcta. Por ejemplo, en la parte inferior derecha, un grupo fue dividido en tres partes. Pero no hay manera, k-means se va a mover uno de estos centroides a todo un lugar diferente del conjunto de datos - es atrapado en un mínimo local (y esto ya fue 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, va a quedar atrapado en un mínimo donde este grupo sigue siendo dividido, y otros dos clusters se fusionó en su lugar. No siempre, pero muy a menudo. Así que hay un montón de iteraciones para tener una suerte de selección. Con 100 iteraciones de k-means, todavía contaba con 6 errores, y con 1000 iteraciones tengo este a 4 errores. K++ por la forma en que los pesos de las muestras aleatorias, funciona mucho mejor en este conjunto de datos.

De los medios continuos

Mientras que usted puede ejecutar k-means sobre los datos binarios (o una caliente codificado categorial de datos) los resultados no serán binario más. Así se obtiene un resultado, pero usted puede ser incapaz de iterpret en el final, porque tiene un tipo de datos diferente de los datos originales.

Asunción oculta: ESS es digno de minimizar

Esta es, esencialmente, ya presente en la respuesta anterior, bien demostrado con la regresión lineal. Hay algunos casos de uso, donde k-means hace perfecto sentido. Cuando Lloyd se había decodificar señales PCM, hizo saber el número de diferentes tonos, y menos del error cuadrado minimiza la posibilidad de errores de decodificación. Y en la cuantización del color de la imagen, haces minimizar el color de error cuando la reducción de la paleta, también. Pero en los datos, es la suma de los cuadrados de las desviaciones significativas criterio de minimizar?

En anteriores contraejemplo, la varianza es no vale la pena minimizar, porque depende del clúster. En su lugar, un Modelo de Mezcla de Gaussianas se debe ajustar a los datos, como en la siguiente figura:

Gaussian Mixture Modeling

(Pero esto no es el último método. Es tan fácil para la construcción de datos que no satisface a la "mezcla de k de distribución Gausiana" supuestos, por ejemplo, mediante la adición de un montón de ruido de fondo)

Muy fácil de usar mal

Todos en todos, es muy fácil tirar k-means sobre sus datos, y que sin embargo se obtiene un resultado (que es bastante aleatorio, pero no se nota). Creo que sería mejor tener una metod que puede fallar si no he entendido tus datos...

K-means como cuantización

Si desea un modelo teórico de lo k hace, consideran que es una cuantización de enfoque, no de un algoritmo de clustering.

El objetivo de k-means, minimizando el error cuadrático - es una opción razonable si usted vuelva a colocar cada objeto por su centroide más cercano. (Tiene mucho menos sentido si usted inspeccionar los grupos de datos original en mi humilde opinión.)

Hay muy buenos casos de uso para esto. El original de la PCM caso de uso de Lloyd viene a la mente, o por ejemplo, el color quanization (Wikipedia). Si desea reducir una imagen para k colores, ¿ desea reemplazar cada píxel con el centroide más cercano. Minimizar el cuadrado de la desviación de color, a continuación, hace medir L2 optimalidad en la imagen aproximación usando $k$ sólo los colores.

Esta cuantificación es probablemente muy similar a la regresión lineal ejemplo. Regresión lineal encuentra el mejor modelo lineal. Y k-means se encuentra (a veces) la mejor reducción a k los valores de un conjunto de datos multidimensionales. Donde la "mejor" es el mínimo error cuadrático.

En mi humilde opinión, k-means es un buen cuantización algoritmo (ver la primera imagen de este post - si usted desea aproximar el conjunto de datos en dos puntos, esta es una opción razonable!). Si usted desea hacer un análisis de cluster como en descubrir la estructura de k-means es en mi humilde opinión no es la mejor opción. Se tiende a agruparse cuando no hay grupos, y que no reconoce las diversas estructuras de hacer ver una gran cantidad de datos.


Fine print: todas las imágenes fueron generadas con ELKI stock funcionalidad. Los datos fueron generados utilizando el .xml de la generación de datos de formato, pero son tan básicos que no vale la pena compartirlos.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by: