¿Cómo decidir sobre el número correcto de grupos?

54

Encontramos los centros de clúster y asignamos puntos a k diferentes agrupaciones de clústeres en k-means clustering, que es un algoritmo muy conocido y se encuentra en casi todos los paquetes de aprendizaje automático en la red. Pero la parte faltante y más importante en mi opinión es la elección de una k correcta. ¿Cuál es el mejor valor para ello? ¿Y qué se entiende por mejor ?

Utilizo MATLAB para la computación científica, donde observar trazados de silueta se da como una forma de decidir sobre k discutido aquí . Sin embargo, estaría más interesado en los enfoques bayesianos. Cualquier sugerencia es apreciada.

petrichor
fuente
2
Buena pregunta ...
Bajo la visualización de agrupación hay (ejem) una forma de visualizar k-agrupaciones y ver el efecto de varias k en una sola toma, utilizando MST.
denis
He respondido esta pregunta con media docena de métodos Rpor aquí
Ben
1
Decidir el "mejor" número k de clústeres implica comparar las soluciones de clúster con diferentes k: qué solución es "mejor". En ese sentido, la tarea parece similar a cómo comparar los métodos de agrupación , que es "mejor" para sus datos. Las pautas generales están aquí .
ttnphns

Respuestas:

28

Esto se ha pedido un par de veces en stackoverflow: aquí , aquí y aquí . Puedes echar un vistazo a lo que la multitud de allí piensa acerca de esta pregunta (o una pequeña variante de la misma).

Permítanme también copiar mi propia respuesta a esta pregunta, en stackoverflow.com:

Desafortunadamente, no hay forma de establecer automáticamente la K "correcta" ni hay una definición de lo que es "correcto". No existe un método estadístico basado en principios, simple o complejo que pueda establecer la "K correcta". Hay heurísticas, reglas generales que a veces funcionan, a veces no.

La situación es más general ya que muchos métodos de agrupación tienen este tipo de parámetros, y creo que este es un gran problema abierto en la comunidad de investigación de agrupación / aprendizaje no supervisado.

carlosdc
fuente
+1 Después de leer esto, me parece muy intuitivo ... pero debo decir que nunca antes había pensado en esto. que en realidad el problema de elegir el número de PC en PCA es equivalente al problema de elegir el número de clústeres en K-mean ...
Dov
2
@Dov estas dos cosas no son del todo equivalentes. Existen medidas específicas que se pueden utilizar para examinar la calidad de una solución de PCA (más notablemente el error de reconstrucción, pero también el porcentaje de varianza capturado, etc.), y estas tienden a ser (en su mayoría) consistentes. Sin embargo, en la agrupación a menudo no hay una "respuesta correcta": una agrupación puede ser mejor que otra por una métrica, y lo contrario puede ser cierto utilizando otra métrica. Y en algunas situaciones, dos agrupaciones diferentes podrían ser igualmente probables bajo la misma métrica.
tdc
@tdc, pero ¿no es esto en.wikipedia.org/wiki/… más o menos así mejoradooutcomes.com/docs/WebSiteDocs/PCA/… ?
Dov
2
@Dov Sí, son "más o menos" entre sí, pero simplemente decía que el problema de elegir la cantidad de clústeres es mucho más complejo que elegir la cantidad de PC, es decir, no son "equivalentes".
tdc
1
+1 Tienes razón. Presentamos algún otro modelo o suposición para decidir la mejor k, pero luego la pregunta es por qué es ese modelo o suposición el mejor ...
petrichor
19

En primer lugar una advertencia. En la agrupación a menudo no hay una "respuesta correcta": una agrupación puede ser mejor que otra por una métrica, y lo contrario puede ser cierto utilizando otra métrica. Y en algunas situaciones, dos agrupaciones diferentes podrían ser igualmente probables bajo la misma métrica.

Dicho esto, es posible que desee echar un vistazo a los Procesos Dirichlet . También vea este tutorial .

Si comienza con un modelo de mezcla gaussiana, tiene el mismo problema que con k-means: debe elegir el número de grupos. Podría usar evidencia modelo, pero no será robusta en este caso. Entonces, el truco es usar un Proceso de Dirichlet antes que los componentes de la mezcla, lo que le permite tener un número potencialmente infinito de componentes de la mezcla, pero el modelo (generalmente) encontrará automáticamente el número "correcto" de componentes (bajo los supuestos de el modelo).

αα

tdc
fuente
1
¿Un proceso de Dirichlet bajo qué parámetro de concentración? Es una especie de equivalente a la misma pregunta original, k-significa bajo qué k? Aunque estoy de acuerdo en que entendemos mejor la distribución de Direchlet que el comportamiento de algún algoritmo complejo en algunos datos del mundo real.
carlosdc
@carlosdc buen punto, he actualizado la respuesta para incluir un poco de discusión sobre el parámetro de concentración
tdc
1
En mi experiencia, es mucho más fácil aprender un parámetro de concentración de valor continuo como alfa que determinar el número de grupos en un modelo de mezcla finita. Si desea seguir con el modelo de mezcla finita y tomar una táctica bayesiana, hay MCMC de salto reversible ( onlinelibrary.wiley.com/doi/10.1111/1467-9868.00095/abstract )
1
Gran respuesta. Añadiría el artículo Revisiting K-Means: New Algorithms via Bayesian Nonparametrics . Lo que da un enfoque simple "continuo" a K-Means. Entonces es fácil, utilizando la optimización, encontrar el valor óptimo.
Royi
9

