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

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

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

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

Пусть набор данных будет представлен множеством векторов S {displaystyle S} в конечномерном Евклидовом пространстве. «Упругая карта» представлена набором её узлов W j {displaystyle W_{j}} в том же пространстве. Для каждой точки данных s ∈ S {displaystyle sin S} , определяется узел-«хозяин» (host) как ближайший к точке узел карты W j {displaystyle W_{j}} (если окажется, что ближайших узлов несколько, то выбирается попросту узел с наименьшим порядковым номером). Набор данных S {displaystyle S} делится на классы-таксоны K j = { s   |   W j  is a host of  s } {displaystyle K_{j}={s | W_{j}{mbox{ is a host of }}s}} .

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

D = 1 2 ∑ j = 1 k ∑ x ∈ K j ‖ x − W j ‖ 2 , {displaystyle D={frac {1}{2}}sum _{j=1}^{k}sum _{xin K_{j}}|x-W_{j}|^{2},}

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

Необходимо ввести следующую дополнительную структуру на множестве узлов. Некоторые пары узлов, ( W i , W j ) {displaystyle (W_{i},W_{j})} , соединены упругими связями-ребрами. Обозначим набор ребер графа как E {displaystyle E} . Кроме того, будем объединять некоторые тройки узлов, ( W i , W j , W k ) {displaystyle (W_{i},W_{j},W_{k})} в «ребра жесткости». Обозначим набор ребер жесткости как G {displaystyle G} .

Энергия растяжения упругой карты определяется как U E = 1 2 λ ∑ ( W i , W j ) ∈ E ‖ W i − W j ‖ 2 ; {displaystyle U_{E}={frac {1}{2}}lambda sum _{(W_{i},W_{j})in E}|W_{i}-W_{j}|^{2};} Энергия сгиба упругой карты определяется как U G = 1 2 μ ∑ ( W i , W j , W l ) ∈ G ‖ W i − 2 W j + W l ‖ 2 ; {displaystyle U_{G}={frac {1}{2}}mu sum _{(W_{i},W_{j},W_{l})in G}|W_{i}-2W_{j}+W_{l}|^{2};}

где λ {displaystyle lambda } и μ {displaystyle mu } являются коэффициентами упругости на растяжение и сгиб соответственно.

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

Энергия упругой карты определена как U = D + U E + U G . {displaystyle U=D+U_{E}+U_{G}.}

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

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

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

• Для заданного положения узлов { W j } {displaystyle {W_{j}}} находим { K j } {displaystyle {K_{j}}} ;
• Для заданного разбиения { K j } {displaystyle {K_{j}}} минимизируем U {displaystyle U} и находим { W j } {displaystyle {W_{j}}} ;
• Если конфигурация узлов мало меняется, завершить процесс, иначе повторить итерацию.

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

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

Применение

Главные применения метод нашёл в биоинформатике, для разведочного анализа и визуализации многомерных данных, для визуализации данных в экономике, социологии и политологии, как вспомогательный метод для визуализации данных различной природы, привязанных к географической сетке. В последнее время метод был адаптирован как средство для систем поддержки принятия решений для отбора, оптимизации и организации биржевых корзин.