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

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

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

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

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

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

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

${\displaystyle D={\frac {1}{2}}\sum _{j=1}^{k}\sum _{x\in K_{j}}\|x-W_{j}\|^{2},}$

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

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

Энергия растяжения упругой карты определяется как ${\displaystyle U_{E}={\frac {1}{2}}\lambda \sum _{(W_{i},W_{j})\in E}\|W_{i}-W_{j}\|^{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 }$ являются коэффициентами упругости на растяжение и сгиб соответственно.

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

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

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

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

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

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

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

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

Применение

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

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