Analyse des données

Le positionnement multidimensionnel (MDS)

Donnez seulement les distances entre des objets, ou une simple impression de ressemblance, et demandez une carte où les points proches représentent des objets semblables. C'est le positionnement multidimensionnel : il redessine une Europe à partir d'un tableau de kilomètres, un cercle des couleurs à partir de jugements, une carte des langues à partir de l'orthographe des nombres.

L'idée en une phrase

On dispose d'un tableau de dissimilarités δ_ij entre n objets : des distances, des écarts de notes, des jugements « ces deux-là se ressemblent peu ». On cherche n points x₁, …, x_n dans un plan (ou un espace de faible dimension) dont les distances d_ij = ‖x_i − x_j‖ reproduisent au mieux les δ_ij. Trois familles :

MDS classique (Torgerson, 1952) : un calcul direct par valeurs propres, exact quand les δ sont de vraies distances euclidiennes ;
MDS métrique par moindres carrés : on minimise un critère d'écart, le stress, par itérations (algorithme SMACOF) ;
MDS non métrique (Shepard 1962, Kruskal 1964) : seul l'ordre des δ compte, ce qui convient aux jugements humains.

La carte n'a ni nord ni sud : on peut la tourner, la retourner en miroir ou la déplacer sans changer aucune distance. Cette page approfondit l'aperçu donné dans la page sur les tableaux de données et les distances.

Des distances à la carte : la méthode de Torgerson pas à pas

Quatorze capitales européennes et leurs distances à vol d'oiseau, calculées sur le globe. On ne garde que ce tableau de 91 nombres, et l'on reconstruit la carte en quatre étapes.

La vraie carte (projection équirectangulaire, cercles gris) et la carte reconstruite à partir des seules distances (points bleus) : d'abord brute, telle que la donne le calcul, puis, après un clic sur le bouton, tournée et retournée pour la comparaison (traits rouges : l'écart de chaque ville).

Part des deux premières valeurs propres—

Masse des valeurs propres négatives—

Écart moyen à la vraie carte—

Contrôle : distances prises sur une carte plane, B − XXᵀ—

À retenir. Le double centrage transforme des carrés de distances en produits scalaires : B = −½·J·D²·J, où J retire les moyennes de lignes et de colonnes. Si les distances viennent d'une carte plane, B vaut exactement XXᵀ (vérifié ici à 10⁻¹⁵ près) et ses deux premiers vecteurs propres redonnent la carte, à une rotation et un miroir près. Ici, les distances sont prises sur le globe : la courbure laisse de petites valeurs propres négatives, et la carte obtenue ressemble à une projection de la sphère.

Combien de dimensions faut-il ?

Les valeurs propres de B disent combien de directions sont nécessaires : autant que de valeurs nettement positives. Des valeurs négatives signalent des dissimilarités qu'aucun espace euclidien ne peut reproduire exactement. Quatre tableaux de distances de natures différentes.

Tableau

Valeurs propres de B, de la plus grande à la plus petite : bleu si positive, rouge si négative.

La carte à deux dimensions obtenue.

Valeurs propres nettement positives—

Part des deux premières (parmi les positives)—

Masse négative / masse totale—

Stress-1 de la carte à deux dimensions—

