Escalamiento multidimensional - Multidimensional scaling

Un ejemplo de escalamiento multidimensional clásico aplicado a los patrones de votación en la Cámara de Representantes de los Estados Unidos . Cada punto rojo representa a un miembro republicano de la Cámara y cada punto azul a un demócrata.

La escala multidimensional ( MDS ) es un medio de visualizar el nivel de similitud de casos individuales de un conjunto de datos. MDS se utiliza para traducir "información sobre las 'distancias' por pares entre un conjunto de objetos o individuos" en una configuración de puntos mapeados en un espacio cartesiano abstracto . ${\ textstyle n}$${\ textstyle n}$

Más técnicamente, MDS se refiere a un conjunto de técnicas de ordenación relacionadas que se utilizan en la visualización de información , en particular para mostrar la información contenida en una matriz de distancia . Es una forma de reducción de dimensionalidad no lineal .

Dada una matriz de distancias con las distancias entre cada par de objetos en un conjunto, y un número elegido de dimensiones, N , un algoritmo MDS coloca cada objeto en un espacio N - dimensional (una representación de menor dimensión) de tal manera que las distancias entre objetos se conservan lo mejor posible. Para N = 1, 2 y 3, los puntos resultantes se pueden visualizar en un diagrama de dispersión .

James O. Ramsay de la Universidad McGill , quien también es considerado el fundador del análisis de datos funcionales, hizo contribuciones teóricas fundamentales a los MDS .

Tipos

Los algoritmos MDS entran en una taxonomía , según el significado de la matriz de entrada:

Escalado multidimensional clásico

También se conoce como análisis de coordenadas principales (PCoA), escala de Torgerson o escala de Torgerson-Gower. Toma una matriz de entrada que da diferencias entre pares de elementos y genera una matriz de coordenadas cuya configuración minimiza una función de pérdida llamada deformación. Por ejemplo, dadas las distancias aéreas euclidianas entre varias ciudades indexadas por i y j , desea encontrar las coordenadas de las ciudades de tal manera que . En este ejemplo, es posible una solución exacta (asumiendo que las distancias euclidianas son exactas). En la práctica, este no suele ser el caso y, por lo tanto, MDS busca aproximarse a la representación de dimensiones inferiores minimizando una función de pérdida. Formas generales de funciones de pérdida llamadas estrés en MDS a distancia y deformación en MDS clásico. La deformación está dada por:, donde ahora denotan vectores en el espacio N -dimensional, denota el producto escalar entre y , y son los elementos de la matriz definidos en el paso 2 del siguiente algoritmo, que se calculan a partir de las distancias. ${\ textstyle d_ {ij}}$${\ textstyle (x_ {i}, y_ {i})}$${\ textstyle d_ {ij} = {\ sqrt {(x_ {i} -x_ {j}) ^ {2} + (y_ {i} -y_ {j}) ^ {2}}}}$${\ Displaystyle {\ text {Strain}} _ {D} (x_ {1}, x_ {2}, ..., x_ {N}) = {\ Biggl (} {\ frac {\ sum _ {i, j} {\ bigl (} b_ {ij} -x_ {i} ^ {T} x_ {j} {\ bigr)} ^ {2}} {\ sum _ {i, j} b_ {ij} ^ {2 }}} {\ Biggr)} ^ {1/2}}$${\ Displaystyle x_ {i}}$${\ Displaystyle x_ {i} ^ {T} x_ {j}}$${\ Displaystyle x_ {i}}$${\ Displaystyle x_ {j}}$${\ Displaystyle b_ {ij}}$${\ Displaystyle B}$

Pasos de un algoritmo MDS clásico:

La MDS clásica utiliza el hecho de que la matriz de coordenadas se puede derivar mediante la descomposición de valores propios de . Y la matriz se puede calcular a partir de la matriz de proximidad mediante el uso de doble centrado. ${\ Displaystyle X}$${\ textstyle B = XX '}$${\ textstyle B}$${\ textstyle D}$

1. Configurar la matriz de proximidad al cuadrado ${\ textstyle D ^ {(2)} = [d_ {ij} ^ {2}]}$
2. Aplicar doble centrado: utilizando la

matriz de centrado , donde está el número de objetos, es la matriz de identidad y es una matriz de todos.${\ textstyle B = - {\ frac {1} {2}} CD ^ {(2)} C}$ ${\ textstyle C = I - {\ frac {1} {n}} J_ {n}}$${\ textstyle n}$${\ textstyle I}$${\ textstyle n \ times n}$${\ textstyle J_ {n}}$${\ textstyle n \ times n}$

Determine los

valores propios más grandes y los vectores propios correspondientes de (donde es el número de dimensiones deseadas para la salida).${\ textstyle m}$ ${\ textstyle \ lambda _ {1}, \ lambda _ {2}, ..., \ lambda _ {m}}$ ${\ textstyle e_ {1}, e_ {2}, ..., e_ {m}}$${\ textstyle B}$${\ textstyle m}$

Ahora,, donde es la matriz de autovectores y es la

matriz diagonal de autovalores de .${\ textstyle X = E_ {m} \ Lambda _ {m} ^ {1/2}}$${\ textstyle E_ {m}}$${\ textstyle m}$${\ textstyle \ Lambda _ {m}}$${\ textstyle m}$${\ textstyle B}$

El MDS clásico asume distancias euclidianas . Por lo tanto, esto no se aplica a las calificaciones de disimilitud directa.

Escalado multidimensional métrico (mMDS)

Es un superconjunto de MDS clásico que generaliza el procedimiento de optimización a una variedad de funciones de pérdida y matrices de entrada de distancias conocidas con pesos, etc. Una función de pérdida útil en este contexto se llama estrés , que a menudo se minimiza mediante un procedimiento llamado mayorización de estrés . Metric MDS minimiza la función de costo llamada "Estrés", que es una suma residual de cuadrados:

${\ Displaystyle {\ text {Estrés}} _ {D} (x_ {1}, x_ {2}, ..., x_ {N}) = {\ Biggl (} \ sum _ {i \ neq j = 1 , ..., N} {\ bigl (} d_ {ij} - \ | x_ {i} -x_ {j} \ | {\ bigr)} ^ {2} {\ Biggr)} ^ {1/2} }$

La escala métrica utiliza una transformación de potencia con un exponente controlado por el usuario : y para la distancia. En escala clásica . La escala no métrica se define mediante el uso de regresión isotónica para estimar de forma no paramétrica una transformación de las diferencias.${\ textstyle p}$${\ textstyle d_ {ij} ^ {p}}$${\ textstyle -d_ {ij} ^ {2p}}$${\ textstyle p = 1}$

Escalado multidimensional no métrico (nMDS)

A diferencia de la MDS métrica, la MDS no métrica encuentra una relación monótona no paramétrica entre las diferencias en la matriz elemento-elemento y las distancias euclidianas entre elementos, y la ubicación de cada elemento en el espacio de baja dimensión. La relación se encuentra típicamente usando regresión isotónica : denotemos el vector de proximidades, una transformación monótona de y las distancias de los puntos; entonces hay que encontrar coordenadas que minimicen la llamada tensión, ${\ textstyle x}$${\ textstyle f (x)}$${\ textstyle x}$${\ textstyle d}$

${\ Displaystyle {\ text {Estrés}} = {\ sqrt {\ frac {\ sum {\ bigl (} f (x) -d {\ bigr)} ^ {2}} {\ sum d ^ {2}} }}}$

Existen algunas variantes de esta función de costes. Los programas MDS minimizan automáticamente el estrés para obtener la solución MDS.

El núcleo de un algoritmo MDS no métrico es un proceso de optimización doble. Primero hay que encontrar la transformación monótona óptima de las proximidades. En segundo lugar, los puntos de una configuración deben disponerse de manera óptima, de modo que sus distancias coincidan lo más posible con las proximidades escaladas. Los pasos básicos en un algoritmo MDS no métrico son:

1. Encuentre una configuración aleatoria de puntos, por ejemplo, tomando muestras de una distribución normal.
2. Calcula las distancias d entre los puntos.
3. Encuentre la transformación monótona óptima de las proximidades, para obtener datos escalados de manera óptima .${\ textstyle f (x)}$
4. Minimice la tensión entre los datos escalados de forma óptima y las distancias encontrando una nueva configuración de puntos.
5. Compare el estrés con algún criterio. Si la tensión es lo suficientemente pequeña, salga del algoritmo; de lo contrario, vuelva a 2.

El análisis de espacio más pequeño (SSA) de Louis Guttman es un ejemplo de un procedimiento MDS no métrico.

Escalado multidimensional generalizado (GMD)

Una extensión del escalado multidimensional métrico, en el que el espacio de destino es un espacio arbitrario uniforme no euclidiano. En los casos en que las diferencias son distancias en una superficie y el espacio objetivo es otra superficie, GMDS permite encontrar la distorsión mínima incrustada de una superficie en otra.

Detalles

Los datos a analizar son una colección de objetos (colores, caras, acciones, ...) sobre los que se define una función de distancia , ${\ Displaystyle M}$

${\ Displaystyle d_ {i, j}: =}$distancia entre los objetos -ésimo y -ésimo.${\ Displaystyle i}$${\ Displaystyle j}$

Estas distancias son las entradas de la matriz de disimilitud

${\ displaystyle D: = {\ begin {pmatrix} d_ {1,1} & d_ {1,2} & \ cdots & d_ {1, M} \\ d_ {2,1} & d_ {2,2} & \ cdots & d_ {2, M} \\\ vdots & \ vdots && \ vdots \\ d_ {M, 1} & d_ {M, 2} & \ cdots & d_ {M, M} \ end {pmatrix}}.}$

El objetivo de MDS es, dado , encontrar vectores tales que ${\ Displaystyle D}$${\ Displaystyle M}$${\ Displaystyle x_ {1}, \ ldots, x_ {M} \ in \ mathbb {R} ^ {N}}$

${\ Displaystyle \ | x_ {i} -x_ {j} \ | \ approx d_ {i, j}}$para todos ,${\ Displaystyle i, j \ in {1, \ dots, M}}$

donde es una norma vectorial . En la MDS clásica, esta norma es la distancia euclidiana , pero, en un sentido más amplio, puede ser una función de distancia métrica o arbitraria. ${\ Displaystyle \ | \ cdot \ |}$

En otras palabras, MDS intenta encontrar un mapeo de los objetos en tal que se conserven las distancias. Si se elige que la dimensión sea ​​2 o 3, podemos graficar los vectores para obtener una visualización de las similitudes entre los objetos. Tenga en cuenta que los vectores no son únicos: con la distancia euclidiana, pueden trasladarse, rotarse y reflejarse arbitrariamente, ya que estas transformaciones no cambian las distancias por pares . ${\ Displaystyle M}$${\ Displaystyle \ mathbb {R} ^ {N}}$${\ Displaystyle N}$${\ Displaystyle x_ {i}}$${\ Displaystyle M}$${\ Displaystyle x_ {i}}$${\ Displaystyle \ | x_ {i} -x_ {j} \ |}$

(Nota: el símbolo indica el conjunto de números reales y la notación se refiere al producto cartesiano de copias de , que es un espacio vectorial -dimensional sobre el campo de los números reales). ${\ Displaystyle \ mathbb {R}}$${\ Displaystyle \ mathbb {R} ^ {N}}$${\ Displaystyle N}$${\ Displaystyle \ mathbb {R}}$${\ Displaystyle N}$

Existen varios enfoques para determinar los vectores . Por lo general, MDS se formula como un problema de optimización , donde se encuentra como un minimizador de alguna función de costo, por ejemplo, ${\ Displaystyle x_ {i}}$${\ Displaystyle (x_ {1}, \ ldots, x_ {M})}$

${\ Displaystyle {\ underset {x_ {1}, \ ldots, x_ {M}} {\ mathrm {argmin}}} \ sum _ {i <j} (\ | x_ {i} -x_ {j} \ | -d_ {i, j}) ^ {2}. \,}$

Entonces se puede encontrar una solución mediante técnicas de optimización numérica. Para algunas funciones de costos particularmente elegidas, los minimizadores pueden expresarse analíticamente en términos de descomposiciones propias de la matriz .

Procedimiento

Hay varios pasos para realizar una investigación de MDS:

1. Formulación del problema : ¿Qué variables desea comparar? ¿Cuántas variables quieres comparar? ¿Para qué se utilizará el estudio?
2. Obtención de datos de entrada : por ejemplo: - A los encuestados se les hace una serie de preguntas. Para cada par de productos, se les pide que califiquen la similitud (generalmente en una escala Likert de 7 puntos de muy similar a muy diferente). La primera pregunta podría ser para Coca-Cola / Pepsi, por ejemplo, la siguiente para Coca-Cola / Hires rootbeer, la siguiente para Pepsi / Dr Pepper, la siguiente para Dr Pepper / Hires rootbeer, etc. El número de preguntas es una función del número de marcas y se puede calcular como donde Q es el número de preguntas y N es el número de marcas. Este enfoque se conoce como “Datos de percepción: enfoque directo”. Hay otros dos enfoques. Existe el "Datos de percepción: enfoque derivado" en el que los productos se descomponen en atributos que se clasifican en una escala diferencial semántica . El otro es el "enfoque de datos de preferencia" en el que se pregunta a los encuestados su preferencia en lugar de similitudes.${\ Displaystyle Q = N (N-1) / 2}$
3. Ejecución del programa estadístico MDS : el software para ejecutar el procedimiento está disponible en muchos paquetes de software estadístico. A menudo, se puede elegir entre MDS métrico (que trata con datos de nivel de intervalo o de razón) y MDS no métrico (que trata con datos ordinales).
4. Decidir el número de dimensiones : el investigador debe decidir el número de dimensiones que desea que cree la computadora. La capacidad de interpretación de la solución MDS es a menudo importante, y las soluciones de dimensiones inferiores suelen ser más fáciles de interpretar y visualizar. Sin embargo, la selección de dimensiones también es una cuestión de equilibrio entre el sobreajuste y el desajuste. Las soluciones de dimensiones inferiores pueden no encajar al omitir dimensiones importantes de los datos de disimilitud. Las soluciones de dimensiones más altas pueden sobreajustarse al ruido en las mediciones de disimilitud. Por lo tanto, las herramientas de selección de modelos como AIC / BIC, factores de Bayes o la validación cruzada pueden ser útiles para seleccionar la dimensionalidad que equilibra el desajuste y el sobreajuste.
5. Mapeo de los resultados y definición de las dimensiones : el programa estadístico (o un módulo relacionado) mapeará los resultados. El mapa trazará cada producto (generalmente en un espacio bidimensional). La proximidad de los productos entre sí indica cuán similares son o cuán preferidos son, según el enfoque que se utilizó. Sin embargo, no es necesariamente obvio cómo las dimensiones de la incrustación corresponden realmente a las dimensiones del comportamiento del sistema. Aquí, se puede hacer un juicio subjetivo sobre la correspondencia (ver mapeo perceptivo ).
6. Pruebe los resultados en cuanto a confiabilidad y validez : calcule R-cuadrado para determinar qué proporción de la varianza de los datos escalados se puede explicar mediante el procedimiento MDS. Un R-cuadrado de 0,6 se considera el nivel mínimo aceptable. Un R-cuadrado de 0,8 se considera bueno para la escala métrica y 0,9 se considera bueno para la escala no métrica. Otras pruebas posibles son el estrés de Kruskal, las pruebas de datos divididos, las pruebas de estabilidad de datos (es decir, la eliminación de una marca) y la fiabilidad test-retest.
7. Informe los resultados de manera integral : junto con el mapeo, se debe proporcionar al menos la medida de la distancia (por ejemplo, índice de Sorenson , índice de Jaccard ) y la confiabilidad (por ejemplo, valor de tensión). También es muy recomendable dar el algoritmo (por ejemplo, Kruskal, Mather), que a menudo se define por el programa utilizado (a veces reemplazando el informe del algoritmo), si ha dado una configuración de inicio o tuvo una elección aleatoria, el número de ejecuciones , la evaluación de la dimensionalidad, los resultados del método de Monte Carlo , el número de iteraciones, la evaluación de la estabilidad y la varianza proporcional de cada eje (r-cuadrado).

Implementaciones

• ELKI incluye dos implementaciones de MDS.
• MATLAB incluye dos implementaciones de MDS (para MDS clásico ( cmdscale ) y no clásico ( mdscale ) respectivamente).
• El lenguaje de programación R ofrece varias implementaciones de MDS.
• sklearn contiene la función sklearn.manifold.MDS .

Ver también

• Agrupación de datos
• Análisis factorial
• Análisis discriminante
• Reducción de dimensionalidad
• Geometría de distancia
• Determinante de Cayley-Menger
• Mapeo de Sammon
• Iconografía de correlaciones

Referencias

Bibliografía