ISOMAP
Los métodos clásicos de reducción de la dimensión (PCA, MDS, Análisis factorial…) son fáciles de implementar, eficientes computacionalmente (ya que suelen ser métodos espectrales) y garantizan encontrar la estructura de nuestros datos si es que estos se encuentran sobre un subespacio lineal.
En PCA nuestros datos se proyectan en una menor dimensión que preserva la varianza; las componentes principales van en la dirección de máxima varianza de nuestros datos. Por otra parte, el escalado multidimensional clásico (métrico) encuentra una configuración de $X$ que preserva las distancias originales entre individuos. Ambos métodos funcionarán bien en tanto en cuanto nuestros datos se encuentren sobre un subespacio lineal.
Ha sido un gran tema de debate, desde que Pearson y Hotelling (en el caso de PCA) o Torgerson (en MDS) empezasen a usar estos métodos, el encontrar una solución a la reducción de la dimensión cuando nuestros datos no se encuentran en un subespacio lineal. Han habido algunas soluciones desde aquel entonces, como la propuesta por Shepard y Kruskal del MDS no métrico. Sin embargo, estas no eran muy buenas soluciones. No fue hasta en 2001 cuando se presentaron dos propuestas diferentes para este problema. La primera fue ISOMAP, de la cual hablaremos a continuación, y la segunda fue LEE (Locally Linear Embeding).
Por qué fallan PCA y MDS en espacios no-lineales?
Tomemos como ejemplo de sub-manifold (subespacio no lineal) el Swiss Roll o como lo llamo yo; el brazo de gitano.
Antes de entrar en detalles, debemos definir un concepto fundamental; la geodésica. En geometría, la línea geodésica se define como la línea de mínima longitud que une dos puntos en una superficie dada, y está contenida en esta superficie . En un espacio euclídeo cualquier línea recta es geodésica. En nuestro caso la línea azul punteada es una recta geodésica en el espacio euclídeo y la línea azul continua es una recta geodésica en el sub-manifold (o sea, en el brazo de gitano).
Los puntos $A$ y $B$ se encuentran muy alejados en el brazo si tomamos la distancia geodésica; $ d’ $, en cambio, parecerá que están muy cerca si consideramos una distancia euclídea; $d’’$. Solo la distancia geodésica puede reflejar la 2-dimensionalidad del brazo de gitano. Pero, PCA y MDS “verán” únicamente la estructura errónea; la euclídea, por tanto, nunca podrán encontrar la 2-dimensionalidad del brazo.
Llegados a este punto, debo hacer un inciso; Si lo que el estimado lector desea es reducir sus datos manteniendo las distancias euclídeas, adelante, use MDS o PCA y olvídese de lo que le acabo de contar. Si ese no es el caso, quédese leyendo.
Estimación de la distancia geodésica
Como acabamos de ver, nos gustaría considerar la distancia geodésica del sub-manifold y no la distancia euclídea. Pero si solo contamos con una nube de puntos y no conocemos la superficie sobre la que se encuentran los datos, ¿cómo podemos calcularla?
Bien, consideremos una superficie circular sobre la que se encuentran dos observaciones; Estefanía ($E$) y Christopher ($C$).
Supongamos que Christopher quiere llegar a Estefanía (porque la quiere mucho y quiere estar con ella). La distancia que deberá recorrer Christopher será la distancia geodésica; $d’$ ya que recorrer una distancia euclídea; $d’’$ sería hacer trampas ya que Chris no se encuentra en un espacio euclídeo sino en uno circular. Pero si solo contamos con las coordenadas en el espacio euclídeo de $E$ y $C$ y desconocemos la superficie sobre la que se encuentran ambos, no podemos calcular $d’$. Aquí es donde entran en juego los amigos de Estefanía que también se encuentran sobre la superficie circular. Una forma de aproximar la distancia geodésica entre $E$ y $C$ es encontrar la observación más cercana a $E$; $r$ y medir la distancia euclídea entre $r$ y $E$. Si $r$ está muy cerca de $E$ no hay grandes diferencias entre la distancia euclídea y la distancia geodésica. Una vez calculada $d(E, r)$ podemos encontrar el amigo más cercano a $r$ y medir su distancia euclídea, así hasta llegar a $C$. Si sumáramos todas estas distancias euclídeas, tendríamos una aproximación de $d’$.
\[d' = d(E, r) + d(r, x_i) + ... + d(x_j, C)\]Más formalmente, lo que vamos a querer hacer es construir un grafo de los k-vecinos más cercanos (aunque en el paper original también se propone considerar como vecinos las observaciones que se encuentren en un radio fijo $\epsilon$ ) y calcular la distancia entre $E$ y $C$ como la distancia del camino más corto en el grafo para ir de $E$ a $C$. Definimos el grafo como;
\[G = (V, E)\]Donde $V$ son las observaciones $x_i$. $E$ son los enlaces del grafo que conectan cada par de nodos $x_i, x_j$. Definimos ahora los pesos ($p_{ij}$) de los arcos como;
\[d(i, j) \rightarrow \text{si } x_i \text{ es vecino de } x_j\] \[∞ \rightarrow \text{en cualquier otro caso}\]Al establecer en $∞$ el peso de las aristas entre dos nodos que no sean vecinos estamos sutilmente conectando únicamente los vecinos más cercanos. Sin embargo, se hace así ya que el grafo debe ser conexo para poder aplicar los siguientes algoritmos.
Caminos más cortos
De momento, tenemos solo las distancias geodésicas entre las observaciones que son vecinas, para las que no lo son la distancia entre estas es infinito. Pero, podemos calcular la distancia entre dos observaciones que no son vecinas; $x_i$ y $x_j$ como la distancia del camino más corto para ir de $x_i$ a $x_j$.
Los algoritmos que se usan para encontrar este camino más corto entre dos nodos en el grafo son Dijkstra o Floyd.
No voy a entrar en detalles sobre cómo funcionan ambos algoritmos, el caso es que ambos nos van a devolver una matriz que contendrá para cada par de observaciones la distancia del camino más corto. Llamaremos a esta matriz $G$, que será nuestra mejor aproximación a la matriz de distancias geodésicas.
\[g_{ij} = ShortestDist(i, j)\]Multidimensional Scaling
Una vez tenemos la matriz $G$, podemos usar MDS (Post MDS) para reducir la dimensión de los datos preservando las distancias geodésicas.
En primer lugar, calculamos la matriz de Gram como:
\[B = -\frac{1}{2}C_n G^2 C_n\]Si recordamos, obteniendo la descomposición en vectores y valores propios de $B$ al final llegábamos a una expresión que nos permitía calcular $X$:
\[X = V_p \sqrt{\Lambda_p}\]Donde $V_p$ es una matriz con los $p$ vectores propios de $B$ asociados a los $p$ mayores valores propios. Y $\sqrt{\Lambda}$ es una matriz diagonal donde los elementos de la diagonal son las raíces de los $p$ mayores valores propios.
Algoritmo ISOMAP
Entrada: $k$ (número de vecinos más cercanos), $p$ (número de dimensiones a obtener en MDS), $L$ (matriz de datos $d \times k$)
Salida: $X_p$, donde $p < d$
Paso 1 Construir el grafo de los k-vecinos más cercanos
Paso 2 Calcular la matriz $G$ de distancias usando Floyd o Dijkstra
Paso 3 Aplicar MDS a $G$ para reducir la dimensión manteniendo las distancias geodésicas