Positionnement multidimensionnel

Le positionnement multidimensionnel (« Multidimensional scaling » ou MDS) est un ensemble de techniques statistiques utilisées dans le domaine de la visualisation d'information pour explorer les similarités dans les données. Le positionnement multidimentionnel est un cas particulier d'analyse multivariée. Un algorithme en PM débute typiquement avec une matrice de similarité entre individus, puis affecte une position à chaque individu dans un espace à m dimensions. Pour m=2 ou m=3, les positions peuvent être représentées dans le plan ou dans un espace à trois dimensions par un nuage de points.

Cadre général

Étant donné $N$ points $x_{1},x_{2},\cdots ,x_{N}$ dans un espace de dimension $p$, le positionnement multidimensionnel consiste à représenter ces points dans un espace de dimension $m<p$ par N nouveaux points $y_{1},y_{2},\cdots ,y_{N}$ en conservant les proximités. On se donne pour cela une matrice de distance $D$ qui peut être définie par la distance euclidienne $d_{ij}=||x_{i}-x_{j}||_{2}$ ou toute autre mesure de similarité. Présenté dans ce contexte, le positionnement multidimensionnel est une technique de réduction de dimension, au même titre que l'analyse en composantes principales.

En pratique, le positionnement multidimensionnel consiste à trouver N vecteurs $y_{1},y_{2},\cdots ,y_{N}$ de taille $m$ qui minimisent une fonction de coût $S(y_{1},y_{2},\cdots ,y_{N})$ appelée stress.

Positionnement multidimensionnel métrique

Un positionnement multidimensionnel métrique se réfère à une fonction de coût définie par la distance euclidienne ou le produit scalaire entre les points $y_{i}$.

Une fonction de coût naturelle pour le positionnement multidimensionnel est

$S(y_{1},y_{2},...,y_{N})=\sum _{i\neq j}{\bigl (}d_{ij}-||y_{i}-y_{j}||{\bigr )}^{2}$

mais cette formulation n'a en général pas de solution explicite.

Positionnement multidimensionnel classique

Pour le positionnement multidimensionnel classique, la fonction de coût est remplacée par

$S(y_{1},y_{2},...,y_{N})=\sum _{i\neq j}(b_{ij}-\langle y_{i},y_{j}\rangle )^{2}$

Le terme $b_{ij}$ est défini par $b_{ij}=<x_{i}-{\overline {x}},x_{j}-{\overline {x}}>$ avec ${\overline {x}}={\frac {1}{N}}\sum _{i=1\cdots N}x_{i}$. De façon générale, la matrice $B$, matrice de similarité, peut être obtenue à partir d'une matrice de distance $D$ par double centrage :

$B=(I-{\frac {1}{N}}J)D^{2}(I-{\frac {1}{N}}J)$

où $J$ est une matrice de taille $N\times N$ ne contenant que des uns.

Cette formulation a l'avantage d'avoir une solution explicite en utilisant la décomposition de $B$ en éléments propres. Soient ${\textstyle \lambda _{1},\lambda _{2},...,\lambda _{m}}$ les ${\textstyle m}$ plus grandes valeurs propres et ${\textstyle e_{1},e_{2},...,e_{m}}$ les vecteurs propres correspondants. Alors une solution pour le PM est de prendre comme vecteurs $y_{1},\cdots ,y_{N}$ les colonnes de la matrice ${\textstyle Y=\Lambda _{m}^{1/2}{E_{m}}^{T}}$, où ${\textstyle {E_{m}}^{T}}$ est la matrice des vecteurs propres transposée et ${\textstyle \Lambda _{m}}$ est la matrice diagonale des valeurs propres.

Positionnement multidimensionnel non métrique

Le positionnement multidimensionnel non métrique décrit des méthodes qui donnent davantage d'importance à l'ordre des proximités plutôt que la conservation des distances. La fonction de coût à minimiser est

$S(y_{1},y_{2},...,y_{N})=\sum _{i\neq j}{\bigl (}d_{ij}-f(||y_{i}-y_{j}||){\bigr )}^{2}$.

Cependant la méthode de PM non métrique a la particularité d'autoriser que la fonction $f$ s'adapte lors de l'optimisation, en prenant une régression monotone des points $(||y_{i}-y_{j}||,d_{ij})$.

Voir aussi

• Exploration de données
• Analyse des données

Notes et références

• (en) T. F. Cox et M. A. A. Cox, Multidimensional Scaling, Chapman and Hall, 2001
• (en) Trevor Hastie, Robert Tibshirani et Jerome Friedman, The Elements of Statistical Learning, Springer, 2009, 2^e éd., section 14.8, p. 570