Icone color1 06

Metodi per la riduzione della dimensionalità basati sulla Varietà differenziabile: il caso ISOMAP

Autore: Matteo Alberti


 

In questo tutorial andiamo ad aprire una mini serie dedicata ai metodi di riduzione della dimensionalità basati su una struttura matematica chiamata Varietà differenziabile (Manifold)

Andiamo dunque a capire che cosa sia una Varietà differenziabile, quando risulta utile e come applicarlo senza però entrare nel dettaglio sulla struttura e sulle proprietà matematiche.

“Manifold non è altro che uno spazio matematico dove localmente viene a ricrearsi uno spazio euclideo (di una specifica dimensione) ma non a livello globale”

Quindi quando e come andremo ad applicare questa serie di metodi?

La risposta è semplice: Quando i metodi lineari falliscono

 

Andiamo ad indagare in maniera più approfondita:


 

Esempio:

Nei metodi lineari (come PCA, MDS, SVD) i nostri dati possono essere ridimensionati solo attraverso combinazioni lineari delle nostre features, ciò comporta che strutture più complesse e non lineari non vengono scovate e dunque discriminate.

Riportiamo un esempio grafico:

 

Metodi Lineari ci ridurrebbero i dati perdendo la struttura geometrica. Come mostra in figura i punti X1 ed X2 risulterebbero avvicinati (e cosi tutta la struttura risulterebbe “appiattita”)

Metodi basati sulla Varietà differenziabile contrariamente ci riescono. I principali sono:

  • ISOMAP
  • Local Linear Embedding (LLE)

 

Vogliamo ricordare che il nostro obiettivo è “preservare la geometria locale”


 

Questa idea di base ci permette di risolvere molti problemi non solo in fase di pre-processing (Nella computer Vision per esempio ci permette di risolvere problemi di: Stima della posizione, compressione dei dati, riduzione del rumore nell’immagine ed interpolazione di dati mancanti)

 

 

ISOMAP

Iniziamo dunque con il primo strumento:

L’algoritmo si compone di tre fasi:

  • Determinare il numero di vicini (neighbors) sul Manifold (basandola sulle distanze Euclidea)

Per ogni punto andremo a mappare i vicini (determinati in base al numero di vicini fissato come nell’algoritmo K-NN o in base ad un raggio fissato)

 

  • In questo step andremo a stimare la Geodetica. Andremo dunque a calcolare la distanza di ogni coppia di punti ma non lavorando in uno spazio Euclideo esso corrisponderà al percorso più breve fra tutti i possibili percorsi per collegare due punti nel manifold. Un esempio di comune utilizzo può esser l’algoritmo di Djkstra, molto comune nel calcolo di della navigazione stradale.
  • In questo ultimo step andremo ad applicare una MDS (multidimensional scaling) alla matrice di distanze della geodetica al fine di ricostruirlo in uno spazio Euclideo che manterrà la stessa struttura geometrica. I vettori di coordinate nello spazio euclideo sono scelti per minimizzare la seguente funzione di costo:


Dy corrisponde alla matrice di distanze Euclidee

L2 corrisponde alla radice quadrata della somma degli elementi

τ non è altro che una funzione di conversione (le distanze vengono sostituite in prodotti interni) al fine di utilizzare algoritmi di ottimizzazione efficienti.


 

 

Andiamo ad implementarlo in Python:

Prima di tutto importiamo i pacchetti necessari di scikit-learn

import numpy as np

import matplotlib.pyplot as plt

from sklearn import manifold

 

La nostra classe sarà cosi articolata:

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)

Andiamo ad analizzare i parametri principali:

  • n_ neighbors= Numero intero, corrisponde al numero di vicini
  • n_ components= Numero intero, generalmente impostato di default su 2. Corrisponde al numero di coordinate nello spazio del Manifold
  • path_ method= di default ’auto’, FW per Floyd-Warshall, D per l’algoritmo di Djkstra imposta in che modo calcolare le distanze nel grafo.

 

 

Se vogliamo andare a stampare un grafico con i relativi tempi di esecuzione:

 

 

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()

Facciamo due ultime considerazioni di utilizzo pratico:

 

ISOMAP risulta esser uno strumento di riduzione molto efficace che ci permette di bypassare molti problemi legati alla linearità ma il poter preservare una struttura geometrica locale naturalmente è a discapito di alcuni fattori, in particolare:

  • Sensibile ad outliers
  • Pochi parametri liberi

Questo perché la funzionalità dell’algoritmo dipende principalmente dalla scelta di pochi parametri (la scelta del numero dei vicini) infatti anche solo pochi valori outliers possono in qualche modo avvicinare porzioni di dati che dovrebbero contrariamente venir discriminati.

Per questo motivo ISOMAP è altamente consigliato quando abbiamo già qualche idea sulla struttura dei dati anche perché rispetto ad altri metodi lineari risulta computazionalmente più intensivo.

 

Nel Prossimo tutorial andremo ad affrontare LLE, il secondo dei nostri metodi basati sul Manifold.

 

Riferimenti

http://scikit-learn.org/stable/index.html (Official Website of Scikit libraries)

http://web.mit.edu/cocosci/Papers/sci_reprint.pdf  (documentazione su ISOMAP)

0 commenti

Lascia un Commento

Vuoi partecipare alla discussione?
Fornisci il tuo contributo!

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *