Classification Ascendante Hiérarchique

Ecran :

Description :
Ce module permet d'obtenir une classification automatique d'entités géographiques en fonction de plusieurs données statistiques.
Les entités du fond de carte sont appelées les individus, et les données en entrées sont appelées les variables.
La Classification Ascendante Hiérarchique consiste à effectuer un regroupement progressif des individus selon leur degré de ressemblance jusqu'à l'obtention d'une unique classe les regroupant tous.
Une fois ce calcul effectué, les individus seront répartis en différentes classes, le nombre de classes étant défini par l'utilisateur.

Ce module peut prendre un module d'A.C.P. en entrée : les données seront alors les coordonnées des individus sur les m premiers axes (m étant le nombre d'axes, variant entre 1 et le nombre d'entrées du module d'A.C.P.).

Calculs :

• Etape 1 :
  On considère les n individus caractérisés par leurs valeurs par rapport aux p variables, et on détermine quels sont les 2 individus qui se ressemblent le plus par rapport à cet ensemble de variables. Ces 2 individus sont regroupés pour former une classe.
• Etape 2 :
  On dispose à ce niveau de (n-1) classes, une étant formée des 2 individus regroupés précédemment, les autres ne contenant qu'un unique individu. On détermine alors quelles sont les 2 classes qui se ressemblent le plus, et on les regroupe.
• Etapes suivantes :
  On répète la même opération jusqu'à obtenir une unique classe regroupant l'ensemble des individus.

Cette procédure impose 2 choix :

1. Déterminer un critère de ressemblance entre les individus. La distance euclidienne sera utilisée.
2. Déterminer une distance entre classes. Ce procédé s'appelle un critère d'agrégation, nous vous en proposons plusieurs.

Les critères d'agrégation :

• plus proche voisin
  la distance entre 2 classes c1 et c2 est définie par la plus courte distance séparant un individu de c1 et un individu de c2 :
     
• diamètre maximum
  la distance entre 2 classes c1 et c2 est définie par la plus grande distance séparant un individu de c1 et un individu de c2 :
     
• distance moyenne
  ce critère consiste à calculer la distance moyenne entre tous les éléments de c1 et tous les éléments de c2:
     
          où ni = nombre d'éléments de la classe ci
• centres de gravité
  la distance entre 2 classes c1 et c2 est définie par la distance entre leurs centres de gravité :
     
          où Gi = centre de gravité de la classe ci
• moment centré d'ordre 2
  ce critère consiste à rechercher une partition telle que la variance interne des classes est minimum alors que la variance entre les classes est maximum :
     
          où désigne l'inertie de la partition où c1 et c2 sont séparés
                désigne l'inertie de la partition où c1 et c2 sont ensemble
               Gi = centre de gravité de la classe ci
  soit :
     
          où Gi = centre de gravité de la classe ci
               G = centre de gravité du nuage
               mi = masse relative de la classe ci =

La difficulté du choix du critère d'agrégation réside dans le fait que ces critères peuvent déboucher sur des résultats différents.
Le critère le plus couramment utilisé est celui du moment centré d'ordre 2, appliqué à une matrice centrée-réduite.

Exemple numérique :
Matrice de départ :

Tableau des distances entre individus :

Les individus C et E apparaissent clairement comme les plus semblables avec une distance carrée de 2 (valeur minimum du tableau).
Ils sont donc regroupés dans une classe, et la première phase de classification, indépendante du critère d'agrégation choisi, est achevée.

Exemple de C.A.H. avec le critère du diamètre maximum :

Tableau des distances entre classes :

Un problème se pose pour savoir quelles classes sont les plus proches : {A} et {B}, ou {A} et {C,E}. Aucun critère autre que l'arbitraire ne permet de choisir quel regroupement faire. On choisira la première distance qui a été calculée : regroupement de {A} et {B}.

Tableau des distances entre classes :

Un problème se pose ici aussi pour savoir quelles classes sont les plus proches : {C,E}et {D}, ou {A,B}et {C,E}. On choisira par exemple le regroupement de {C,E}et {D}.

Restent donc 2 classes :
{A,B} et {C,D,E}

Voici l'arbre hiérarchique obtenu :

Si on effectue une division en 2 classes, on obtient : {A,B} et {C,D,E}.
Si on effectue une division en 3 classes, on obtient : {A,B}, {C,E} et {D}.

Avec le critère du plus proche voisin, on obtient l'arbre suivant :

Si on effectue une division en 2 classes, on obtient : {A,C,D,E} et {B}.
Si on effectue une division en 3 classes, on obtient : {A,C,E}, {B} et {D}.

Les résultats sont donc différents selon le critère d'agrégation choisi.

Eléments de vocabulaire :
Un vocabulaire assez précis est utilisé dans le cadre de la classification ascendante hiérarchique. Nous vous le présentons en utilisant l'exemple numérique précédant.
Les individus A, B, C, D et E forment des classes à un seul élément, appelées classes terminales.
Le regroupement de 2 classes forme un nœud.
Le premier de ces nœuds a pour numéro le nombre total de classes terminales +1 ( = n+1). Ici, ce numéro est 6.
Chaque regroupement donne lieu à un nouveau nœud dont le numéro suit exactement celui du regroupement précédent.
Le dernier nœud aura donc pour numéro : 2 x n -1. Ici, ce numéro est donc 2 x 5 - 1 = 9.
Chaque nœud est ainsi formé de 2 classes que l'on appelle ses successeurs, l'un étant appelé l'aîné et l'autre le benjamin (de façon arbitraire).

Par extension, on désignera également les individus par un numéro de nœud compris entre 1 et n. Si vous voulez connaître précisément le numéro de nœud qui correspond à un individu particulier, il vous faut cliquer sur le bouton Sauvegarder les résultats et lire, dans le fichier texte créé, le paragraphe intitulé "Les classes de la hiérarchie".

Avec le critère du plus proche voisin, on obtient donc l'arbre suivant :

             qui équivaut à           

Le nœud 8 a donc pour successeurs les classes {D} et 7. De façon arbitraire, {D} est désigné comme l'aîné et 7 comme le benjamin.

Les indices de niveau permettent de mesurer et de représenter l'importance de la différence entre 2 classes que l'on regroupe. Ils sont définis par la distance entre les 2 classes formant le nœud.
Ainsi, le nœud 6 a pour indice de niveau racine de 2 (distance entre les éléments C et E, voir plus haut).
Ces indices sont très utiles dans l'étude de l'arbre hiérarchique.

Interprétation :
Le graphique représente l'arbre hiérarchique obtenu après classification, ainsi que l'histogramme des indices de niveau. Il dépend du nombre de nœuds dessinés, qui varie de 3 à 21. Si vous modifiez ce nombre, le graphique changera en conséquence.

En changeant la taille de la fenêtre, le dessin s'adaptera automatiquement à la nouvelle taille.

Choix du nombre de classes :
L'utilisateur doit choisir le nombre de classes qu'il désire. Ce nombre varie entre 1 et le nombre d'entités du fond de carte.
Un choix en fonction de l'indice de niveau est judicieux. Il est déterminé par la lecture de l'histogramme des indices de niveau : l'utilisateur doit remarquer des sauts extrêmement importants dans les valeurs de l'indice de niveau. Si ces sauts concernent les k derniers nœuds de l'arbre, alors un découpage en (k+1) classes sera pertinent.
Par exemple, sur la copie d'écran située en tête de ce document, on voit que l'indice de niveau subit des sauts importants pour les cinq derniers nœuds de l'arbre. L'histogramme est ensuite plus régulier. Une division en 6 classes paraît alors pertinente.

Afin de faciliter la lecture de l'histogramme et le repérage des sauts importants de l'indice de niveau, nous vous conseillons d'augmenter au maximum le nombre de nœuds à dessiner.
Si vous voulez connaître précisément la valeur d'un indice de niveau, il vous suffit de passer la souris sur l'histogramme correspondant, et la valeur de l'indice s'affichera dans la zone de texte située en-dessous du graphique.

Construction des classes :
Pour construire une partition en 4 classes, on découpe la hiérarchie en partant du nœud final. Les successeurs de ce nœud sont les classes i et j. A ce niveau, on a donc une partition en 2 classes. On subdivise ensuite le nœud le plus élevé de la hiérarchie (i par exemple). Celui-ci est formé de 2 classes k et l, et on a à ce niveau 3 classes : j, k et l. Le nœud le plus élevé est encore subdivisé en 2 classes pour obtenir la partition à 4 classes souhaitée.

Résultats :
En cliquant sur le bouton Sauvegarder les résultats, vous allez créer un fichier texte tabulé dans lequel seront inscrits tous les résultats de la C.A.H.

Dans ce fichier, vous allez trouver :

• Vos choix relatifs aux paramètres du module qui influent sur la classification :
  - le critère d'agrégation sélectionné.
  - si la case Centrer et réduire la matrice a été cochée, ce choix sera également inscrit.
  - le nombre de classes choisi.
