Table des matières

Échelonnement Multidimensionnel

Principes

L'échelonnement multidimensionnel (multidimensional scaling) est une famille de procédures–dont certaines métriques, d'autres non métriques– d'analyse de matrices de dissimilarité. Ceci peut être vu comme une alternative à (ou généralisation de?) l'analyse factorielle : des matrices de corrélation, similarité ou dissimilarité peuvent être analysées.

Soit \delta_{i,j} la distance entre objets i et j, composant la matrice

\Delta := \begin{pmatrix} \delta_{1,1} & \delta_{1,2} & \cdots & \delta_{1,I} \\ \delta_{2,1} & \delta_{2,2} & \cdots & \delta_{2,I} \\ \vdots & \vdots & & \vdots \\ \delta_{I,1} & \delta_{I,2} & \cdots & \delta_{I,I} \end{pmatrix}.

Le but de l'EMD est, étant donnée Δ, trouver I vecteurs x_1,\ldots,x_I \in \mathbb{R}^N tels que

\|x_i - x_j\| \approx \delta_{i,j} \quad \forall i,j\in I,
où \|\cdot\| est une norme. Dans EMD classique, cette norme est la distance Euclidienne, mais plus généralement elle peut être une distance métrique ou arbitraire?

Autrement dit, EMD recherche une embedding des I objets dans \mathbb{R}^N telle que les distances sont conservées. Si la dimension N choisie est 2 ou 3, l'on peut représenter graphiquement les vecteurs x_i afin de visualiser les similarités des I objets. Notons que les vecteurs x_i ne sont pas uniques : les distances \|x_i - x_j\| sont conservées par des translations et rotations .

Il y a divers approches pour trouver les vecteurs x_i. Souvent, EMD est formulé comme un problème d'optimisations où \left(x_1,\ldots,x_I\right) est une solution qui minimise une fonction de coût (ou pénalité) ; par exemple

\min_{x_1,\ldots,x_I} \sum_{i<j} ( \|x_i - x_j\| - \delta_{i,j} )^2.
Une solution peut être trouvée par une technique d'optimisation numerique. Pour quelques fonctions de coût bien choisies, les minimisation peuvent être exprimées en termes de eigendécompositions de matrices.

Sources