À retenir. Deux valeurs propres positives pour une carte plane, trois pour un objet en relief : la MDS classique retrouve la dimension cachée. Sur le globe, des valeurs négatives apparaissent : on ne peut pas aplatir une sphère sans la déformer (c'est le problème de toutes les projections cartographiques). La distance des rues en damier (dite de Manhattan) n'est pas non plus euclidienne : elle aussi produit des valeurs négatives.

Le stress et l'algorithme SMACOF

Quand les dissimilarités ne sont pas euclidiennes, on cherche plutôt la carte qui les reproduit le mieux, au sens d'un critère : le stress, somme des carrés des écarts (δ_ij − d_ij)². L'algorithme SMACOF de Jan de Leeuw (1977) part d'une carte quelconque et la corrige pas à pas ; chaque pas fait baisser le stress, garanti.

Stress-1 = √( Σ (δ_ij − d_ij)² / Σ δ_ij² )

La carte des 14 capitales pendant les itérations (distances du globe). Traits gris : la trace de chaque ville.

Stress-1 à chaque itération (échelle logarithmique).

Diagramme de Shepard : chaque point est une paire de villes, distance donnée δ en abscisse, distance sur la carte d en ordonnée. Un ajustement parfait les aligne sur la diagonale.

Itération—

Stress-1—

Plus forte remontée du stress—

Stress de Torgerson (sans itérer)—

50 départs au hasard : stress final minimal / maximal—

À retenir. SMACOF remplace un problème difficile par une suite de problèmes faciles : à chaque pas, on minimise une fonction plus simple qui majore le stress et le touche au point courant (une « majorante »), ce qui garantit la descente. Comme pour les k-moyennes, on peut s'arrêter dans un minimum local : partir de la solution de Torgerson est le remède habituel. Sur les distances du globe, SMACOF fait un peu mieux que Torgerson, car c'est le stress lui-même qu'il minimise.

Seul l'ordre compte : la MDS non métrique

Quand on demande à des personnes de juger des ressemblances, les nombres obtenus n'ont pas d'échelle fiable : seul leur ordre a un sens. Ici, 20 points ont une vraie position, mais on ne fournit que δ = f(d), avec f croissante et déformante (une puissance γ). La MDS métrique prend ces nombres au pied de la lettre ; la MDS non métrique cherche seulement une carte dont les distances sont rangées dans le même ordre, grâce à une régression monotone (l'algorithme PAVA) à chaque itération.

Déformation γ (δ = d^γ)2,50

Vraies positions (cercles gris) ; MDS métrique (orange) et non métrique (bleu), chacune ajustée à la vérité par rotation et changement d'échelle. Traits : l'erreur de chaque point.

Diagramme de Shepard de la solution non métrique : distances obtenues en fonction des δ (points), et la fonction en escalier croissante ajustée par la régression monotone (rouge).

Erreur de la MDS métrique (Procuste)—

Erreur de la MDS non métrique (Procuste)—

Stress non métrique (de Kruskal)—

Corrélation des rangs entre δ et distances obtenues—

À retenir. Sans déformation (γ = 1), les deux méthodes se valent. Dès que l'échelle des dissimilarités est tordue, la MDS métrique déforme la carte, tandis que la non métrique la retrouve presque parfaitement : un classement de toutes les paires contient en fait assez d'information pour fixer les positions, à une similitude près. C'est la découverte de Roger Shepard en 1962, formalisée par Joseph Kruskal en 1964.

Applications : dérouler, comparer des langues, voir des couleurs

Trois usages qui montrent la souplesse de la méthode : il suffit de savoir mesurer une dissimilarité, quelle qu'elle soit.

300 points sur une surface enroulée en spirale dans l'espace (le « gâteau roulé »). La MDS sur les distances à vol d'oiseau ne fait que montrer le rouleau vu par la tranche, toujours enroulé : deux points de spires voisines y paraissent proches alors qu'il faut faire tout un tour pour aller de l'un à l'autre. Isomap (Tenenbaum, de Silva et Langford, 2000) remplace ces distances par des distances le long de la surface : on relie chaque point à ses k plus proches voisins, on calcule les plus courts chemins dans ce réseau, puis on applique la MDS classique. Le réglage de k est délicat : trop peu de voisins et le réseau se coupe en morceaux ; trop de voisins et des liaisons « raccourcis » traversent d'une spire à l'autre, ce qui ruine le dépliage (essayez k = 3, puis k = 12).

Nombre de voisins k7

Le rouleau en perspective (il tourne lentement), coloré selon la position le long de la spirale, avec les liaisons entre voisins.

MDS sur les distances à vol d'oiseau : la spirale reste enroulée, aucun axe ne suit la position le long du rouleau.

Isomap : le rouleau est déplié, les couleurs se suivent.

MDS directe : corrélation des rangs, axe 1 / position le long de la spirale—

Isomap : même corrélation—

État du réseau des voisins—

Seize langues, et les nombres de un à dix écrits dans chacune (en alphabet latin, sans accents). La dissimilarité entre deux langues est la distance d'édition moyenne (nombre de lettres à ajouter, supprimer ou remplacer, ramené à la longueur du mot) entre leurs mots pour un même nombre. Aucune connaissance de linguistique n'est fournie à la méthode.

Carte des langues par MDS non métrique (départ par Torgerson). Couleurs ajoutées après coup selon la famille : romane (rouge), germanique (bleu), slave (vert), grec (violet), finno-ougrienne (orange).

Stress non métrique de la carte—

Langues dont le plus proche voisin est de la même famille—

Paire la plus proche—

Quatorze teintes, du violet au rouge. Des observateurs (simulés ici) notent la ressemblance de chaque paire sur une échelle de 0 à 10, avec leur part d'arbitraire. On ne connaît ni les longueurs d'onde ni les teintes, seulement ces notes. La MDS non métrique dessine-t-elle un segment, comme le spectre, ou un cercle ?

Arbitraire des notes0,60

Carte obtenue par MDS non métrique ; chaque point a sa couleur, et les teintes sont reliées dans l'ordre du spectre.

Stress non métrique—

Teintes rangées dans l'ordre autour du centre—

Écart angulaire violet – rouge (fermeture du cercle)—

Avec des jugements réels publiés par Gösta Ekman en 1954, Roger Shepard obtint en 1962 exactement ce cercle : le violet et le rouge, aux deux bouts du spectre, sont perçus comme voisins. La perception des couleurs n'est pas rangée comme les longueurs d'onde.

À retenir. La MDS ne demande qu'une manière de dire « ceci ressemble plus à cela qu'à autre chose » : distances le long d'une surface (Isomap, apprentissage de variétés), distances d'édition entre mots (linguistique, génétique avec les distances entre séquences), jugements de ressemblance (psychologie, marketing et cartes de perception des marques), votes de députés, matrices de corrélations. Elle rend visible une structure qu'on n'a jamais mesurée directement.

Repères historiques

1938 — Gale Young et Alston Householder : condition pour qu'une matrice de distances soit réalisable dans un espace euclidien.
1952 — Warren Torgerson publie la MDS classique, fondée sur le double centrage.
1954 — Gösta Ekman recueille des jugements de ressemblance entre 14 couleurs.
1962 — Roger Shepard : l'analyse des proximités, première MDS non métrique, retrouve le cercle des couleurs.
1964 — Joseph Kruskal définit le stress et l'ajustement par régression monotone.
1966 — John Gower montre l'équivalence entre MDS classique et ACP : on parle aussi d'analyse en coordonnées principales.
1970 — Carroll et Chang (INDSCAL) : MDS pour plusieurs sujets à la fois.
1977 — Jan de Leeuw : l'algorithme SMACOF par majoration.
2000 — Isomap (Tenenbaum, de Silva, Langford) et LLE ouvrent l'apprentissage de variétés.
2008 — Laurens van der Maaten et Geoffrey Hinton : t-SNE, héritier de la MDS pour visualiser de très grandes données.

Synthèse

MDS classique

Double centrage de D², puis valeurs propres : rapide, exacte pour des distances euclidiennes, et identique à l'ACP quand on part de coordonnées. Les valeurs négatives mesurent l'écart à l'euclidien.

MDS par stress

On minimise Σ(δ − d)² par SMACOF : chaque itération baisse le stress, mais le départ compte. La version non métrique ne retient que l'ordre des δ, grâce à la régression monotone.

Applications

Cartes de perception, linguistique et génétique, apprentissage de variétés (Isomap), comparaison de sujets, de textes, de votes : tout ce qui se décrit par des ressemblances.

Pour aller plus loin

Pourquoi le double centrage marche. Si les points sont centrés, d_ij² = ‖x_i‖² + ‖x_j‖² − 2x_i·x_j. Retirer les moyennes de ligne et de colonne de −½d² élimine les deux premiers termes et laisse exactement x_i·x_j.

La transformation de Guttman. Le pas de SMACOF s'écrit X ← (1/n)·B(X)·X, où B(X) contient les rapports δ_ij/d_ij : chaque point est poussé vers une moyenne de positions corrigées par ces rapports.

Le stress de Kruskal. En non métrique, on compare d_ij à des « disparités » d̂_ij obtenues par régression monotone de d sur l'ordre des δ ; stress = √(Σ(d − d̂)²/Σd²). Kruskal jugeait 0,20 médiocre, 0,10 correct, 0,05 bon, 0,025 excellent.

Liens avec les autres pages. ACP et AFC sont des MDS classiques pour la distance euclidienne et la distance du χ² ; la page de classification utilise aussi des matrices de distances, et la page sur les cathédrales la distance de Gower.