Yo uso el método del codo :

  • Comience con K = 2 y siga incrementándolo en cada paso en 1, calculando sus grupos y el costo que viene con la capacitación. A algún valor de K, el costo cae dramáticamente, y después de eso alcanza una meseta cuando lo aumenta aún más. Este es el valor K que desea.

La razón es que después de esto, aumenta el número de clústeres, pero el nuevo clúster está muy cerca de algunos de los existentes.

vonPetrushev
fuente
Esto suena como si fuera el principio que evalúa el Método L (ver mi respuesta).
winwaed
6

Los tamaños de los clústeres dependen en gran medida de sus datos y de para qué utilizarán los resultados. Si está utilizando sus datos para dividir cosas en categorías, intente imaginar cuántas categorías desea primero. Si es para la visualización de datos, hágalo configurable, para que las personas puedan ver tanto los grupos grandes como los más pequeños.

Si necesita automatizarlo, es posible que desee agregar una penalización al aumento de k, y calcular el clúster óptimo de esa manera. Y luego solo pesas k dependiendo de si quieres un montón de grupos o si quieres muy pocos.

neurona
fuente
5

Me las arreglé para usar el "Método L" para determinar el número de clústeres en una aplicación geográfica (es decir, esencialmente un problema 2d, aunque técnicamente no es euclidiano).

El método L se describe aquí: Determinación del número de agrupaciones / segmentos en algoritmos jerárquicos de agrupación / segmentación Stan Salvador y Philip Chan

Esencialmente, esto evalúa el ajuste para varios valores de k. Se ve un gráfico en forma de "L" con el valor k óptimo representado por la rodilla en el gráfico. Se usa un cálculo simple de ajuste de mínimos cuadrados de doble línea para encontrar el punto de inflexión.

Encontré el método muy lento porque la k-medias iterativa debe calcularse para cada valor de k. También encontré que k-means funcionó mejor con múltiples carreras y eligiendo la mejor al final. Aunque cada punto de datos tenía solo dos dimensiones, no se podía utilizar una distancia pitagórica simple. Eso es mucho cálculo.

Una idea es omitir cualquier otro valor de k (digamos) a la mitad de los cálculos y / o reducir el número de iteraciones de k-medias, y luego suavizar ligeramente la curva resultante para producir un ajuste más preciso. Pregunté sobre esto en StackOverflow - En mi humilde opinión, la pregunta de suavización sigue siendo una pregunta de investigación abierta.

winwaed
fuente
4

k

Pero, ¿qué pasa si su conjunto de datos no se ajusta realmente al esquema Voronoi?

kk

k

Anony-Mousse
fuente
3
Aunque la descripción de K-means en el primer párrafo no es incorrecta, puede inducir a error a algunas personas a equiparar este método con la partición de Voronoi basada en los datos originales. Esto no es así: la partición se basa en las ubicaciones de los medios del clúster, que pueden no coincidir (y generalmente no) con ninguno de los datos originales.
whuber
3

En general, puede elegir el número de clústeres en dos rutas diferentes.

  1. impulsado por el conocimiento: debe tener algunas ideas sobre cuántos clústeres necesita desde el punto de vista comercial. Por ejemplo, si está agrupando clientes, debe preguntarse, después de obtener estos clientes, ¿qué debo hacer a continuación? ¿Puede ser que tenga un tratamiento diferente para diferentes grupos? (por ejemplo, publicidad por correo electrónico o teléfono). Entonces, ¿cuántos tratamientos posibles está planeando? En este ejemplo, selecciona decir que 100 clústeres no tendrán demasiado sentido.

  2. Impulsado por los datos: más cantidad de clusters está sobreadaptada y menos cantidad de clusters está mal ajustada. Siempre puede dividir los datos por la mitad y ejecutar la validación cruzada para ver cuántos grupos de clústeres son buenos. Tenga en cuenta que en la agrupación aún tiene la función de pérdida, similar a la configuración supervisada.

Finalmente, siempre debe combinar el conocimiento y los datos en el mundo real.

Haitao Du
fuente
2

Como nadie lo ha señalado todavía, pensé que compartiría esto. Hay un método llamado X-means, ( vea este enlace ) que estima el número adecuado de clústeres utilizando el criterio de información bayesiano (BIC). Esencialmente, esto sería como probar K significa con diferentes Ks, calcular BIC para cada K y elegir la mejor K. Este algoritmo lo hace de manera eficiente.

También hay una implementación weka , cuyos detalles se pueden encontrar aquí .

rivu
fuente
0

Otro enfoque es utilizar un algoritmo evolutivo cuyos individuos tengan cromosomas de diferentes longitudes. Cada individuo es una solución candidata: cada uno lleva las coordenadas centroides. El número de centroides y sus coordenadas evolucionan para alcanzar una solución que produzca el mejor puntaje de evaluación de agrupamiento.

Este artículo explica el algoritmo.

felipeduque
fuente