Scaling multidimensionale

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 $M$ oggetti (colori, immagini,...) sui quali sia definita una funzione di distanza,

d_{i, j} :=

distanza tra gli oggetti di indice

i

e

j

.

Tali distanze sono gli elementi di una matrice di dissimilarità

D ≜ (\begin{matrix} d_{1, 1} & d_{1, 2} & \dots & d_{1, M} \\ d_{2, 1} & d_{2, 2} & \dots & d_{2, M} \\ ⋮ & ⋮ & ⋮ \\ d_{M, 1} & d_{M, 2} & \dots & d_{M, M} \end{matrix}) .

L'obiettivo di MDS è, data $D$ , quello di trovare $M$ vettori $x_{1}, \dots, x_{M} \in ℝ^{N}$ tali che

‖ x_{i} - x_{j} ‖ \approx d_{i, j}

per ogni

i, j \in 1, \dots, M

,

dove $‖ \cdot ‖$ è una norma vettoriale. Nell'MDS classico, tale norma è la distanza euclidea, ma, per estensione, potrebbe essere una metrica o una funzione di distanza arbitraria. 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 $M$ oggetti su $ℝ^{N}$ tale che le distanze siano preservate. Se si sceglie una dimensionalità $N$ pari a 2 o 3, si possono riprodurre i vettori $x_{i}$ in una visualizzazione che mostri le similarità fra gli $M$ oggetti. Si noti che i vettori $x_{i}$ 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 $‖ x_{i} - x_{j} ‖$ per coppie di vettori.

Ci sono vari approcci atti a determinare i vettori $x_{i}$ . Solitamente, MDS viene formulato come problema di ottimizzazione, nel quale si trova $(x_{1}, \dots, x_{M})$ tale da minimizzare una funzione di costo, ad esempio,

\underset{x_{1}, \dots, x_{M}}{a r g m i n} \sum_{i < j} (‖ x_{i} - x_{j} ‖ - d_{i, j})^{2} .

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 ${Strain}_{D} (x_{1}, x_{2}, ..., x_{n}) = (\frac{\sum_{i, j} (b_{i j} - x_{i}^{T} x_{j})^{2}}{\sum_{i, j} b_{i j}^{2}})^{1 / 2},$ dove $x_{i}$ denota vettori nello spazio N-dimensionale, $x_{i}^{T} x_{j}$ denota il prodotto scalare fra $x_{i}$ e $x_{j}$ e $b_{i j}$ sono gli elementi della matrice $B$ definita al passo 2 dell'algoritmo seguente, calcolati a partire dalle distanze.

MDS classico:

Si sfrutta il fatto che la matrice delle coordinate

X

possa essere derivata dalla decomposizione agli autovalori

