La méthode de positionnement multidimensionnel est une méthode qui ressemble à l’ACP en pratique. Cependant elle ne travaille pas sur la matrice des données, mais sur une matrice de similarité à travers une distance \(d\text{.}\) L’idée est de se munir d’une notion de distance qui mesure la similarité. Plus des données sont similaires/différentes plus la distance va être petite/grande. À partir de là on construira une réduction qui devra préserver ces similarités. On considère l’échantillon \(\mathcal{X}=(x_1,..,x_n)\) et la matrice de similarité/distance \(D\) qui normalement est une matrice dense de distance entre les données:
\begin{equation*}
D\in \mathcal{M}_{n,n}(\mathbb{R}), \mbox{ avec},\quad D_{ij}=d(x_i,x_j)
\end{equation*}
La matrice \(D\) peut être construite avec des distances issues de la norme \(p\) ou avec la distance de Manhattan. On se focalisera sur le cas \(p=2\) qui est plus simple. Avant de construire l’algorithme, on va rappeler des propriétés utiles à la suite.
Définition 4.14.
Soit une matrice \(D \in \mathcal{M}_{n,n}(\mathbb{R})\text{.}\) On dit qu’elle est une matrice de distance euclidienne si il existe \(d \gt 0\) et \(\mathcal{X}=(x_1,...,x_n)\in \mathbb{R}^d\) tel que
\begin{equation*}
D_{ij}=d_2(x_i,x_j)
\end{equation*}
et la matrice de distance carrée euclidienne est définie par
\begin{equation*}
S_{ij}=d_2(x_i,x_j)^2
\end{equation*}
Dans le cas l’ensemble \(\mathcal{X}\) est appelé ensemble de configuration.
Définition 4.15.
Soit l’ensemble \(\mathcal{X}=(x_1,...,x_n)\in \mathbb{R}^d\text{,}\) on appelle la matrice de Gram associée, la matrice \(G\in \mathcal{M}_{n,n}(\mathbb{R})\) tel que:
\begin{equation*}
G_{ij}= \langle x_i,x_j \rangle
\end{equation*}
Cette matrice est symétrique positive. Si elle est de rang \(r\) il existe une décomposition de Cholesky \(G=X^tX\) avec \(X=(x_1,...,x_n)\mathcal{M}_{r,n}(\mathbb{R})\text{.}\)
On peut montrer qu’à l’inverse une matrice définie positive est une matrice de Gram pour un certain échantillon de point. On rappelle que
\begin{equation*}
d_2(x,y)=\sqrt{\langle x,x \rangle+\langle y,y\rangle -2 \langle x,y\rangle }
\end{equation*}
donc
\begin{equation*}
D_{ij}=\sqrt{G_{ii} + G_{jj}-2G_{ij}}
\end{equation*}
On va montrer que cette relation est inchangée si on prend des données centrées. On définit le centre
\begin{equation*}
\bar{x}=\frac{1}{n}\sum_{i=1}^n x_i
\end{equation*}
si (comme on l’assume) les données vivent dans un hyperplan de dimension \(m\text{,}\) c’est aussi vrai pour le centre et donc le jeu de données centrées (\(\hat{x}_i=x_i-\bar{x})\)):
\begin{equation*}
\hat{\mathcal{X}}={\hat{x}_1,...,\hat{x}_n}
\end{equation*}
est aussi concentré sur un hyperplan parallèle au précédent. Soit la matrice de Gram associée aux données centrées:
\begin{equation*}
G^{c} = \hat{X}^t\hat{X}
\end{equation*}
avec la matrice le vecteur des éléments de \(\mathcal{X}\text{.}\) Un rapide calcul utilisant les propriétés du produit scalaire donne que :
\begin{equation*}
D_{ij}=\sqrt{G^c_{ii} + G^c_{jj}-2G^c_{ij}}
\end{equation*}
Les matrices de Gram centrées seront importantes dans la suite. On introduit donc une dernière définition et des résultats.
Maintenant grâce à ces matrices de Gram, on va montrer qu’on peut effectuer une 1ère réduction de dimension puis que si la dimension obtenue est encore trop grande il est toujours possible d’en effectuer une deuxième en agissant de façon similaire à l’ACP. Pour commencer, on va introduire le principe du positionnement multidimensionnel. L’idée est de trouver une représentation en petite dimension qui préserve les distances/les voisinages. Cela revient à trouver \(\mathcal{Y}=(y_1,...y_n)\in \mathbb{R}^m\) tel qu’ une matrice de distance associée à \(\mathcal{Y}\) noté \(D_y\) soit proche de \(D\) la matrice distance centrée associée à \(\mathcal{X}\) dans \(\mathbb{R}^d\text{.}\) Cela équivaut a chercher \(\mathcal{Y}\)> tel que
\begin{equation*}
d_{y}(y_i,y_j) \approx d_2(\hat{x}_i,\hat{x}_j) \quad \forall 1\lt i,j\lt n
\end{equation*}
On va d’abord montrer qu’une première réduction est rapidement possible. Soit \(S\) la matrice distance carrée euclidienne associée à \(D\text{.}\) On prend
\begin{equation*}
G^c = -\frac12 S^c
\end{equation*}
la matrice de Gram centrée. On suppose que le rang de \(G^c\) est \(r\text{.}\) Par conséquent puisqu’il s’agit d’une matrice symétrique positive il existe une décomposition de Cholesky \(G^c=X^tX\) avec \(X\) (configuration exacte) la matrice de vecteur
\begin{equation*}
(X_1,....X_n)\in \mathbb{R}^r
\end{equation*}
Cela revient à dire que :
\begin{equation*}
d_{2}(z_i,z_j) =d_2(\hat{x}_i,\hat{x}_j) \quad \forall 1 \lt i,j \lt n
\end{equation*}
Ce résultat veut dire que si le rang de \(G_c\) est \(r\) (la configuration intrasecque de \(D\)) les données de l’échantillon centré sont en pratique dans \(\mathbb{R}^r\text{.}\) Si on s’arrête la on a trouver l’hyperplan de dimension \(r\) sur lequel les données sont distribuées. Cependant est possible/probable que \(r\) soit encore trop important. On va donc chercher l’hyperplan de dimension \(m \lt \lt r\) le meilleur possible. Pour cela on introduit la fonctionnelle:
\begin{equation*}
\mathcal{J}(\mathcal{Y})=\sum_{i,j}^n \mid d_2^{2}(z_i,z_j)-d_2^2(y_i,y_j)\mid, \mbox{ avec } \mathcal{Y}=T(\mathcal{Z})
\end{equation*}
avec \(T\) le projecteur orthogonal de \(\mathbb{R}^r\) dans un hyperplan de \(\mathbb{R}^k\text{.}\) On a la solution
\begin{equation*}
(y_1,...,y_n) =\operatorname{argmin}\mathcal{J}(\mathcal{Y}), \mbox{ avec }
\mathcal{Y}=T(\mathcal{Z})
\end{equation*}
De la même façon que, comme pour l’ACP, la solution sera donnée par une SVD.
L ’algorithme est en pratique proche de l’algorithme d’ACP mais travaille sur une matrice différente obtenue à partir de la matrice des distance centrée. On peux choisir une autre distance que la distance euclidienne.
