Isomap

Isomap es un método de reducción de dimensionalidad no lineal . Es uno de los 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 altamente eficiente y generalmente aplicable a una amplia gama de fuentes de datos y dimensionalidades.

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 grafo ponderado. Específicamente, el escalamiento clásico del MDS métrico realiza una incrustación de baja dimensión basada en la distancia entre pares de puntos de datos, que generalmente se mide utilizando la distancia euclidiana en línea recta . Isomap se distingue por su uso de la distancia geodésica inducida por un grafo de vecindad incrustado en el escalamiento clásico. Esto se hace para incorporar la estructura de la variedad en la incrustación resultante. Isomap define la distancia geodésica como la suma de los pesos de las aristas a lo largo del camino más corto entre dos nodos (calculado utilizando el algoritmo de Dijkstra , por ejemplo). Los n autovectores superiores de la matriz de distancia geodésica representan las coordenadas en el nuevo espacio euclidiano n -dimensional.

A continuación se ofrece una descripción general del algoritmo Isomap .

• Determina los vecinos de cada punto.
  • Todos los puntos dentro de un radio fijo.
  • K vecinos más cercanos.
• Construye un grafo de vecindad.
  • Cada punto está conectado a otro si es un vecino más cercano de K.
  • La longitud de la arista es igual a la distancia euclidiana.
• Calcula la ruta más corta entre dos nodos.
  • El algoritmo de Dijkstra
  • Algoritmo de Floyd-Warshall
• Calcular la incrustación de menor dimensión.
  • Escalamiento multidimensional

• LandMark ISOMAP (L-ISOMAP) : Landmark-Isomap es una variante de Isomap que es más rápida que Isomap. Sin embargo, la precisión de la variedad se ve comprometida por un factor marginal. En este algoritmo, se utilizan n << N puntos de referencia de un 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) a 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, mientras que todo lo demás permanece inalterado. ^{[ 2 ]}
• Despliegue de transporte paralelo : Reemplaza las estimaciones de distancia geodésica basadas en la ruta de Dijkstra con aproximaciones basadas en el transporte paralelo , mejorando la robustez ante irregularidades y vacíos en el muestreo. ^{[ 3 ]}

La conectividad de cada punto de datos en el grafo 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 de la variedad o si el ruido en los datos desplaza ligeramente los puntos fuera de la variedad. ^{[ 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 grafo de vecindad puede volverse demasiado disperso para aproximar con precisión las trayectorias geodésicas. Sin embargo, se han realizado mejoras en este algoritmo para que funcione mejor con conjuntos de datos dispersos y ruidosos. ^{[ 5 ]}

Siguiendo la conexión entre el escalamiento clásico y el PCA , el MDS métrico puede interpretarse como PCA de núcleo (KPCA). 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

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

dónde${\displaystyle D^{2}=D_{ij}^{2}:=(D_{ij})^{2}}$es el cuadrado elemento a elemento de la matriz de distancia geodésica D = [ D _ij ], H es la matriz de centrado, dada por

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

Sin embargo, la matriz del núcleo K no siempre es semidefinida positiva . La idea principal para el isomap del núcleo es hacer que esta K sea una matriz del núcleo de Mercer (es decir, semidefinida positiva) utilizando un método de desplazamiento de constantes, para relacionarla con el PCA del núcleo de manera que la propiedad de generalización surja naturalmente. ^{[ 6 ] [ 7 ] [ 8 ]} Los primeros que demostraron que el PCA del núcleo ~ métodos de aprendizaje de variedades fueron Bengio et al. en la Conferencia sobre Sistemas de Procesamiento de Información Neuronal 2003 (NeurIPS'03). ^{[ 6 ]}

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

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