Clusters pouvant être causés par K-means

J'ai obtenu la question suivante comme question test pour mon examen et je ne comprends tout simplement pas la réponse.

Un diagramme de dispersion des données projetées sur les deux premières composantes principales est présenté ci-dessous. Nous souhaitons examiner s'il existe une structure de groupe dans l'ensemble de données. Pour ce faire, nous avons exécuté l'algorithme k-means avec k = 2 en utilisant la mesure de distance euclidienne. Le résultat de l'algorithme k-means peut varier entre les exécutions en fonction des conditions initiales aléatoires. Nous avons exécuté l'algorithme plusieurs fois et obtenu des résultats de clustering différents.

Seuls trois des quatre regroupements présentés peuvent être obtenus en exécutant l'algorithme k-means sur les données. Lequel ne peut pas être obtenu par k-means? (il n'y a rien de spécial dans les données)

La bonne réponse est D. L'un de vous peut-il expliquer pourquoi?

Pour mettre un peu plus de viande sur la réponse de Peter Flom, le clustering k-means recherche k groupes dans les données. La méthode suppose que chaque cluster a un centroïde à un certain point (x,y). L'algorithme k-means minimise la distance de chaque point au centroïde (cela peut être une distance euclidienne ou manhattan selon vos données).

Pour identifier les clusters, une première estimation est faite des points de données appartenant à quel cluster, et le centroïde est calculé pour chaque cluster. La métrique de distance est ensuite calculée, puis certains points sont échangés entre les clusters pour voir si l'ajustement s'améliore. Il y a beaucoup de variations sur les détails, mais fondamentalement, k-means est une solution de force brute qui dépend des conditions initiales, car il existe des minima locaux à la solution de clustering.

Donc, dans votre cas, il semble que le cas A avait des conditions initiales largement séparées xet que les clusters se résolvent car les distances entre les centroïdes et les données sont petites, et c'est une solution stable. Inversement, vous ne pouvez pas obtenir D car ce point rouge unique est plus proche du centre de gravité des points bleus que de nombreux autres, de sorte que le point rouge aurait dû faire partie de l'ensemble bleu.

Par conséquent, la seule façon d'obtenir D est d'interrompre le processus de clustering avant qu'il ne soit terminé (ou le code qui a créé les clusters est rompu).

Parce que le point encerclé en D n'est pas loin des autres points de la dimension PC1, de la dimension PC2 ou de la distance euclidienne les combinant.

En A, le point unique est loin des autres sur PC1

En B et C, il existe deux grands groupes facilement séparables. En effet, B et C sont le même clustering (sauf s'il me manque un point) ils ne varient qu'en termes d'étiquette

Puisque D ne contient qu'un seul point, son centre est exactement à ce point.

Pour le reste des données, le centre doit être proche de 0,0 dans cette projection.

Au moins l'un des points bleus est sensiblement plus proche du centre rouge que du bleu dans les deux premiers composants principaux. Le résultat ne semble pas provenir des cellules de Voronoi.

Ce n'est pas une réponse directe à votre question, mais je ne comprends pas comment la configuration suggérée par votre enseignant, c'est-à-dire appliquer d'abord l'APC puis rechercher des grappes, est logique:

Si l'ensemble de données a une structure en cluster, la réduction dimensionnelle obtenue par PCA n'est pas garantie de respecter cette structure. Dans vos figures, PC1 et PC2 ne vous donneront que les variables (ou combinaisons linéaires de variables) qui captent le plus de variation dans les données.

Autrement dit: si vous supposez d'emblée que l'ensemble de données contient des clusters, les caractéristiques les plus importantes sont clairement celles qui distinguent les clusters, qui, en général, ne coïncident pas avec les directions de grandes variations dans l'ensemble de données.

Dans un tel scénario, ce qui est plus logique est de commencer par cluster (sans aucune réduction de dimensionnalité) puis d' effectuer LDA ou XCA , ou quelque chose de similaire qui préserve les informations discriminatoires de classe / cluster.