Analyse des données

Classer automatiquement : CAH et k-moyennes

Regrouper des individus semblables sans savoir à l'avance quels groupes existent, c'est la classification non supervisée. Deux familles dominent : la classification ascendante hiérarchique (CAH), qui fusionne pas à pas jusqu'à former un arbre, et les k-moyennes, qui ajustent k centres jusqu'à stabilité. On les voit travailler, on compare leurs choix, puis on les combine.

L'idée en une phrase

Une bonne classification rassemble dans une même classe des individus proches, et sépare les classes. Le théorème de Huygens donne la mesure : l'inertie totale du nuage se partage en inertie intra-classes (l'étalement à l'intérieur des classes, qu'on veut petite) et inertie inter-classes (l'écart entre les centres, qu'on veut grande). La part inter / totale, notée R², dit quelle fraction de l'étalement la partition « explique ».

La CAH part de n classes d'un seul individu et, à chaque étape, fusionne les deux classes les plus proches ; elle produit un arbre, le dendrogramme, qu'on coupe à la hauteur voulue. Les k-moyennes partent de k centres et alternent deux gestes, affecter chaque point au centre le plus proche puis remplacer chaque centre par la moyenne de ses points, jusqu'à ce que plus rien ne bouge. Cette page complète la page de classification des cathédrales (distance de Gower, test par permutation).

La CAH pas à pas

Douze points (déplaçables). À chaque étape, on cherche les deux classes les plus proches selon le critère choisi, on les fusionne, et l'arbre grandit d'un étage. La hauteur de l'étage est la « distance » de fusion. Après onze fusions, tout est réuni.

Critère d'agrégation

Les classes à l'étape courante (une couleur par classe de plus d'un point). Trait rouge : la fusion qui vient d'avoir lieu.

Le dendrogramme se construit en même temps : chaque fusion est un trait horizontal à sa hauteur (l’échelle verticale s’agrandit au fil des fusions).

Étape—

Fusion—

Hauteur de fusion—

Mise à jour de Lance-Williams contre recalcul direct—

Ward : somme des hauteurs − inertie totale—

À retenir. La CAH ne demande qu'une règle pour mesurer la distance entre deux classes. Après chaque fusion, la formule de Lance et Williams (1967) calcule les nouvelles distances à partir des anciennes, sans revenir aux points ; la page vérifie qu'elle donne le même résultat que le calcul direct. Avec le critère de Ward, chaque hauteur est exactement l'inertie intra perdue lors de la fusion : leur somme redonne l'inertie totale du nuage.

Le critère d'agrégation change tout

Quatre nuages, quatre critères. On coupe chaque arbre au nombre de classes qui a servi à fabriquer les données, puis on compare la partition obtenue à la vraie avec l'indice de Rand ajusté (1 = accord parfait, 0 = pas mieux que le hasard).

Nuage

Les partitions obtenues par chaque critère, coupées au bon nombre de classes. Sous chaque vignette : indice de Rand ajusté (ARI) et corrélation cophénétique.

À retenir. Le saut minimal suit les formes allongées et retrouve les croissants, mais il « fait la chaîne » : le moindre pont de points relie deux groupes, et il isole souvent quelques points en laissant tout le reste ensemble. Le saut maximal et Ward préfèrent des classes compactes et de même taille ; Ward est le plus souvent le meilleur sur des groupes ronds, et c'est le seul qui se rattache à l'inertie. Aucun critère n'est le meilleur partout : le choix dépend de la forme des groupes qu'on s'attend à trouver.

Où couper l'arbre ?

Le dendrogramme contient toutes les partitions emboîtées, de n classes à une seule. Pour choisir, on cherche un grand saut de hauteur : deux classes très différentes qu'on hésite à fusionner. Trois indices aident à décider. Déplacez la coupure.

Nombre de classes4

Écartement des groupes1,60

