Escalamiento Multidimensional

José A. Perusquía Cortés

Análisis Multivariado Semestre 2024 - I

 Motivación

‣ ¿De qué va?

Un conjunto de métodos enfocados en reducir la dimensión usando como criterio preservar la

“distancia” entre observaciones.

‣ Tipos

Escalamiento multidimensional clásico (lineal)

Escalamiento multidimensional métrico (no lineal)
Escalamiento multidimensional no métrico (no lineal)
 Ejemplo 1: Ciudades de [Link].
‣ Reconstrucción de un mapa a través de las distancias entre ciudades
 Ejemplo 1: Ciudades de [Link].

‣ Distancia en avión

Atl Chic Denv Hous LA Mia NY SF Seat Wash

Atlanta -
Chicago 587 -
Denver 1212 920 -
Houston 701 940 879 -
LA 1936 1745 831 1374 -
Miami 604 1188 1726 968 2339 -
NY 748 713 1631 1420 2451 1092 -
SF 2139 1858 949 1645 347 2594 2571 -
Seattle 2182 1737 1021 1891 959 2734 2408 678 -
Wash. DC 543 597 1494 1220 2300 923 205 2442 2329 -
 Ejemplo 1: Ciudades de [Link].

‣ Solución del escalamiento multidimensional clásico

 Ejemplo 1: Ciudades de [Link].

‣ Rotando la solución
 Ejemplo 1: Ciudades de [Link].

‣ Problema similar: identi car las ciudades

-
587 -
1212 920 -
701 940 879 -
1936 1745 831 1374 -
604 1188 1726 968 2339 -
748 713 1631 1420 2451 1092 -
2139 1858 949 1645 347 2594 2571 -
2182 1737 1021 1891 959 2734 2408 678 -
543 597 1494 1220 2300 923 205 2442 2329 -
fi
Ejemplo 1: Ciudades de [Link].
Escalamiento Multidimensional
Métrico (Clásico)
 Objetivo

‣ Construir una matriz de distancias/disimilitudes D

1. di,j ≥ 0 para toda i, j = 1,…, n

2. di,i = 0
T
3. D = D

k
‣ Encontrar un conjunto de vectores y1, …, yn ∈ ℝ tales que dx(i, j) ≈ dy(i, j)

‣ Observaciones
1. D es euclidiana si existe una con guración tal que dx(i, j) = dy(i, j) (no siempre ocurre).

2. En ocasiones D es una medición con error.

fi
 Construcción

De nición (matriz doblemente centrada)

Sea D una matriz de “distancias” entonces la matriz doblemente centrada está de nida como

B = HAH

donde,

2
1 dij
A=− D⊙D aij = −
2 2
fi
fi
 Construcción
Teorema
1
Sea Dn×n una matriz de distancias con matriz doblemente centrada B = − H(D ⊙ D)H
2
entonces

T
1. Si Dn×n es euclidiana entonces B = (HX)(HX) y así B es semi-de nida positiva.

2. Si B es semi-de nida positiva con eigenvalores λ1 ≥ λ2 ≥ ⋯ ≥ λk > 0 y descomposición

T
espectral B = UΛU entonces

1
X = UΛ 2

es una matriz de datos de dimensión n × k con matriz euclidiana de distancias D.

fi
fi
 Propiedades

1. La solución no es única (invariante ante cambios de origen, rotaciones y re exiones)

2. ȳ = 0

3. Robusto ante perturbaciones [e.g. Sibson (1978, 1979, 1981) y Mardia (1978)]

(1)
4. Si λ1 y λ2 son mucho más grandes que los restantes eigenvalores y los elementos de y y
2
(2) 2 2
∑
y son razonablemente diferentes entonces si (yik − yjk) ≈ dij se tiene una buena
k=1

representación en 2 dimensiones

5. Si la matriz es no euclidiana podemos hacer uso de los primeros l eigenvalores positivos y

(1) (l)
así, se tiene una con guración razonable con (y , …, y )
fi
fl
 Algoritmo

1. Construir la matriz A.

2. Obtener la matriz doblemente centrada B.

3. Obtener los k eigenvalores positivos y los eigenvectores asociados.

4. Si k = 2 o k = 3 se tiene una con guración que se puede gra car.

‣ En R : cmdscale( )
fi
fi
 Ejemplo 1: Ciudades de [Link].

‣ Distancia en avión de 10 ciudades de Estados Unidos

Atl Chic Denv Hous LA Mia NY SF Seat Wash

