Mapa elástico

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 13 de marzo de 2021; las comprobaciones requieren 2 ediciones .

El mapa elástico se utiliza para la reducción no lineal de la dimensión de los datos. En un espacio de datos multidimensional, existe una superficie que se aproxima a los puntos de datos disponibles y, si es posible, no demasiado curvada. Los datos se proyectan sobre esta superficie y luego se pueden mostrar en ella, como en un mapa. Puede considerarlo como una placa elástica sumergida en el espacio de datos y unida a puntos de datos con resortes. Sirve como una generalización del método de componentes principales (en el que se utiliza un plano absolutamente rígido en lugar de una placa elástica).

Por construcción, un mapa elástico es un sistema de resortes elásticos incrustados en un espacio de datos multidimensional [1] [5] . Este sistema se aproxima a una variedad bidimensional. Cambiar los coeficientes elásticos del sistema permite al usuario cambiar de un agrupamiento de K-means completamente desestructurado (en el límite de elasticidad cero ) a variedades cercanas a las variedades de componentes principales lineales (en el límite de módulos de flexión muy grandes y módulos de tracción pequeños). En el rango intermedio de valores de los coeficientes de elasticidad, el sistema se aproxima efectivamente a alguna variedad no lineal. Este enfoque se basa en una analogía con la mecánica: la variedad principal que pasa por el "medio" de los datos se puede representar como una membrana o placa elástica. El método fue desarrollado por el prof. A. N. Gorban , A. Zinoviev y A. Pitenko en 1996-2001.

Mapa de energía elástica

Sea el conjunto de datos representado por un conjunto de vectores en un espacio euclidiano de dimensión finita . Un "mapa elástico" está representado por un conjunto de sus nodos en el mismo espacio. Para cada punto de datos , el nodo "anfitrión" (host) se define como el nodo del mapa más cercano al punto (si resulta que hay varios nodos más cercanos, simplemente se selecciona el nodo con el número de serie más bajo). El conjunto de datos se divide en clases taxonómicas . $S$ $W_j$ $S \ en S$ $W_j$ $S$ $K_{j}=\{s\ |\ W_{j}{\mbox{ es una gran cantidad de }}s\}$

La energía de aproximación es simplemente la raíz de la desviación cuadrática media de los nodos del mapa

D={\frac {1}{2}}\sum_{{j=1}}^{k}\sum_{{x\in K_{j}}}\|x-W_{j}\| ^{2},

o, en otras palabras, existe la energía elástica total de los resortes con coeficiente de elasticidad unitario que conecta cada punto de datos con su nodo "maestro".

Es necesario introducir la siguiente estructura adicional en el conjunto de nodos. Algunos pares de nodos, , están conectados por enlaces elásticos. Denotemos el conjunto de aristas del gráfico como . Además, combinaremos algunos triples de nodos en "refuerzos". Denotemos el conjunto de rigidizadores como . $(W_{i},W_{j})$ $mi$ $(W_{i},W_{j},W_{k})$ $GRAMO$

La energía de tensión de un mapa elástico se define como

U_{{E}}={\frac {1}{2}}\lambda \sum_{{(W_{i},W_{j})\in E}}\|W_{i}-W_{j }\|^{2};

La energía de flexión de una tarjeta elástica se define como

U_{G}={\frac {1}{2}}\mu \sum_{{(W_{i},W_{j},W_{l})\en G}}\|W_{i}- 2W_{j}+W_{l}\|^{2};

donde y son los coeficientes de elasticidad para tensión y flexión, respectivamente. $\lambda$ $\mu$

Por ejemplo, en el caso de una cuadrícula rectangular bidimensional de nodos, los enlaces elásticos son bordes de celosía verticales y horizontales (pares de vértices más cercanos), mientras que los refuerzos son triples verticales y horizontales de nodos consecutivos (más cercanos).

La energía del mapa elástico se define como

U=D+U_{E}+U_{G}.

Requerimos de la inserción del mapa que el mapa esté en equilibrio mecánico: el mapa debe minimizar la energía elástica . $tu$

Algoritmo de maximización de expectativas (algoritmo EM )

Para una partición dada del conjunto de datos en clases , la minimización del funcional cuadrático se reduce al problema de resolver un sistema de ecuaciones lineales con una matriz dispersa de coeficientes. De manera muy similar al algoritmo iterativo para construir los componentes principales o el algoritmo del método de K-medias , se puede utilizar la técnica de "división": $S$ $K_{j}$ $tu$

Para una posición dada de nodos, encontramos ; $\{W_{j}\}$ $\{K_{j}\}$
Para una partición dada , minimizamos y encontramos ; $\{K_{j}\}$ $tu$ $\{W_{j}\}$
Si la configuración de los nodos cambia poco, finalice el proceso; de lo contrario, repita la iteración.

