Agrupamientos que pueden ser causados por K-means

Question

He recibido la siguiente pregunta como pregunta de prueba para mi examen y simplemente no puedo entender la respuesta.

Un gráfico de dispersión de los datos proyectados en los dos primeros componentes principales se muestra a continuación. Queremos examinar si existe alguna estructura de grupo en el conjunto de datos. Para hacer esto, hemos ejecutado el algoritmo k-means con k = 2 utilizando la medida de distancia euclidiana. El resultado del algoritmo k-means puede variar entre ejecuciones dependiendo de las condiciones iniciales aleatorias. Ejecutamos el algoritmo varias veces y obtuvimos algunos resultados de agrupamiento diferentes.

Solo tres de los cuatro agrupamientos mostrados se pueden obtener ejecutando el algoritmo k-means en los datos. ¿Cuál no se puede obtener mediante k-means? (no hay nada especial sobre los datos)

La respuesta correcta es D. ¿Alguno de ustedes puede explicar por qué?

Answer 1

Para agregar más información a la respuesta de Peter Flom, el clustering k-means busca k grupos en los datos. El método asume que cada grupo tiene un centroide en un cierto (x,y). El algoritmo k-means minimiza la distancia de cada punto al centroide (esto podría ser distancia euclidiana o de Manhattan dependiendo de tus datos).

Para identificar los grupos, se hace una suposición inicial de qué puntos de datos pertenecen a qué grupo, y se calcula el centroide para cada grupo. Luego se calcula la métrica de distancia, y luego se intercambian algunos puntos entre grupos para ver si la precisión mejora. Hay muchas variaciones en los detalles, pero fundamentalmente k-means es una solución de fuerza bruta que depende de las condiciones iniciales, ya que existen mínimos locales en la solución de clustering.

Por lo tanto, en tu caso parece que el caso A tenía condiciones iniciales que estaban ampliamente separadas en x y por lo tanto los grupos se resuelven porque las distancias desde los centroides a los datos son pequeñas, y es una solución estable. Por el contrario, no se puede obtener D porque ese único punto rojo está más cerca del centroide de los puntos azules que muchos otros, por lo que el punto rojo debería haber formado parte del conjunto azul.

Por lo tanto, la única forma de obtener D es si interrumpes el proceso de clustering antes de que esté terminado (o si el código que hizo los clusters está roto).

Answer 2

Porque el punto marcado en D no está lejos de otros puntos en la dimensión PC1, dimensión PC2 o la distancia euclidiana que los combina.

En A, el único punto está lejos de los otros en PC1

En B y C hay dos grandes grupos que son fácilmente separables. De hecho, B y C son el mismo agrupamiento (a menos que me falte un punto) solo varían en términos de etiqueta

Answer 3

Dado que D contiene solo un punto, su centro está exactamente en este punto.

Para el resto de los datos, el centro debe estar cerca de 0,0 en esta proyección.

Al menos uno de los puntos azules está sustancialmente más cerca del centro rojo que del azul en los dos primeros componentes principales. El resultado no parece ser producido por celdas de Voronoi.

Answer 4

Esta no es una respuesta directa a tu pregunta, pero no entiendo cómo la configuración que sugiere tu profesor, es decir, aplicar primero PCA y luego buscar clusters, tiene sentido:

Si el conjunto de datos tiene una estructura de clusters, la reducción dimensional obtenida a través de PCA no garantiza respetar esta estructura en absoluto. En tus gráficos, PC1 y PC2 solo te darán las variables (o combinaciones lineales de variables) que capturan la mayor variación en los datos.

En otras palabras: si partes de la hipótesis de que el conjunto de datos contiene clusters, las características más importantes son claramente aquellas que discriminan entre clusters, las cuales, en general, no coinciden con las direcciones de grandes variaciones en todo el conjunto de datos.

En un escenario así tiene más sentido primero clusterizar (sin realizar ninguna reducción de dimensionalidad) y luego realizar LDA o XCA, o algo similar que preserve la información discriminatoria de clases/clusters.