Mayoría del estrés

Colocación geométrica basada en distancias ideales

La mayorización de la tensión es una estrategia de optimización utilizada en el escalamiento multidimensional (MDS) donde, para un conjunto de elementos de datos de dimensión , se busca una configuración de puntos en un espacio de dimensión que minimice la llamada función de tensión . Por lo general es o , es decir, la matriz enumera los puntos en el espacio euclidiano de dimensión r para que se pueda visualizar el resultado (es decir, un gráfico MDS ). La función es una función de costo o pérdida que mide las diferencias al cuadrado entre las distancias ideales ( -dimensionales) y las distancias reales en el espacio de dimensión r . Se define como: ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle (\ll m)}$ ${\displaystyle \sigma (X)}$ ${\displaystyle r}$ ${\displaystyle 2}$ ${\displaystyle 3}$ ${\displaystyle (n\times r)}$ ${\displaystyle X}$ ${\displaystyle 2-}$ ${\displaystyle 3-}$ ${\displaystyle \sigma }$ ${\displaystyle m}$

${\displaystyle \sigma (X)=\sum _{i<j\leq n}w_{ij}(d_{ij}(X)-\delta _{ij})^{2}}$

donde es un peso para la medición entre un par de puntos , es la distancia euclidiana entre y y es la distancia ideal entre los puntos (su separación) en el espacio de datos de dimensión . Nótese que se puede utilizar para especificar un grado de confianza en la similitud entre puntos (por ejemplo, se puede especificar 0 si no hay información para un par en particular). ${\displaystyle w_{ij}\geq 0}$ ${\displaystyle (i,j)}$ ${\displaystyle d_{ij}(X)}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \delta _{ij}}$ ${\displaystyle m}$ ${\displaystyle w_{ij}}$

Una configuración que minimiza genera un gráfico en el que los puntos que están cerca entre sí corresponden a puntos que también están cerca entre sí en el espacio de datos dimensional original. ${\displaystyle X}$ ${\displaystyle \sigma (X)}$ ${\displaystyle m}$

Existen muchas formas de minimizarlo. Por ejemplo, Kruskal ^[1] recomendó un enfoque iterativo de descenso más pronunciado . Sin embargo, Jan de Leeuw introdujo un método significativamente mejor (en términos de garantías y tasa de convergencia) para minimizar el estrés . ^{[2] El método} de mayorización iterativo de De Leeuw en cada paso minimiza una función convexa simple que limita desde arriba y toca la superficie de en un punto , llamado punto de apoyo . En el análisis convexo, una función de este tipo se denomina función mayorizadora . Este proceso de mayorización iterativo también se conoce como algoritmo SMACOF ("Escalado mediante mayorización de una función complicada"). ${\displaystyle \sigma (X)}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle Z}$

El algoritmo SMACOF

La función de estrés se puede desarrollar de la siguiente manera: ${\displaystyle \sigma }$

${\displaystyle \sigma (X)=\sum _{i<j\leq n}w_{ij}(d_{ij}(X)-\delta _{ij})^{2}=\sum _{i<j}w_{ij}\delta _{ij}^{2}+\sum _{i<j}w_{ij}d_{ij}^{2}(X)-2\sum _{i<j}w_{ij}\delta _{ij}d_{ij}(X)}$

Nótese que el primer término es una constante y el segundo término es cuadrático en (es decir, para la matriz hessiana, el segundo término es equivalente a tr ) y, por lo tanto, se resuelve con relativa facilidad. El tercer término está acotado por: ${\displaystyle C}$ ${\displaystyle X}$ ${\displaystyle V}$ ${\displaystyle X'VX}$

${\displaystyle \sum _{i<j}w_{ij}\delta _{ij}d_{ij}(X)=\,\operatorname {tr} \,X'B(X)X\geq \,\operatorname {tr} \,X'B(Z)Z}$

donde tiene: ${\displaystyle B(Z)}$

${\displaystyle b_{ij}=-{\frac {w_{ij}\delta _{ij}}{d_{ij}(Z)}}}$para ${\displaystyle d_{ij}(Z)\neq 0,i\neq j}$

y para ${\displaystyle b_{ij}=0}$ ${\displaystyle d_{ij}(Z)=0,i\neq j}$

y . ${\displaystyle b_{ii}=-\sum _{j=1,j\neq i}^{n}b_{ij}}$

La prueba de esta desigualdad se obtiene mediante la desigualdad de Cauchy-Schwarz , véase Borg ^[3] (pp. 152-153).

Así, tenemos una función cuadrática simple que mayoriza el estrés: ${\displaystyle \tau (X,Z)}$

${\displaystyle \sigma (X)=C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(X)X}$

${\displaystyle \leq C+\,\operatorname {tr} \,X'VX-2\,\operatorname {tr} \,X'B(Z)Z=\tau (X,Z)}$

El procedimiento de minimización iterativa es entonces:

• en el paso que fijamos ${\displaystyle k^{th}}$ ${\displaystyle Z\leftarrow X^{k-1}}$
• ${\displaystyle X^{k}\leftarrow \min _{X}\tau (X,Z)}$
• Detenerse, en caso contrario repetir. ${\displaystyle \sigma (X^{k-1})-\sigma (X^{k})<\epsilon }$

Se ha demostrado que este algoritmo reduce el estrés de forma monótona (véase de Leeuw ^[2] ).

Uso en el dibujo de gráficos

La mayorización de tensiones y algoritmos similares a SMACOF también tienen aplicación en el campo del dibujo de grafos . ^{[4] [5]} Es decir, se puede encontrar un diseño razonablemente atractivo estéticamente para una red o grafo minimizando una función de tensión sobre las posiciones de los nodos en el grafo. En este caso, los se establecen generalmente en las distancias teóricas de grafos entre nodos y y los pesos se toman como . Aquí, se elige como un equilibrio entre preservar distancias ideales de largo o corto alcance. Se han demostrado buenos resultados para . ^[6] ${\displaystyle \delta _{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle w_{ij}}$ ${\displaystyle \delta _{ij}^{-\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha =2}$

Referencias

1. Kruskal, JB (1964), "Escalamiento multidimensional mediante la optimización del ajuste a una hipótesis no métrica", Psychometrika , 29 (1): 1–27, doi :10.1007/BF02289565.
2. de Leeuw, J. (1977), "Aplicaciones del análisis convexo al escalamiento multidimensional", en Barra, JR; Brodeau, F.; Romie, G.; et al. (eds.), Desarrollos recientes en estadística , págs. 133–145.
3. Borg, I.; Groenen, P. (1997), Escalamiento multidimensional moderno: teoría y aplicaciones , Nueva York: Springer-Verlag.
4. Michailidis, G.; de Leeuw, J. (2001), "Visualización de datos mediante el dibujo de gráficos", Computation Stat. , 16 (3): 435–450, CiteSeerX 10.1.1.28.9372 , doi :10.1007/s001800100077 .
5. Gansner, E.; Koren, Y.; North, S. (2004), "Dibujo de gráficos por mayorización de la tensión", Actas del 12.º Simposio Internacional de Dibujo de Gráficos (GD'04) , Notas de clase en Ciencias de la Computación, vol. 3383, Springer-Verlag, págs. 239-250.
6. Cohen, J. (1997), "Dibujar gráficos para transmitir proximidad: un método de ordenamiento incremental", ACM Transactions on Computer-Human Interaction , 4 (3): 197–229, doi :10.1145/264645.264657.