isomapa

Isomapa del conjunto de datos del “rollo suizo”. (A) Dos puntos del rollo suizo y su curva geodésica. (B) El gráfico KNN (con K = 7 y N = 2000) permite un gráfico geodésico (rojo) que se aproxima a la geodésica suave. (C) El rollo suizo "desenrollado", mostrando la gráfica geodésica (rojo) y la geodésica suave (azul). Replicación de la Figura 3 de ^[1] .

Isomap es un método de reducción de dimensionalidad no lineal . Es uno de varios métodos de incrustación de baja dimensión ampliamente utilizados. ^[1] Isomap se utiliza para calcular una incrustación cuasi isométrica de baja dimensión de un conjunto de puntos de datos de alta dimensión. El algoritmo proporciona un método simple para estimar la geometría intrínseca de una variedad de datos basándose en una estimación aproximada de los vecinos de cada punto de datos en la variedad. Isomap es muy eficiente y generalmente aplicable a una amplia gama de fuentes y dimensionalidades de datos.

Introducción

Isomap es un representante de los métodos de mapeo isométrico y extiende el escalamiento multidimensional métrico (MDS) al incorporar las distancias geodésicas impuestas por un gráfico ponderado. Para ser específico, el escalado clásico de MDS métrico realiza una incrustación de baja dimensión basada en la distancia por pares entre puntos de datos, que generalmente se mide utilizando la distancia euclidiana en línea recta . Isomap se distingue por el uso de la distancia geodésica inducida por un gráfico de vecindad integrado en la escala clásica. Esto se hace para incorporar una estructura múltiple en la incrustación resultante. Isomap define la distancia geodésica como la suma de los pesos de los bordes a lo largo del camino más corto entre dos nodos (calculado utilizando el algoritmo de Dijkstra , por ejemplo). Los n vectores propios superiores de la matriz de distancias geodésicas representan las coordenadas en el nuevo espacio euclidiano de n dimensiones.

Algoritmo

A continuación se proporciona una descripción de muy alto nivel del algoritmo Isomap .

• Determine los vecinos de cada punto.
  • Todos los puntos en algún radio fijo.
  • K vecinos más cercanos.
• Construya una gráfica de vecindad.
  • Cada punto está conectado con otro si es un K vecino más cercano.
  • Longitud del borde igual a la distancia euclidiana.
• Calcule el camino más corto entre dos nodos.
  • algoritmo de dijkstra
  • Algoritmo de Floyd-Warshall
• Calcule la incrustación de dimensiones inferiores.
  • Escalado multidimensional

Extensiones de ISOMAP

• LandMark ISOMAP (L-ISOMAP) : Landmark-Isomap es una variante de Isomap que es más rápida que Isomap. Sin embargo, la precisión del colector se ve comprometida por un factor marginal. En este algoritmo, se utilizan n << N puntos de referencia del total de N puntos de datos y se calcula una matriz nxN de la distancia geodésica entre cada punto de datos y los puntos de referencia. Luego se aplica Landmark-MDS (LMDS) en la matriz para encontrar una incrustación euclidiana de todos los puntos de datos. ^[2]

• C Isomap  : C-Isomap implica ampliar las regiones de alta densidad y reducir las regiones de baja densidad de puntos de datos en la variedad. Los pesos de los bordes que se maximizan en el escalado multidimensional (MDS) se modifican y todo lo demás no se ve afectado. ^[2]
• Despliegue del transporte paralelo  : reemplaza las estimaciones de distancia geodésica basadas en trayectorias de Dijkstra con aproximaciones basadas en transporte paralelo , mejorando la robustez ante irregularidades y vacíos en el muestreo. ^[3]

Posibles problemas

La conectividad de cada punto de datos en el gráfico de vecindad se define como sus k vecinos euclidianos más cercanos en el espacio de alta dimensión. Este paso es vulnerable a "errores de cortocircuito" si k es demasiado grande con respecto a la estructura del colector o si el ruido en los datos mueve los puntos ligeramente fuera del colector. ^[4] Incluso un solo error de cortocircuito puede alterar muchas entradas en la matriz de distancias geodésicas, lo que a su vez puede conducir a una incrustación de baja dimensión drásticamente diferente (e incorrecta). Por el contrario, si k es demasiado pequeño, el gráfico de vecindad puede volverse demasiado escaso para aproximarse con precisión a los caminos geodésicos. Pero se han realizado mejoras en este algoritmo para que funcione mejor con conjuntos de datos escasos y ruidosos. ^[5]

Relación con otros métodos

Siguiendo la conexión entre el escalado clásico y PCA , la MDS métrica puede interpretarse como PCA del núcleo . De manera similar, la matriz de distancias geodésicas en Isomap puede verse como una matriz central . La matriz de distancias geodésicas K doblemente centrada en Isomap tiene la forma

${\displaystyle K=-{\frac {1}{2}}HD^{2}H\,}$

donde es el cuadrado de elementos de la matriz de distancias geodésicas D = [ D _ij ], H es la matriz de centrado, dada por ${\displaystyle D^{2}=D_{ij}^{2}:=(D_{ij})^{2}}$

${\displaystyle H=I_{n}-{\frac {1}{N}}e_{N}e_{N}^{T},\quad {\text{where }}e_{N}=[1\ \dots \ 1]^{T}\in \mathbb {R} ^{N}.}$

Sin embargo, la matriz nuclear K no siempre es semidefinida positiva . La idea principal de kernel Isomap es hacer que este K sea una matriz de kernel de Mercer (es decir, semidefinida positiva) usando un método de cambio constante, para relacionarlo con el PCA del kernel de manera que la propiedad de generalización surja naturalmente. ^[6]

Ver también

• PCA del núcleo
• Agrupación espectral
• Reducción de dimensionalidad no lineal.

Referencias

1. Tenenbaum, Joshua B.; Silva, Vin de; Langford, John C. (22 de diciembre de 2000). "Un marco geométrico global para la reducción de dimensionalidad no lineal". Ciencia . 290 (5500): 2319–2323. doi : 10.1126/ciencia.290.5500.2319.
2. Silva, Vin; Tenenbaum, Josué (2002). "Métodos globales versus locales en reducción de dimensionalidad no lineal". Avances en los sistemas de procesamiento de información neuronal . 15 . Prensa del MIT.
3. Budninskiy, Max; Yin, Gloria; Feng, Leman; Tong, Yiying; Desbrun, Mathieu (2019). "Despliegue del transporte paralelo: un enfoque de aprendizaje múltiple basado en conexiones". Revista SIAM de Álgebra y Geometría Aplicadas . 3 (2): 266–291. arXiv : 1806.09039 . doi :10.1137/18M1196133. ISSN  2470-6566.
4. M. Balasubramanian, EL Schwartz, El algoritmo de isomapas y la estabilidad topológica. Ciencia 4 de enero de 2002: vol. 295 núm. 5552 p. 7
5. A. Saxena , A. Gupta y A. Mukerjee . Reducción de dimensionalidad no lineal mediante isomapas localmente lineales . Apuntes de conferencias sobre informática , 3316:1038–1043, 2004.
6. H. Choi, S. Choi, Isomapa de núcleo robusto, reconocimiento de patrones, vol. 40, núm. 3, págs. 853-862, 2007

Enlaces externos

• Página web de Isomap en la Universidad de Stanford