B = X X^{'}

. La matrice

B

può a sua volta essere calcolare dalla matrice di prossimità

D

usando la doppia centratura.

Inizializzare la matrice di prossimità quadratica $D^{(2)} = [d_{i j}^{2}]$
Applicare la doppia centratura: $B = - \frac{1}{2} C D^{(2)} C$ usando la matrice di centratura $C = I - \frac{1}{n} J_{n}$ , dove $n$ è il numero di oggetti, $I$ è la matrice d'identità $n \times n$ e $J_{n}$ è una matrice $n \times n$ con soli 1.
Determinare gli $m$ autovalori più grandi $λ_{1}, λ_{2}, ..., λ_{m}$ e i corrispondenti autovettori $e_{1}, e_{2}, ..., e_{m}$ di $B$ (dove $m$ è il numero di dimensioni desiderato per l'output).
Infine, $X = E_{m} Λ_{m}^{1 / 2}$ , dove $E_{m}$ è la matrice di $m$ autovettori e $Λ_{m}$ è la matrice diagonale di $m$ autovalori di $B$ .

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:

{Stress}_{D} (x_{1}, x_{2}, ..., x_{n}) = \sqrt{\sum_{i \neq j = 1, ..., n} (d_{i j} - ‖ x_{i} - x_{j} ‖)^{2}} .

MDS usa una trasformazione di potenza con esponente $p$ deciso dall'utente: $d_{i j}^{p}$ e $- d_{i j}^{2 p}$ per la distanza. Nello scaling classico $p = 1.$ 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 $d_{i j}$ la dissimilarità fra i punti $i, j$ e ${\hat{d}}_{i j} = ‖ x_{i} - x_{j} ‖$ la distanza euclidea fra le proiezioni $x_{i}, x_{j}$ dei punti.

Per una data scelta delle proiezioni $x_{i}$ , data una funzione monotona crescente $f$ , si definisce lo "stress" come segue:

S (x_{1}, ..., x_{n}; f) = \sqrt{\frac{\sum_{i < j} (f (d_{i j}) - {\hat{d}}_{i j})^{2}}{\sum_{i < j} {\hat{d}}_{i j}^{2}}} .

Il fattore di $\sum_{i < j} {\hat{d}}_{i j}^{2}$ al denominatore serve a prevenire il "collasso" delle proiezioni su un unico punto. Infatti, se si definisse invece $S = \sqrt{\sum_{i < j} (f (d_{i j}) - {\hat{d}}_{i j})^{2}}$ , allora sarebbe banalmente minimizzato ponendo $f = 0$ , 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 $x_{i}$ casualmente, ad es. campionando da una gaussiana.
Eseguire fino all'avverarsi di un criterio di fermata (ad esempio, S<ϵ)
1. Trovare $f = \arg min_{f} S (x_{1}, ..., x_{n}; f)$ mediante regressione isotonica.
2. Trovare $x_{1}, ..., x_{n} = \arg min_{x_{1}, ..., x_{n}} S (x_{1}, ..., x_{n}; f)$ mediante discesa di gradiente o mediante altri metodi.
Restituire $x_{i}$ e $f$

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

↑ A. Mead, Review of the Development of Multidimensional Scaling Methods, in The Statistician, vol. 41, n. 1, 1992, pp. 27, DOI:10.2307/2348634.
↑ Kevin P. Murphy, 20. Dimensionality reduction, in Probabilistic Machine Learning, MIT Press, 2022, pp. 682–699, ISBN 978-0-262-04682-4.
↑ Ethem Alpaydin, 6. Dimensionality Reduction, in Introduction to machine learning, collana Adaptive computation and machine learning series, Fourth edition, The MIT Press, 2020, ISBN 978-0-262-04379-3.
1 2 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.
↑ Il simbolo $ℝ$ indica l'insieme dei numeri reali e la notazione $ℝ^{N}$ si riferisce al prodotto cartesiano di $N$ copie di $ℝ$ , il quale costituisce uno spazio vettoriale $N$ -dimensionale sul campo dei numeri reali.
1 2 Ingwer Borg e Patrick J. F. Groenen, Modern multidimensional scaling: theory and applications, collana Springer series in statistics, Springer, 1997, ISBN 978-0-387-94845-4.
↑ Wickelmaier, Florian. "An introduction to MDS." Sound Quality Research Unit, Aalborg University, Denmark (2003): 46
↑ Bronstein AM, Bronstein MM, Kimmel R, Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching, in Proc. Natl. Acad. Sci. U.S.A., vol. 103, n. 5, gennaio 2006, pp. 1168–72, Bibcode:2006PNAS..103.1168B, DOI:10.1073/pnas.0508601103, PMC 1360551, PMID 16432211.

Voci correlate

Altri progetti

Wikimedia Commons contiene immagini o altri file su scaling multidimensionale

Controllo di autorità	Thesaurus BNCF 56778 · LCCN (EN) sh85088344 · BNF (FR) cb11947073k (data) · J9U (EN, HE) 987007550963905171 · NDL (EN, JA) 01160098

Portale Informatica

Portale Matematica

[1] A. Mead, Review of the Development of Multidimensional Scaling Methods, in The Statistician, vol. 41, n. 1, 1992, pp. 27, DOI:10.2307/2348634.

[2] Kevin P. Murphy, 20. Dimensionality reduction, in Probabilistic Machine Learning, MIT Press, 2022, pp. 682–699, ISBN 978-0-262-04682-4.

[3] Ethem Alpaydin, 6. Dimensionality Reduction, in Introduction to machine learning, collana Adaptive computation and machine learning series, Fourth edition, The MIT Press, 2020, ISBN 978-0-262-04379-3.

[Kruskal-4] 1 2 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.

[5] Il simbolo $ℝ$ indica l'insieme dei numeri reali e la notazione $ℝ^{N}$ si riferisce al prodotto cartesiano di $N$ copie di $ℝ$ , il quale costituisce uno spazio vettoriale $N$ -dimensionale sul campo dei numeri reali.

[borg-6] 1 2 Ingwer Borg e Patrick J. F. Groenen, Modern multidimensional scaling: theory and applications, collana Springer series in statistics, Springer, 1997, ISBN 978-0-387-94845-4.

[7] Wickelmaier, Florian. "An introduction to MDS." Sound Quality Research Unit, Aalborg University, Denmark (2003): 46

[bron-8] Bronstein AM, Bronstein MM, Kimmel R, Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching, in Proc. Natl. Acad. Sci. U.S.A., vol. 103, n. 5, gennaio 2006, pp. 1168–72, Bibcode:2006PNAS..103.1168B, DOI:10.1073/pnas.0508601103, PMC 1360551, PMID 16432211.

V · D · M Apprendimento automatico
Problemi	Teoria dell'apprendimento statistico · Classificazione · Regressione · Classificazione a singola classe · Ranking · Regole di associazione · Apprendimento non supervisionato · Apprendimento semi-supervisionato · Apprendimento supervisionato · Apprendimento debolmente supervisionato · Apprendimento auto-supervisionato · Apprendimento da pochi esempi · Apprendimento gerarchico · Apprendimento per rinforzo · Apprendimento profondo · Apprendimento online · Apprendimento incrementale · Apprendimento trasduttivo · Apprendimento di rappresentazioni · Apprendimento per similarità · Apprendimento per contrasto · Concept drift · Meta-apprendimento · Dati mancanti
Apprendimento non supervisionato	Clustering · Clustering gerarchico · K-means · Algoritmo EM · Clustering spettrale · DBSCAN · Mean shift · Rete generativa avversaria (cGAN · VAE-GAN · cycleGAN)
Apprendimento supervisionato	Albero di decisione · Foresta casuale · Conditional random field CRF · Modello di Markov nascosto · Algoritmo k-nearest neighbors (k-NN) · Ragionamento basato su casi (CBR) · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Modello grafico · Rete bayesiana · Macchine a vettori di supporto (SVM) · Processo gaussiano · Modello ensemble · Boosting · Bagging · Classifier chain · Cascading · Classificatore ECOC · Stacking · Voting
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Analisi della correlazione canonica (CCA) · Analisi delle componenti indipendenti (ICA) · Analisi discriminante lineare (LDA) · Analisi delle componenti principali (PCA) · Apprendimento di varietà (manifold learning) · Estrazione di caratteristiche · Immersione localmente lineare (LLE) · Isomap · Scaling multidimensionale (MDS) · Selezione delle caratteristiche · t-distributed stochastic neighbor embedding (t-SNE)
Reti neurali artificiali	Percettrone · Percettrone basato su kernel · Rete neurale a funzioni base radiali (RBF net) · Rete neurale feed-forward · Rete di Hopfield · Percettrone multistrato · Rete neurale ricorrente (LSTM) · Macchina di Boltzmann ristretta · Mappa auto-organizzata · Rete neurale convoluzionale · Rete neurale a ritardo · Rete neurale spiking · Rete neurale grafica · Trasformatore
Software	Keras · Microsoft Cognitive Toolkit · Scikit-learn · TensorFlow · Theano · PyTorch · Weka
Altro	Algoritmo genetico · Particle Swarm Optimization · Caratteristica · Compromesso bias-varianza · Minimizzazione del rischio empirico