The lecture explains the K‑means partitioning algorithm as a direct clustering alternative to hierarchical agglomerative methods. It walks through the algorithm on a 2‑dimensional example with three clusters, detailing the initialization of random centroids, iterative assignment of points to the nearest centroid, recomputation of centroids, and convergence when assignments stabilize. Two inherent drawbacks are highlighted: the need to pre‑specify the number of clusters and the sensitivity of the final partition to the random initialization, which can be mitigated by multiple runs and selecting the best solution. The speaker then discusses how K‑means can be used to refine partitions obtained from hierarchical clustering, noting that while it improves the clustering criterion, it discards the hierarchical relationships. Strategies for handling large‑scale or high‑dimensional data are presented, including dimensionality reduction via Principal Component Analysis (PCA) before clustering, and a two‑stage approach where a coarse K‑means partition creates a manageable set of centroids that are then clustered hierarchically. For qualitative variables, two routes are described: transforming the data with Multiple Correspondence Analysis (MCA) to obtain quantitative coordinates, or employing appropriate similarity/dissimilarity measures such as the Jaccard index. Finally, the lecture emphasizes the benefits of combining factor analysis with clustering: noise reduction, more stable partitions, and the ability to visualise both the hierarchical tree and class memberships on factor planes, providing a richer, both continuous and discrete, interpretation of the data.
Chapters
Donc on a vu ici comment construire une classification ascendante hiérarchique, un arbre hiérarchique. On va voir maintenant une méthode de partitionnement direct qui ne nécessite pas la construction d'un arbre hiérarchique. Cette méthode de partitionnement est appelée méthode des K-means ou méthode d'agrégation autour des centres mobiles. Présentons l'algorithme des K-means sur un exemple en 2 dimensions. L'algorithme des K-means nécessite de connaître le nombre de classes Q que l'on souhaite construire. Ici nous allons prendre Q= 3 et construire donc une partition en 3 classes. Au départ, on choisit Q centres de classe au hasard. Rennes, Vichy et Clermont sont les 3 centres de classe choisis au hasard. C'est la première étape, l'étape d'initialisation de l'algorithme. Ensuite j'affecte tous les individus, tous les points, au centre de classe le plus proche. Donc tous les individus ici en rouge sont plus proches de Rennes que de Vichy ou Clermont. Tous les individus en vert sont plus proches de Vichy que de Clermont et Rennes. Et tous les individus en noir sont plus proches de Clermont. On a ainsi réparti les individus dans 3 classes. On calcule maintenant les centres de gravité de chacune de ces classes. Voici les centres de gravité des classes. Ces centres de gravité ne sont plus des individus mais ce sont des points fictifs. Et on va itérer ces 2 étapes d'affectation des points au centre le plus proche puis de calcul des centres de gravité des classes. On va affecter à nouveau les points au centre le plus proche, calculer les centres de gravité des nouvelles classes et on continue d'itérer. On affecte les villes au centre de gravité le plus proche, on calcule les centres de gravité, les centres de gravité se déplacent, on affecte les points au centre le plus proche, On calcule les nouveaux centres de gravité et on voit que les classes n'ont pas changé et que les centres de gravité ne bougent plus. L'algorithme a alors convergé. On a ainsi constitué les 3 classes. Et donc voici le fonctionnement de l'algorithme des K-means. C'est un algorithme très rapide qui peut être lancé avec beaucoup d'individus mais qui a 2 défauts. Le premier est qu'il faut connaître le nombre de classes a priori. Le second est que la partition dépend de l'initialisation du choix des centres de classes au hasard. D'une initialisation à l'autre, la partition peut être très différente. Pour remédier à ce problème, on lancera plusieurs fois l'algorithme avec des initialisations différentes et on conservera la meilleure partition. Nous avons vu comment construire une classification hiérarchique et comment construire une partition sur les individus. Dans cette partie, nous allons voir quelques compléments sur la classification et notamment comment consolider une partition Comment construire une partition quand on a un jeu de données en grandes dimensions? Comment faire quand les variables sont qualitatives? Et enfin quel est l'intérêt de combiner analyse factorielle et classification? On peut consolider la partition obtenue par la classification ascendante hiérarchique. En effet, nous avons vu que la partition obtenue en coupant un arbre hiérarchique n'est pas optimale parce que l'on prend en compte toute une hiérarchie entre les individus et groupes d'individus. On peut alors consolider la partition en utilisant les k-means. On part de la partition obtenue par le découpage de l'arbre hiérarchique comme initialisation dans l'algorithme des k-means et on va itérer quelques étapes de k-means jusqu'à convergence. Cela améliore nécessairement la partition puisque par construction, à chaque étape des k-means, le critère diminue. L'inconvénient par contre est que les liens hiérarchiques entre individus sont perdus. En effet, certains individus vont changer de classe par rapport à la partition obtenue depuis l'arbre et donc on perd complètement la hiérarchie. La construction de l'arbre hiérarchique nécessite de calculer à chaque étape de nombreuses distances entre individus et groupes d'individus. Et pour des données en grandes dimensions, cet algorithme est trop long et fonctionne mal. Alors comment faire pour gérer des données de grandes dimensions? Si le nombre de variables est grand, on peut dans un premier temps faire une ACP et ne conserver que les premières dimensions de l'ACP. L'ACP va permettre de concentrer l'information sur les premières dimensions factorielles et par suite on va pouvoir faire la classification sur un tableau avec des individus et quelques dimensions factorielles en colonnes. On se ramène alors à un tableau individus× variables quantitatives de taille raisonnable. Si maintenant on a beaucoup d'individus, l'algorithme de classification est trop long et en pratique on ne peut pas construire l'arbre hiérarchique. Une possibilité est alors de travailler par étapes. D'abord on construit une partition très grossière avec la méthode des K-means en construisant une centaine de classes par exemple. Cette première étape, du fait du grand nombre de classes, assure le regroupement d'individus globalement proches. Il est alors possible de considérer les centres des classes et de construire une classification hiérarchique à partir de ces centres de classes. Évidemment, on utilisera les effectifs des classes dans le calcul de l'arbre. L'arbre obtenu correspond au haut de l'arbre hiérarchique qui serait obtenu à partir de tous les individus, le bas de l'arbre hiérarchique étant perdu. Cependant, avec 1 million d'individus, le bas de l'arbre n'est pas lisible et est inutile car seul le haut de l'arbre est en général commenté. Voici un exemple avec 300 individus. À gauche, on a l'arbre construit avec tous les individus et à droite l'arbre construit après avoir préalablement construit une partition en 50 classes. On voit que les hauts des 2 arbres sont très similaires et seront commentés à peu près de la même façon. Nous avons jusqu'à maintenant traité le cas où les variables sont quantitatives. Si maintenant les variables sont qualitatives, comment peut-on faire? Il y a 2 stratégies. La première stratégie est de se ramener à des variables quantitatives en utilisant l'analyse des correspondances multiples. L'ACM va permettre de passer d'un tableau de variables qualitatives à un tableau de coordonnées des individus sur les dimensions et les coordonnées des individus ce sont bien des variables quantitatives. On peut alors conserver les premières dimensions de l'ACM ou éventuellement toutes les dimensions. Une fois qu'on s'est ramené à un tableau individus 3 variables quantitatives, on peut réaliser la classification comme précédemment. Une autre stratégie consiste à utiliser des mesures adaptées spécifiquement aux données qualitatives. De nombreux indices existent, indices de similarité ou de dissimilarité comme par exemple l'indice de Jaccard. Ces indices vont permettre de calculer une matrice de distances ou de dissimilarités entre individus. Et à partir de cette matrice de distances, on peut construire un arbre hiérarchique. Nous venons de voir que si les données sont qualitatives, l'ACM renvoie des composantes principales qui sont quantitatives et sur lesquelles on va pouvoir faire directement une classification pour utiliser le même algorithme de classification. Mais les méthodes d'analyse factorielle ont d'autres avantages. Soulignons ici l'intérêt d'un enchaînement analyse factorielle/ classification. Pourquoi il est intéressant de faire une analyse factorielle avant de faire une classification? L'analyse factorielle va concentrer l'information sur les premières composantes principales, les dernières composantes n'étant que du bruit, c'est-à-dire de l'aléatoire. Et donc il est possible d'éliminer ces dernières composantes avant de faire la classification. Ainsi on va éliminer l'aléatoire, le bruit, avant de faire la classification, ce qui permettra d'obtenir une classification qui, en pratique, est plus stable. Plus stable dans le sens où, en enlevant ou ajoutant quelques individus, les classes restent les mêmes. Et autre intérêt des méthodes factorielles utilisées en complément de la classification: la possibilité de représenter l'arbre hiérarchique ainsi que les classes sur le plan factoriel. Si on a sur un même graphe les points sur le plan factoriel, l'arbre hiérarchique et les individus coloriés en fonction de leur appartenance à différentes classes, on a 3 informations. On a notamment une vision continue grâce aux plans de l'analyse factorielle. On a une vision discontinue avec la classification ascendante hiérarchique qui nous permet également de voir ce qui se passe sur les dimensions 3-4 de l'analyse factorielle par exemple. Dans notre exemple, les individus sont parfaitement représentés sur le plan 1-2 et donc les proximités entre individus sur le plan 1-2 sont les proximités des individus dans l'espace. Mais il se peut que certains individus semblent proches sur le plan factoriel et soient assez éloignés sur une 3ème dimension ou une 4ème dimension ce que la classification pourra mettre en évidence. Cela pourrait arriver dans d'autres exemples où 3 ou 4 dimensions sont nécessaires pour l'interprétation de l'ACP. On a alors une vision très synthétique avec les classes et un peu plus fine avec le plan factoriel. Nous avons vu dans cette vidéo comment construire des classes. Nous verrons dans la vidéo suivante comment caractériser les individus d'une même classe.
