¿Qué tan aleatorios son los resultados del algoritmo de kmeans?

Question

Tengo una pregunta sobre el algoritmo de kmeans . Sé que kmeans es un algoritmo aleatorio, pero qué tan aleatorio es y qué resultados puedo esperar. Supongamos que has agrupado un conjunto de datos en $4$ cúmulos, donde cada punto tiene identidad $1$ , $2$ , $3$ o $4$ (que te dice a qué grupo pertenece). Luego se realiza una segunda agrupación en el mismo conjunto de datos con el mismo criterio.

1. ¿Todos los puntos de un cúmulo específico dirán que durante la primera agrupación estarán en el mismo cúmulo la próxima vez que se aplique el algoritmo de kmeans?
2. Si no es así, ¿estarán muy probablemente en el mismo grupo y hay alguna medida para esta probabilidad?

Por alguna salida que recibí en R, creo que 1. no se mantiene ya que obtengo diferentes tamaños de cúmulos para diferentes ejecuciones en el mismo conjunto de datos.

¡Toda la ayuda es muy apreciada!

Answer 1

Hay más de un algoritmo k-means .

Probablemente se refiere a Algoritmo de Lloyds que sólo depende de los centros iniciales del grupo. Pero también está el de MacQueen, que depende de la secuencia es decir. ordenando de puntos. Luego está Hartigan, Wong, Forgy, ...

Y por supuesto, varios implementaciones pueden tener diferencias de aplicación y optimización. Pueden tratar enlaces de manera diferente, también! Por ejemplo, muchas implementaciones ingenuas siempre asignarán elementos al primer o último grupo cuando se empaten. Otras preservarán la asignación de clusters actual. Así que cuando se agrupan valores enteros, donde los empates son mucho más comunes, pero también en el conjunto de datos del Iris, se pueden ver artefactos y diferencias causadas por esto.

Además, los clústeres pueden terminar siendo reordenados por la dirección de memoria después de terminar k-means, por lo que no se puede asumir con seguridad que el clúster 1 sigue siendo el clúster 1 aunque k-means convergiera después de la primera iteración. Otros reordenarán los clústeres según el tamaño del clúster (lo que en realidad tiene sentido para k-means, ya que es más probable que devuelva el mismo resultado en una inicialización aleatoria diferente)

Pero asumiendo que todos iteren a Lloyd hasta la convergencia (¡lo cual no ocurrió con los medios originales de MacQueen!) todos deberían llegar al menos a un local óptima. Sólo habrá un óptimo local...

Consideremos, por ejemplo, el conjunto de datos generados por $p_j=( \sin (2 \pi \frac {j}{n}), \cos (2 \pi \frac {j}{n}))$ y dejar que $n$ ser divisible por $j$ . Habrá un lote de soluciones óptimas locales. Ejecutar los medios K con diferentes semillas al azar le dará soluciones muy diferentes. Para los parámetros apropiados, creo que la posibilidad de que dos elementos diferentes que estaban en el mismo cúmulo estén en el mismo cúmulo otra vez en otro resultado estará en algún lugar alrededor de $50\%$ . En una dimensionalidad más alta, probablemente se puede reducir aún más este número. Por ejemplo, en el $n$ conjunto de datos dimensionales donde $p_{jj}=1$ y $p_{ij}=0$ para $i \neq j$ todos los puntos son equidistantes. Es fácil ver que esto causará estragos en los medios de comunicación...

Answer 2

La K-means es sólo aleatoria en sus centros de partida. Una vez que se determinan los centros candidatos iniciales, es determinístico después de ese punto. Dependiendo de su implementación de los medios K, los centros pueden ser elegidos cada vez de la misma manera, similares cada vez, o completamente al azar cada vez. Con las implementaciones de MATLAB/R, la elección es aleatoria pero el resultado que se obtiene es la mejor ejecución entre unos 50 conjuntos de opciones para los centros iniciales. Nota con la función R stats::kmeans, el valor por defecto es ejecutar sólo un conjunto de centros iniciales (es decir, nstart = 1). Dependiendo de sus datos, el aumento de este valor puede estabilizar las asignaciones de los clústeres en las ejecuciones y hacerlo es Generalmente se recomienda .

Para responder a tu primera pregunta, realmente depende del tipo de datos que tengas. Si está bien dividido en cúmulos de forma esférica, entonces típicamente obtendrás cúmulos muy, muy similares. Si no, entonces puede que obtengas cúmulos bastante aleatorios cada vez.

No existe una medida general de "probabilidad" de estar en el mismo grupo, pero si se necesita una, se puede establecer una basada en la similitud/distancia de cualquier instancia con respecto a las otras en comparación con su similitud/distancia con otros puntos. O quizás podrías ejecutar primero un algoritmo de enlace (único o completo) y luego sopesar su "probabilidad" de estar en el mismo cúmulo por sus distancias al antepasado común más bajo. O hay un número de otros donde podrías hacerlo dependiendo de cómo se ven tus datos y cuál es la aplicación.