Dendrogramme de Ward (120 points, 4 vrais groupes). Trait rouge : la coupure. En haut à droite, la hauteur des huit dernières fusions ; la barre numérotée i est la fusion qui ferait passer de i à i − 1 classes (en rouge : celle qu'on refuse en coupant au nombre choisi).

Le nuage colorié selon la coupure choisie.

Trois indices selon le nombre de classes, chacun ramené entre 0 et 1 : R² (vert, croît toujours), Calinski-Harabasz (bleu) et silhouette moyenne (violet). Les maxima des deux derniers sont marqués.

R² = inter / totale—

Calinski-Harabasz—

Silhouette moyenne—

Nombre de classes conseillé (CH / silhouette)—

Intra + inter − totale—

Silhouette d'un point : (b − a)/max(a, b), où a est sa distance moyenne aux points de sa classe et b sa distance moyenne à la classe voisine la plus proche. Proche de 1 : bien classé ; négative : il serait mieux ailleurs. Calinski-Harabasz : (inter/(k − 1)) / (intra/(n − k)), le rapport des variances comme dans une analyse de la variance.

À retenir. R² augmente toujours avec le nombre de classes (avec n classes, il vaut 100 %) : il ne peut pas choisir seul. On cherche plutôt le « coude » ou le grand saut de hauteur, et les indices qui pénalisent le nombre de classes (Calinski-Harabasz, silhouette). Quand les groupes s'interpénètrent (écartement faible), les indices hésitent : c'est le signe honnête qu'il n'y a pas de coupure évidente.

Les k-moyennes : affecter, recentrer, recommencer

Chaque étape fait baisser l'inertie intra, ou la laisse égale : l'affectation au centre le plus proche ne peut que raccourcir les distances, et la moyenne est le point qui minimise la somme des carrés. L'algorithme s'arrête donc forcément. Mais où il s'arrête dépend du départ.

Nombre de classes k6

Fond coloré : la zone attribuée à chaque centre (cellules de Voronoï). Croix : les centres, avec la trace de leurs déplacements.

Inertie intra (par point) à chaque demi-pas : elle ne remonte jamais.

Itération—

Inertie intra—

Plus forte remontée observée—

Écart au meilleur optimum connu—

200 départs au hasard (orange) et 200 départs k-moyennes++ (bleu) : inertie finale obtenue. Plusieurs pics = plusieurs minima locaux.

Hasard : part des départs qui atteignent le meilleur—

k-moyennes++ : part des départs qui atteignent le meilleur—

À retenir. Les k-moyennes convergent toujours, mais vers un minimum local : avec un mauvais départ, deux centres se partagent un groupe pendant qu'un seul centre en couvre deux, et aucun pas ne peut corriger cela. Remède : relancer depuis de nombreux départs et garder le meilleur, ou choisir des départs bien étalés (k-moyennes++ d'Arthur et Vassilvitskii, 2007, qui tire chaque nouveau centre avec une probabilité proportionnelle au carré de sa distance aux centres déjà choisis).

Applications et pièges

Trois usages : réduire les couleurs d'une image, classer de grands fichiers en combinant les deux méthodes, et reconnaître les situations où la classification se trompe.

Chaque pixel est un point de l'espace des couleurs (rouge, vert, bleu). Les k-moyennes cherchent k couleurs représentatives ; on remplace chaque pixel par la couleur de son centre. C'est la « quantification » utilisée par les images GIF et PNG à palette, ou pour l'impression en peu d'encres.

Nombre de couleurs k6

L'image d'origine (paysage de synthèse, 16 000 pixels, plusieurs milliers de couleurs).

L'image avec k couleurs seulement, et sa palette.

Couleurs distinctes à l'origine—

Écart moyen par pixel (sur 255)—

PSNR (rapport signal sur bruit)—

Taille : bits par pixel—

La CAH compare toutes les paires : pour 6 000 individus, 18 millions de distances et des milliers de passages sur la matrice. Les k-moyennes sont rapides mais demandent k. La classification mixte (méthode courante en France depuis Lebart, Morineau et Piron) prend le meilleur des deux : on découpe d'abord le nuage en 50 petites classes par k-moyennes, on fait la CAH de Ward sur ces 50 centres pondérés par leurs effectifs, on lit k sur l'arbre, puis on « consolide » par quelques itérations de k-moyennes.

Nombre de classes final5

