Comprendre Classification hiérarchique
La classification agglomérative part de chaque observation comme classe d'un seul élément et fusionne à répétition les deux classes les moins dissemblables jusqu'à ce qu'il n'en reste qu'une. La dissemblance à laquelle chaque fusion se produit est enregistrée comme sa hauteur, et le registre de ces fusions est le dendrogramme.
Couper le dendrogramme horizontalement produit un regroupement, et le nombre de traits verticaux traversés par la coupe est le nombre de classes. Un seul arbre contient donc une réponse pour chaque k à la fois, ce qui est le principal avantage pratique sur les K-moyennes. Les regroupements ainsi obtenus sont emboîtés, chaque coupe raffinant celle du dessus.
Cet emboîtement est une hypothèse et non un cadeau. La méthode impose que les classes d'un niveau soient contenues dans celles du niveau supérieur : si le vrai regroupement n'est pas emboîté - si la meilleure division selon un attribut coupe en travers de la meilleure division selon un autre - aucune coupe ne le retrouvera, et une hiérarchie sera imposée à des données qui n'en ont pas.
Fusionner exige une dissemblance entre groupes et non entre points, et il n'existe pas une seule bonne façon d'étendre l'une à l'autre. Le saut maximum prend la plus grande distance entre un point d'un groupe et un point de l'autre, le saut minimum la plus petite, le saut moyen la moyenne, et le saut centroïde la distance entre les deux centroïdes. Ce choix change la réponse, et pas seulement sa présentation.
Comment calculer
complete: max d(a, b) single: min d(a, b) average: mean d(a, b), a ∈ A, b ∈ B
où
- A, B
- les deux classes dont on mesure la dissemblance
- d(a, b)
- la dissemblance entre une observation de A et une de B
- height
- la valeur de cette dissemblance de groupe au moment où les deux classes fusionnent
Exemple : Classification hiérarchique
Prenez dix points du plan : un groupe compact de trois à gauche, un groupe compact de trois à droite, et quatre points régulièrement espacés faisant le pont. Coupez chaque dendrogramme en deux classes et les sauts divergent. Les sauts maximum et moyen partagent les données 5 et 5, au milieu du pont. Le saut minimum donne 3 et 7.
La raison tient à la définition et non à un détail d'implémentation. Le saut minimum fusionne sur la plus petite distance : chaque point du pont s'accroche un à un à l'amas grandissant, et la chaîne entraîne un groupe entier avec elle - une classe traînante. Les sauts maximum et moyen considèrent la plus grande distance et la moyenne, et refusent donc de fusionner des groupes globalement éloignés.
James et ses coauteurs rapportent cela comme le comportement général : le saut minimum tend à produire des classes traînantes, tandis que les sauts maximum et moyen donnent des dendrogrammes plus équilibrés. Le saut centroïde a un défaut propre, l'inversion, où deux classes fusionnent à une hauteur inférieure à celle de l'une d'elles, rendant l'arbre difficile à lire.
Avantages et inconvénients
Avantages
- Aucun engagement sur le nombre de classes avant l'ajustement.
- Le dendrogramme est un résumé interprétable de la structure à toutes les échelles à la fois.
- Déterministe : contrairement aux K-moyennes, aucune initialisation aléatoire à redémarrer.
- Fonctionne à partir d'une seule matrice de dissemblance, donc partout où une distance sensée existe.
Inconvénients
- Impose une hiérarchie emboîtée, que les données en aient une ou non.
- Le saut et la dissemblance changent le résultat, et aucun ne peut être choisi à partir des données.
- Une fusion n'est jamais reconsidérée : une erreur précoce se propage à tout l'arbre.
- Le coût croît vite avec le nombre d'observations, ce qui limite la méthode sur de grands jeux de données.
Questions fréquentes
Comment lire correctement un dendrogramme ?
Uniquement par la hauteur de fusion. Deux observations qui fusionnent bas sont semblables ; deux qui fusionnent près du sommet ne le sont pas. La position horizontale ne porte aucune information : les feuilles peuvent être réordonnées librement sans changer l'arbre, et des observations côte à côte peuvent ne se rejoindre qu'au tout dernier moment.
Quel saut employer ?
Le saut maximum ou moyen par défaut, car ils donnent des dendrogrammes équilibrés. Le saut minimum est à éviter sauf si l'enchaînement est précisément ce que vous cherchez à détecter, et le saut centroïde peut produire des inversions qui rendent l'arbre illisible.
Comment choisir le nombre de classes ?
En décidant où couper, ce qui est un jugement et non un calcul. Il n'y a pas d'erreur hors échantillon pour valider, et la pratique honnête consiste à essayer plusieurs jeux de choix raisonnables et à rapporter la structure qui apparaît sous la plupart d'entre eux.
En résumé
La classification hiérarchique supprime la nécessité de fixer k à l'avance et la remplace par le saut, la mesure de dissemblance et la hauteur de coupe - qu'aucune donnée ne peut choisir à votre place. Lisez la similarité aux seules hauteurs de fusion, préférez le saut maximum ou moyen, et traitez l'arbre comme une hypothèse sur la structure plutôt que comme un résultat.