Tal algoritmo de maximización de expectativas garantiza la convergencia a un mínimo local . Para mejorar la aproximación, se pueden utilizar varios métodos adicionales: por ejemplo, la estrategia de "suavizado". Según esta técnica, debemos comenzar construyendo un mapa con un sistema muy rígido (pequeñas longitudes de borde, pequeñas curvas y grandes valores de coeficientes de elasticidad y ), y completar la construcción con un sistema "flexible" (pequeños valores de y ). El entrenamiento del mapa se lleva a cabo en varias etapas, y cada etapa se caracteriza por su elasticidad. $tu$ $\lambda$ $\mu$ $\lambda$ $\mu$

Otra variante de la estrategia de optimización puede llamarse "cuadrícula creciente": la construcción de un mapa comienza con una pequeña cantidad de nodos y continúa con la adición gradual de nuevos nodos, seguido de la optimización de la posición del sistema en cada etapa [5] .

Aplicación

El método ha encontrado sus principales aplicaciones en bioinformática [7] [8] , para análisis exploratorio y visualización de datos multidimensionales, para visualización de datos en economía, sociología y ciencias políticas [9] , como método auxiliar para visualizar datos de diversa naturaleza, atado a una cuadrícula geográfica. Más recientemente, el método se ha adaptado como una herramienta para los sistemas de apoyo a la toma de decisiones para seleccionar, optimizar y organizar cestas de valores . [diez]

Notas

↑ 1 2 A. N. Gorban, AY Zinovyev, Principal Graphs and Manifolds Archivado el 6 de septiembre de 2008 en Wayback Machine , de: Manual de investigación sobre aplicaciones y tendencias de aprendizaje automático: algoritmos, métodos y técnicas, Olivas ES et al Eds. Referencia de ciencia de la información, IGI Global: Hershey, PA, EE. UU., 2009. 28-59.
↑ Wang, Y., Klijn, JG, Zhang, Y., Sieuwerts, AM, Look, MP, Yang, F., Talantov, D., Timmermans, M., Meijer-van Gelder, ME, Yu, J. et. al.: Perfiles de expresión génica para predecir la metástasis a distancia del cáncer de mama primario con ganglios linfáticos negativos. Lancet 365, 671-679 (2005); Conjunto de datos en línea Archivado el 17 de julio de 2011 en Wayback Machine .
↑ A. Zinovyev, ViDaExpert Archivado el 26 de abril de 2012 en Wayback Machine : herramienta de visualización de datos multidimensionales. Instituto Curie .
↑ A. Zinovyev, resumen de ViDaExpert Archivado el 4 de marzo de 2012 en Wayback Machine ( Institut des Hautes Études Scientifiques ).
↑ 1 2 A. Yu. Zinoviev. Visualización de datos multidimensionales Archivado el 13 de junio de 2008 en Wayback Machine . Krasnoyarsk: Editorial KSTU, 2000. - 168 p.
↑ AN Gorban, A. Zinovyev, Principales variedades y gráficos en la práctica: de la biología molecular a los sistemas dinámicos. Archivado el 10 de junio de 2016 en Wayback Machine , International Journal of Neural Systems , vol. 20, núm. 3 (2010) 219-232.
↑ AN Gorban, B. Kegl, D. Wunsch, A. Zinovyev (Eds.), Principal Manifolds for Data Visualization and Dimension Reduction Archivado el 6 de marzo de 2019 en Wayback Machine , LNCSE 58, Springer: Berlín-Heidelberg-Nueva York, 2007 ISBN 978-3-540-73749-0
↑ M. Chacón, M. Lévano, H. Allende, H. Nowak, Detection of Gene Expressions in Microarrays by Applying Iteratively Elastic Neural Net Archivado el 24 de agosto de 2011 en Wayback Machine , en: B. Beliczynski et al. (Eds.), Lecture Notes in Computer Sciences, vol. 4432, Springer: Berlín-Heidelberg 2007, 355-363.
↑ A. Zinovyev, Visualización de datos en ciencias políticas y sociales Archivado el 26 de agosto de 2016 en Wayback Machine , en: SAGE Archivado el 11 de enero de 2012 en Wayback Machine " Enciclopedia internacional de ciencia política ", Badie, B., Berg-Schlosser, D ., Morlino, LA (Eds.), 2011.
↑ M. Resta, Optimización de cartera a través de mapas elásticos: algunas pruebas de la bolsa de valores italiana , Sistemas de ingeniería e información inteligentes basados en el conocimiento, B. Apolloni, RJ Howlett y L. Jain (eds.), Lecture Notes in Computer Science, vol. . . 4693, Springer: Berlín-Heidelberg, 2010, 635-641.