Classification Ascendante Hierarchique (CAH) - Jonathan Lenoir

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 d'un ensemble d'individus (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 d'espèces ou de relevés
(exercice de typologie des stations). On pourra utiliser les résultats
obtenu par l'AFC sur le jeu de données des montagnes du Lomont pour
illustrer la méthode de CAH. Table des matières
1 INTRODUCTION A LA CAH 3 1.1 Dans quelles situations a t-on recours à la CAH ? 3
1.2 Principes de la CAH 3
1.2.1 Le problème de la classification : explosion combinatoire 3
1.2.2 Classification dans un espace métrique : choix d'une distance et
d'un critère 4
1.2.3 Méthode de classification : algorithme de la CAH 5
1.3 Exemple élémentaire sur deux variables issues d'une AFC (axes F1 et
F2) 6 2 JEU DE DONNEES 8 2.1 Récupération des coordonnées factorielles des axes de l'AFC
phytoécologique 8
2.2 Préparation des données sous R 8 3 CAH D'UN TABLEAU FLORISTIQUE ET INTERPRETATIONS DES GROUPES 9 3.1 Réalisation de la CAH 9
3.1.1 Classification des espèces 9
3.1.2 Classification des relevés 9
3.1.3 Intégration des groupes dans le tableau floristique 9 INTRODUCTION A LA CAH L'objectif 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 d'axes factoriels par exemples). 1 Dans quelles situations a t-on recours à la CAH ? Lorsque l'on cherche à faire des groupes homogènes. Cette situation se
rencontre souvent en écologie dans la conception des typologies :
typologies d'occupations du sol ; typologies de peuplements forestiers ;
typologies de stations ; etc. Exemples :
- Classer 93 départements à partir de 11 variables décrivant l'occupation
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 d'une AFC.
C'est une méthode qui vient souvent en complément d'une ACP ou d'une
AFC.
Question : Comment faire k groupes ?
2 Principes de la CAH Pour l'essentiel, les techniques de classification font appel à une
démarche algorithmique et non à des techniques mathématiques complexes :
les résultats sont obtenus au terme d'une série d'opérations simples et
répétitives. Regrouper les individus les plus proches nécessite plusieurs conditions
préalables afin d'effectuer une mesure de proximité entre chaque paires
d'individus :
- Besoin d'une distance ;
- Besoin d'un critère de comparaison pour le regroupement des individus ;
- Besoin d'une méthode de classement, d'un algorithme prédéfini.
1 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
l'ensemble E.
Définition d'une 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 d'une 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 :
[pic] partitions possible de 10 individus en 4 groupes.
Si l'on n'a pas une idée a priori du nombre de groupes que l'on
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 :
[pic] partitions possible de 10 individus.
Très rapidement l'on atteint des chiffres astronomiques, on parle
d'explosion 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 d'examiner l'ensemble des partitions possibles, de les
comparer une à une, et d'en sélectionner la plus optimale suivant des
critères prédéfinis.
L'examen 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 d'autres et ne constitue donc pas la seule
manière de classer des individus dans des groupes. Néanmoins il s'agit
d'une méthode simple qui permet à partir d'un algorithme simplifié,
d'étudier des distances entre individus et groupes.
Comment mesurer la « distance » entre 2 groupes ?
2 Classification dans un espace métrique : choix d'une distance et d'un
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, d'où 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 d'individus homogènes entre eux et bien différents d'un groupe
à l'autre, c'est de faire des paquets d'individus en fonction des distances
qui les séparent. C'est à dire minimiser les distances qui séparent les
différents individus à l'intérieur d'un paquet tout en maximisant les
distances qui séparent les individus appartenant à des paquets différents :
Inertie totale :
[pic]
Inertie intra-groupe :
[pic]
[pic]
[pic]
[pic]
Inertie inter-groupe :
[pic]
Propriété : Itot = Iintra + Iinter
On utilise le critère d'inertie comme une mesure de la dispersion des
individus autour du centre de gravité G de l'ensemble E (inertie totale) ou
bien autour du centre de gravité du groupe auquel ils appartiennent
(inertie intra-groupe). Plus l'inertie est faible, plus les individus sont
ramassés autour du centre de gravité considéré. L'inertie totale de E est
constante étant donné que les éléments constituant E ne bougent pas, tandis
que l'inertie 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 l'inertie
intra-groupe dans le maximum de groupes, ce qui équivaut à trouver la
configuration des k groupes dans E qui maximise l'inertie inter-groupe
(différence entre l'inertie 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 l'inertie intra-groupe pour constituer des
groupes d'individus homogènes entre eux.
3 Méthode de classification : algorithme de la CAH
L'algorithme 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
d'inertie sont les suivantes :
Iintra = 0
Iinter = Itot
Etape 1, n groupes : L'algorithme recherche les 2 individus les plus
proches en terme de distance euclidienne pour former un premier couple, ce
qui provoque une augmentation de l'inertie intra-groupe (augmentation la
plus faible parmi l'ensemble des augmentations possible étant donné que
l'algorithme à sélectionné les 2 individus les plus proches). L'algorithme
remplace les 2 individus par le couple placé au barycentre des 2 individus
qui le compose, le nombre d'individus diminue (n-1).
Etape 2, (n-1) groupes : L'algorithme recalcule les distances entre
tous les individus (n-1). A nouveau, l'algorithme regroupe les 2 individus
les plus proches en formant un nouveau couple ce qui provoque une nouvelle
augmentation de l'inertie intra-groupe couplée d'une diminution du nombre
d'individus (n-2).
Etape 3, (n-2) groupes : Réitération de la procédure...
Etape n, 1 groupe : C'est la dernière étape de l'algorithme, cette fois
l'inertie totale est contenue dans l'inertie intra-groupe, il n'existe plus
d'inertie inter-groupe.
L'algorithme procède de manière ascendante jusqu'à n'obtenir qu'un 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 d'un niveau de la hiérarchie au suivant consiste à fusionner
les deux groupes qui se ressemblent le plus, l'idée générale est de
minimiser la variabilité (inertie) intra-groupe et de maximiser la
variabilité (inertie) inte