Cours de classification (ancienne version)

Nous allons voir dans ce cours différentes méthodes de classification et notamment la classification ascendante hiérarchique. Donc le plan de cours est le suivant: je vais d'abord faire une rapide introduction sur le type de données sur lesquelles nous allons pouvoir construire des classifications, quels sont les objectifs de la classification. Ensuite je détaillerai les principes généraux de la classification, notamment de la classification ascendante hiérarchique: quels sont les critères qui peuvent être utilisés, quels sont les algorithmes et puis comment évaluer la qualité d'une partition obtenue à partir d'une classification ascendante hiérarchique. Et cela nous permettra de proposer une nouvelle méthode qui est appelée la méthode de Ward. Ensuite, je donnerai un exemple de construction de classification. Puis ensuite, nous parlerons de classification avec des algorithmes de partitionnement, dont un algorithme très connu qui est les K-means. Et enfin, nous verrons différents compléments sur l'utilisation conjointe de la classification et des k-means ou la classification sur des données de grandes dimensions par exemple ou avec des variables qualitatives. Et enfin quand on a fait une classification, quand on a construit des classes d'individus, il est intéressant de caractériser ces classes d'individus par les variables. Nous verrons comment caractériser les classes d'individus. Donc en introduction je vais donner quelques définitions sur la classification. Donc la classification c'est l'action de constituer ou de construire des classes. Et les classes, c'est des ensembles d'individus ou d'objets qui possèdent des traits de caractère communs. Donc on va essayer de constituer des groupes, des catégories d'individus. Donc des caractères communs, c'est-à-dire que ce sont des individus qui se ressemblent du point de vue de l'ensemble des caractères qui les décrivent. Alors des classifications, vous en connaissez. Par exemple, le règne animal est un arbre de classification particulier. Le disque dur d'un ordinateur organisé avec des répertoires, des sous-répertoires, des sous-sous-répertoires Toute cette arborescence est en fait une classification. La division géographique de la France avec des régions, des départements, des cantons, des communes. Et puis des classes, vous en connaissez aussi, les classes sociales, les catégories socioprofessionnelles, les classes politiques. Donc ça va regrouper des individus qui ont des caractéristiques communes. Et donc ça amène à 2 types de classification, classification qu'on appelle hiérarchique: on va essayer de construire un arbre hiérarchique pour voir comment s'organisent les objets, les individus. On va parler ici de classification ascendante hiérarchique. Et puis des classifications de type méthode de partitionnement: on va essayer uniquement de constituer des groupes d'individus qui se ressemblent et donc de constituer une partition. Alors voici un arbre hiérarchique, c'est l'arbre hiérarchique du règne animal. Avec le règne animal dans lequel il y a des embranchements, différents embranchements, donc les arthropodes, les cnidaires, les vertébrés. Dans les vertébrés, il y a là encore différents vertébrés: des mammifères, des oiseaux, des reptiles, des amphibiens, des poissons. Dans les mammifères, il y a des monotrèmes, des édentés, des tubulidentés, des carnivores, etc. Et puis on peut descendre dans la hiérarchie comme ça pour avoir des classes de plus en plus homogènes. Dans le bas de la hiérarchie, on a les espèces qui sont très caractéristiques avec des caractéristiques très communes, et puis au-dessus on a des genres qui regroupent plusieurs espèces, donc des classes qui sont plus grosses mais les individus d'une même classe se ressemblent un petit peu moins. Alors quels sont les principes de la classification ascendante hiérarchique? Tout d'abord, les données sur lesquelles on va pouvoir construire une classification hiérarchique. On va s'intéresser à des tableaux de données avec des individus en lignes et des variables quantitatives. Donc on a un tableau ayant la même structure que les tableaux en analyse en composantes principales avec I individus et K variables. Alors les variables doivent être quantitatives, nous verrons comment faire quand les variables sont qualitatives. Et l'objectif de la classification, ça va être de produire une arborescence qui va permettre de mettre en évidence les liens hiérarchiques entre les individus ou entre des groupes d'individus. Par exemple, sur l'arbre hiérarchique à droite ici, on a les individus A et C qui sont très proches et ils sont aussi assez proches de l'individu B et ces 3 individus forment une classe. On a également les 5 individus D, E, F, G, H qui se ressemblent et dans cette classe les individus F et G se ressemblent encore plus. La construction d'un tel arbre va permettre également de détecter un nombre de classes naturel à l'intérieur de la population. Par exemple dans l'arbre qui est proposé ici, on peut se dire qu'on peut décomposer les individus en 2 classes: la classe A, B, C et la classe D, E, F, G, H. Alors quels sont les critères de la classification? Il faut pour réaliser une classification avoir une mesure de la ressemblance entre 2 individus. Quand est-ce que 2 individus sont très proches? Quand est-ce qu'on va les mettre dans une même classe? Donc une distance qui est très connue, c'est la distance euclidienne. Alors très connue, elle est utilisée par exemple dans les méthodes d'analyses factorielles, en ACP, on utilise la distance euclidienne et on verra qu'en classification, sur des tableaux avec des individus en lignes et des variables en colonnes, c'est une distance qui est assez naturelle. Il y a également des indices de similarité et puis il y a de nombreuses mesures de ressemblance entre individus. Dans ce cours, on va surtout s'intéresser à la distance euclidienne. Donc là on s'intéresse à la ressemblance entre 2 individus, on doit aussi définir la ressemblance entre des groupes d'individus. Entre 2 groupes d'individus, donc ici sur le petit schéma on voit 2 groupes d'individus, il existe plusieurs mesures de ressemblance. La mesure du saut minimum, on parle aussi de lien simple, la distance du saut minimum entre 2 groupes ça va être la plus petite distance entre un élément du premier groupe et un élément du second groupe. Donc c'est la distance ici en rouge. Une autre mesure de distance entre 2 groupes c'est ce qu'on appelle le lien complet. C'est-à-dire qu'on va chercher la plus grande distance entre un individu du premier groupe et un individu du deuxième groupe. Et puis on verra un autre critère qui est le critère de Ward qu'on définira par la suite. Donc il existe plusieurs mesures de ressemblance entre individus, il existe plusieurs mesures de ressemblance entre des groupes d'individus et tout ça va conduire à des classifications légèrement différentes. Donc dans certaines situations on va utiliser plutôt certaines distances entre individus et plutôt certaines mesures de ressemblance entre groupes d'individus. Alors comment faire pour construire une classification ascendante hiérarchique? On va voir le fonctionnement d'un algorithme sur un exemple très simple avec 8 points A, B, C, D, E, F, G, H. Ces 8 points, je les ai représentés sur un plan et donc ça permet de visualiser des distances entre les points. Donc dans un premier temps, chaque point représente une classe constituée d'un seul individu. Je vais calculer la distance entre les points. Donc j'ai une matrice de distances. Par exemple, entre le point A et le point B, j'ai une distance de 0.5. Entre A et C, j'ai une distance de 0.25. Entre B et C, de 0.56, etc. Première étape: on va chercher la plus petite distance dans cette matrice de distances, 0.25, et on va regrouper les points A et C. On commence ainsi à construire l'arbre hiérarchique. Et donc on a cette fois des groupes d'individus constitués d'un seul individu plus un groupe constitué des individus A et C. On va alors calculer la distance entre chaque individu et le groupe AC. Donc la distance entre AC et l'individu B, si je considère le critère du saut minimum, ça va être la distance de 0.5. En effet, la distance entre A et B vaut 0.5, la distance entre B et C vaut 0.56. Donc la plus petite distance est égale à 0.5. Et ainsi je vais calculer toutes les distances entre le groupe AC et chaque individu. J'ai une nouvelle matrice de distances, je cherche la plus petite distance La plus petite distance est la distance entre le groupe AC et l'individu B et donc je vais regrouper ces 2 individus. Alors je regroupe ces 2 individus à une hauteur, l'arbre est à une hauteur de 0.5. Je les regroupe au niveau 0.5 et donc j'ai maintenant un groupe ABC et 5 groupes constitués d'un individu. Je calcule la distance entre le groupe ABC et chacun des individus, j'ai une nouvelle matrice de distances Et dans cette nouvelle matrice de distances, je vais regrouper les 2 individus les plus proches ou les 2 groupes d'individus les plus proches. Donc là on voit que c'est la distance entre F et G qui est la plus petite à 0.61. Donc je vais regrouper les points F et G à la distance de 0.61. Je continue, j'ai regroupé les individus F et G donc je vais calculer les distances entre le groupe F et G et tous les autres groupes. Donc la plus petite distance cette fois est entre D et E, une distance de 1. Donc je regroupe D et E à la distance de 1 et j'ai constitué le groupe DE. Donc j'ai les groupes ABC, DE, FG et H. Je vais calculer la matrice de distance. La plus petite distance est entre FG et le point H. Je regroupe FG et le point H. Et j'itère, je continue. J'ai plus que 3 groupes. La plus petite distance est entre DE et FGH. Je les regroupe. Il ne me reste plus que 2 groupes que je regroupe à la distance de 4.07. Et donc itérativement j'ai construit l'arbre hiérarchique en regroupant pas à pas les groupes les plus proches. Alors évidemment construire un arbre hiérarchique ici est relativement aisé car on a peu d'individus, mais dès qu'on a beaucoup plus d'individus, il va être nécessaire d'utiliser des programmes informatiques. Alors une fois qu'on a constitué cet arbre, eh bien les arbres hiérarchiques, comme tous les arbres, finissent tous par être coupés, et donc on a envie, en coupant l'arbre, de constituer des classes. En définissant un niveau de coupure sur un arbre, on définit une partition. Donc ici sur cet arbre hiérarchique, Je peux définir un niveau de coupure là où il y a le trait noir et on voit qu'on va constituer 4 classes d'individus. Donc en définissant le niveau de coupure, on définit un nombre de classes. Alors évidemment, vu le mode de construction de l'arbre, la partition n'est pas nécessairement optimale. En effet, on a pris en compte toute une hiérarchie entre les individus, entre les groupes d'individus. Donc la partition n'est pas nécessairement optimale mais souvent c'est une partition qui est de bonne qualité. On verra en fin d'exposé comment améliorer cette partition justement. Donc une partition va être bonne si les individus d'une même classe sont très proches et si au contraire— une partition sera bonne si les individus d'une même classe sont proches, s'ils ont des caractéristiques communes. Une partition est bonne également si les individus de 2 classes différentes sont éloignés, ont peu de caractéristiques communes. Alors comment traduire mathématiquement ces 2 idées? 2 individus d'une même classe sont proches, ça veut dire que la variabilité intra-classe est petite, c'est-à-dire qu'à l'intérieur d'une classe il y a très peu de variabilité, les individus se ressemblent. Et la 2ème affirmation: les individus de 2 classes différentes sont éloignés, ça veut dire que d'une classe à l'autre il y a une grande variabilité et donc ça veut dire qu'on veut une variabilité inter-classes grande. Donc on a envie d'avoir à la fois une variabilité intra-classe petite et une variabilité inter-classes grande. Donc ça nous donne 2 critères. Alors lequel choisir? C'est toujours délicat de choisir et là heureusement on a en fait un seul critère. En effet, l'inertie totale, la variabilité totale, se décompose en variabilité intra-classe plus variabilité inter-classes. Donc ici Xi_i, Q_i, c'est la valeur prise par l'individu i de la classe q. X barre c'est la moyenne générale et X barre q c'est la moyenne dans la classe q. Donc l'inertie intra c'est la variabilité à l'intérieur de la classe, donc c'est tous les écarts entre les Xi q et les X barre q, les écarts au carré. Et puis l'inertie inter c'est la somme des ². Et donc grâce au théorème de Wilcoxon, on sait que l'inertie totale c'est bien l'inertie inter plus l'inertie intra. Et donc si on minimise l'inertie intra, on est en train de maximiser l'inertie inter puisque l'inertie totale ne bouge pas. Donc finalement on a vraiment un seul critère: on peut se focaliser sur l'inertie intra et la minimiser ou sur l'inertie inter et la maximiser. Alors donc la qualité de la partition, on va pouvoir la mesurer par le ratio entre inertie inter sur inertie totale. Inertie inter sur inertie totale égale 0, ça veut dire que tous les X barre q sont égaux et ils sont tous égaux à x-barre, ça veut dire que toutes les classes ont la même moyenne. Alors évidemment, si toutes les classes ont la même moyenne, c'est une partition qui ne va pas séparer les classes, ça ne permet pas de classifier. Si l'inertie inter sur l'inertie totale est égale à 1, ça veut dire que l'inertie intra sera égale à 0 et ça veut donc dire qu'à l'intérieur d'une classe, les individus sont identiques. Si les individus à l'intérieur d'une classe sont identiques, Ça veut dire que les classes sont très homogènes et ça c'est idéal pour classifier. Alors attention toutefois, c'est que ce critère d'inertie inter sur inertie totale ne peut pas être jugé en absolu. En effet, ce critère dépend du nombre d'individus et du nombre de classes. Si on augmente le nombre de classes qu'on constitue, il sera plus facile d'avoir des classes homogènes. Si le nombre de classes est réduit, si on a peu de classes, À l'intérieur des classes, il y aura plus de variabilité. Donc on doit relativiser ce critère par rapport au nombre d'individus et au nombre de classes. Alors ça nous conduit à une méthode pour construire la classification ascendante hiérarchique qui a été développée par Ward, qu'on appelle la méthode de Ward. Le principe est simple: on part d'une classification où une classe est égale à un individu. Donc si un individu est égal à une classe, alors à l'intérieur de la classe il n'y a pas de variabilité intra et donc l'inertie inter est égale à 1. Donc on a une partition qui est idéale. Et donc l'objectif ça va être d'agréger 2 classes A et B qui minimisent la diminution de l'inertie inter. En effet, l'inertie inter ne va pouvoir que diminuer quand on va regrouper des classes. Et donc ce qu'on va chercher à faire c'est à minimiser la diminution de l'inertie interne. Alors on peut noter que l'inertie d'une classe A plus l'inertie d'une classe B c'est égal à l'inertie de la réunion de ces 2 classes moins une quantité qui est égale à MA MB sur MA+ MB multiplié par d² de AB. Alors MA c'est le nombre d'individus dans la classe A, MB le nombre d'individus dans la classe B et d² de AB c'est la distance entre les centres de gravité de la classe A et de la classe B. Alors ce qu'on cherche c'est à ce que la réunion des classes A et B soit la plus proche possible de l'inertie de A plus l'inertie de B. Quand on regroupe A et B, on ne perde pas trop. Et là on voit que ce qu'on perd c'est m_A m_B sur m_A+ m_B multiplié par d². Donc on va chercher à minimiser cette dernière quantité. Alors minimiser cette dernière quantité, il y a finalement 2 choses dans cette quantité: il y a le produit m_A m_B sur m_A+ m_B Cette quantité va en fait permettre de regrouper des objets de faible poids et en fait ça va éviter des effets de chaîne. Alors j'ai ici un petit graphe avec 2 classes, la classe bleue et la classe rouge, et les arbres hiérarchiques avec le saut minimum et le critère de Ward. Donc quand les classes sont bien séparées, on retrouve bien 2 classes avec nos 2 méthodes de construction de l'arbre hiérarchique. En revanche, si on a la classe B et la classe A et puis beaucoup d'individus qui vont de la classe A à la classe B. Avec la distance du saut minimum, on voit que l'arbre hiérarchique est très mauvais, il y a un effet de chaîne et on va avoir tendance à regrouper les individus de proche en proche. Donc l'arbre ne montre pas du tout qu'il y a 2 classes séparées et on voit qu'avec Ward, en prenant en compte MAMB/ , on sépare bien les 2 classes rouge et bleue. Et donc d² qui intervient dans ce produit, c'est juste la distance entre les barycentres des classes A et B. Donc c'est naturel ici de regrouper des classes qui ont des centres de gravité qui sont proches. Donc là, l'intérêt, on le voit immédiatement pour la classification: on regroupe des classes qui sont très proches. Alors prenons un exemple. C'est un exemple sur des températures. On a 15 villes de France en ligne. Et 12 variables qui correspondent aux températures mensuelles annuelles mesurées sur 30 ans. Et on a en plus 2 variables, la latitude et longitude, qui vont pouvoir servir éventuellement pour caractériser les classes mais qui ne vont pas nous servir pour construire les classes. Je vais construire les classes uniquement à partir des données de température. Donc ce que je cherche quand je fais une classification, c'est à regrouper des villes qui ont des profils météo qui sont similaires. Et puis la deuxième étape, ce sera de caractériser ces différents groupes de villes. Alors voici l'arbre hiérarchique. Donc on voit par exemple que les villes de Toulouse et Bordeaux ont des profils météo qui se ressemblent et qui se ressemblent sur toute l'année. On voit un groupe Toulouse, Bordeaux, Nice, Montpellier, Marseille qui sont regroupés assez facilement. Donc je constitue ici un autre groupe de villes. On peut voir comme ça les proximités entre différentes villes. Dans le diagramme en haut à droite, on voit l'évolution de l'inertie pour différentes partitions. Alors on va voir ce diagramme de plus près. Le diagramme montre les pertes d'inertie interne lors du passage de 15 classes en 14 classes, de 14 classes en 13 classes, etc. Donc la première barre, la plus grande, montre la perte d'inertie interne lorsqu'on passe de 2 classes en 1 classe. Donc j'ai 2 classes d'individus et je les regroupe en une seule classe, j'ai une perte d'inertie inter de 7.88. Donc c'est une perte d'inertie inter qui est très importante, ça veut dire que je n'ai pas envie de regrouper les 2 classes. La barre rouge montre la perte d'inertie lorsqu'on passe de 3 classes en 2 classes. Il y a une perte d'inertie inter qui est de 1.56. C'est relativement important également et on peut se demander si on a envie de passer de 3 classes à 2 classes, donc de regrouper 2 classes. Et puis on voit toutes les pertes d'inertie interne. Si on somme les pertes d'inertie interne, on trouve la valeur de 12. Alors à quoi correspond cette valeur de 12? Cette valeur de 12 correspond ici au nombre de variables et comme on a réduit les données, comme on a centré-réduit chaque variable, eh bien ça correspond à la somme des variances de chaque variable. Donc on retrouve bien l'inertie totale qui est égale à 12. Alors sur cet arbre hiérarchique, combien dois-je faire de groupes? Est-ce qu'il faut faire 2 groupes, 3 groupes, 4 groupes? On peut se poser la question. Alors si je choisis un niveau de coupure ici, j'ai un découpage en 2 groupes. L'inertie interne vaut 7.88, l'inertie totale vaut 12 et Et donc le ratio inertie inter sur inertie totale est égal à 66%. C'est-à-dire qu'en séparant les villes en 2 groupes, des villes en rouge: Toulouse, Bordeaux, Nice, Montpellier, Marseille, et des villes en bleu: Brest, Rennes, Nantes, Grenoble, etc. jusqu'à Strasbourg, avec cette séparation des villes en 2 groupes, je récupère 66% de l'information qui est contenue dans le tableau de données. Donc j'ai un résumé du tableau de données sur les ressemblances entre individus. Alors à quoi est-ce que je peux comparer ce pourcentage de 66%? Eh bien en fait, je pourrais comparer ces 66% au pourcentage de variabilité expliqué par le premier axe de l'ACP. Avec le premier axe de l'ACP, j'avais récupéré environ 80% de l'information du jeu de données. Donc c'est-à-dire qu'avec la classification en en séparant juste les villes rouges des villes bleues, je récupère 66% de l'information. Donc je récupère un peu moins d'informations qu'avec le premier axe de l'ACP. En effet, le premier axe de l'ACP donne une information un peu plus fine. Il sépare Nice de Toulouse, Bordeaux. Il dit bien que Nice est plus extrême que Toulouse, Bordeaux, etc. Il dit que Lille est également plus extrême que Nantes. Avec la classification, j'ai juste fait les regroupements et je récupère 66% de l'information. Donc on a un résumé plus grossier avec la classification. Alors maintenant, si je sépare les villes froides Brest, Rennes, Nantes, Grenoble, Lyon jusqu'à Strasbourg en 2 groupes, je suis en train de faire une classification en 3 groupes. Et donc le passage de 2 classes à 3 classes, je vais récupérer une inertie de 1,56, donc je récupère 13% de l'information. Donc cette séparation des villes froides me permet de récupérer 13% de l'information totale. Et ces 13%, je peux les comparer au 2ème axe de l'ACP ici puisque effectivement le 2ème axe de l'ACP me sépare les villes froides en 2 groupes les villes en bleu des villes en vert. Donc avec la classification, si je fais une classification en 3 classes, je récupère 66%+ 13%, c'est-à-dire 79% de la variabilité des données. En constituant 3 classes, je récupère 79% de la variabilité des données. Avec l'ACP et 2 axes, je récupérerais en gros 99% de l'information. Alors comment déterminer un nombre de classes? On peut déterminer un nombre de classes à partir de l'arbre: on va avoir plutôt tendance à couper l'arbre là où les branches sont assez longues. On peut aussi s'appuyer sur l'histogramme des indices de niveau. Et voir quand est-ce qu'il y a un saut, quand est-ce qu'on récupère assez peu d'informations et qu'il n'est plus vraiment utile de regrouper certaines classes. Le nombre de classes dépend également de l'enquête, ça dépend aussi du nombre d'individus. Si on a une enquête avec des milliers d'individus, eh bien ça va être intéressant de constituer 5, 6, voire une dizaine de classes. Si on a maintenant beaucoup moins d'individus, on aura envie d'avoir un résumé et d'avoir moins de classes. De même, si on est en train de classifier des individus statistiques qui sont très différents, on va avoir envie de constituer plus de classes. Et puis un critère ultime lorsqu'on constitue des classes, ça va être l'interprétabilité des classes. Est-ce qu'on arrive à comprendre les classes? Il est inutile de séparer une classe en 2 classes si on ne comprend pas les 2 classes qu'on est en train de constituer. Alors on va voir une autre méthode pour construire une classification avec un algorithme de partitionnement qui est appelé les K-means. Alors l'algorithme de partitionnement des K-means, qu'on appelle aussi l'algorithme d'agrégation autour des centres mobiles, fonctionne de la façon suivante: au départ on choisit Q centres de classe au hasard. Donc ici dans mon exemple je vais prendre Q= 3 et je choisis donc 3 centres de classe: Rennes, Vichy et Clermont. Ce sont 3 centres de classes au hasard. Ça c'est la première étape: l'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. J'ai ainsi constitué 3 classes. Je vais calculer maintenant les centres de gravité de chacune de ces classes. Donc je calcule le centre de gravité de la classe rouge, de la classe noire et de la classe verte. Voici les centres de gravité des classes. Et puis je vais itérer ces 2 étapes: je vais affecter à nouveau les points au centre le plus proche. Donc on voit ici que les centres de gravité ne sont plus des individus, ce sont des points fictifs. Et donc j'affecte les individus aux centres de classes les plus proches. Et j'itère. Donc je vais constituer les classes rouge, vert et noir, je calcule les centres de gravité, le centre de gravité se déplace, j'affecte les points au centre le plus proche, je calcule les nouveaux centres de gravité, j'affecte les points au centre le plus proche, et on voit que les classes n'ont pas changé, les centres de gravité ne bougent plus, l'algorithme a convergé. Et on a ainsi constitué les 3 classes. Voilà le fonctionnement de l'algorithme des k-means. Alors cet algorithme est très rapide, très intéressant, il dépend en revanche de l'initialisation. Quand on choisit 3 classes au hasard, ça conduit vers une classification. Si on choisit 3 autres centres de classes, 3 autres villes comme centres de classes au début de l'algorithme, ça peut conduire à une autre classification. Comment on va faire en pratique? On va utiliser plusieurs initialisations et conserver la meilleure partition. Alors quelques compléments sur la classification. On peut consolider la partition obtenue par la classification ascendante hiérarchique. En effet, je vous ai dit tout à l'heure, en construisant l'arbre hiérarchique, que la partition obtenue n'était pas optimale parce qu'on prenait en compte toute une hiérarchie entre les individus statistiques. Cette hiérarchie est intéressante. Maintenant, si on veut uniquement utiliser l'information sur la partition, il peut être intéressant de consolider la partition en utilisant les K-means. Donc on va se servir 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'à la convergence. Ça va améliorer la partition Nécessairement on améliore le critère, donc ça consolide la partition. Maintenant l'inconvénient c'est qu'on a perdu une information: on perd l'information de la hiérarchie. Une fois qu'on a consolidé la partition, certains individus changent de classe et donc on perd complètement la hiérarchie. Comment faire maintenant si on a des données de grandes dimensions? Donc si on a beaucoup de variables, c'est assez simple: on peut d'abord faire une ACP et ne conserver que les premières dimensions de l'ACP. Donc l'ACP va permettre de concentrer l'information sur les premières dimensions factorielles et donc ensuite, comme on a assez peu de dimensions, on va pouvoir faire la classification sur un tableau avec des individus et quelques variables. Et donc là on se ramène au cas classique: un tableau individus× variables. Si maintenant on a beaucoup d'individus, l'algorithme de classification est très long. Si on a 1 million d'individus, la construction de l'algorithme hiérarchique est beaucoup trop longue et donc on peut pas le construire. Donc en pratique, comment on peut faire? On peut travailler par étapes. D'abord faire une partition très grossière avec des K-means. Donc on va constituer une centaine de classes. Le fait de constituer une centaine de classes va regrouper les individus qui sont globalement proches. Et puis ensuite on va construire la classification hiérarchique à partir des classes qui ont été précédemment construites. Alors évidemment, en construisant la classification ici, on va utiliser les effectifs des classes dans le calcul. On va obtenir le haut de l'arbre hiérarchique de la classification hiérarchique et on va perdre le bas de l'arbre hiérarchique. Mais de toute façon le bas de l'arbre hiérarchique, quand on a 1 million d'individus, n'est pas lisible et il n'est pas intéressant de le lire. Ce qui nous intéresse c'est uniquement le haut de l'arbre. Si maintenant on a des données qualitatives, comment peut-on faire? Il y a 2 stratégies. Première stratégie, c'est de se dire on va se ramener à des variables quantitatives Pour ce faire, on peut faire une ACM, une analyse des correspondances multiples, et ne conserver que les premières dimensions de l'ACM ou éventuellement toutes les dimensions de l'ACM. L'ACM va permettre de passer d'un tableau de variables qualitatives à un tableau avec uniquement les coordonnées des individus. Les coordonnées des individus sont des variables qui sont quantitatives. Et donc on va avoir un tableau individus x variables quantitatives. Sur lequel on va pouvoir réaliser une CAH. Une autre façon de faire, c'est d'utiliser des mesures adaptées aux données qualitatives. Donc on va utiliser des indices: l'indice de similarité, l'indice de Jaccard. Donc ces indices vont permettre d'obtenir la matrice de distances entre individus. Et donc à partir de la matrice de distances, on peut construire un arbre hiérarchique. Alors un dernier point sur l'enchaînement analyse factorielle/ classification: Pourquoi il est intéressant de faire une analyse factorielle avant de faire une classification? On a vu 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. On peut utiliser le même algorithme de classification. Et puis l'autre aspect c'est que l'analyse factorielle va concentrer l'information sur les premières composantes, les dernières composantes n'étant que du bruit, c'est-à-dire de l'aléatoire. Et donc on va pouvoir éliminer ces dernières composantes avant de faire la classification. On va donc éliminer l'aléatoire, le bruit, avant de faire la classification. Et donc si on élimine le bruit, ça permet d'obtenir une classification qui en pratique est plus stable. Et puis le dernier intérêt, ça va être de pouvoir représenter l'arbre hiérarchique, les classes sur le plan factoriel. Donc le fait d'avoir à la fois 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 à l'analyse factorielle, grâce au plan factoriel. 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 finalement sur une 3e et 4e dimension. Et avec la classification, on va pouvoir avoir cette information. Donc on a à la fois une vision très synthétique avec les classes et une vision un peu plus fine avec le plan factoriel. Alors maintenant qu'on a constitué les classes, comment est-ce qu'on peut caractériser les classes d'individus? Tout d'abord, une première caractérisation, ça va être de trouver l'individu le plus proche du centre de la classe. Pourquoi utiliser l'individu le plus proche du centre de la classe? C'est que le centre de gravité d'une classe est un individu fictif qui n'existe pas, et donc on peut utiliser un vrai individu pour voir comment se comporte la moyenne de la classe. Donc par exemple ici, on voit que dans la classe 1, c'est l'individu Montpellier qui est le plus proche du centre de la classe, il est à une distance de 0.42. Donc c'est-à-dire que si je veux interpréter comment se comporte la moyenne de la classe, je vais pouvoir regarder l'individu Montpellier. Pour la classe 2, c'est Rennes qui est le plus proche du centre de la classe et pour la classe 3 c'est Vichy. Donc ces parangons parlent assez bien en général aux professionnels. Et on peut représenter ces parangons sur le plan factoriel. Donc on a ici le centre de gravité de la classe 2 et le parangon de cette classe qui est reine. Alors maintenant je vais aussi avoir envie de caractériser les classes par les variables. Donc mon objectif va être de trouver les variables les plus caractérisantes pour la partition. Ça va être également de caractériser une classe, un groupe d'individus, par des variables quantitatives et donc de trier les variables qui caractérisent les classes de la variable la plus caractérisante à la moins caractérisante. Donc les questions c'est: quelles sont les variables qui caractérisent le mieux la partition? Comment caractériser les individus de la classe 1? Quelle variable les caractérise le mieux? Alors quelle variable caractérise le mieux la partition? En fait, pour chaque variable quantitative, je vais construire un modèle d'analyse de variance entre la variable quantitative qui va me servir de variable réponse en fonction de la variable classe qui est une variable qualitative. Je fais l'analyse de variance de la variable quantitative en fonction de la variable de classe et je vais construire le test de Fisher pour voir s'il y a un effet de la variable de classe. Et je peux trier les variables par probabilité croissante. Donc là je vois que la variable qui caractérise le mieux les classes est la variable octobre qui a la probabilité critique la plus petite et donc qui va me permettre de bien séparer les classes. Donc là c'est un critère qui est très global Maintenant si je veux comprendre chacune des classes, comment caractériser chaque classe par les variables? Ici j'ai représenté différentes variables du jeu de données et chaque point représente une ville. Les points en vert représentent les villes Lyon, Paris, Grenoble, Clermont, Vichy, Strasbourg, Lille. En bleu Nantes, Rennes, Brest. Et en rouge Nice, Marseille, Montpellier, Bordeaux, Toulouse. Et ce que je cherche à voir c'est est-ce qu'il y a des variables qui me permettent de bien caractériser une classe. Donc est-ce que les valeurs sont extrêmes, particulières pour les individus d'une classe? On a l'impression par exemple que pour la variable janvier, les individus en vert, les points en vert ont des valeurs plus faibles que tous les autres et donc la variable janvier caractérise la classe verte. Évidemment je vais avoir besoin de procédures automatiques L'idée de la caractérisation d'une classe, ça va être que si j'ai une variable quantitative X, si les valeurs de X pour la classe q semblent tirées complètement au hasard parmi les valeurs de X, alors c'est que X ne caractérise pas la classe q. Et au contraire, si les valeurs de X semblent particulières pour la classe q, donc si l'hypothèse d'un tirage au hasard est douteuse, alors X caractérise bien la classe. Donc j'ai représenté ici une variable avec des données au hasard et puis la variable du mois d'août avec la position des points. Donc on voit que pour la variable au hasard, on a des points bleus, verts et rouges qui sont répartis un peu n'importe comment et on a l'impression que c'est un peu plus structuré pour le mois d'août. Le mois d'août va caractériser sûrement la classe rouge par exemple, qui a des points assez extrêmes. Dans le détail comment faire pour construire un test. Première idée, ça va être de comparer la moyenne de la classe qui m'intéresse, de la classe q, et la moyenne générale. Si la moyenne de la classe q est très différente de la moyenne générale, c'est que la variable caractérise la classe. Et si la moyenne de la classe X barre q est proche de la moyenne X barre générale, ça veut dire que X va avoir du mal à caractériser la classe. Donc j'ai envie de prendre en compte X barre q dans la caractérisation d'une classe. Alors maintenant 3 cas où l'écart entre X barre q et X barre est le même. Si je regarde le cas 1 et le cas 2, je vois que X explique mieux la classe q dans le cas 1 que dans le cas 2 car les valeurs en rouge ici semblent extrêmes alors que pour le cas 2 les valeurs en rouge ne sont pas extrêmes et sont plutôt au milieu de la distribution de toutes les valeurs. Je vais avoir envie de relativiser l'écart entre X barre Q et X barre par rapport à l'écart-type de la variable X. Maintenant si je compare le cas 2 et le cas 3, les valeurs en rouge sont à peu près au même endroit. Maintenant dans le cas 2, j'ai quelques valeurs en rouge qui sont à peu près au même endroit, je me dis que c'est peut-être du hasard. Et dans le cas 3, j'ai une quarantaine de valeurs en rouge qui sont au même endroit. Et là je me dis c'est pas possible que ce soit du hasard. Donc je vais avoir envie de relativiser l'écart entre X barre q et X barre par le nombre d'individus dans la classe q. Donc je vais avoir envie, pour caractériser la classe, de prendre en compte l'écart entre X barre q et X barre, de relativiser par rapport à S et par le nombre d'individus dans la classe q. Donc l'idée générale pour caractériser une classe, ça va être l'idée du tirage au hasard de iq valeurs parmi i. J'ai iq valeurs dans ma classe q, est-ce qu'elles sont choisies au hasard parmi les i valeurs de la population? Et donc la question c'est finalement quelle valeur peut prendre X barre q? C'est-à-dire quelle est la loi de X barre q? Donc l'espérance de X barre q, sous l'hypothèse d'un tirage au hasard, l'espérance de X barre q c'est la moyenne de toute la population, c'est-à-dire X barre. La variance de X barre q, je tire iq valeurs parmi i valeurs, donc c'est l'écart-type de la population, ici s carré. Divisé par le nombre d'individus tirés Iq. Et puis il y a un terme correctif ici parce qu'on est dans un tirage dans une population de taille finie. Donc il y a ce terme correctif / . Et puis X barre q suit une loi normale car X barre est une moyenne. Donc comme X barre est une moyenne, le théorème central limite nous dit que X barre q va suivre une loi normale. Et donc je vais calculer une valeur centrée-réduite X barre q moins X barre sur l'écart-type de X barre q, c'est-à-dire la racine carrée de la variance de X barre q. Cette quantité, sous l'hypothèse d'un tirage au hasard, va suivre une loi normale centrée-réduite. Si la valeur-test est comprise entre -1,96 et 1,96, elle peut provenir d'une loi normale centrée-réduite et donc elle n'est pas particulière. Si maintenant la valeur-test en valeur absolue est supérieure à 2, alors cette valeur-test est particulière, on va dire qu'il est peu probable qu'elle provienne d'une loi normale centrée réduite et on va remettre en cause l'hypothèse d'un tirage au hasard. Donc on va dire que les Iq valeurs ne semblent pas être choisies au hasard parmi les I valeurs, c'est-à-dire que les valeurs de X pour la classe q semblent particulières et donc ça veut dire que la variable X caractérise la classe q. Et plus l'hypothèse d'un tirage au hasard est douteuse, plus la valeur-test sera grande et plus la variable X caractérisera la classe. Donc l'idée ça va être de classer les variables par valeur-test décroissante. On a les résultats pour la classe 1 avec les valeurs-tests. Donc la valeur-test la plus grande est pour la variable septembre. Donc ça veut dire que la variable septembre est la variable qui caractérise le mieux la classe 1. La moyenne des individus pour septembre est de 19.30°C alors que la moyenne générale pour tous les individus, y compris ceux de la classe 1, est égale à 17°C. On a ensuite l'écart-type dans la catégorie, 0.755, et l'écart-type de la population totale. Et puis on a la probabilité critique associée au test de la valeur-test suit une loi normale. Donc on voit qu'il y a beaucoup de variables qui caractérisent cette classe q et toutes les valeurs-tests sont positives, ça veut dire que les valeurs prises par les variables sont plus grandes pour les individus de la classe q que pour les individus en général. Pour la classe 2, les valeurs-tests sont négatives. La valeur-test la plus extrême est la valeur-test pour l'amplitude thermique annuelle. Donc là, la valeur-test étant négative, la moyenne de la catégorie, 12.40, est inférieure à la moyenne générale qui est de 15.90. Et pour la classe 3, eh bien là encore on a des valeurs-tests qui sont négatives donc les variables qui caractérisent caractérisent parce que les moyennes dans la classe sont inférieures à la moyenne générale. Donc la variable qui caractérise le plus est la variable de janvier qui a une valeur-test qui est plus extrême, -3.36. Effectivement la moyenne dans la classe est de 2.11°C contre 3.97°C pour la moyenne générale. On peut également caractériser les classes par les dimensions factorielles. Donc les dimensions factorielles, c'est les coordonnées des individus sur les axes factoriels. C'est donc une variable quantitative et donc je peux utiliser exactement la même méthodologie. Je vois que la classe 1 est caractérisée par le premier axe factoriel, la dimension 1. Donc la valeur-test est positive, ça veut dire que les individus de la classe 1 ont des coordonnées plus extrêmes et positives sur la première dimension factorielle. La moyenne dans la classe est de 3.97 alors que la moyenne générale est de 0. Pour les dimensions factorielles, la moyenne de toutes les coordonnées est toujours égale à 0 puisque les coordonnées sont centrées. Donc on voit que la classe 2 a des valeurs plus extrêmes sur la dimension 2 et les individus de la classe 3 ont des valeurs plus extrêmes sur les dimensions 1 et 2, donc des valeurs négatives sur la dimension 2 et sur la dimension 1. Merci de votre attention.