Lo scaling multidimensionale (MDS, dall'inglese MultiDimensional Scaling) è una tecnica di riduzione della dimensionalità spesso utilizzata in analisi statistica e apprendimento automatico per mostrare graficamente le differenze o somiglianze tra elementi di un insieme. Essa è una generalizzazione del concetto di ordinamento: partendo da una matrice quadrata, contenente la "somiglianza" di ogni elemento di riga con ogni elemento di colonna, l'algoritmo assegna a ogni elemento una posizione in uno spazio N-dimensionale, con N stabilito a priori. Se N è sufficientemente piccolo, questo spazio può essere rappresentato con un grafo o una visualizzazione 3D. In pratica questa tecnica parte con un sistema con tante dimensioni quanti gli elementi del sistema e riduce le dimensioni fino a un certo numero N. Nel fare questo quindi c'è un'inevitabile perdita di informazione (loss) ed esistono quindi diversi algoritmi di scaling multidimensionale, che si adattano meglio alle diverse situazioni di utilizzo.

MDS venne proposto inizialmente all'Università di Princeton da Warren S. Torgerson all'inizio degli anni 50, nell'ambito di una ricerca in psicologia. Un importante contributo è venuto da Joseph Bernard Kruskal.

In Dettaglio

Si supponga che i dati da analizzare siano costituiti da una collezione di oggetti (colori, immagini,...) sui quali sia definita una funzione di distanza,

distanza tra gli oggetti di indice e .

Tali distanze sono gli elementi di una matrice di dissimilarità

L'obiettivo di MDS è, data , quello di trovare vettori tali che

per ogni ,

dove è una norma vettoriale. NellMDS classico, tale norma è la distanza euclidea, ma, per estensione, potrebbe essere una metrica o una funzione di distanza arbitraria.Kruskal, J. B., and Wish, M. (1978), Multidimensional Scaling, Sage University Paper series on Quantitative Application in the Social Sciences, 07-011. Beverly Hills and London: Sage Publications. Ad esempio, se si trattano dati di tipi misti contenenti descrittori numerici ma anche categorici, un'alternativa comunemente usata è la distanza di Gower.

In altre parole, MDS cerca di trovare una mappatura degli oggetti su tale che le distanze siano preservate. Se si sceglie una dimensionalità pari a 2 o 3, si possono riprodurre i vettori in una visualizzazione che mostri le similarità fra gli oggetti. Si noti che i vettori non sono unici: con l'uso della distanza euclidea, essi possono essere arbitrariamente traslati, ruotati e riflessi, dato che tali trasformazioni non cambiano le distanze per coppie di vettori.Il simbolo indica l'insieme dei numeri reali e la notazione si riferisce al prodotto cartesiano di copie di , il quale costituisce uno spazio vettoriale -dimensionale sul campo dei numeri reali.

Ci sono vari approcci atti a determinare i vettori . Solitamente, MDS viene formulato come problema di ottimizzazione, nel quale si trova tale da minimizzare una funzione di costo, ad esempio,

Si può allora trovare una soluzione mediante tecniche di ottimizzazione numerica. Per alcune particolari funzione di costo, le soluzioni ottimali possono essere definite analiticamente in termini di decomposizioni spettrali di matrici.

Tipologie I diversi algoritmi di MDS ricadono una specifica tassonomia, in base al significato della matrice richiesta in input:

MDS classico Noto anche come Principal Coordinates Analysis (PCoA), Torgerson Scaling o Torgerson–Gower scaling. Richiede in input una matrice con le dissimilarità fra coppie di elementi e produce in output una matrice di coordinate atte a minimizzare una loss function detta strain, data da dove denota vettori nello spazio N-dimensionale, denota il prodotto scalare fra e e sono gli elementi della matrice definita al passo 2 dell'algoritmo seguente, calcolati a partire dalle distanze.

MDS classico: Si sfrutta il fatto che la matrice delle coordinate possa essere derivata dalla decomposizione agli autovalori . La matrice può a sua volta essere calcolare dalla matrice di prossimità usando la doppia centratura.Wickelmaier, Florian. "An introduction to MDS." Sound Quality Research Unit, Aalborg University, Denmark (2003): 46 Inizializzare la matrice di prossimità quadratica Applicare la doppia centratura: usando la matrice di centratura , dove è il numero di oggetti, è la matrice d'identità e è una matrice con soli 1. Determinare gli autovalori più grandi e i corrispondenti autovettori di (dove è il numero di dimensioni desiderato per l'output). Infine, , dove è la matrice di autovettori e è la matrice diagonale di autovalori di . MDS Classico assume di lavorare su distanze metriche. Quindi non può essere applicato a valutazioni di dissimilarità dirette. MDS metrico (mMDS) Estensione di MDS classico che generalizza la procedura di ottimizzazione per coprire una varietà più ampia di funzioni di costo e matrici di input di distanze pesate note. In tale contesto, un'utile funzione di costo è quella dello stress, spesso minimizzata usando una procedura detta maggiorazione dello stress. MDS metrico minimizza la seguente funzione di “stress”, una somma di residui quadratici:

MDS usa una trasformazione di potenza con esponente deciso dall'utente: e per la distanza. Nello scaling classico Quello non-metrico viene definito dall'uso della regressione isotonica per stimare in modo non-parametrico una trasformazione delle dissimilarità.

MDS Non-metrico (NMDS) A differenza del MDS metrico, quello non-metrico determina sia una relazione non-parametrica monotona fra le dissimilarità nella matrice elemento-elemento e le distanze euclidee fra elementi, sia una posizione di ogni elemento nello spazio a basse-dimensioni.

Siano la dissimilarità fra i punti e la distanza euclidea fra le proiezioni dei punti.

Per una data scelta delle proiezioni , data una funzione monotona crescente , si definisce lo "stress" come segue:

Il fattore di al denominatore serve a prevenire il "collasso" delle proiezioni su un unico punto. Infatti, se si definisse invece , allora sarebbe banalmente minimizzato ponendo , provocando il collasso.

Esistono alcune altre varianti della funzione di costo previste nelle diverse implementazioni.

Il fulcro di un algoritmo MDS non-metrico è costituito da un duplice processo di ottimizzazione. Innanzitutto, occorre individuare la trasformazione monotona ottimale delle distanze. In secondo luogo, i punti di una configurazione devono essere disposti in modo ottimale, in modo che le loro distanze corrispondano il più possibile alle distanze riscalate.

NMDS ha bisogno di ottimizzare due obiettivi simultaneamente. Questo viene fatto in modo iterativo:

Inizializzare casualmente, ad es. campionando da una gaussiana. Eseguire fino all'avverarsi di un criterio di fermata (ad esempio, ) Trovare mediante regressione isotonica. Trovare mediante discesa di gradiente o mediante altri metodi. Restituire e

Un esempio di procedura MDS non-metrica è la Smallest Space Analysis (SSA) ideata da Louis Guttman.

MDS Generalizzato (GMDS) Un'estensione del MDS metrico si basa su uno spazio-obiettivo arbitrario non-euclideo. In casi nei quali le dissimilarità rappresentino distanze su una superficie e lo spazio-obiettivo sia un'altra superficie, il metodo esteso mira a trovare l'embedding di minima distorsione di una superficie nell'altra.

Note

Voci correlate Decomposizione agli autovalori Distanza Riduzione della dimensionalità

Altri progetti

Categoria:Statistica multivariata Categoria:Apprendimento automatico