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 un colector de datos basado en una estimación aproximada de los vecinos de cada punto de datos en el colector. Isomap es altamente eficiente y generalmente aplicable a una amplia gama de fuentes de datos y dimensionalidades.
Introducción
Isomap es un representante de los métodos de mapeo isométrico y extiende la escala métrica multidimensional (MDS) incorporando las distancias geodésicas impuestas por un gráfico ponderado. Para ser específicos, 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 usando 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 incrustado 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 de la ruta más corta entre dos nodos (calculada utilizando el algoritmo de Dijkstra , por ejemplo). Los n primeros vectores propios de la matriz de distancia geodésica , representan las coordenadas en el nuevo espacio euclidiano n- dimensional.
Algoritmo
A continuación se ofrece una descripción de muy alto nivel del algoritmo Isomap .
- Determina los vecinos de cada punto.
- Todos los puntos en un radio fijo.
- K vecinos más cercanos.
- Construya una gráfica de vecindad.
- Cada punto está conectado con otro si K es un vecino más cercano.
- Longitud del borde igual a la distancia euclidiana.
- Calcule la ruta más corta entre dos nodos.
- Calcule la incrustación de dimensiones inferiores.
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 la escala multidimensional (MDS) se modifican y todo lo demás no se ve afectado. [2]
- Despliegue de transporte paralelo : reemplaza las estimaciones de distancia geodésica basadas en trayectorias de Dijkstra por aproximaciones basadas en transporte paralelo , lo que mejora 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 distancia geodésica, 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 aproximar las rutas geodésicas con precisión. 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 , el MDS métrico se puede interpretar como PCA del kernel . De manera similar, la matriz de distancia geodésica en Isomap puede verse como una matriz de núcleo . La matriz de distancia geodésica doblemente centrada K en Isomap tiene la forma
dónde es el cuadrado de elementos de la matriz de distancia geodésica D = [ D ij ], H es la matriz de centrado, dada por
Sin embargo, la matriz del núcleo K no siempre es semidefinita positiva . La idea principal para el kernel Isomap es hacer esta K como una matriz del kernel de Mercer (que es semidefinida positiva) usando un método de cambio constante, para relacionarlo con el kernel PCA de manera que la propiedad de generalización emerja naturalmente. [6]
Ver también
Referencias
- ^ JB Tenenbaum, V. de Silva, JC Langford, Un marco geométrico global para la reducción de dimensionalidad no lineal, Ciencia 290, (2000), 2319-2323.
- ^ a b "Métodos globales versus locales en la reducción de dimensionalidad no lineal" (PDF) . Consultado el 9 de septiembre de 2014 .
- ^ Budninskiy, Max; Yin, Gloria; Feng, Leman; Tong, Yiying; Desbrun, Mathieu (2019). "Despliegue de transporte paralelo: un enfoque de aprendizaje múltiple basado en conexión" . Revista SIAM de Álgebra Aplicada y Geometría . 3 (2): 266-291. arXiv : 1806.09039 . doi : 10.1137 / 18M1196133 . ISSN 2470-6566 .
- ^ M. Balasubramanian, EL Schwartz, El algoritmo Isomap y la estabilidad topológica. Science 4 de enero de 2002: Vol. 295 no. 5552 p. 7
- ^ A. Saxena , A. Gupta y A. Mukerjee . Reducción de dimensionalidad no lineal por isomapas localmente lineales . Lecture Notes in Computer Science , 3316: 1038–1043, 2004.
- ^ H. Choi, S. Choi, Isomap de núcleo robusto, Reconocimiento de patrones, Vol. 40, núm. 3, págs. 853-862, 2007