Approssimazione di matrici in flussi di dati

Approximation of matrices in data streams

Approssimare una matrice senza avere tutte le sue righe

Image credit: unsplash.com

L’approssimazione di matrici è un sotto-campo molto studiato nell’ambito dell’analisi dei dati e dell’apprendimento automatico. Un ampio insieme di compiti di analisi dei dati si basa sull’ottenimento di un’approssimazione a basso rango delle matrici. Esempi sono la riduzione della dimensionalità, la rilevazione di anomalie, la denoising dei dati, il clustering e i sistemi di raccomandazione. In questo articolo, esamineremo il problema dell’approssimazione di matrici e come calcolarlo quando non si ha a disposizione l’intero set di dati!

Il contenuto di questo articolo è in parte tratto dalla mia lezione presso Stanford – corso CS246. Spero che lo troviate utile. Trovate il contenuto completo qui.

Dati come una matrice

La maggior parte dei dati generati sul web può essere rappresentata come una matrice, in cui ogni riga della matrice è un punto dati. Ad esempio, nei router ogni pacchetto inviato sulla rete è un punto dati che può essere rappresentato come una riga in una matrice di tutti i punti dati. Nel settore del commercio al dettaglio, ogni acquisto effettuato è una riga nella matrice di tutte le transazioni.

Figura 1: Dati come una matrice - Immagine dell'autore

Allo stesso tempo, quasi tutti i dati generati sul web hanno una natura di streaming; il che significa che i dati vengono generati da una fonte esterna a una velocità rapida su cui non abbiamo controllo. Pensate a tutte le ricerche che gli utenti effettuano sul motore di ricerca di Google ogni secondo. Chiamiamo questi dati i dati di streaming; perché proprio come un flusso, si riversano.

Alcuni esempi di tipici dati su larga scala di streaming web sono i seguenti:

Figura 2: Dimensione tipica dei dati su larga scala di streaming web - Immagine dell'autore

Pensate ai dati di streaming come una matrice A contenente n righe in uno spazio d-dimensionale, dove tipicamente n >> d. Spesso n è dell’ordine dei miliardi e in aumento.

Modello di streaming dati

Nel modello di streaming, i dati arrivano ad alta velocità, una riga alla volta, e gli algoritmi devono elaborare gli elementi rapidamente, altrimenti vengono persi per sempre.