fr.wikipedia.org

Positionnement multidimensionnel — Wikipédia

Un article de Wikipédia, l'encyclopédie libre.

Exemple de positionnement multidimensionnel de données.

Le positionnement multidimensionnel[1] 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. Typiquement, un algorithme de positionnement multidimensionnel part d'une matrice de similarité entre tous les points pour affecter à chaque point une position dans un espace à {\displaystyle m} dimensions. Pour {\displaystyle m} = 2 ou {\displaystyle m} = 3, les positions peuvent être visualisées sur un plan ou dans un volume par un nuage de points.

Étant donné {\displaystyle N} points {\displaystyle x_{1},x_{2},\cdots ,x_{N}} dans un espace de dimension {\displaystyle p}, le positionnement multidimensionnel consiste à représenter ces points dans un espace de dimension {\displaystyle m<p} par {\displaystyle N} nouveaux points {\displaystyle y_{1},y_{2},\cdots ,y_{N}} en conservant les proximités. On se donne pour cela une matrice de distance {\displaystyle D} qui peut être définie par la distance euclidienne {\displaystyle d_{ij}=||x_{i}-x_{j}||_{2}}. Si on part de valeurs de similarité, il faut les convertir en valeurs de vraie distance mathématique, car il faut conserver à l'esprit que distance et similarité sont des notions opposées : plus faible est la distance, plus grande est la similarité, et réciproquement. Présenté sous cet angle, 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 {\displaystyle N} vecteurs {\displaystyle y_{1},y_{2},\cdots ,y_{N}} de taille {\displaystyle m} qui minimisent une fonction de coût {\displaystyle S(y_{1},y_{2},\cdots ,y_{N})} appelée stress.

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 {\displaystyle y_{i}}.

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

{\displaystyle 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.

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

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

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

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

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

Cette formulation a l'avantage d'avoir une solution explicite par décomposition de {\displaystyle 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 positionnement multidimensionnel est de prendre comme vecteurs {\displaystyle 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.

Le positionnement multidimensionnel non métrique s'intéresse aux méthodes qui privilégient l'ordre des proximités sur la conservation des distances. La fonction de coût à minimiser est

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

On permet à la fonction {\displaystyle f} de s'adapter lors de l'optimisation. Pour ce faire, on peut calculer une régression monotone des points {\displaystyle (||y_{i}-y_{j}||,d_{ij})}.

  • (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, 2e éd., section 14.8, p. 570
  1. ↑ Alain Baccini et Philippe Besse, Exploration Statistique, chapitre 7