Упругая карта

Сравнение нелинейного метода главных многообразий и линейного метода главных компонент (МГК) ^[1] для визуализации данных генетических чипов по экспрессии генов в раке груди: a) Расположение узлов карты и двумерная главная поверхность, спроектированная на трехмерное линейное многообразие первых трех главных компонент. Распределение точек данных искривленно и не может быть адекватно аппроксимировано двумерной главной плоскостью; b) Распределение проекций точек данных во внутренние координаты двумерной нелинейной главной поверхности (ELMap2D) вместе с оценкой плотности точек; c) То же, что и b), но для линейного двумерного главного многообразия (PCA2D). «Базальный» («basal») подтип рака груди визуализируется более адекватно на нелинейном отображении ELMap2D, а также некоторые особенности распределения точек данных (такие как, небольшие локальные сгущения плотности) лучше отражены в сравнении с PCA2D. Главные многообразия построены с использованием метода упругих карт. Данные об экспрессии генов взяты из ^[2]. Программное обеспечение доступно для свободного некоммерческого использования. ^[3][4]

Упругая карта служит для нелинейного сокращения размерности данных. В многомерном пространстве данных располагается поверхность, которая приближает имеющиеся точки данных и при этом является, по возможности, не слишком изогнутой. Данные проецируются на эту поверхность и потом могут отображаться на ней, как на карте. Ее можно представлять себе как упругую пластину, погруженную в пространство данных и прикрепленную к точкам данных пружинками. Служит обобщением метода главных компонент (в котором вместо упругой пластины используется абсолютно жесткая плоскость).

По построению, упругая карта представляет собой систему упругих пружин, вложенную в многомерное пространство данных^[1][5]. Эта система апроксимирует двумерное многообразие. Изменение коэффициэнтов упругости системы позволяет пользователю переключаться от совершенно неструктурированной кластеризации методом K-средних (в пределе нулевой упругости) к многообразиям близким к линейным многообразиям главных компонент (в пределе очень больших модулей изгиба и малых модулей растяжения). В промежуточном диапазоне значений коэффициэнтов упругости, система эффективно апроксимирует некоторое нелинейное многообразие. Данный подход основывается на аналогии с механикой: главное многообразие, проходящее через «середину» данных, может быть представлено как упругая мембрана или пластинка. Метод был разработан проф., д.ф.-м.н. А. Н. Горбанем, к.т.н. А. Зиновьевым и к.т.н А. Питенко в 1996—2001 гг.

Упругая энергия карты

Пусть набор данных будет представлен множеством векторов $S$ в конечномерном Евклидовом пространстве. «Упругая карта» представлена набором её узлов $W_j$ в том же пространстве. Для каждой точки данных $s \in S$ , определяется узел-«хозяин» (host) как ближайший к точке узел карты $W_j$ (если окажется, что ближайших узлов несколько, то выбирается попросту узел с наименьшим порядковым номером). Набор данных $S$ делится на классы-таксоны $K_j=\{s \ | \ W_j \mbox{ is a host of } s\}$.

Энергия апроксимации есть попросту среднеквадратичное уклонение от узлов карты

$D=\frac{1}{2}\sum_{j=1}^k \sum_{x \in K_j}\|x-W_j\|^2,$

или, другими словами, есть суммарная упругая энергия пружинок с единичным коэффициэнтом упругости, соединяющих каждую точку данных с её узлом-«хозяином».

Необходимо ввести следующую дополнительная структуру на множестве узлов. Некоторые пары узлов, $(W_i,W_j)$, соединены упругими связями-ребрами. Обозначим набор ребер графа как $E$. Кроме того, будем объединять некоторые тройки узлов, $(W_i,W_j,W_k)$ в «ребра жесткости». Обозначим набор ребер жесткости как $G$.

Энергия растяжения упругой карты определяется как $U_{E}=\frac{1}{2}\lambda \sum_{(W_i,W_j) \in E} \|W_i -W_j\|^2 ;$

Энергия сгиба упругой карты определяется как $U_G=\frac{1}{2}\mu \sum_{(W_i,W_j,W_l) \in G} \|W_i -2W_j+W_l\|^2 ;$

где $\lambda$ и $\mu$ являются коэффициэнтами упругости на растяжение и сгиб соответственно.

Например, в случае двумерной прямоугольной сетки узлов, упругие связи являются вертикальными и горизонтальными ребрами решетки (пары ближайших вершин), в то время как ребра жесткости есть вертикальные и горизонтальные тройки последовательных (ближайших) узлов.

Энергия упругой карты определена как $U=D+U_E+U_G.$

Мы требуем от вложения карты того, чтобы карта находилась бы в механическом равновесии: карта должна минимизировать энергию упругости $U$.

Алгоритм максимизации ожидания (EM-алгоритм)

