Classification Hiérarchique et Non Hiérarchique

Ce document présente les méthodes de classification hiérarchique et non hiérarchique, destinées aux étudiants et chercheurs souhaitant regrouper des individus en classes homogènes à partir de données numériques. Il détaille les principes, calculs des distances, choix des groupes, ainsi que des exemples de manipulation, notamment avec le logiciel SPSS.

Classification Hiérarchique

La classification hiérarchique consiste à regrouper des individus selon une structure en arbre, appelée dendrogramme. Elle peut être réalisée selon deux approches :

• Méthode descendante : du groupe global vers les individus.
• Méthode ascendante : des individus vers la formation progressive de groupes.

La méthode ascendante est la plus courante et se déroule en plusieurs étapes successives où l'on fusionne les individus ou groupes les plus proches jusqu'à obtenir un seul groupe englobant tous les individus.

Méthode ascendante : étapes

1. Calcul des distances entre individus.
2. Fusion des deux individus ou groupes les plus proches.
3. Recalcul des distances entre groupes fusionnés et les autres groupes.
4. Répétition des étapes 2 et 3 jusqu'à la formation d'un seul groupe.

Calcul des distances entre individus

Pour mesurer la dissimilarité entre deux individus, on utilise principalement :

• La distance euclidienne, définie pour deux individus I1 et I2 aux coordonnées respectives (X1, Y1, Z1) et (X2, Y2, Z2) par :

d(I1, I2) = √[(X1 − X2)² + (Y1 − Y2)² + (Z1 − Z2)²]

• Le carré de la distance euclidienne :

d²(I1, I2) = (X1 − X2)² + (Y1 − Y2)² + (Z1 − Z2)²

Il est important de standardiser ou de centrer et réduire les données pour éviter les biais liés aux unités de mesure différentes des variables.

Calcul des distances entre groupes d’individus

Pour regrouper des groupes d’individus, plusieurs indices d’agrégation sont utilisés :

• Distance du saut minimal : distance minimale entre un individu du groupe G_i et un individu du groupe G_j.
• Distance du diamètre : distance maximale entre un individu du groupe G_i et un individu du groupe G_j.
• Distance moyenne : moyenne arithmétique des distances entre tous les individus des deux groupes.
• Méthode de Ward : minimise la variance intra-groupe en fusionnant les groupes de façon à minimiser l’augmentation de la somme des carrés des distances.

Formellement :

Distance du saut minimal : d(G_i, G_j) = min { d(x_i, y_j) | x_i ∈ G_i, y_j ∈ G_j }

Distance du diamètre : d(G_i, G_j) = max { d(x_i, y_j) | x_i ∈ G_i, y_j ∈ G_j }

Distance moyenne : d(G_i, G_j) = moyenne { d(x_i, y_j) | x_i ∈ G_i, y_j ∈ G_j }

Méthode de Ward : d_w(G_i, G_j) = ((n_i * n_j) / (n_i + n_j)) * ||m_i - m_j||²

où n_i et n_j sont les tailles des groupes, et m_i, m_j leurs centres respectifs.

Choix du nombre de groupes

La classification hiérarchique ne nécessite pas de fixer a priori le nombre de classes. Le choix se fait en examinant le dendrogramme :

• On considère des critères théoriques, conceptuels et pratiques.
• Les tailles relatives des groupes doivent être cohérentes.
• On effectue une coupe au niveau du saut d’agrégation le plus important dans le dendrogramme.

Interprétation des groupes

Pour analyser les groupes formés, on examine les centres des groupes pour chaque variable utilisée. Une analyse plus approfondie peut être réalisée via une analyse discriminante pour identifier les variables qui différencient significativement les groupes.

Limites de la classification hiérarchique

• Le nombre d’individus doit être au moins deux fois supérieur au nombre de variables.
• Cette méthode n’est pas adaptée pour un très grand nombre d’individus en raison de sa complexité computationnelle.

Classification non hiérarchique (Nuées dynamiques)

La classification non hiérarchique s’applique uniquement aux données numériques multivariées et est particulièrement adaptée lorsque le nombre d’individus est important. Elle consiste à regrouper un nuage de points en classes homogènes en fixant préalablement le nombre de classes K.

Algorithme des k-moyennes (k-means)

1. Choisir au hasard les centres initiaux des K classes.
2. Affecter chaque individu à la classe dont le centre est le plus proche (par exemple selon la distance euclidienne).
3. Déplacer chaque centre de classe vers la moyenne des individus qui lui sont affectés.
4. Répéter les étapes 2 et 3 jusqu’à convergence (plus aucun changement d’affectation).

Exemple simplifié

Supposons que l’on choisisse 3 individus au hasard comme centres initiaux k1, k2, k3. Chaque point est affecté à la classe dont le centre est le plus proche. Ensuite, les centres sont recalculés comme la moyenne des points de chaque classe. Certains points peuvent changer de classe si un autre centre devient plus proche. On répète ce processus jusqu’à stabilisation des classes.

Choix du nombre de classes

Le nombre de classes K doit être fixé avant de lancer l’algorithme. Pour déterminer le nombre optimal :

• Faire varier K et calculer les moyennes par classe.
• Comparer les solutions obtenues et retenir celle qui est la plus pertinente selon les critères d’homogénéité et d’interprétabilité.

Manipulation sur SPSS

Les deux méthodes de classification (hiérarchique et non hiérarchique) peuvent être mises en œuvre dans SPSS. L’utilisateur peut analyser les résultats, notamment les dendrogrammes pour la classification hiérarchique, ou les centres et affectations des classes pour la classification non hiérarchique, afin de décider du nombre de groupes à retenir.

Glossaire des termes clés

• Classification hiérarchique : méthode de regroupement des individus en classes imbriquées, représentée par un dendrogramme.
• Dendrogramme : arbre hiérarchique illustrant les regroupements successifs des individus ou groupes.
• Distance euclidienne : mesure de dissimilarité entre deux individus dans un espace multi-dimensionnel.
• Distance du saut minimal : distance minimale entre deux groupes, utilisée pour fusionner les groupes les plus proches.
• Distance du diamètre : distance maximale entre deux groupes.
• Distance moyenne : moyenne des distances entre tous les individus de deux groupes.
• Méthode de Ward : méthode d’agrégation minimisant la variance intra-groupe.
• Classification non hiérarchique : méthode de regroupement en classes fixes, souvent réalisée par l’algorithme des k-moyennes.
• k-moyennes (k-means) : algorithme de classification non hiérarchique basé sur l’affectation itérative des individus aux centres de classes.
• Standardisation : transformation des données pour leur donner une moyenne nulle et un écart-type unitaire, afin d’éviter les biais liés aux unités.

Points clés à retenir

• La classification hiérarchique regroupe les individus sans fixer a priori le nombre de classes, en construisant un dendrogramme.
• La distance euclidienne est la mesure de dissimilarité la plus utilisée entre individus.
• Différentes méthodes existent pour calculer la distance entre groupes, notamment le saut minimal, le diamètre, la moyenne et la méthode de Ward.
• Le choix du nombre de groupes en classification hiérarchique se fait en fonction du dendrogramme et des critères pratiques.
• La classification non hiérarchique nécessite de fixer le nombre de classes avant le regroupement.
• L’algorithme des k-moyennes est un processus itératif d’affectation et de recalcul des centres de classes.
• La classification hiérarchique est moins adaptée aux très grands jeux de données, contrairement à la classification non hiérarchique.