6 000 points ; les cercles sont les 50 centres de la préclassification (taille selon l'effectif), coloriés selon la classe finale.

Dendrogramme de Ward sur les 50 centres pondérés.

Durée des trois étapes—

Distances qu'aurait demandées la CAH directe—

R² après la CAH sur les centres—

R² après consolidation—

Accord avec les vrais groupes (ARI)—

Piège

ARI à gauche—

ARI à droite—

À retenir. Les k-moyennes servent bien au-delà des statistiques : compression d'images, choix d'emplacements (dépôts, antennes), vecteurs « représentants » en reconnaissance de la parole. La classification mixte rend la CAH praticable sur de grands fichiers (enquêtes, clientèles, segmentation d'un marché) en gardant l'arbre pour choisir k. Mais toute classification trouve des classes, qu'elles existent ou non : il faut choisir une distance adaptée (réduire les variables), une méthode adaptée à la forme des groupes, et vérifier la stabilité du résultat.

Repères historiques

1909 — Paul Jaccard mesure la ressemblance entre flores alpines par la part d'espèces communes.
1951 — Kazimierz Florek et les mathématiciens de Wrocław inventent la classification par lien minimal (la « dendrite de Wrocław »).
1957 — Stuart Lloyd, aux laboratoires Bell, conçoit l'algorithme des k-moyennes pour quantifier des signaux (publié en 1982).
1958 — Robert Sokal et Charles Michener proposent le lien moyen (UPGMA) en taxinomie numérique.
1963 — Joe Ward : à chaque étape, fusionner les deux classes qui font le moins augmenter la perte d'information (l'inertie intra).
1965–1967 — Edward Forgy, puis James MacQueen, qui donne le nom de « k-means ».
1967 — Godfrey Lance et William Williams unifient les critères d'agrégation par une seule formule de mise à jour.
1974–1987 — Calinski et Harabasz (1974) proposent leur indice, Peter Rousseeuw la silhouette (1987).
1977–1985 — Lebart, Morineau et Piron popularisent en France la classification mixte et la consolidation ; Hubert et Arabie publient l'indice de Rand ajusté (1985).
2007 — David Arthur et Sergei Vassilvitskii : l'initialisation k-moyennes++, avec une garantie de qualité.

Synthèse

CAH

Fusions successives selon un critère d'agrégation ; produit un arbre où l'on choisit k après coup. Ward est relié à l'inertie, le saut minimal suit les formes allongées. Coûteuse sur de grands fichiers.

k-moyennes

Affecter, recentrer : l'inertie intra baisse jusqu'à un minimum local. Rapide, mais il faut fixer k et multiplier les départs. Elle cherche des groupes ronds et de taille comparable.

Les combiner

Préclassification par k-moyennes, CAH sur les centres pour choisir k, consolidation par k-moyennes : la méthode mixte. Toujours vérifier la distance, la forme des groupes et la stabilité.

Pour aller plus loin

La formule de Lance et Williams. Après fusion de i et j, la distance de la nouvelle classe à k s'écrit d(k, i∪j) = a_id(k,i) + a_jd(k,j) + b·d(i,j) + c·|d(k,i) − d(k,j)|. Saut minimal : a = ½, b = 0, c = −½ ; saut maximal : c = +½ ; lien moyen : a_i = n_i/(n_i + n_j) ; Ward : a_i = (n_i + n_k)/(n_i + n_j + n_k), b = −n_k/(n_i + n_j + n_k), appliquée aux pertes d'inertie.

Ward et k-moyennes cherchent la même chose. Les deux minimisent l'inertie intra : Ward le fait de façon gloutonne en fusionnant, les k-moyennes en déplaçant les centres. C'est pourquoi une consolidation après Ward ne peut qu'améliorer le R².

Complexité. Une CAH naïve coûte de l'ordre de n³ opérations ; avec des voisins réciproques ou des files de priorité, on descend vers n². Les k-moyennes coûtent n·k par itération.

Au-delà. Méthodes à densité (DBSCAN, qui retrouve des formes quelconques et isole le bruit), mélanges gaussiens estimés par l'algorithme EM (des k-moyennes « souples » qui donnent des probabilités d'appartenance), classification spectrale, k-médoïdes pour des distances quelconques. Le test par permutation de la page sur les cathédrales répond à la question « ces classes existent-elles ? ».