Classification Ascendante Hierarchique (CAH) - Jonathan Lenoir
TD Master EAB : Classification Ascendante Hiérarchique appliquée à des
données .... L'examen complet des possibilités étant impossible, il est nécessaire
de .... et dont la projection sur le plan factoriel (F1 : F2) d'une AFC est la suivante :
.
part of the document
Classification Ascendante Hiérarchique : application a des données phytoécologiques
TD Master EAB
Théorie et application sous R à des données de présence/absence issues de relevés floristiques forestiers
Le but de cette session de Travaux Dirigés est de réaliser une classification automatique dun ensemble dindividus (espèces ou relevés en phytoécologie) dans des groupes homogènes. Dans un premier temps, nous présenterons une méthode possible de classification, la Classification Ascendante Hiérarchique (CAH), algorithme largement utilisé en écologie. Ensuite, nous appliquerons cette méthode au cas de données phytoécologiques, ceci afin de créer des groupes despèces ou de relevés (exercice de typologie des stations). On pourra utiliser les résultats obtenu par lAFC sur le jeu de données des montagnes du Lomont pour illustrer la méthode de CAH.
Table des matières
TOC \o "1-3" 1 INTRODUCTION A LA CAH PAGEREF _Toc476749269 \h 3
1.1 Dans quelles situations a t-on recours à la CAH ? PAGEREF _Toc476749270 \h 3
1.2 Principes de la CAH PAGEREF _Toc476749271 \h 3
1.2.1 Le problème de la classification : explosion combinatoire PAGEREF _Toc476749272 \h 3
1.2.2 Classification dans un espace métrique : choix dune distance et dun critère PAGEREF _Toc476749273 \h 4
1.2.3 Méthode de classification : algorithme de la CAH PAGEREF _Toc476749274 \h 5
1.3 Exemple élémentaire sur deux variables issues dune AFC (axes F1 et F2) PAGEREF _Toc476749275 \h 6
2 JEU DE DONNEES PAGEREF _Toc476749276 \h 8
2.1 Récupération des coordonnées factorielles des axes de lAFC phytoécologique PAGEREF _Toc476749277 \h 8
2.2 Préparation des données sous R PAGEREF _Toc476749278 \h 8
3 CAH DUN TABLEAU FLORISTIQUE ET INTERPRETATIONS DES GROUPES PAGEREF _Toc476749279 \h 9
3.1 Réalisation de la CAH PAGEREF _Toc476749280 \h 9
3.1.1 Classification des espèces PAGEREF _Toc476749281 \h 9
3.1.2 Classification des relevés PAGEREF _Toc476749282 \h 9
3.1.3 Intégration des groupes dans le tableau floristique PAGEREF _Toc476749283 \h 9
INTRODUCTION A LA CAH
Lobjectif de la CAH est de classer des individus ayant un comportement similaire suivant un ensemble de variables (variables mesurées directement sur le terrain, variables calculées, ou bien des variables synthétiques issues daxes factoriels par exemples).
Dans quelles situations a t-on recours à la CAH ?
Lorsque lon cherche à faire des groupes homogènes. Cette situation se rencontre souvent en écologie dans la conception des typologies : typologies doccupations du sol ; typologies de peuplements forestiers ; typologies de stations ; etc.
Exemples :
Classer 93 départements à partir de 11 variables décrivant loccupation du sol ;
Classer 43 placettes forestières de Pin de Salzmann à partir de 5 variables de peuplements ;
Classer 85 espèces décrites par 2 axes factoriels issus dune AFC.
Cest une méthode qui vient souvent en complément dune ACP ou dune AFC.
Question : Comment faire k groupes ?
Principes de la CAH
Pour lessentiel, les techniques de classification font appel à une démarche algorithmique et non à des techniques mathématiques complexes : les résultats sont obtenus au terme dune série dopérations simples et répétitives.
Regrouper les individus les plus proches nécessite plusieurs conditions préalables afin deffectuer une mesure de proximité entre chaque paires dindividus :
Besoin dune distance ;
Besoin dun critère de comparaison pour le regroupement des individus ;
Besoin dune méthode de classement, dun algorithme prédéfini.
Le problème de la classification : explosion combinatoire
Classification : Faire k groupes « optimaux » dans un ensemble E à n éléments. Les différentes possibilités de constituer k groupes dans un ensemble de n individus sont des combinaisons appelées partitions de lensemble E.
Définition dune partition : tout éléments de E ne peut appartenir quà un seul groupe à la fois et chaque éléments appartient obligatoirement à un groupe, de sorte que la somme des éléments contenus dans les différents groupes dune partition est égale à la totalité des éléments de E.
Soit un ensemble E de 10 individus dont on veut extraire 4 groupes. Le nombre total de combinaisons possibles de diviser E en 4 groupes différents peut être approché par la formule suivante :
EMBED Equation.3 partitions possible de 10 individus en 4 groupes.
Si lon na pas une idée a priori du nombre de groupes que lon aimerait faire dans cet ensemble de 10 individus, le nombre totale de partitions possible correspond à la somme des partitions pour chaque valeur de k allant de 1 à 10, soit :
EMBED Equation.3 partitions possible de 10 individus.
Très rapidement lon atteint des chiffres astronomiques, on parle dexplosion combinatoire. Par exemple pour classer 85 espèces en 6 groupes, on compte 2.1063 possibilités. Il est impossible, même pour un ordinateur très puissant dexaminer lensemble des partitions possibles, de les comparer une à une, et den sélectionner la plus optimale suivant des critères prédéfinis.
Lexamen complet des possibilités étant impossible, il est nécessaire de passer par des méthodes sub-optimales de classification. La CAH est une méthode de classification parmi dautres et ne constitue donc pas la seule manière de classer des individus dans des groupes. Néanmoins il sagit dune méthode simple qui permet à partir dun algorithme simplifié, détudier des distances entre individus et groupes.
Comment mesurer la « distance » entre 2 groupes ?
Classification dans un espace métrique : choix dune distance et dun critère
Une distance : Pour regrouper les individus les plus proches, il faut pouvoir connaître la distance qui sépare les différents individus entre eux, doù la nécessité de choisir une distance. Par exemple en phytoécologie, on travaille avec une distance euclidienne sur les axes factoriels.
Un critère de choix : De manière intuitive, la meilleure façon de faire des groupes dindividus homogènes entre eux et bien différents dun groupe à lautre, cest de faire des paquets dindividus en fonction des distances qui les séparent. Cest à dire minimiser les distances qui séparent les différents individus à lintérieur dun paquet tout en maximisant les distances qui séparent les individus appartenant à des paquets différents :
Inertie totale :
EMBED Equation.3
Inertie intra-groupe :
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
EMBED Equation.3
Inertie inter-groupe :
EMBED Equation.3
Propriété : Itot = Iintra + Iinter
On utilise le critère dinertie comme une mesure de la dispersion des individus autour du centre de gravité G de lensemble E (inertie totale) ou bien autour du centre de gravité du groupe auquel ils appartiennent (inertie intra-groupe). Plus linertie est faible, plus les individus sont ramassés autour du centre de gravité considéré. Linertie totale de E est constante étant donné que les éléments constituant E ne bougent pas, tandis que linertie intra-groupe est variable au sein de chaque groupe à k fixé, suivant les partitions considérées de n éléments parmi k groupes. Le but sera donc de comparer ces différentes inerties intra-groupe pour chaque partition possible et de conserver la partition qui minimise linertie intra-groupe dans le maximum de groupes, ce qui équivaut à trouver la configuration des k groupes dans E qui maximise linertie inter-groupe (différence entre linertie totale et la somme, sur les groupes, des inerties intra-groupes).
Par conséquent, la CAH utilise les distances euclidiennnes et le critère de Ward, qui minimise linertie intra-groupe pour constituer des groupes dindividus homogènes entre eux.
Méthode de classification : algorithme de la CAH
Lalgorithme de la CAH est simple, il consiste à partir de la situation initiale où chaque individu de E constitue un groupe à lui tout seul, soit un total de n groupes. Par conséquent les conditions initiales en termes dinertie sont les suivantes :
Iintra = 0
Iinter = Itot
Etape 1, n groupes : Lalgorithme recherche les 2 individus les plus proches en terme de distance euclidienne pour former un premier couple, ce qui provoque une augmentation de linertie intra-groupe (augmentation la plus faible parmi lensemble des augmentations possible étant donné que lalgorithme à sélectionné les 2 individus les plus proches). Lalgorithme remplace les 2 individus par le couple placé au barycentre des 2 individus qui le compose, le nombre dindividus diminue (n-1).
Etape 2, (n-1) groupes : Lalgorithme recalcule les distances entre tous les individus (n-1). A nouveau, lalgorithme regroupe les 2 individus les plus proches en formant un nouveau couple ce qui provoque une nouvelle augmentation de linertie intra-groupe couplée dune diminution du nombre dindividus (n-2).
Etape 3, (n-2) groupes : Réitération de la procédure
Etape n, 1 groupe : Cest la dernière étape de lalgorithme, cette fois linertie totale est contenue dans linertie intra-groupe, il nexiste plus dinertie inter-groupe.
Lalgorithme procède de manière ascendante jusquà nobtenir quun seul groupe.
Finalement, la CAH produit une hiérarchie des individus (espèces ou relevés en phytoécologie) où ceux-ci sont progressivement agrégés en groupes de plus en plus gros :
à la base du dendrogramme (arbre des groupes), chaque individu forme à lui seul un groupe ;
au sommet, tous les individus appartiennent au même groupe.
Le passage dun niveau de la hiérarchie au suivant consiste à fusionner les deux groupes qui se ressemblent le plus, lidée générale est de minimiser la variabilité (inertie) intra-groupe et de maximiser la variabilité (inertie) inter-groupe.
Exemple élémentaire sur deux variables issues dune AFC (axes F1 et F2)
Soit 5 individus distribués dans un espace à plusieurs dimensions, et dont la projection sur le plan factoriel (F1 : F2) dune AFC est la suivante :
Etape 1 : 5 individus, 5 classes
On construit la matrice des distances entre les 5 individus et on regroupe les 2 individus les plus proches :
Etape 2 : 5 individus, 4 classes
En utilisant un critère dagrégation, tel que le critère de Ward qui cherche à minimiser linertie intra-groupe (ce qui revient à maximiser linertie inter-groupe, puisque linertie totale est constante et égale à la somme des inerties intra et inter-groupes), on mesurer la distance entre une classe et un élément individuel. On assimile les individus 1 et 2 comme une classe et lon compare les distances entre cette classe et les 3 individus restants (3, 4 et 5), et à nouveau, on regroupe les 2 individus les plus proches :
Etape 3 : 5 individus, 3 classes
On réitère la même procédure que précédemment, suivant le même critère dagrégation de Ward et la distance dite euclidienne :
Etape 4 : 5 individus, 2 classes
Etape finale : choix du nombre de groupes
JEU DE DONNEES
Récupération des coordonnées factorielles des axes de lAFC phytoécologique
Pour ce TD sur la CAH, nous utiliserons les données récoltés par la 16ème promotion de la FIF au cours du projet phytoécologie 2006. Veuillez télécharger le fichier « lomont.xlsx » ici : HYPERLINK "https://jonathanlenoir.wordpress.com/datasets/" https://jonathanlenoir.wordpress.com/datasets/. Le but de cet exercice phytoécologique réalisé en 2006 était la réalisation dune typologie de stations forestières pour aider les gestionnaires forestiers à établir un diagnostic rapide des conditions écologiques existant sur une parcelle forestière dans la région du Lomont. Un tel diagnostic permet dadapter la gestion aux conditions écologiques en conciliant production de bois de qualité et respect de lenvironnement dans le contexte actuel de production durable.
La classification sera réalisée à partir des coordonnées factorielles des deux premiers axes de lAFC réalisée sur le tableau floristique du jeu de données précédent (cf. TD AFC aussi disponible sur le même site Internet : HYPERLINK "https://jonathanlenoir.wordpress.com/exercices/" https://jonathanlenoir.wordpress.com/exercices/). Pour récupérer les coordonnées factorielles nécessaires à la réalisation des groupes despèces et de relevés sous le logiciel R, il est préférable de relancez rapidement lAFC sur la feuille « flo » du classeur lomont.xlsx, avec les fonctions et lignes de commandes R vues en TD lors de la réalisation de lAFC.
Préparation des données sous R
Pour récupérer les coordonnées factorielles à partir de lAFC du tableau floristique « flo » (cf. jeu de données lomont.xlsx), la préparation des données de coordonnées factorielles pour le traitement sous CAH nécessite quelques manipulations sous R.
( Dans un premier temps, il faut extraire les éléments co (coordonnées factorielles des espèces) et li (coordonnées factorielles des relevés) contenus dans lobjet résultat de lAFC (cf. le nom que vous avez donné à votre résultat dAFC, ex : monafc).
> cfco cfli cfco$noms cfli$noms esp.dist esp.cah plot(esp.cah)# Visualisation du dendrogramme des espèces
( Combien de groupes désirez-vous faire ?
> rect.hclust(esp.cah, k=8)# Découpage du dendrogramme en 8 groupes despèces
> esp.grp rel.dist rel.cah plot(rel.cah)# Visualisation du dendrogramme des espèces (cas du relevé « 109 » ?)
( Que pensez-vous du relevé n°109 ? Faut-il relancer lAFC et la CAH en excluant ce relevé atypique ?
( Combien de groupes désirez-vous faire ?
> rect.hclust(rel.cah, k=8)# Découpage du dendrogramme en 8 groupes de relevés
> rel.grp flo$grp flo
