Tableaux de données et distances
Un tableau de chiffres devient un nuage de points dès qu'on regarde chaque ligne comme une position. Reste à dire ce que « proche » veut dire : c'est le rôle de la distance, et le choix de cette distance décide de tout ce que l'on verra ensuite.
Le fil de la page
Un tableau de données range des individus en lignes (ici dix villes françaises) et des variables en colonnes (quatre mesures du climat). Chaque ligne est donc une liste de nombres, c'est-à-dire un point d'un espace qui a autant de dimensions que de colonnes. Une distance est une règle qui associe à deux individus un nombre positif, nul seulement s'ils sont identiques, symétrique, et qui respecte l'inégalité triangulaire : le détour par un troisième point ne raccourcit jamais le chemin.
La page suit une progression simple : voir le nuage (planche 1), comparer plusieurs formules de distance (planche 2), découvrir pourquoi il faut presque toujours centrer et réduire (planche 3), corriger les redondances entre variables corrélées (planche 4), puis montrer, en signature, que les distances seules suffisent à redessiner une carte — et qu'en très grande dimension elles finissent par toutes se ressembler (planche 5).
Les valeurs climatiques sont des normales arrondies, indicatives : elles servent d'exemple, pas de référence météorologique.
Le tableau devient un nuage
Choisissez deux colonnes : chaque ville devient un point dont ces deux colonnes sont les coordonnées. Cliquez une ligne ou un point pour désigner la ville A, puis la ville B ; leur distance est le théorème de Pythagore appliqué aux écarts colonne par colonne.
Cliquez une ligne : le premier clic choisit A, le suivant B, et ainsi de suite en alternance.
L'inertie du nuage, trois fois
L'inertie mesure l'étalement du nuage : c'est la moyenne des carrés des distances au centre G. On peut aussi l'obtenir comme somme des variances des colonnes, ou par les distances entre toutes les paires de points, sans jamais calculer G.
Et si l'on prend les quatre colonnes ?
La formule ne change pas : on ajoute simplement un carré par colonne, d² = Δ₁² + Δ₂² + Δ₃² + Δ₄². Voici le détail pour la paire A, B choisie.
Plusieurs façons de mesurer « proche »
À vol d'oiseau, en suivant les rues d'un quartier quadrillé, ou en ne retenant que le plus grand écart : ce sont trois distances, toutes membres d'une même famille réglée par un exposant p. Déplacez A, B et C, et faites varier p.
dp(A,B) = ( |Δx|p + |Δy|p )1/p
Pour p = 2 on retrouve la distance euclidienne ; pour p = 1, la distance « de Manhattan » (somme des écarts, le chemin en escalier) ; quand p grandit sans limite, seul le plus grand écart compte : c'est la distance de Tchebychev, notée d∞. La courbe tracée autour de A est la « sphère » de la distance : l'ensemble des points situés à la même distance que B.
L'inégalité triangulaire
Le piège des unités : centrer et réduire
Mesurer la pluie en millimètres ou en mètres ne change rien au climat, mais change tout à la distance brute. Le remède classique consiste à centrer chaque colonne (soustraire sa moyenne) puis à la réduire (diviser par son écart-type) : chaque variable s'exprime alors en « nombre d'écarts-types », sans unité.
zij = ( xij − x̄j ) / sj
Qui pèse dans d²(A,B) ?
Variables corrélées : la distance de Mahalanobis
Réduire égalise les colonnes, mais ne voit pas que deux colonnes peuvent dire presque la même chose. Quand deux variables sont corrélées, le nuage forme une ellipse inclinée : s'écarter le long de l'ellipse est banal, s'en écarter en travers est exceptionnel. La distance de Mahalanobis (1936) mesure l'écart en tenant compte de cette forme.
dM(x)² = (x − m)T S−1 (x − m)
Ici m est le centre du nuage et S sa matrice de covariance. Autre lecture, équivalente : on « blanchit » le nuage par une transformation linéaire qui le rend rond (décomposition de Cholesky S = LLT, puis w = L−1(x − m)), et l'on prend la distance euclidienne ordinaire de w.
Ce que disent les distances, et ce qu'elles taisent
Deux expériences opposées. D'abord, une matrice de distances suffit, à elle seule, à redessiner une carte : c'est le positionnement multidimensionnel. Ensuite, quand les colonnes se comptent par centaines, toutes les distances deviennent presque égales : c'est la « malédiction de la dimension ».
On ne donne à l'ordinateur que les 45 distances entre les dix villes, sans aucune coordonnée. La méthode de Torgerson (1952) transforme les carrés des distances en une matrice de produits scalaires par double centrage, B = −½·J·D²·J, puis en tire les axes principaux par diagonalisation. Les deux premiers axes donnent une carte, que l'on superpose à la vraie par une simple rotation (ajustement de Procuste). La seconde méthode, SMACOF, part de positions tirées au hasard et les corrige pas à pas pour réduire l'écart entre distances dessinées et distances données (le « stress »).
On tire 150 points au hasard, uniformément dans un cube de dimension p, et l'on calcule les 11 175 distances entre eux. En dimension 2, il y a des voisins proches et des points lointains. Montez la dimension : l'histogramme des distances se resserre autour de sa moyenne, si bien que le plus proche voisin n'est guère plus proche que le plus lointain.
Repères historiques
- vers −300 — Euclide : la distance comme longueur du segment, et l'inégalité triangulaire (le côté d'un triangle est plus court que la somme des deux autres).
- 1896 — Hermann Minkowski, Geometrie der Zahlen : les normes dp et l'idée qu'une « sphère » peut être un carré ou un losange.
- 1901 — Karl Pearson ajuste un plan au plus près d'un nuage de points : premier pas vers l'ACP, fondée sur la distance euclidienne.
- 1906 — Maurice Fréchet définit l'espace métrique abstrait : n'importe quel ensemble muni d'une distance qui vérifie les trois axiomes.
- 1936 — Prasanta Chandra Mahalanobis, à Calcutta, propose sa distance pour comparer des populations décrites par des mesures corrélées.
- 1952 — Warren Torgerson publie le positionnement multidimensionnel classique, qui retrouve des coordonnées à partir de distances.
- 1957 — Richard Bellman nomme la « malédiction de la dimension » à propos de la programmation dynamique.
- 1966–1971 — John Gower relie double centrage et ACP, puis propose un coefficient de distance pour variables de natures mélangées.
- 1977 — Jan de Leeuw introduit l'algorithme de majorisation (SMACOF) qui fait baisser le stress à chaque pas.
- 1999 — Beyer, Goldstein, Ramakrishnan et Shaft démontrent que, sous des hypothèses larges, plus proche et plus lointain voisin tendent à se confondre quand la dimension croît.
Synthèse
Le tableau est un nuage
Lignes = points, colonnes = axes. L'inertie du nuage se lit indifféremment autour du centre de gravité, colonne par colonne ou par toutes les paires de points.
La distance est un choix
Exposant p, unités, centrage-réduction, prise en compte des corrélations : chaque décision change les voisins. Réduire égalise les colonnes ; Mahalanobis corrige en plus leurs redondances.
Les distances suffisent
Une matrice de distances contient une carte, que le double centrage retrouve. En revanche, en très grande dimension, toutes les distances se ressemblent : il faut d'abord résumer.
Pour aller plus loin
Les trois axiomes. d(x,y) ≥ 0 avec égalité si et seulement si x = y ; d(x,y) = d(y,x) ; d(x,z) ≤ d(x,y) + d(y,z). Pour p < 1, la formule dp viole le troisième : la planche 2 l'exhibe.
Pourquoi un quart exactement ? Pour une colonne réduite, Σi<k(zi − zk)² = n²·Var(z) = n², la même valeur pour chaque colonne : avec quatre colonnes, chacune pèse 25 %.
Le double centrage. Si les points ont des coordonnées centrées X, alors −½·J·D²·J = X·XT, où J = I − (1/n)·11T. Diagonaliser cette matrice donne les coordonnées à une rotation près ; des valeurs propres négatives signalent des distances qu'aucun espace euclidien ne peut réaliser exactement.
Distances pour d'autres données. Pour des tableaux de contingence, la distance du χ² (voir la page d'AFC) ; pour des variables qualitatives, des indices de dissimilarité (Jaccard, Gower) ; pour des courbes ou des répartitions, la distance de Wasserstein (page du transport optimal).
Le chiffre √(7/20). Pour deux points uniformes du cube de dimension p, d² a pour moyenne p/6 et pour variance 7p/180 ; d'où un coefficient de variation de d voisin de ½·√(7·36/180)/√p = √(7/20)/√p ≈ 0,5916/√p.