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