É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,
\|\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

 
multidimensional_scaling.txt · Dernière modification: 2011/01/18 10:13 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki