Classification ascendante hiérarchique (cours 1/4) : les données, la problématique

Cette semaine, nous nous intéressons aux méthodes de classification, la classification ascendante hiérarchique et une méthode de partitionnement, les K-means. L'ensemble des vidéos de cours de cette semaine aborde les points suivants: après une brève introduction sur les données rencontrées en classification et les objectifs de la classification, nous verrons quels sont les principes généraux de la classification, notamment de la classification ascendante hiérarchique. Quels critères peuvent être utiliser et quels algorithmes. Ensuite nous décrirons une méthode de partitionnement, la méthode très connue des k-means. Et enfin nous verrons différents compléments sur l'utilisation conjointe de la classification et des k-means, de la classification sur des données de grandes dimensions ou de la classification sur des données qualitatives. Nous terminerons cet exposé en proposant une méthode pour caractériser les individus d'une même classe. Commençons dans cette vidéo par donner quelques définitions et par présenter la classification ascendante hiérarchique.

La classification, c'est l'action de constituer ou de construire des classes, des groupes ou des catégories. Et les classes sont des ensembles d'individus ou d'objets qui possèdent des traits de caractère communs. Des traits de caractère 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. Des classes, vous en connaissez aussi, les classes sociales, les catégories socioprofessionnelles, les classes politiques, donc on va regrouper des individus qui ont des caractéristiques communes. Et donc cela amène à 2 types de classification: des classifications appelées hiérarchiques pour lesquelles on cherchera à construire un arbre hiérarchique pour voir comment s'organisent les objets ou les individus. On va parler ici de classification ascendante hiérarchique. Et puis des classifications de type méthode de partitionnement où on va essayer uniquement de constituer des groupes d'individus qui se ressemblent et de constituer une partition. Voici un exemple d'arbre hiérarchique, l'arbre hiérarchique du règne animal. On trouve dans le règne animal des embranchements, donc différents embranchements: les arthropodes, les cnidaires, les vertébrés. Dans les vertébrés, on trouve différents vertébrés: les mammifères, les oiseaux, les reptiles, les amphibiens, les poissons. Dans les mammifères, on trouve les monotrènes, les identés, les tulidentés, les carnivores, etc. Et si on descend dans la hiérarchie, on trouve des classes de plus en plus homogènes. Dans le bas de la hiérarchie, les espèces ont des caractéristiques très communes et 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. Décrivons les principes généraux de la classification ascendante hiérarchique. Nous allons voir quels sont les critères utilisés, les algorithmes pour construire un arbre hiérarchique et enfin comment quantifier la qualité d'une partition avant de proposer une méthode pour des données euclidiennes: la méthode de Ward. Donc quelles sont les données sur lesquelles on va pouvoir construire une classification ascendante hiérarchique? Eh bien ce sont les mêmes données qu'en analyse en composantes principales, à savoir des tableaux de données avec des individus en lignes et des variables quantitatives en colonnes. Les variables sont quantitatives mais nous verrons en fin d'exposé comment faire quand les variables sont qualitatives. L'objectif de la classification est de produire une arborescence qui met en évidence les liens hiérarchiques entre les individus ou entre des groupes d'individus. Par exemple, sur l'arbre hiérarchique ici à droite, les individus A et C sont très proches et sont aussi assez proches de l'individu B. Ces 3 individus forment une classe. D'autre part, les 5 individus D, E, F, G et H se ressemblent et, à l'intérieur de cette classe, les individus F et G se ressemblent un peu plus. Cette représentation sous forme d'arbre permet également de détecter un nombre de classes naturel dans une population. Par exemple, dans l'arbre proposé, on peut décomposer les individus en 2 classes: la classe ABC et la classe DEFGH. Alors quels sont les critères de la classification? Il faut, pour réaliser une classification, définir une mesure de 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? Une distance très connue et naturelle lorsqu'on visualise les données, c'est la distance euclidienne. Nous avons déjà utilisé cette distance en ACP et nous verrons qu'en classification, sur des tableaux avec des individus en lignes et des variables en colonnes, c'est une distance qui est aussi naturelle. Il existe également des indices de similarité souvent associés à un domaine d'application spécifique. En écologie par exemple, l'indice de Jaccard est très utilisée. Il existe de nombreuses mesures de ressemblance entre individus. Dans ce cours, on va principalement s'intéresser à la distance euclidienne, notamment parce qu'on fera le lien avec les méthodes d'analyse factorielle qui fournissent des représentations elles aussi euclidiennes. Donc là on s'est intéressé à la ressemblance entre 2 individus. On doit aussi définir la ressemblance entre groupes d'individus. Donc sur le petit schéma suivant, on voit 2 groupes d'individus et une première mesure de ressemblance est le saut minimum. On parle aussi de lien simple. C'est la distance ici en rouge. La distance minimum entre 2 groupes est égale à la plus petite distance entre un élément du premier groupe et un élément du second groupe. Une autre mesure de distance entre 2 groupes est ce qu'on appelle le lien complet. On va prendre cette fois la plus grande distance entre un individu du premier groupe et un individu du 2ème groupe. On définira dans la suite de l'exposé une autre mesure de ressemblance appelée le critère de Ward Et il existe plusieurs mesures de ressemblance entre individus et plusieurs mesures de ressemblance entre groupes d'individus. Le choix de la mesure de ressemblance modifie la classification que l'on obtiendra. Donc selon les données, on utilisera certaines distances entre individus et certaines mesures de ressemblance entre groupes d'individus. Donc à partir d'un exemple simple, nous allons construire à la main un arbre hiérarchique afin de comprendre le fonctionnement de l'algorithme. Nous considérons ici 8 points A, B, C, D, E, F, G et H et les coordonnées de ces points sur 2 dimensions. Nous pouvons ainsi représenter les 8 points dans un plan afin de visualiser les distances entre ces 8 points. Donc dans un premier temps, chaque point représente une classe constituée d'un seul individu. Pour cette raison, chaque point est entouré d'une petite ellipse qui ne contient qu'un seul point. La première chose à faire est de calculer la distance entre les points. On utilise ici la distance euclidienne. 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, 0.56, etc. La première étape: on va chercher la plus petite distance dans cette matrice de distances. La plus petite distance correspond à 0.25 et est celle entre les points A et C. On commence ainsi à construire l'arbre hiérarchique en regroupant les points A et C. Le regroupement de ces 2 points se fait à une hauteur de 0.25, c'est-à-dire la distance entre ces 2 points. Et donc on a maintenant 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. Pour ce faire, nous allons utiliser la mesure de ressemblance du sceau minimum. La distance entre A et C 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 et la distance entre B et C vaut 0.56. Donc la plus petite distance est égale à 0.5. On calcule ainsi toutes les distances entre le groupe AC et chaque individu, ce qui donne une nouvelle matrice de distances. On cherche la plus petite distance de cette nouvelle matrice. C'est la distance entre le groupe AC et l'individu B. Donc on va regrouper ces 2 groupes d'individus et les regrouper à une hauteur de 0.5 dans l'arbre. Donc j'ai maintenant un groupe ABC et 5 groupes constitués d'un individu. On calcule la distance entre le groupe ABC et chacun des individus pour avoir une nouvelle matrice de distances et dans cette nouvelle matrice de distances, la plus petite distance nous indique qu'il faut regrouper E et F. On regroupe donc ces 2 points à une hauteur de 0.61. On continue en calculant une nouvelle matrice de distances qui contient le groupe EF. La plus petite distance cette fois est entre D et E avec une distance de 1. On regroupe D et E à une distance de 1. On a alors à cette étape les groupes ABC, DE, FG et H. On calcule la nouvelle matrice de distances. La plus petite distance est entre FG et le point H. On regroupe donc le groupe FG et le point H à une hauteur de 1,12. On continue avec les 3 groupes restants. La plus petite distance est entre le groupe DE et le groupe FGH. On les regroupe à la hauteur de 1,81. Il ne reste plus que 2 groupes que l'on regroupe à la distance de 4,07. Et nous finissons la construction de l'arbre avec ce dernier regroupement. Ainsi, itérativement, nous avons construit l'arbre hiérarchique en regroupant pas à pas les 2 groupes les plus proches. Évidemment, construire un arbre hiérarchique est ici relativement aisé car on a peu d'individus. Mais dès que le nombre d'individus est plus grand, il sera difficile de construire un tel arbre à la main et il sera nécessaire d'utiliser des programmes. Alors une fois qu'on a construit cet arbre, Eh bien, les arbres hiérarchiques, comme tous les arbres, finissent par être coupés. Ici, on va vouloir couper l'arbre pour constituer des classes. En définissant un niveau de coupure sur un arbre, on définit une partition. Dans l'arbre suivant, le niveau de coupure représenté par le trait noir définit une partition en 4 classes. En définissant une coupure, je définis 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 lors de la construction de l'arbre une contrainte de hiérarchie entre individus ou groupes d'individus, ce qui n'est pas utile pour définir une partition. En levant cette contrainte de hiérarchie, il est possible d'améliorer la partition, ce que nous verrons à la fin de cet exposé. Toutefois, si la partition obtenue en coupant un arbre hiérarchique n'est pas nécessairement optimale, c'est souvent une partition qui est de bonne qualité. Alors une partition va être de bonne qualité si les individus d'une même classe sont très 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? Eh bien 2 individus d'une même classe sont proches si la variabilité intra-classe est petite. Ça veut dire que, à 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 si d'une classe à l'autre il y a une grande variabilité. Et donc ça veut dire qu'on veut une variabilité interclasses grande. Donc on a envie d'avoir à la fois une variabilité intra-classes petite et une variabilité interclasses grande. Donc ça nous donne 2 critères. Alors lequel choisir? C'est toujours délicat de choisir mais là Ces 2 critères n'en font en fait qu'un. En effet, l'inertie totale, la variabilité totale, représentée en bleu sur le schéma, se décompose en une variabilité intra-classe représentée en noir plus une variabilité inter-classes représentée en rouge. Donc ici XIQ est la valeur prise par l'individu i de la classe q, X-barre est la moyenne générale, X-barre q est la moyenne dans la classe q. L'inertie intra, c'est la variabilité à l'intérieur de la classe et cela correspond à la somme de tous les écarts au carré entre les Xi_q et le X barre_q. L'inertie inter, c'est la somme des écarts au carré entre les moyennes de chaque classe X barre_q et la moyenne générale X barre. Et donc grâce au théorème de Huygens, on sait que l'inertie totale c'est égal à l'inertie inter plus l'inertie intra. Par conséquent, minimiser l'inertie intra revient à maximiser l'inertie inter puisque l'inertie totale reste constante. Donc finalement on a un seul critère: on peut se focaliser sur l'inertie intra et la minimiser ou sur l'inertie inter et la maximiser. Cela nous suggère un indicateur de la qualité d'une partition: le ratio inertie inter sur inertie totale. Ce ratio varie entre 0 et 1 et plus il est proche de 1, meilleure est la partition. L'inertie inter sur l'inertie totale est égale à 0 quand tous les X barre q sont égaux et sont égaux à X barre. Cela signifie 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 sépare pas les classes et qui ne permet pas de classifier. Si l'inertie inter sur l'inertie totale est égale à 1, ça veut dire que l'inertie intra est égale à 0. Cela signifie que, à 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, ce critère 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, il est plus facile d'avoir des classes homogènes. Au contraire, si le nombre de classes est petit, à l'intérieur de chaque classe, la variabilité est plus grande. Il faut donc relativiser ce critère par rapport au nombre d'individus et au nombre de classes. Ce critère de qualité d'une partition suggère une nouvelle méthode pour construire une classification ascendante hiérarchique. Cette méthode a été développée par Ward et s'appelle la méthode de Ward. Le principe est le suivant: on part d'une classification où une classe correspond à un individu. Si une classe correspond à un individu, alors à l'intérieur de la classe il n'y a pas de variabilité intra et l'inertie inter est donc égale à 1. La partition est donc idéale. L'objectif est alors de choisir 2 classes A et B telles que leur agrégation minimise la diminution de l'inertie inter. En effet, l'inertie inter ne peut que diminuer lors d'un regroupement de 2 classes et on va chercher à minimiser cette diminution de l'inertie inter. Voyons comment s'écrit la somme de l'inertie d'une classe A et de l'inertie d'une classe B en fonction de l'inertie de l'agrégation de ces 2 classes. L'inertie de A plus l'inertie de B est égale à l'inertie de la réunion de ces 2 classes moins une quantité mA fois mB divisé par mA+ nB multiplié par d². mA est le nombre d'individus de la classe A. Mb le nombre d'individus de la classe B et d²AB est la distance entre les centres de gravité de la classe A et de la classe B. Comme on veut que l'inertie de la réunion des classes A et B soit la plus proche possible de l'inertie de A plus l'inertie de B, il suffit donc de minimiser cette dernière quantité. Cette dernière quantité contient 2 choses: des poids et une distance au carré. Cette quantité tout d'abord, Ma fois Mb sur Ma+ Mb, va permettre de regrouper des objets de faible poids et éviter ce qu'on appelle des effets de chaîne. On a ici un petit graphique avec 2 classes, la classe bleue et la classe rouge, et les arbres hiérarchiques avec le saut minimum à gauche et le critère de Ward à droite. Quand les classes sont bien séparées, on retrouve les 2 mêmes classes avec les 2 critères. En revanche, avec ces 2 mêmes classes plus beaucoup d'individus qui vont de la 1ère classe à la 2ème, En utilisant la distance du saut minimum, l'arbre hiérarchique est très mauvais car on a un effet de chaîne qui conduit à regrouper les individus de proche en proche. Donc l'arbre ne met pas du tout en évidence 2 classes séparées. Avec Ward en revanche, et grâce à cette pondération, les 2 classes rouge et bleue sont bien séparées. Le 2ème terme de la quantité à minimiser est d², c'est la distance entre les barycentres des classes A et B. Il est tout à fait naturel de regrouper des classes qui ont des centres de gravité qui sont proches. L'intérêt est immédiat ici pour la classification: on regroupe des classes qui sont très proches.

Nous avons vu comment fonctionne la classification ascendante hiérarchique. Nous verrons dans les vidéos suivantes comment la mettre en œuvre sur un exemple, comment utiliser la classification ascendante hiérarchique pour déterminer un nombre de classes et comment construire une partition des individus. Nous verrons également dans la dernière vidéo comment caractériser les individus d'une même classe.

N'oubliez pas de faire les quiz pour vous assurer que vous avez bien compris les différentes notions abordées dans cette vidéo.