Aprendizaje Maquina II: Multidimensional Scaling (MDS) de la Universitat de València

ETSE-UV: 25 Anys d'Enginyeria

1993-2018 25 ETSE-UV 25 Anys d'Enginyeria Campus de Burjassot - Paterna ETSE-UV Escola Técnica Superior d'Enginyeria Universitat de València

MASTER EN CIENCIA DE DATOS

Aprendizaje Máquina II: Multidimensional Scaling (MDS)

Universidad de Valencia, Avda Universidad S/N Escuela Técnica Superior de Ingeniería Departamento de Ingeniería Electrónica, Ricardo Sanz Díaz 46100, Burjassot (Valencia) ricardo.sanz@uv.es IDAL Intelligent Data Analysis LaboratoryAprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

Contenidos del Máster

• Motivación
• MDS clásico (CMDS]
• MDS métrico (MMDS]
• MDS no métrico (NMDS)
• Goodness of fit (GoF)

VNIVERSITAT ₱ VALÊNCIA [90] Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 2Aprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

Motivación del MDS

• MultiDimensional Scaling (MDS), también conocido como Principal Coordinate Analysis (PCoA).
• Convierte datos de distancias entre muestras a una visualización basada en un mapa perceptual de estas muestras (normalmente en 2D]
• Los mapas se utilizan para entender mejor que casos están cerca unos con otros, por lo que permite identificar grupos o clusters.

VNIVERSITAT ₱ VALÊNCIA [6%] Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 3Aprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

Ejemplo de Motivación: Ciudades

300 Strasbourg Nice 200 Lille Lyon 100 Marseille Paris Nantes 0 -100 Montpellier -200 Lyon Bordeaux -300 Bordeaux -400 Toulouse -500 -600 -400 -200 0 200 400 Toulouse Marseille VNIVERSITAT ₱ VALÊNCIA [90] Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 4 Lille Paris Strasbourg Nantes Nice MontpellierAprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

Motivación: Análisis de Datos de Dulces

A data.frame: 10 × 5 X Sweet Sour Salty Bitter <chr> <int> <int> <int> ‹int> Candy 1 95 70 8 2 Candy 2 90 29 12 4 Candy 3 75 54 6 8 Candy 4 70 72 33 6 Candy 5 60 12 69 7 Candy 6 40 18 4 5 Candy 7 35 33 2 3 Candy 8 30 67 25 8 -20 T -40 -20 0 20 40 Candy 9 28 23 21 5 Candy 10 26 8 4 6 VNIVERSITAT ₱ VALÊNCIA Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica Candy 5 50 - 40 30 20 10 - Candy 2 Candy 4 0 - Candy 9 Candy 1 Candy 10 Candy 6 Candy 3 -10 - Candy 8 Candy 7 5Aprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

MDS clásico (CMDS)

• El CMDS se obtiene al minimizar la distorsión [diferencia entre matrices de gram) min strain(Z) = min ZERnxk ZERNxk ||ZZI - T 2 K| F
• La matriz de gram K se obtiene mediante KA - - HEH = HXX H = X XT 2 1
• E: squared-distances; H: centering matrix ej ª |xi-x;ll2 HAI -- 1.1T 1 n

VNIVERSITAT ₱ VALÊNCIA [6%] Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 6Aprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

Resolución del CMDS

• Se puede demostrar que el problema del CMDS: min strain(Z) = min ||ZZI - T 2 K F ZERnxk ZERNXk
• Se resuelve mediante la descomposición spectral K = VAVT
• Calculando los puntos proyectados como ZMDS = = VIVA

VNIVERSITAT ₱ VALÊNCIA [90] Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 7Aprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

MDS métrico (MMDS)

• El MDS métrico parte de una formulación más intuitiva y práctica (pero no lineal) del problema: min stress(Z) = min ZERnxk ZERnxk Zwij(Iki -zjll - dip)2 i
• Es decir, busca colocar puntos de forma que la distancia en el mapa perceptual sea lo más parecida posible a la distancia indicada por la matriz de dissimilarities (puede no ser euclidea)

VNIVERSITAT ₱ VALÊNCIA Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 8Aprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

Optimización del MMDS y Matriz de Dissimilarity

• Sin embargo, por su formulación, se trata de un problema de optimización no lineal · Se resuelve en la práctica mediante SMACOF [algoritmo iterativo]
• ¿Qué es una dissimilarity matrix? 1. dij ≥ 0 for all i, j = 1, ... , n. 2. dii = 0 for i = 1, . . . , n and 3. D = D , i.e., D is symmetric (dij = dji).

VNIVERSITAT ₱ VALÊNCIA [90] Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 9Aprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

(C)MDS GoF: Sheppard Plot

• Permite evaluar la calidad de la proyección Shepard Plot 30 Pares de distancias -- Ideal Distancias en el espacio MDS 25 20 15 10 5 0 - 0 5 10 15 20 25 30 Distancias originales (dissimilarities)

VNIVERSITAT ₱ VALÊNCIA Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 10Aprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

MDS no métrico (NMDS)

• Shepard y Kruskal desarrollaron esta variante denominada NMDS
• Se asume que las proximidades están en escala ordinal (solo importa el orden]
• Solamente su rango u orden se considera información confiable y válida. Strongly disagree Question 1 Disagree Neither agree nor disagree Agree Strongly agree Question 2 - 50% 40% 30% 20% 10% 0% 10% 20% 30% 40% 50% 60% Percentage of Responses

VNIVERSITAT VALÊNCIA Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 11Aprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

Función de Coste NMDS

• En el NMDS, la función de coste minimizada no es el stress convencional, sino stress-1(Z) = Eiki isi (IlZi - Zjll - Sj(dj)2 Eizilli - zjll2 i
• Las distancias se transforman mediante funciones monótonas 8ij(s): $1>$2=>8ij($1)>8ij(s2)
• A los valores 8 ;; (dij) se les llama disparidades
• La transformación hace que solo importe el orden

VNIVERSITAT ₱ VALÊNCIA [6%] Escola Tecnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 12Aprendizaje Máquina MASTER EN CIENCIA DE DATOS ilil

NMDS GoF: stress-1

• Para evaluar mediante Sheppard plot deberíamos disponer de las disparidades (la implementación sklearn, por ejemplo, no las proporciona]
• Si no las tenemos, podemos referirnos a la siguiente tabla: Stress % Goodness of Fit 20 Poor 10 Fair 5 Good 2.5 Exellent 0 Perfect

VNIVERSITAT ₱ VALÊNCIA [90] Escola Técnica Superiord' Enginyeria Departament d'Enginyeria Electrónica 13