• La liste des individus invalides, s'il en existe.
  Un individu est considéré comme invalide si au moins une des données en entrée ne possède pas de valeur associée à l'individu.
• L'inertie totale du nuage.
• Les classes de la hiérarchie :
  Ce tableau permet d'analyser en détail les ressemblances entre individus. Il permet aussi d'établir le contenu des classes correspondant à la partition choisie.
  Il s'agit d'un tableau dont chaque ligne correspond à un nœud de la hiérarchie. Par lignes, on a les colonnes suivantes :
  - numéro de la classe (si le noeud correspond à une classe)
  - numéro du nœud
  - aîné du nœud
  - benjamin du nœud
  - nombre d'éléments contenus dans le nœud
  - identifiants des individus formant le nœud
• Les paramètres de la hiérarchie :
  Il s'agit d'un tableau dont chaque ligne correspond à un nœud de la hiérarchie. Par lignes, on a les colonnes suivantes :
  - numéro du nœud
  - indice de niveau du nœud
  - taux d'inertie du nœud (ex : s'il vaut 230, cela signifie que le nœud représente 23 % de l'inertie totale)
  - cumul des taux d'inertie (ex : s'il vaut 548 pour le k^ième dernier nœud de l'arbre, cela signifie que 54.8 % des différences entre individus s'expriment à travers cette partition en (k+1) classes)
• Les aides à l'interprétation :
  Ce tableau donne quelques paramètres généraux sur chacun des nœuds. Il permet d'établir directement les caractéristiques de chaque classe de la partition.
  Il s'agit d'un tableau dont chaque ligne correspond à un nœud de la hiérarchie. Par lignes, on a les colonnes suivantes :
  - numéro de la classe (si le noeud correspond à une classe)
  - numéro du nœud
  - masse relative du nœud
  - contribution du nœud à la dispersion du nuage
  - écart brut qui sépare le nœud de la moyenne générale
  - dans les colonnes suivantes : écart du nœud par rapport à la moyenne de chaque variable. Les plus fortes valeurs, en valeur absolue, de ces colonnes indiquent quelles variables caractérisent le mieux le nœud (ex : pour une classe donnée, si la variable V1 a pour valeur 1500, V2 2700, V3 100, V4 200, V5 -1200, alors les caractères contribuant le plus à différencier cette classe de l'ensemble des autres individus sont dans l'ordre : l'importance des caractères V2 puis V1, et la relative faiblesse du caractère V5, les autres variables contribuant de façon insignifiante à la spécificité de cette classe).

Formules utilisées :
Inertie totale du nuage :
   
        où G = centre de gravité du nuage
             mi = masse relative de l'individu i =

Taux d'inertie du nœud J :
   
        où I(J) = indice de niveau du nœud J

Masse relative de la classe c :
   

Contribution de la classe c à la dispersion du nuage :
   
        où mc = masse relative de la classe c =

Ecart brut qui sépare la classe c de la moyenne générale :
   

Remarque :
Toutes les valeurs données dans les paragraphes "Les paramètres de la hiérarchie" et "Les aides à l'interprétation" sont multipliées par 1000, à l'exception de RHO2 qui est multipliée par 100.
Cette méthode a été adoptée par la plupart des logiciels d'analyse de données, et a pour but de simplifier la présentation des résultats.

Graphiques :
Sous le graphique, vous trouverez un bouton : permettant de créer une nouvelle "fenêtre graphique" à partir du dessin courant. Cette fenêtre vous permettra de comparer plusieurs graphiques, de les exporter ou de les imprimer.

Pour plus de détails, vous pouvez vous reporter au livre suivant :
L'analyse statistique des données en géographie. Lena Sanders. Collection Alidade. Groupement d'Intérêt Public Reclus. Montpellier. 1989.

Script :

2      module untyped_list ""
3        mod_type integer "103"
3        mod_subtype integer "527"
3        mod_name string "CAH"
3        mod_dads integer_list ""
4          ? integer "5"
4          ? integer "8"
4          ? integer "9"
4          ? integer "4"
4          ? integer "6"
4          ? integer "7"
3        class_nb integer "6"
3        cah_type integer "705"
3        center_matrix boolean "T"
3        draw_nb integer "17"
3        ind_nb integer "20"
3        var_nb integer "6"
3        acp_dad boolean "F"
3        axis_nb integer "1"

Valeurs pour cah_type :
plus proche voisin         701
diamètre maximum           702
distance moyenne           703
centres de gravité         704
moment centré d'ordre 2    705