Для заданного разбиения набора данных $S$ на классы $K_j$ , минимизация квадратичного функционала $U$ сводится к задаче решения системы линейных уравнений с разреженной матрицей коэффициэнтов. Вполне аналогично итеративному алгоритму построения главных компонент или алгоритму метода K-средних, может быть использован прием «расщепления»:

• Для заданного положения узлов $\{W_j\}$ находим $\{K_j\}$;
• Для заданного разбиения $\{K_j\}$ минимизируем $U$ и находим $\{W_j\}$;
• Если конфигурация узлов мало меняется, завершить процесс, иначе повторить итерацию.

Подобный алгоритм максимизации ожидания гарантирует сходимость к локальному минимуму $U$. Для того, чтобы улучшить апроксимацию, могут быть использованы различные дополнительные методы: например, стратегия «размягчения». Согласно этому приему, мы должны начать построение карты с очень жесткой системы (малые длины ребер, малые изгибы и большие значения коэффициэнтов упругости $\lambda$ и $\mu$), а завершать построение «гибкой» системой (малые значения $\lambda$ и $\mu$). Обучение карты проходит в несколько этапов, причем каждый этап характеризуется своей упругостью.

Другой вариант стратегии оптимизации может быть назван «растущей сеткой»: построение карты начинается с небольшого числа узлов, и продолжается постепенным добавлением новых узлов, с последующей оптимизацией положения системы на каждом этапе^[5].

Применение

Пример использования главной кривой, построенной методом упругих карт: Нелинейный индекс качества жизни^[6]. Здесь точки представляют собой данные о 171 странах в 4-мерном пространстве сформированном значениями четырёх показателей: валовый доход на душу населения, ожидаемая продолжительность жизни, детская смертность, заболеваемось туберкулезом. Различные формы и цвета точек отображают разные географические местоположения. Толстая красная линия изображает «главную кривую», апроксимирующую набор данных.

Главные применения метод нашёл в биоинформатике ^{[7] [8]}, для разведочного анализа и визуализации многомерных данных, для визуализации данных в экономике, социологии и политологии ^[9], как вспомогaтельный метод для визуализации данных различной природы, привязанных к географической сетке. В последнее время метод был адаптирован как средство для систем поддержки принятия решений для отбора, оптимизации и организации биржевых корзин.^[10]

Примечания

1. ↑ ^{1 2} A. N. Gorban, A. Y. Zinovyev, Principal Graphs and Manifolds, Из: Handbook of Research on Machine Learning Applications and Trends: Algorithms, Methods and Techniques, Olivas E.S. et al Eds. Information Science Reference, IGI Global: Hershey, PA, USA, 2009. 28-59.
2. ↑ Wang, Y., Klijn, J.G., Zhang, Y., Sieuwerts, A.M., Look, M.P., Yang, F., Talantov, D., Timmermans, M., Meijer-van Gelder, M.E., Yu, J. et al.: Gene expression profiles to predict distant metastasis of lymph-node-negative primary breast cancer. Lancet 365, 671—679 (2005); Набор данных в сети
3. ↑ A. Zinovyev, ViDaExpert - Multidimensional Data Visualization Tool (free for non-commercial use). Institut Curie, Paris.
4. ↑ A. Zinovyev, ViDaExpert overview, IHES (Institut des Hautes Études Scientifiques), Bures-Sur-Yvette, Île-de-France.
5. ↑ ^{1 2} А. Ю. Зиновьев. Визуализация многомерных данных. Красноярск: Изд-во КГТУ, 2000. — 168 с.
6. ↑ A. N. Gorban, A. Zinovyev, Principal manifolds and graphs in practice: from molecular biology to dynamical systems, International Journal of Neural Systems, Vol. 20, No. 3 (2010) 219—232.
7. ↑ A.N. Gorban, B. Kegl, D. Wunsch, A. Zinovyev (Eds.), Principal Manifolds for Data Visualisation and Dimension Reduction, LNCSE 58, Springer: Berlin — Heidelberg — New York, 2007. ISBN 978-3-540-73749-0
8. ↑ M. Chacón, M. Lévano, H. Allende, H. Nowak, Detection of Gene Expressions in Microarrays by Applying Iteratively Elastic Neural Net, In: B. Beliczynski et al. (Eds.), Lecture Notes in Computer Sciences, Vol. 4432, Springer: Berlin — Heidelberg 2007, 355—363.
9. ↑ A. Zinovyev, Data visualization in political and social sciences, In: SAGE «International Encyclopedia of Political Science», Badie, B., Berg-Schlosser, D., Morlino, L. A. (Eds.), 2011.
10. ↑ M. Resta, Portfolio optimization through elastic maps: Some evidence from the Italian stock exchange, Knowledge-Based Intelligent Information and Engineering Systems, B. Apolloni, R.J. Howlett and L. Jain (eds.), Lecture Notes in Computer Science, Vol. 4693, Springer: Berlin — Heidelberg, 2010, 635—641.