Atlanta -
Chicago 587 -
Denver 1212 920 -
Houston 701 940 879 -
LA 1936 1745 831 1374 -
Miami 604 1188 1726 968 2339 -
NY 748 713 1631 1420 2451 1092 -
SF 2139 1858 949 1645 347 2594 2571 -
Seattle 2182 1737 1021 1891 959 2734 2408 678 -
Wash. DC 543 597 1494 1220 2300 923 205 2442 2329 -
 Ejemplo 1: Ciudades de [Link].

‣ Los eigenvalores de B están dados por

λ1 = 9582144
λ2 = 1686820
λ3 = 8157.298
λ4 = 1432.87
λ5 = 508.6687
λ6 = 25.14349
λ7 = − 6.218108e − 10
λ8 = − 897.7013
λ9 = − 5467.577
λ10 = − 35478.89

‣ D no es Euclidiana
 Ejemplo 1: Ciudades de [Link].

‣ Nos quedamos con los 6 eigenvalores positivos y construimos Y

-718.7594 142.99427 35.102499 -1.224963 -7.4094776 1.5046461

-382.0558 -340.83962 29.602228 -8.237885 -12.0242975 -2.3383016
481.6023 -25.28504 53.393802 1.339279 15.6658897 -0.9526963
-161.4663 572.76991 1.452571 -1.762318 -0.6718656 2.7007621
1203.7380 390.10029 -18.635065 14.974864 -3.1692006 -1.6561488
-1133.5271 581.90731 -32.268842 -2.375685 2.9718537 -2.0471878
-1072.2357 -519.02423 -34.341878 -14.253857 6.4473289 0.2709088
1420.6033 112.58920 -7.754755 -18.120276 -0.8054123 0.8695197
1341.7225 -579.73928 -23.650787 5.961453 -1.4286322 0.6143794
-979.6220 -335.47281 -2.899773 23.699388 0.4238136 1.0341183

‣ Podemos quedarnos con las primeras dos columnas

 Otras consideraciones

1. Si se tienen similitudes con las siguientes condiciones:

‣ sij ≤ sii

‣ sij = sji

Podemos transformarlo a una matriz de disimilitudes

1
dij = (sii − 2sij + sjj) 2

[Link]ón cercana entre el escalamiento multidimensional clásico y los componentes principales

[Link] puede considerar la formulación: dx(i, j) ≈ dy(i, j) + a (additive constant problem)
 MDS vs PCA

1. Si D es euclidiana entonces el MDS clásico (o análisis de coordenadas principales) da los

mismos resultados que PCA.

2. MDS es más exible ya que acepta a las observaciones X o a una matriz de distancias/
disimilitudes D.

3. MDS es computacionalmente más demandante.

fl
 Ejemplo 2: Calificaciones

‣ Los eigenvalores de S son:

λ1 = 60000.28
λ2 = 17478.45
λ3 = 9006.942
λ4 = 7511.62
λ5 = 2805.543

‣ Iguales a los 5 eigenvalores de B distintos de cero

 Ejemplo 2: Calificaciones

‣ Aplicando las transformaciones a los alumnos 1, 2, 3, 4, 86, 87 y 88

Alumno PCA1 PCA2 MDS1 MDS2

1 -66.28 -6.48 -66.28 6.48

2 -63.60 6.79 -63.60 -6.79
3 -62.86 -3.26 -62.86 3.26
4 -44.51 5.65 -44.51 -5.65
86 44.35 7.86 44.35 -7.86
87 62.54 7.58 62.54 -7.58
88 65.93 2.66 65.93 -2.66
 Constante aditiva

‣ Se busca encontrar la constante c más pequeña tal que un conjunto de disimilitudes tengan
una representación euclidiana mediante,

c
di,j = di,j + c i≠j

‣ Problema estudiado por muchos autores (e.g. Messick & Abelson, 1956; Saito, 1978; Cailliez,
1983)

‣ La solución de Cailliez se utiliza en R: cmdscale(…,add=T)

‣ Por cuestiones numéricas no se puede garantizar que todos los eigenvalores sean no
negativos
 Ejemplo 1: Ciudades de [Link].

‣ Los eigenvalores de B al sumarle la constante aditiva c = 39.12509

λ1 = 9851759
λ2 = 1760672
λ3 = 49961.61
λ4 = 23925.69
λ5 = 22217.78
λ6 = 15077.03
λ7 = 11721.03
λ8 = 7807.841
λ9 = 1.55739e − 10
λ10 = − 5.297162e − 10
 Ejemplo 1: Ciudades de [Link].
