Entradas

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)

 

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

Autor: Matteo Alberti

 

 

 

 

Entre metodologías principales  que hay en la  reducción lineal de dimensionalidad, tenemos las PCA o los componentes principales,estas son ciertamente las principales herramientas del Statistical Machine Learning.

Nos enfocamos muy a menudo en instrumentos que capturan el componente no lineal, el análisis de los componentes principales es el punto de partida para muchos análisis (y como una herramienta de preprocesamiento) y su conocimiento se vuelve imperativo en caso  que las condiciones en la linealidad sean satisfactorios.

En este tutorial vamos a presentar a nivel matemático la formación de los principales componentes de forma clara y concisa, como se implementa en python pero sobre todo su interpretación

“La idea básica es encontrar un sistema de referencia que maximice la varianza de las variables representadas”

Esto se hace dividiendo la varianza total en un número igual de variables de inicio, pero será posible reducir el número en función de la contribución que cada PC proporciona en la construcción de nuestra varianza total.

Nos gustaría recordarle que la aplicación de Análisis de Componentes Principales es útil cuando las variables de inicio no son independientes

 

Dado un conjunto de p variables cuantitativas X1, X2 ,. . . , Xp (variables centradas o estandarizadas) queremos determinar un nuevo conjunto de k variables t.c k≤p indicadas con Ys (s = 1,2, … k) que tienen las siguientes propiedades:

 

sin correlación, reproducir la mayor parte posible de la varianza restante después de la construcción de los primeros s-1 componentes, construido en orden creciente con respecto al porcentaje de varianza total que se reproducen, En promedio, no son nada

Como resultado, la combinación lineal será:

Por lo tanto, debemos encontrar los coeficientes v t.a.c que satisfacen nuestras propiedades.Este es un problema de restricción máxima donde la primera restricción se llama normalización:

Nuestro sistema es así:

Donde la varianza se puede expresar de la siguiente manera:

Y se resuelve mediante el método multiplicador de Lagrange:

Cálculo del gradiente de L1 y su cancelación obteniendo:

Donde   Este sistema admite infinitas soluciones (que respetan la restricción) al disminuir el rango de la matriz de coeficientes del sistema:

que corresponden a λs llamados valores propios de Σ.

Analogamente per la costruzione della seconda PCA (e cosi per tutte le altre) subentra al nostro sistema il Vincolo di Ortogonalità, dato dalla nostra richiesta che le PC siano incorrelate, esprimibile nel seguente modo:

De manera similar, para la construcción del segundo PCA (y para todos los demás), se agrega a nuestro sistema la Restricción de Ortogonalidad, le perdimos nuestra solicitud a los PC que estan sin correlación,podemos dar un ejemplo  de la siguiente manera:

Entonces al establecer la lagrangiana en p + 2 variables obtenemos:

De donde obtenemos el segundo valor propio de Y2 donde recordamos que se aplica la siguiente propiedad:

Propiedades de computador:

a) Cada valor propio de Σ tiene un papel en varianza respectiva del computador.

su valor es positivo

Varianza total

Varianza General

 

CRITERIOS DE SELECCIÓN:

Para la elección del número k (con k <p) de PC que se mantendrá en el análisis no existe un criterio universalmente aceptado y válido. Por lo tanto, es una buena práctica usarlos de forma conjunta y siempre tener en cuenta las necesidades del análisis. Expodremos los principales:

  1. a) Porcentaje acumulado de la varianza total reproducida:

 

                                                                                   

medida absoluta                           Normalización                                     Porcentaje acumulado

 

Establezca un umbral T en el porcentaje acumulado y mantenga el primer kPC en análisis que garantice que excede el umbral

 

b) Screen-Plot

Representa los valores propios con respecto al número de orden del componente

Donde se selecciona el primer k PC basado en la reducción de pendiente (también llamado criterio de codo). En este caso específico, los PC que se mantendrán en análisis serían los dos primeros.

 

c) Criterio Kaiser

También conocido como criterio de valor proprio mayor que 1 (válido solo para variables estandarizadas)

 

 

Vamos a implementar:

Importamos los paquetes necesarios de scikit-learn

import numpy as np

from sklearn.decomposition import PCA

La clase tiene los siguientes atributos:

Sklearn.decomposition.PCA(n_components=None, copy=True, whiten=False, svd_solver=’auto’, tol=0.0, iterated_power=’auto’, random_state=None)

Comentemos los principales parámetros:

  • n_components = número de componentes a analizar. Aconsejamos en una fase de elección no establecer este valor y evaluar en función de los criterios anteriores.
  • svd_solver = nos da algunas de las alternativas principales (arpack, randomized ..) queremos recordar que PCA no admite datos dispersos (para lo cual deberá cargar TruncatedSVD)

Vamos a probarlo en nuevos datos reales, por ejemplo, en los datos de Wine que se pueden importar a través del comando

from sklearn import datasets

import matplotlib.pyplot as plt

from mpl_toolkits.mplot3d import Axes3D

from sklearn import decomposition

En este punto vamos a implementar PCA y hacer un plot:

np.random.seed(123)
wine = datasets.load_wine()

X = wine.data

y = wine.target



fig = plt.figure(1, figsize=(5, 4))

plt.clf()

ax = Axes3D(fig, rect=[1, 0, 1, 0.9], elev=30, azim=222)



plt.cla()

pca = decomposition.PCA(n_components=None)

pca.fit(X)

X = pca.transform(X)





for name, label in [('Setosa', 0), ('Versicolour', 1), ('Virginica', 2)]:

ax.text3D(X[y == label, 0].mean(),

X[y == label, 1].mean() + 1.5,

X[y == label, 2].mean(), name,

bbox=dict(alpha=.5, edgecolor='b', facecolor='w'))

# Reorder the labels to have colors matching the cluster results

y = np.choose(y, [1, 2, 0]).astype(np.float)

ax.scatter(X[:, 0], X[:, 1], X[:, 2], c=y, cmap=plt.cm.spectral,

edgecolor='r')



ax.w_xaxis.set_ticklabels([])

ax.w_yaxis.set_ticklabels([])

ax.w_zaxis.set_ticklabels([])



plt.show()

Este será el gráfico que obtendremos:

Por lo tanto, vamos a seleccionar solo las primeras 3 variables de referencia