Mayorización estrés es una estrategia de optimización utilizado en escalamiento multidimensional (MDS), donde, para un conjunto de n m elementos de datos dimensionales, una configuración X de n puntos en r (<< m) se busca espacio dimensional que minimiza los llamados función de estrés. Por lo general, r es 2 o 3, es decir, la matriz ( n x r ) X enumera puntos en el espacio euclidiano bidimensional o tridimensional para que se pueda visualizar el resultado (es decir, un gráfico MDS ). La funciónes una función de costo o pérdida que mide las diferencias al cuadrado entre ideal (-dimensional) distancias y distancias reales en el espacio r -dimensional. Se define como:
dónde 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).
Una configuración que minimiza da una gráfica en la que los puntos que están juntos corresponden a puntos que también están cerca en el original -espacio de datos dimensional.
Hay muchas formas en las que podría minimizarse. Por ejemplo, Kruskal [1] recomendó una aproximación iterativa de descenso más empinado . 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 ambos límites desde arriba y toca la superficie de en un punto , llamado el punto de apoyo . En el análisis convexo, esta función se denomina función mayorizadora . Este proceso de mayorización iterativo también se conoce como el algoritmo SMACOF ("Escalado por mayorización de una función implícita").
El algoritmo SMACOF
La función de estrés se puede ampliar de la siguiente manera:
Tenga en cuenta que el primer término es una constante y el segundo término es cuadrático en X (es decir, para la matriz de Hesse V, el segundo término es equivalente a tr) y, por lo tanto, se resuelve con relativa facilidad. El tercer término está delimitado por:
dónde posee:
- por
y por
y .
Prueba de esta desigualdad es la desigualdad de Cauchy-Schwarz , véase Borg [3] (págs. 152-153).
Por lo tanto, tenemos una función cuadrática simple que mayoriza el estrés:
El procedimiento de minimización iterativo es entonces:
- en el k- ésimo paso que ponemos
- detente si de lo contrario repita.
Se ha demostrado que este algoritmo reduce el estrés de forma monótona (véase de Leeuw [2] ).
Usar en el dibujo de gráficos
La mayorización de estrés y 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, elgeneralmente se establecen en las distancias teóricas de gráficos entre los nodos i y j y los pesos se toman para ser . Aquí,se elige como una compensación entre preservar distancias ideales de largo o corto alcance. Se han demostrado buenos resultados para. [6]
Referencias
- ^ Kruskal, JB (1964), "Escalado multidimensional optimizando la bondad de ajuste a una hipótesis no métrica", Psychometrika , 29 (1): 1–27, doi : 10.1007 / BF02289565.
- ^ a b de Leeuw, J. (1977), "Aplicaciones del análisis convexo al escalado multidimensional", en Barra, JR; Brodeau, F .; Romie, G .; et al. (eds.), Desarrollos recientes en las estadísticas , págs. 133–145.
- ^ Borg, I .; Groenen, P. (1997), Escalado multidimensional moderno: teoría y aplicaciones , Nueva York: Springer-Verlag.
- ^ Michailidis, G .; de Leeuw, J. (2001), "Visualización de datos a través del dibujo de gráficos", Computation Stat. , 16 (3): 435–450, CiteSeerX 10.1.1.28.9372 , doi : 10.1007 / s001800100077.
- ^ Gansner, E .; Koren, Y .; North, S. (2004), "Dibujo de gráficos por mayorización de la tensión", Actas de la 12ª Int. Symp. Graph Drawing (GD'04) , Lecture Notes in Computer Science, 3383 , Springer-Verlag, págs. 239–250.
- ^ Cohen, J. (1997), "Dibujar gráficos para transmitir la proximidad: un método de arreglo incremental", ACM Transactions on Computer-Human Interaction , 4 (3): 197–229, doi : 10.1145 / 264645.264657.