Icone color1 06

Métodos para la reducción de la dimensionalidad manifold-based: el caso ISOMAP

Autor: Matteo Alberti


 

En este tutorial veremos una miniserie dedicada a métodos de reducción de dimensionalidad basados en una estructura matemática llamada Manifold.

Entonces, primero que todo comprendamos qué es un Manifold, cuándo es útil y cómo aplicarlo, pero sin entrar en detalles sobre la estructura y las propiedades matemáticas.

“Manifold no es más que un espacio matemático donde viene recreado localmente un espacio euclidiano (de una dimensión específica) pero no a nivel global”

Entonces, ¿cuándo y cómo vamos a aplicar métodos basados en Manifold?

La respuesta es simple: cuando fallan los métodos lineales

Investigemos con más profundidad:

 

Ejemplo:

En los métodos lineales (como PCA, MDS, SVD), nuestros datos pueden redimensionarse solo mediante combinaciones lineales de nuestras características, esto significa que no se encuentran estructuras más complejas y no lineales, y por lo tanto se discriminan.

Veamos un ejemplo gráfico:

Metodos Lineares reduciríamos los datos al perder la estructura geométrica. Como se muestra en la figura, se abordarán los puntos X1 y X2  estos se ven mas cerca.(y, por lo tanto, toda la estructura sería “aplanada”)

Metodos Manifold,

los principales son:

  • ISOMAP
  • Local Linear Embedding (LLE)

 

Esta idea básica nos permite resolver muchos problemas no solo en la fase de preproceso (en la computadora Vision, por ejemplo, nos permite resolver problemas de: estimación de posición, compresión de datos, reducción de ruido en la imagen e interpolación de datos faltantes)

 

 

ISOMAP

Comencemos con la primera herramienta:

El algoritmo consta de tres fases:

(1)

Determinar el número de vecinos (neighbors) en Manifold ( basadonde según las distancias euclidianas). Para cada punto, asignaremos los vecinos (determinados según el número de vecinos fijados como en el algoritmo K-NN o en función de un radio fijo)

 

El radio/ el número de vecinos es constante

(2)

En este paso, calcularemos la geodésica. Por lo tanto, calcularemos la distancia de cada par de puntos pero no trabajará en un espacio euclidiano, corresponderá con el camino más corto entre todos los caminos posibles para conectar dos puntos en el colector. Un ejemplo de uso común puede ser el algoritmo Djkstra, muy común en el cálculo de la navegación por carretera.

(3)

En este último paso aplicaremos un MDS (escalado multidimensional) a la matriz de distancia de las geodésicas para reconstruirlo en un espacio euclidiano que mantendrá la misma estructura geométrica. Los vectores de coordenadas en el espacio euclidiano se eligen para minimizar la siguiente función de costo:

  • Dy corresponde a las matriz de las distancias Euclidee
  • L2 corresponde a la raíz cuadrada de la suma de los elementos
  • τ no es más que una función de conversión (las distancias se reemplazan en productos internos) para utilizar algoritmos de optimización eficientes

 

 

Implementémoslo en Python:

En primer lugar, importamos los paquetes necesarios de  scikit-learn


import numpy as np

import matplotlib.pyplot as plt

from sklearn import manifold

 

entonces:

OUR_DATA= manifold.Isomap(n_neighbors=N, n_components=C, eigen_solver=’auto’, tol=0, max_iter=None, path_method=’auto’, neighbors_algorithm=’auto’, n_jobs=1)

 

Analicemos los parámetros principales:
• n_ neighbors = Número entero, que corresponde al número de vecinos
• n_ components = Integer, generalmente establecido de manera predeterminada en 2. Corresponde al número de coordenadas en el espacio del Colector
• path_method = default ‘auto’, FW para Floyd-Warshall, D para el algoritmo Djkstra establece cómo calcular las distancias en el gráfico

Si queremos ir a imprimir un gráfico con los tiempos de ejecución relativos:

 

from time import time

t0=time()

ISOMAP_DATA= manifold.Isomap(n_neighbors, n_components=2).fit_transform(OUR_DATA)

t1=time()

print("%s: %.2g sec" % ('ISO' t1-t0))

plot.embedding(ISOMAP_DATA, "ISOMAP ottenuto in " % (t1-t0)

plot.show()

Hacemos dos últimas consideraciones de uso práctico:

ISOMAP resulta ser una herramienta de reducción muy efectiva que nos permite eludir muchos problemas relacionados con la linealidad, pero es capaz de preservar una estructura geométrica local naturalmente es a expensas de algunos factores, en particular:
• Sensible a outliers
• Pocos parámetros libres

Esto se debe a que la funcionalidad del algoritmo depende principalmente de la elección de algunos parámetros (la elección del número de vecinos), de hecho, incluso unos pocos valores atípicos pueden, de alguna manera, reunir porciones de datos que de otra manera deberían ser discriminados.
Por este motivo, ISOMAP es muy recomendable cuando ya tenemos algunas ideas sobre la estructura de datos porque, comparado con otros métodos lineales, es computacionalmente más intensivo.

En el próximo tutorial abordaremos LLE, el segundo de nuestros métodos basados en Manifold.

 

Referencias
• http://scikit-learn.org/stable/index.html (Official Website of Scikit libraries)
• http://web.mit.edu/cocosci/Papers/sci_reprint.pdf (documentazione su ISOMAP)