‣ El mapa reconstruido con la constante aditiva c = 39.12509
Escalamiento Multidimensional
Métrico
 Ejemplo 3: Rollo suizo

MDS Clásico
 Motivación

‣ ¿De qué va?

Una generalización no lineal del escalamiento clásico en donde se busca preservar las
distancias y no solo los productos interiores.

‣ Objetivo
Minimizar una función objetivo conocida coloquialmente como “Stress”

1
wij [dx(i, j) − dy(i, j)]
2

2∑
Stress =
i,j

‣ En la práctica, wij = 1 y wij = 0 (valores faltantes).

 Sammon

‣ NLM: Mapeo no-lineal de Sammon (1969)

[ ]
2
1 dx(i, j) − dy (i, j)
c∑ ∑
Stress = c= dx(i, j)
i,j
dx(i, j) i<j

‣ Por lo general, dx(i, j) es la distancia Euclidiana (no necesariamente).

‣ Da más importancia a distancias cortas

‣ Requiere una rutina numérica (quasi-Newton) y de un parámetro “magic” (recomendado

entre .3 y .4).

‣ En R: función sammon en librería MASS

 Ejemplo 3: Rollo suizo

Sammon NLM
Escalamiento Multidimensional No
Métrico
 Motivación

‣ ¿De qué va?

Alternativa menos rígida al MDS utilizando una función monótona desconocida de las
distancias/proximidades, i.e.
dx(i, j) = f(dy(i, j))

‣ Para el MDS no métrico, construimos dy(i, j) utilizando solo los rangos de dx(i, j), e.g. para las
ciudades de Estados Unidos usamos:
- El viaje más corto es entre NY y Washington D.C.
- El segundo viaje más corto es entre Seattle y Atlanta.
…
- El viaje más largo es entre Seattle y Miami
 MDS no métrico

‣ Objetivo
Optimizar la función “stress”

∑ij wij [f(δx(i, j)) − dy(i, j)]

2

Stress =
c

donde
- δx(i, j) son proximidades
- f es una función monótona tal que f(δx(i, j)) ≈ dx(i, j) (distancia Euclidiana)
- c es un factor de escala
- wij son pesos no negativos como en el escalamiento multidimensional métrico
 isoMDS
‣ Algoritmo dado por Shepard (1962) y Kruskal (1964)

1. Dada una matriz de disimilitudes D ordenar las entradas fuera de la diagonal.

2. Para una con guración k- dimensional, minimizar la función Stress dada por

2
∑i<j [d*
ij − dy(i, j)]
Stress =
∑i<j dy(i, j)2

con respecto a valores d*

ij
tal que d*
ij
esté relacionada de forma monótona con dx(i, j) , i.e.,

dx(i, j) < dx(k, l) ⇒ d*

ij
≤ d*
kl
.
fi
 Consideraciones
‣ Los valores d*
ij
se encuentran a través de una regresión monótona (isotonic regression).

‣ Requiere de rutinas numéricas.

‣ Para encontrar la dimensión adecuada calcular para cada k

Sk = min Stress 2

detenerse hasta que Sk sea pequeño para k = k0 o una regla de dedo de Kruskal donde
Sk ≥ 20 % es pobre, Sk = 10 % es justo, Sk ≤ 5 % es bueno y Sk = 0 es perfecto.

‣ En R: isoMDS/Shepard de la librería MASS utilizando una con guración inicial (e.g. solución
clásica).

fi
 Ejemplo 3: Rollo suizo

MDS Clásico isoMDS

 Variantes

‣ Hacer uso de otras distancias, e.g. distancia geodésica en la variedad y no en el espacio

‣ Si la distancia geodésica es difícil de calcular (común) hacer uso de aproximaciones discretas

usando grafos.

‣ Por ejemplo, Isomap (en R isomap en librería MASS):

1. Conectamos cada punto con sus K vecinos más cercanos (o los que caigan en una bola de
radio ϵ).
2. Aproximamos la matriz de distancias geodésicas a través del camino más corto en la red
(algoritmo de Dijkstra o Floyd-Warshall)
3. Usamos escalamiento multidimensional clásico en la matriz de distancias.
 Ejemplo 3: Rollo suizo

Isomap K = 7 Isomap K = 9
 Ejemplo 3: Rollo suizo

Isomap K = 5 Isomap K = 10