Riduzione della dimensionalità

La riduzione della dimensionalità, o riduzione della dimensione, è la trasformazione dei dati da uno spazio di dimensione più alta a uno di dimensione minore, in modo che questa rappresentazione mantenga alcune proprietà significative dei dati di origine, idealmente vicina alla sua dimensione intrinseca. Lavorare con spazi ad alta dimensionalità può essere indesiderabile per molte ragioni: i dati grezzi sono spesso sparsi come conseguenza della "maledizione della dimensionalità" e l'analisi dei dati è di solito più computazionalmente sconveniente. La riduzione della dimensionalità è comune nei campi che trattano un gran numero di osservazioni o un gran numero di variabili, come l'elaborazione del segnale, il riconoscimento vocale, la neuroinformatica e la bioinformatica.

I metodi sono comunemente suddivisi in approcci lineari e non lineari. Gli approcci possono anche essere suddivisi in selezione ed estrazione delle caratteristiche. La riduzione della dimensionalità può essere utilizzata per la riduzione del rumore, la visualizzazione dei dati, l'analisi dei cluster o come passaggio intermedio per facilitare altre analisi.

Selezione delle caratteristiche

Gli approcci alla selezione delle caratteristiche cercano di trovare un sottoinsieme delle variabili di input (chiamate anche caratteristiche o attributi o feature). Le tre strategie sono: la strategia del filtro (es. guadagno di informazioni ), la strategia wrapper (es. ricerca guidata dall'accuratezza) e la strategia incorporata (le caratteristiche selezionate vengono aggiunte o rimosse durante la costruzione del modello in base agli errori di previsione).

L'analisi dei dati come la regressione o la classificazione può essere eseguita nello spazio ridotto in modo più accurato rispetto allo spazio originale.

Proiezione delle caratteristiche

La proiezione delle caratteristiche (chiamata anche estrazione delle caratteristiche) trasforma i dati dallo spazio ad alta dimensione a uno spazio con meno dimensioni. La trasformazione dei dati può essere lineare, come nell'analisi delle componenti principali (PCA), ma esistono anche molte tecniche non lineari per la riduzione della dimensionalità. Per i dati multidimensionali, la rappresentazione tensoriale può essere utilizzata nella riduzione della dimensionalità attraverso l'apprendimento subspaziale multilineare .

Decomposizione ai valori singolari (SVD)

La decomposizione ai valori singolari (SVD dall'inglese Singular Value Decomposition) è alla base di tutte le tecniche di riduzione lineare della dimensionalità. Data una matrice $X_{n\times k}$ questa può essere espressa come il prodotto di tre matrici $X=U\cdot \Sigma \cdot V^{T}$ tali che:

• $U_{n\times k}$ ha le colonne tra loro ortonormali, ovvero $U^{T}U=I_{k\times k}$
• $\Sigma _{k\times k}$ è una matrice diagonale che ha come valori sulla diagonale i valori singolari: $\Sigma =diag(\sigma _{1},\dots ,\sigma _{k})$
• $V_{k\times k}$ è una matrice ortogonale, ovvero $V^{T}V=VV^{T}=I_{k\times k}$

Per la riduzione della dimensionalità, risulta utile considerare la formula alternativa, essendo $\Sigma$ diagonale si può scrivere

$X=U\cdot \Sigma \cdot V^{T}=\sum _{i=1}^{k}\sigma _{i}u_{i}v_{i}^{T}=\sum _{i=1}^{k}\sigma _{i}Z_{i}$

dove

• $\sigma _{i}$ è l'i-esimo valore singolare
• $u_{i}$ è l'i-esima colonna di $U$
• $v_{i}$ è l'iesima colonna di $V$
• $Z_{i}$ è una matrice a rango 1 ottenuta dal prodotto $u_{i}v_{i}^{T}$

Dal teorma di Eckart-Young la miglior approssimazione nella norma di Frobenius di $X$ ad una matrice di rango inferiore è data da $\sum _{i=1}^{p}\sigma _{i}Z_{i}$. Dove $p<k$ è il rango a cui vogliamo approssimare e i valori singolari sono ordinati in maniera decrescente. Avendo approssimato $X$ ad una matrice di rango inferiore possiamo facilmente convertirla nella relativa matrice ${\hat {X}}_{n\times p}=U_{[p]}\Sigma _{[p]}$ dove

• $U_{[p]}$ è la matrice $n\times p$ costituita dalle prime $p$ colonne di $U$
• $\Sigma _{[p]}$ è la matrice $p\times p$ diagonale che contiene i primi $p$ valori singolari ordinati in maniera decrescente.

L'analisi delle componenti principali è un caso specifico dell'SVD. Infatti la PCA è l'SVD applicata alla matrice dei dati centrati.

Analisi delle componenti principali (PCA)

L'analisi delle componenti principali (la principale tecnica lineare per la riduzione della dimensionalità) esegue una mappa lineare dei dati in uno spazio a dimensione inferiore in modo tale che la varianza dei dati nella rappresentazione a bassa dimensione sia massima. In pratica, si costruisce la matrice della covarianza (o talvolta correlazione) dei dati e si calcolano gli autovettori. Quelli che corrispondono agli autovalori maggiori (le componenti principali) possono ora essere utilizzati per ricostruire una grande frazione della varianza dei dati originali. Inoltre, i primi autovettori possono spesso essere interpretati in termini del comportamento fisico del sistema su larga scala, perché spesso contribuiscono alla maggior parte dell'energia del sistema, specialmente nei sistemi a bassa dimensionalità. Tuttavia, questo deve essere dimostrato caso per caso poiché non tutti i sistemi mostrano questo comportamento. Lo spazio originale (con dimensione del numero di punti) è stato ridotto (con perdita di dati, ma idealmente conservando la varianza più importante) allo spazio coperto da pochi autovettori.

Fattorizzazione a matrice non negativa (NMF)

NMF decompone una matrice non negativa nel prodotto di due non negative, che è stato uno strumento promettente in campi in cui esistono solo segnali non negativi, come l'astronomia. NMF è ben noto sin dalla regola di aggiornamento moltiplicativo di Lee & Seung, che è stata continuamente sviluppata: l'inclusione delle incertezze, la considerazione dei dati mancanti e il calcolo parallelo, costruzione sequenziale che porta alla stabilità e linearità di NMF, così come altri aggiornamenti inclusa la gestione dei dati mancanti nell'elaborazione digitale delle immagini.

Con una base di componenti stabili durante la costruzione e un processo di modellazione lineare, l'NMF sequenziale è in grado di preservare il flusso nell'imaging diretto delle strutture circumstellari in astronomia, come uno dei metodi per rilevare gli esopianeti, in particolare per il imaging dei dischi circumstellari. Rispetto a PCA, NMF non rimuove la media delle matrici, il che porta a flussi non negativi non fisici; pertanto NMF è in grado di conservare più informazioni rispetto alla PCA come dimostrato da Ren et al.

Kernel PCA

L'analisi delle componenti principali può essere impiegata in modo non lineare mediante il metodo kernel. La tecnica risultante è in grado di costruire mappature non lineari che massimizzano la varianza nei dati. Questa tecnica è chiamata kernel PCA.

Kernel PCA graph-based

Tra le altre, alcune importanti tecniche non lineari sono tecnich di manifold learning, come Isomap, embedding localmente lineare (LLE), Hessian LLE, automappe (eigenmap) laplaciane e metodi basati sull'analisi dello spazio tangente. Queste tecniche costruiscono una rappresentazione dei dati a bassa dimensionalità utilizzando una funzione di costo che conserva le proprietà locali dei dati e può essere vista come la definizione di un kernel graph-based per il metodo kernel PCA.

Più recentemente, sono state proposte tecniche che, invece di definire un kernel fisso, cercano di imparare il kernel usando la programmazione semidefinita. L'esempio più eminente di tale tecnica è il maximum variance unfolding (MVU, letteralmente "dispiegamento della massima varianza"). L'idea centrale di MVU è di preservare esattamente tutte le distanze a coppie tra i primi vicini, massimizzando le distanze tra i punti che non sono primi vicini.

Un approccio alternativo alla conservazione dei punti vicini è attraverso la minimizzazione di una funzione di costo che misura le differenze tra le distanze negli spazi di input e output. Esempi importanti di tali tecniche includono: scaling multidimensionale classico, che è identico a PCA; Isomap, che utilizza le distanze geodetiche nello spazio dati; mappe di diffusione, che utilizzano distanze di diffusione nello spazio dei dati; t-distributed stochastic neighbor embedding (t-SNE), che minimizza la divergenza tra le distribuzioni su coppie di punti; e analisi delle componenti curvilinee.

Un approccio diverso alla riduzione della dimensionalità non lineare è attraverso l'uso di autoencoder, un tipo speciale di reti neurali feed-forward con uno strato nascosto a collo di bottiglia. L'addestramento degli encoder profondi viene in genere eseguito utilizzando un avido pre-addestramento a strati (ad esempio, utilizzando una pila di macchine Boltzmann limitate) che è seguito da una fase di fine-tuning basata sulla retropropagazione.

Analisi discriminante lineare (LDA)

L'analisi discriminante lineare (LDA) è una generalizzazione del discriminante lineare di Fisher, un metodo utilizzato in statistica, riconoscimento di modelli e apprendimento automatico per trovare una combinazione lineare di caratteristiche che caratterizza o separa due o più classi di oggetti o eventi.

Analisi discriminante generalizzata (GDA)

GDA si occupa dell'analisi discriminante non lineare utilizzando l'operatore di funzione del kernel. La teoria sottostante è vicina alle macchine a vettori di supporto (SVM) nella misura in cui il metodo GDA fornisce una mappatura dei vettori di input nello spazio delle caratteristiche ad alta dimensione. Simile a LDA, l'obiettivo di GDA è trovare una proiezione per le caratteristiche in uno spazio dimensionale inferiore massimizzando il rapporto tra dispersione tra classi e dispersione all'interno della classe.

Autocodificatore

Gli autocodificatori, o autoencoder, possono essere utilizzati per apprendere le funzioni e le codifiche di riduzione delle dimensioni non lineari insieme a una funzione inversa dalla codifica alla rappresentazione originale.

t-SNE

L'algoritmo t-distributed stochastic neighbor embedding (t-SNE) è una tecnica di riduzione della dimensionalità non lineare utile per la visualizzazione di set di dati ad alta dimensionalità. Non è raccomandato per l'uso in analisi come il clustering o il rilevamento di valori anomali poiché non conserva necessariamente bene densità o distanze.

UMAP

L'approssimazione e proiezione di varietà uniformi (UMAP) è una tecnica di riduzione della dimensionalità non lineare. Visivamente, è simile a t-SNE, ma assume che i dati siano distribuiti uniformemente su una varietà riemanniana localmente connessa e che la metrica riemanniana sia localmente costante o approssimativamente localmente costante.

Riduzione delle dimensioni

Per set di dati ad alta dimensionalità (cioè con un numero di dimensioni superiore a 10), la riduzione delle dimensioni viene solitamente eseguita prima di applicare un algoritmo K-nearest neighbors (k-NN) per evitare gli effetti della maledizione della dimensionalità .

L'estrazione delle caratteristiche e la riduzione delle dimensioni possono essere combinate in un unico passaggio utilizzando l'analisi delle componenti principali (PCA), l'analisi discriminante lineare (LDA), l'analisi di correlazione canonica (CCA) o le tecniche di fattorizzazione a matrice non negativa (NMF) come fase di pre-elaborazione seguita mediante clustering di K-NN su vettori di caratteristiche in spazi di dimensioni ridotte. Nell'apprendimento automatico questo processo è anche chiamato embedding a bassa dimensione.

Per set di dati con dimensioni molto elevate (ad es. quando si esegue una ricerca di somiglianza su flussi video in diretta, dati del DNA o serie temporali ad alta dimensione) eseguire una ricerca K-NN approssimativa veloce utilizzando locality-sensitive hashing, proiezione casuale, "sketch", o altre tecniche di ricerca per similarità ad alta dimensione dal toolbox della conferenza VLDB potrebbero essere l'unica opzione fattibile.

Collegamenti esterni

• Edizione speciale JMLR sulla selezione di variabili e funzioni
• MAP elastiche Archiviato il 20 luglio 2011 in Internet Archive.
• Incorporamento lineare locale
• Confronto visivo di vari metodi di riduzione della dimensionalità
• Un quadro geometrico globale per la riduzione della dimensionalità non lineare

Controllo di autorità	GND (DE) 4224279-4