DIMENSIONALITY REDUCTION

Multidimensional Scaling - Metric MDS

Mire de cerca la imagen, ¿qué observa? Si no reconoce nada, a veces ayuda retroceder un poco, para tener una mejor perspectiva.

¿Y qué observa ahora?

La distancia crea claridad. La imagen general nos permite ver las cosas con una mayor claridad y entender mejor las conexiones. A menudo, así vemos mucho más claro. Con los datos ocurre igual. Cuando nos enfrentamos a un conjunto de datos con miles de variables es necesario una reducción de la dimensión para observar con claridad qué relaciones existen.

Multidimensional scaling

El escalado multidimensional (MDS a partir de ahora) es un algoritmo de reducción de la dimensión que se usa muy frecuentemente para visualizar similitudes entre individuos de un mismo dataset. MDS, a diferencia de otros algoritmos, no usa la matriz de datos $X$ sino que parte de la matriz de distancias. A partir de esta matriz de distancias $D$, MDS trata de reconstruir la matriz $X$ en una menor dimensión manteniendo las distancias originales.

Objetivo

Dada una matriz de distancias o similitudes; $D = (d_{ij})$. MDS encuentra $x_1, …, x_n \in R^p$ de forma que;

\[d_{ij} \approx ||x_{i} - x_{j}||^2\]

MDS encuentra una estructura en una dimensión menor que la original ($p$) de forma que las distancias en $R^p$ sean tan similares como sea posible a las distancias en la dimensión original. O sea, MDS trata de encontrar $X = [x_1, x_2, …, x_n]$ de forma que $\lVert x_i - x_j\rVert = d_{ij}$.

Matriz de Gram

La matriz de Gram o matriz de productos escalares se define como:

\[B = X \cdot X^t\]

Los elementos de $B$ son los productos escalares de las filas de la matriz $X$, o sea;

\[b_{ij} = \langle x_i, x_j \rangle = \sum_{k=1}^K x_{ik} \cdot x_{jk}\]

Una vez conocida $B$ se puede calcular $X$, como luego veremos. Por otra parte, la matriz de distancias se puede escribir en función de los productos escalares, o sea, de $b_{ij}$.

\[d_{ij}^2 = \sum_{k=1}^K (x_{ik}- x_{jk})^2 = \sum_{k=1}^K (x_{ik} \cdot x_{ik}) + (x_{jk} \cdot x_{jk}) - 2 (x_{ik} \cdot x_{jk})=\] \[= \sum_{k=1}^K (x_{ik} \cdot x_{ik}) + \sum_{k=1}^K (x_{jk} \cdot x_{jk}) - 2 \sum_{k=1}^K (x_{ik} \cdot x_{jk}) =\] \[= b_{ii} + b_{jj} - 2 b_{ij}\]

Problema del escalado

Como hemos comentado, el objetivo de MDS es encontrar una matriz $X$ tal que $\lVert x_i - x_j\rVert = d_{ij}$. Sin embargo, $X$ no tiene por qué ser única ya que las traslaciones no afectan a $D$. Por ejemplo, si tenemos que $X = [x_1, x_2, …, x_n]^t$ también podríamos tener la solución $X^* = [x_1 + c, x_2 + c, …, x_n + c]^t$ y ambas serían soluciones ya que;

\[\lVert x_i* - x_j*\rVert = \lVert (x_i +c) - (x_j +c) \rVert = \lVert x_i - x_j \rVert = d_{ij}\]

Pero $X^*$ estaría escalada por el vector $c$. Para que $X$ sea invariante a traslaciones o rotaciones debemos asumir que $X$ es una matriz centrada con media 0. O sea;

\[\sum_{i=1}^n x_{ik} = 0, \text{para todas las k}\]

Teniendo esto en cuenta, si sumamos las columnas de la matriz $B$, tenemos que;

\[\sum_{i=1}^n b_{ij} = \sum_{i=1}^n \langle x_i, x_j \rangle =\] \[= \sum_{i=1}^n \sum_{k=1}^K x_{ik} \cdot x_{jk} = \sum_{k=1}^K x_{jk }\sum_{i=1}^n x_{ik} = 0\]

para $j=1,…,n$

Obtención de $B$ usando $D^2$

Para poder reconstruir $X$ primero deberemos obtener la matriz de Gram. Sin embargo, solo contamos con la matriz de distancias. ¿Podríamos llegar a $B$ usando solo $D$ ? 😮

Definamos $T = traza(B) = \sum_{i=1}^n b_{ii}$. Si sumamos la matriz de distancias al cuadrado por filas, tenemos que;

\[\require{cancel} \sum_{i=1}^{n} d_{ij}^2 = \sum_{i=1}^n (b_{ii} + b_{jj} - 2b_{ij}) = \sum_{i=1}^n b_{ii} + \sum_{i=1}^n b_{jj} - 2 \cancelto{0}{\sum_{i=1}^n b_{ij}} =\] \[= T + n \; b_{jj}\]

De forma análoga tenemos que $\sum_{j=1}^{n} d_{ij}^2 = T + n \; b_{ii}$. De donde obtenemos que;

\[b_{ii} = \frac{ \sum_{j=1}^{n} d_{ij}^2 - T}{n} \;\; \text{y} \;\; b_{jj} = \frac{ \sum_{i=1}^{n} d_{ij}^2 - T}{n}\]

Si sumamos filas y columnas tenemos que;

\[\sum_{i=1}^n\sum_{j=1}^n d_{ij}^2 = \sum_{i=1}^n (T + n \; b_{ii}) = \sum_{i=1}^n T + n \sum_{i=1}^n b_{ii}=\] \[= nT + nT = n(T + T) = 2nT\]

Tomando la definición de $d_{ij}^2$ (en función de $b_{ij}$) y las expresiones anteriores, tenemos que;

\[d_{ij} = b_{ii} + b_{jj} - 2b_{ij} = \frac{1}{n} (\sum_{j=1}^{n} d_{ij}^2 - T) + \frac{1}{n} (\sum_{i=1}^{n} d_{ij}^2 - T) -2b_{ij} =\] \[= \frac{1}{n} \sum_{j=1}^n d_{ij}^2 - \frac{T}{n} + \frac{1}{n} \sum_{i=1}^n d_{ij}^2 - \frac{T}{n} - 2b_{ij}=\] \[= \frac{1}{n} \sum_{j=1}^n d_{ij}^2 + \frac{1}{n} \sum_{i=1}^n d_{ij}^2 - \frac{2T}{n} - 2b_{ij}\]

Ahora, aplicando el truco del almendruco, multiplicamos la expresión $\frac{2T}{n}$ por $\frac{n}{n}$ y obtenemos; $\frac{2Tn}{n^2}$. Si recordamos $2Tn = \sum_{i=1}^n\sum_{j=1}^n d_{ij}^2 $. Sustituyendo tenemos que;

\[d_{ij} = \frac{1}{n} \sum_{j=1}^n d_{ij}^2 + \frac{1}{n} \sum_{i=1}^n d_{ij}^2 - \frac{1}{n^2} \sum_{i=1}^n\sum_{j=1}^n d_{ij}^2 - 2b_{ij}\]

Despejando $b_{ij}$ llegamos a la siguiente expresión;

\[b_{ij} = -\frac{1}{2}(d_{ij} - \frac{1}{n} \sum_{j=1}^n d_{ij}^2 - \frac{1}{n} \sum_{i=1}^n d_{ij}^2 + \frac{1}{n^2}\sum_{i=1}^n\sum_{j=1}^n d_{ij}^2) =\] \[= -\frac{1}{2}(d_{ij} - d_{i.}^2 - d_{.j}^2+d_{..}^2)\]

En forma matricial;

\[B = -\frac{1}{2}C_nD^2C_n\]

Donde $C_n$ es la matriz de centrado que se define como;

\[C_n = I_n - \frac{1}{n} 1 1^t\]

Donde $I_n$ es la matriz identidad y el vector $1$ es un vector columna de unos. Para cualquier matriz $X \in R^{ \; n \times n}$. $C_n X$ resta las medias de las columnas de $X$ y $XC_n$ resta las medias de las filas. Así, $C_n X C_n$ centra filas y columnas.

O sea, podemos obtener la matriz de Gram a partir de la matriz de distancias $d_{ij}$ 🎉 🎉  !!! Ahora ya solo nos queda obtener $X$.

Descomposición de $B$

Dado que la matriz de Gram es simétrica y positiva, siempre tendrá valores propios reales y podemos usar la descomposición de $B$ en vectores y valores propios para obtener $X$.

\[B = V \Lambda V^t = V(\Lambda^{\frac{1}{2}})^t \Lambda^{\frac{1}{2}} V^t = (\Lambda^{\frac{1}{2}} V^t)^t (\Lambda^{\frac{1}{2}} V^t)\]

Donde $V$ es la matriz de vectores propios y $\Lambda$ es una matriz diagonal de valores propios. Recordemos que $B = XX^t$. Entonces tenemos que;

\[B = (\Lambda^{\frac{1}{2}} V^t)^t (\Lambda^{\frac{1}{2}} V^t) = X X^t\]

De donde se observa fácilmente que;

\[X = V \Lambda^{\frac{1}{2}} = V \sqrt{\Lambda}\]

Al fin! Ya tenemos una expresión para obtener $X$ 😈 Podemos definir ahora una matriz $X$ de una dimensión $p$ escogiendo los $p$ vectores propios asociados a los $p$ mayores valores propios de $B$.

\[X_p = V_p\sqrt{\Lambda_p}\]

Algoritmo MDS

Entrada: Matriz de distancias o similitudes

Salida: Matriz $X$

Paso 1 Calcular la matriz de Gram como; $B = -\frac{1}{2}C_nD^2C_n$

Paso 2 Encontrar los vectores y valores propios de $B$

Paso 3 Usar los $p$ vectores propios asociados a los $p$ mayores valores propios para construir la matriz $X_p$

Referencias

updated_at 20-07-2020