Proyección al espacio con una dimensión más pequeña que guarda una distancia

Question

Supongamos que tenemos un conjunto numerable de objetos $\{x_i|i \in [1..m]\}$ en un espacio métrico $(\mathbb R^n,d_n)$ y un mapa ($F$) que mapea los objetos a objetos en un espacio métrico $(\mathbb R^1,d_1)$. Para cada par de objetos podemos definir un error:

$$e_{ij} = \frac{d_m(x_i,x_j)}{d_1(F(x_i),F(x_j))}$$

Dejemos que $e_{ii}$ sea 1.

Es obvio que podemos definir el conjunto numerable de tal manera que cualquier proyección tenga un error ($e_{ij}\ne 1$) al menos para un par de objetos.

Pero para un conjunto dado de objetos podemos definir el mapa intentando minimizar los errores.

Me encontré con este problema al desarrollar un sistema de calificación de un sitio web basado en varios criterios. En este momento uso el siguiente algoritmo para calcular F (imágenes de objetos):

1. selecciona un conjunto aleatorio $\{y_i|i \in [1..m]\}$ en el espacio $(\mathbb R^1,d_1)$ y considera que $y_i=F(x_i)$ donde F es el mapa definido
2. para cada punto calcula $\delta_i=\sum\limits_{j}k\frac{1}{2}e_{ij}(y_i-y_j)$ donde $k$ es un parámetro ($0 \le k \le 1$) y luego cambia los elementos en el conjunto $y_i \to y_i + \delta_i$

Repito el paso dos una y otra vez varias veces, pero en cada paso hago que el parámetro $k$ sea más pequeño.

Infiero este algoritmo a partir de la intuición física: si dos objetos están muy cerca se repelen, si están muy lejos se atraen y $k$ es una resistencia del ambiente.

Quiero obtener un conocimiento más profundo sobre este problema, ¿podrías proporcionarme algunos enlaces a artículos y literatura al respecto o el nombre oficial del problema?

Answer 1

Tu problema es casi exactamente escalado multidimensional: dado un conjunto de $n$ objetos con disimilitudes $\delta_{ij}$ dadas, encontrar $n$ puntos correspondientes $y_i$ en un espacio de baja dimensionalidad tal que $\lVert y_i - y_j\rVert \approx \delta_{ij}$. No estoy muy familiarizado con esta área, pero el artículo de Wikipedia menciona una serie de algoritmos que podrías consultar. Debes tener en cuenta que a menudo habrá muchas configuraciones óptimas locales para un problema dado.

Sin embargo, el escalado multidimensional se utiliza típicamente para aplicaciones de visualización, donde deseas mapear tus datos a 2 o 3 dimensiones y ver qué objetos son similares entre sí. No estoy seguro de cómo planeas utilizarlo para calcular valoraciones, porque reemplazar todos los $y_i$ con $-y_i$ es exactamente una solución igual de buena pero convertirá valoraciones bajas en altas y viceversa.