Упругая карта
Упругая карта служит для нелинейного сокращения размерности данных. В многомерном пространстве данных располагается поверхность, которая приближает имеющиеся точки данных и при этом является, по возможности, не слишком изогнутой. Данные проецируются на эту поверхность и потом могут отображаться на ней, как на карте. Её можно представлять себе как упругую пластину, погруженную в пространство данных и прикрепленную к точкам данных пружинками. Служит обобщением метода главных компонент (в котором вместо упругой пластины используется абсолютно жесткая плоскость).
По построению, упругая карта представляет собой систему упругих пружин, вложенную в многомерное пространство данных[1][5]. Эта система апроксимирует двумерное многообразие. Изменение коэффициентов упругости системы позволяет пользователю переключаться от совершенно неструктурированной кластеризации методом K-средних (в пределе нулевой упругости) к многообразиям близким к линейным многообразиям главных компонент (в пределе очень больших модулей изгиба и малых модулей растяжения). В промежуточном диапазоне значений коэффициентов упругости, система эффективно апроксимирует некоторое нелинейное многообразие. Данный подход основывается на аналогии с механикой: главное многообразие, проходящее через «середину» данных, может быть представлено как упругая мембрана или пластинка. Метод был разработан проф., А. Н. Горбанем, А. Зиновьевым и А. Питенко в 1996—2001 годах.
Упругая энергия карты
[править | править код]Пусть набор данных будет представлен множеством векторов в конечномерном Евклидовом пространстве. «Упругая карта» представлена набором её узлов в том же пространстве. Для каждой точки данных , определяется узел-«хозяин» (host) как ближайший к точке узел карты (если окажется, что ближайших узлов несколько, то выбирается попросту узел с наименьшим порядковым номером). Набор данных делится на классы-таксоны .
Энергия апроксимации есть попросту среднеквадратичное уклонение от узлов карты
или, другими словами, есть суммарная упругая энергия пружинок с единичным коэффициентом упругости, соединяющих каждую точку данных с её узлом-«хозяином».
Необходимо ввести следующую дополнительную структуру на множестве узлов. Некоторые пары узлов, , соединены упругими связями-ребрами. Обозначим набор ребер графа как . Кроме того, будем объединять некоторые тройки узлов, в «ребра жесткости». Обозначим набор ребер жесткости как .
- Энергия растяжения упругой карты определяется как
- Энергия сгиба упругой карты определяется как
где и являются коэффициентами упругости на растяжение и сгиб соответственно.
Например, в случае двумерной прямоугольной сетки узлов, упругие связи являются вертикальными и горизонтальными ребрами решетки (пары ближайших вершин), в то время как ребра жесткости есть вертикальные и горизонтальные тройки последовательных (ближайших) узлов.
- Энергия упругой карты определена как
Мы требуем от вложения карты того, чтобы карта находилась бы в механическом равновесии: карта должна минимизировать энергию упругости .
Алгоритм максимизации ожидания (EM-алгоритм)
[править | править код]Для заданного разбиения набора данных на классы , минимизация квадратичного функционала сводится к задаче решения системы линейных уравнений с разреженной матрицей коэффициентов. Вполне аналогично итеративному алгоритму построения главных компонент или алгоритму метода K-средних, может быть использован прием «расщепления»:
- Для заданного положения узлов находим ;
- Для заданного разбиения минимизируем и находим ;
- Если конфигурация узлов мало меняется, завершить процесс, иначе повторить итерацию.
Подобный алгоритм максимизации ожидания гарантирует сходимость к локальному минимуму . Для того, чтобы улучшить апроксимацию, могут быть использованы различные дополнительные методы: например, стратегия «размягчения». Согласно этому приему, мы должны начать построение карты с очень жесткой системы (малые длины ребер, малые изгибы и большие значения коэффициентов упругости и ), а завершать построение «гибкой» системой (малые значения и ). Обучение карты проходит в несколько этапов, причем каждый этап характеризуется своей упругостью.
Другой вариант стратегии оптимизации может быть назван «растущей сеткой»: построение карты начинается с небольшого числа узлов, и продолжается постепенным добавлением новых узлов, с последующей оптимизацией положения системы на каждом этапе[5].
Применение
[править | править код]Главные применения метод нашёл в биоинформатике[7][8], для разведочного анализа и визуализации многомерных данных, для визуализации данных в экономике, социологии и политологии[9], как вспомогательный метод для визуализации данных различной природы, привязанных к географической сетке. В последнее время метод был адаптирован как средство для систем поддержки принятия решений для отбора, оптимизации и организации биржевых корзин.[10]
Примечания
[править | править код]- ↑ 1 2 A. N. Gorban, A. Y. Zinovyev, Principal Graphs and Manifolds Архивная копия от 6 сентября 2008 на Wayback Machine, Из: 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.
- ↑ 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); Набор данных в сети Архивная копия от 17 июля 2011 на Wayback Machine
- ↑ A. Zinovyev, ViDaExpert Архивная копия от 26 апреля 2012 на Wayback Machine — Multidimensional Data Visualization Tool. Institut Curie.
- ↑ A. Zinovyev, ViDaExpert overview Архивная копия от 4 марта 2012 на Wayback Machine (Institut des Hautes Études Scientifiques).
- ↑ 1 2 А. Ю. Зиновьев. Визуализация многомерных данных Архивная копия от 13 июня 2008 на Wayback Machine. Красноярск: Изд-во КГТУ, 2000. — 168 с.
- ↑ A. N. Gorban, A. Zinovyev, Principal manifolds and graphs in practice: from molecular biology to dynamical systems Архивная копия от 10 июня 2016 на Wayback Machine, International Journal of Neural Systems, Vol. 20, No. 3 (2010) 219—232.
- ↑ A.N. Gorban, B. Kegl, D. Wunsch, A. Zinovyev (Eds.), Principal Manifolds for Data Visualisation and Dimension Reduction Архивная копия от 6 марта 2019 на Wayback Machine, LNCSE 58, Springer: Berlin — Heidelberg — New 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 Архивная копия от 24 августа 2011 на Wayback Machine, In: B. Beliczynski et al. (Eds.), Lecture Notes in Computer Sciences, Vol. 4432, Springer: Berlin — Heidelberg 2007, 355—363.
- ↑ A. Zinovyev, Data visualization in political and social sciences Архивная копия от 26 августа 2016 на Wayback Machine, In: SAGE Архивная копия от 11 января 2012 на Wayback Machine «International Encyclopedia of Political Science», Badie, B., Berg-Schlosser, D., Morlino, L. A. (Eds.), 2011.
- ↑ 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.