Mayoría del estrés

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: ${\estilo de visualización n}$ ${\estilo de visualización m}$${\estilo de visualización X}$${\estilo de visualización n}$${\estilo de visualización r}$ ${\displaystyle (\ll m)}$${\displaystyle \sigma (X)}$${\estilo de visualización r}$${\estilo de visualización 2}$${\estilo de visualización 3}$${\displaystyle (n\times r)}$${\estilo de visualización X}$${\estilo de visualización 2-}$${\estilo de visualización 3-}$${\estilo de visualización \sigma}$${\estilo de visualización 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}$${\estilo de visualización (i,j)}$$Estilo de visualización d_{ij}(X)}$${\estilo de visualización i}$${\estilo de visualización j}$${\displaystyle \delta _{ij}}$${\estilo de visualización m}$$estilo de visualización 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. ${\estilo de visualización X}$${\displaystyle \sigma (X)}$${\estilo de visualización 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)}$${\estilo de visualización \sigma}$${\estilo de visualización \sigma}$${\estilo de visualización Z}$

La función de estrés se puede desarrollar de la siguiente manera: ${\estilo de visualización \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: ${\estilo de visualización C}$${\estilo de visualización X}$ ${\estilo de visualización V}$${\estilo de visualización X'VX}$

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

donde tiene: $Estilo de visualización 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+\,\nombre del operador {tr} \,X'VX-2\,\nombre del operador {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] ).

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}$