Riduzione della dimensionalità

processo consistente nella riduzione del numero di variabili considerate

La riduzione della dimensionalità, o riduzione della dimensione, è la trasformazione dei dati da uno spazio ad alta dimensione in uno spazio di dimensione minore, in modo che quest'ultima mantenga alcune proprietà significative dei dati originali, idealmente vicino 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 è solitamente 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.[1]

I metodi sono comunemente suddivisi in approcci lineari e non lineari.[1] Gli approcci possono anche essere suddivisi in selezione ed estrazione delle caratteristiche.[2] 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 caratteristicheModifica

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.[3]

Proiezione delle caratteristicheModifica

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à.[4][5] Per i dati multidimensionali, la rappresentazione tensoriale può essere utilizzata nella riduzione della dimensionalità attraverso l'apprendimento subspaziale multilineare .[6]

Analisi delle componenti principali (PCA)Modifica

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

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,[7][8] come l'astronomia.[9][10] NMF è ben noto sin dalla regola di aggiornamento moltiplicativo di Lee & Seung,[7] che è stata continuamente sviluppata: l'inclusione delle incertezze,[9] la considerazione dei dati mancanti e il calcolo parallelo, costruzione sequenziale[11] che porta alla stabilità e linearità di NMF,[10] così come altri aggiornamenti inclusa la gestione dei dati mancanti nell'elaborazione digitale delle immagini.[12]

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,[10] 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.[10]

Kernel PCAModifica

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-basedModifica

Tra le altre, alcune importanti tecniche non lineari sono tecnich di manifold learning, come Isomap, embedding localmente lineare (LLE),[13] Hessian LLE, automappe (eigenmap) laplaciane e metodi basati sull'analisi dello spazio tangente.[14][15] 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.[16] 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)Modifica

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

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.[17][18] 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.

AutocodificatoreModifica

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-SNEModifica

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.[19]

UMAPModifica

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 dimensioniModifica

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à .[20]

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.[21]

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,[22] "sketch",[23] o altre tecniche di ricerca per similarità ad alta dimensione dal toolbox della conferenza VLDB potrebbero essere l'unica opzione fattibile.

NoteModifica

  1. ^ a b Dimensionality Reduction: A Comparative Review (PDF), in J Mach Learn Res, vol. 10, 26 ottobre 2009, pp. 66–71.
  2. ^ P. Pudil e J. Novovičová, Novel Methods for Feature Subset Selection with Respect to Problem Knowledge, in Liu (a cura di), Feature Extraction, Construction and Selection, 1998, pp. 101, DOI:10.1007/978-1-4615-5725-8_7, ISBN 978-1-4613-7622-4.
  3. ^ Reducing Vector Space Dimensionality in Automatic Classification for Authorship Attribution, in Revista Ingeniería Electrónica, Automática y Comunicaciones, vol. 38, n. 3, 2017, pp. 26–35, ISSN 1815-5928 (WC · ACNP).
  4. ^ Samet, H. (2006) Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann. ISBN 0-12-369446-9
  5. ^ C. Ding, X. He, H. Zha, H.D. Simon, Adaptive Dimension Reduction for Clustering High Dimensional Data, Proceedings of International Conference on Data Mining, 2002
  6. ^ A Survey of Multilinear Subspace Learning for Tensor Data (PDF), in Pattern Recognition, vol. 44, n. 7, 2011, pp. 1540–1551, DOI:10.1016/j.patcog.2011.01.004.
  7. ^ a b Daniel D. Lee, Learning the parts of objects by non-negative matrix factorization, in Nature, vol. 401, n. 6755, 1999, pp. 788–791, DOI:10.1038/44565, PMID 10548103.
  8. ^ Algorithms for Non-negative Matrix Factorization (PDF), Advances in Neural Information Processing Systems, 2001.
  9. ^ a b Blanton, K-corrections and filter transformations in the ultraviolet, optical, and near infrared, in The Astronomical Journal, vol. 133, n. 2, 2007, pp. 734–754, DOI:10.1086/510127, arXiv:astro-ph/0606170.
  10. ^ a b c d Ren, Non-negative Matrix Factorization: Robust Extraction of Extended Structures, in The Astrophysical Journal, vol. 852, n. 2, 2018, pp. 104, DOI:10.3847/1538-4357/aaa1f2, arXiv:1712.10317.
  11. ^ (EN) Guangtun B. Zhu, Nonnegative Matrix Factorization (NMF) with Heteroscedastic Uncertainties and Missing data, 19 dicembre 2016.
  12. ^ Ren, Using Data Imputation for Signal Separation in High Contrast Imaging, in The Astrophysical Journal, vol. 892, n. 2, 2020, pp. 74, DOI:10.3847/1538-4357/ab7024, arXiv:2001.00563.
  13. ^ Sam T. Roweis e Lawrence K. Saul, Nonlinear Dimensionality Reduction by Locally Linear Embedding, in Science, vol. 290, n. 5500, 22 dicembre 2000, pp. 2323-2326, DOI:10.1126/science.290.5500.2323, PMID 11125150.
  14. ^ Zhenyue Zhang e Hongyuan Zha, Principal Manifolds and Nonlinear Dimensionality Reduction via Tangent Space Alignment, in SIAM J. Sci. Comput., vol. 26, n. 1, 2004, pp. 313–338, DOI:10.1137/s1064827502419154.
  15. ^ (EN) Yoshua Bengio, Martin Monperrus e Hugo Larochelle, Nonlocal Estimation of Manifold Structure, in MIT Press, vol. 18, n. 10, 2006, pp. 2509-2528, DOI:10.1162/neco.2006.18.10.2509, PMID 16907635.
  16. ^ Hongbing Hu, Stephen A. Zahorian, (2010) "Dimensionality Reduction Methods for HMM Phonetic Recognition", ICASSP 2010, Dallas, TX
  17. ^ G. Baudat e F. Anouar, Generalized Discriminant Analysis Using a Kernel Approach, vol. 12, 2000, DOI:10.1162/089976600300014980, PMID 11032039.
  18. ^ CloudID: Trustworthy cloud-based and cross-enterprise biometric identification, in Expert Systems with Applications, vol. 42, n. 21, 30 novembre 2015, pp. 7905-7916, DOI:10.1016/j.eswa.2015.06.025.
  19. ^ (EN) Intrinsic t-Stochastic Neighbor Embedding for Visualization and Outlier Detection, in Similarity Search and Applications, Lecture Notes in Computer Science, vol. 10609, Springer International Publishing, 2017, pp. 188–203, DOI:10.1007/978-3-319-68474-1_13, ISBN 978-3-319-68474-1.
  20. ^ Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, Uri Shaft (1999) "When is "nearest neighbor" meaningful?". Database Theory—ICDT99, 217–235
  21. ^ B. Shaw e T. Jebara, Structure preserving embedding (PDF), in Proceedings of the 26th Annual International Conference on Machine Learning – ICML '09, 2009, p. 1, DOI:10.1145/1553374.1553494, ISBN 9781605585161.
  22. ^ E. Bingham e H. Mannila, Random projection in dimensionality reduction, in Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining – KDD '01, 2001, pp. 245, DOI:10.1145/502512.502546, ISBN 978-1581133912.
  23. ^ Shasha, D High (2004) Performance Discovery in Time Series Berlin: Springer. ISBN 0-387-00857-8

Collegamenti esterniModifica

Controllo di autoritàGND (DE4224279-4
  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica