Mayorización del estrés

Colocación geométrica basada en distancias ideales.

La mayorización de tensiones es una estrategia de optimización utilizada en el escalamiento multidimensional (MDS) donde, para un conjunto de elementos de datos -dimensionales, se busca una configuración de puntos en el espacio -dimensional que minimice la llamada función de tensión . Generalmente es o , es decir, la matriz enumera puntos en el espacio euclidiano dimensional 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 distancias ideales (-dimensionales) y distancias reales en un espacio r -dimensional. 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 dimensional. Tenga en cuenta 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 proporciona una gráfica en la que los puntos que están muy juntos corresponden a puntos que también están muy juntos en el espacio de datos dimensional original. ${\displaystyle X}$ ${\displaystyle \sigma (X)}$ ${\displaystyle m}$

Hay 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 iterativa 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, dicha función se denomina función mayorizadora . Este proceso de mayorización iterativa también se conoce como algoritmo SMACOF ("Escalar mediante la mayorización de una función complicada"). ${\displaystyle \sigma (X)}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle Z}$

El algoritmo SMACOF

La función de tensión se puede ampliar 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)}$

Tenga en cuenta que el primer término es una constante y el segundo término es cuadrático (es decir, para la matriz de Hesse, el segundo término es equivalente a tr ) y, por lo tanto, se resuelve con relativa facilidad. El tercer término está limitado 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 es la desigualdad de Cauchy-Schwarz , véase Borg ^[3] (págs. 152-153).

Por tanto, 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 iterativo es entonces:

• en el paso que marcamos ${\displaystyle k^{th}}$ ${\displaystyle Z\leftarrow X^{k-1}}$
• ${\displaystyle X^{k}\leftarrow \min _{X}\tau (X,Z)}$
• deténgase si no, repita. ${\displaystyle \sigma (X^{k-1})-\sigma (X^{k})<\epsilon }$

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

Uso en dibujo de gráficos

La mayorización de tensiones y los algoritmos similares a SMACOF también tienen aplicación en el campo del dibujo de gráficos . ^{[4] [5]} Es decir, se puede encontrar un diseño razonablemente atractivo desde el punto de vista estético para una red o gráfico minimizando una función de tensión sobre las posiciones de los nodos en el gráfico. En este caso, generalmente se establecen en las distancias teóricas de grafos entre nodos y y los pesos se consideran . Aquí, se elige como un equilibrio entre preservar distancias ideales de largo o corto alcance. Se han mostrado 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 optimizando la bondad de 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, yo; 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 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 mediante mayorización de tensión", Actas del 12º Int. Síntoma. Dibujo de gráficos (GD'04) , Apuntes de conferencias sobre informática, vol. 3383, Springer-Verlag, págs. 239-250.
6. Cohen, J. (1997), "Dibujo de gráficos para transmitir proximidad: un método de disposición incremental", ACM Transactions on Computer-Human Interaction , 4 (3): 197–229, doi :10.1145/264645.264657.