Многомерное масштабирование¶
Многомерное масштабирование ( $MDS$ ) - это средство визуализации уровня сходства отдельных объектов в наборе данных. $MDS$ используется для перевода информации о попарных« расстояниях между $n$ объектами в наборе данных в конфигурацию $n$ точек, отображаемых в абстрактное декартово пространство. С технической точки зрения, $MDS$ относится к набору связанных методов ординации , используемых при визуализации информации , в частности, для отображения информации, содержащейся в матрице расстояний . Это форма нелинейного уменьшения размерности. Учитывая матрицу расстояний расстояниями между каждой парой объектов в наборе данных, и выбрав число измерений $N$ , $MDA$ алгоритм помещает каждый объект в $N$ - мерном пространстве (низкоразмерное представление), так что между объектами расстояния сохранялись как можно лучше. Для N = 1, 2 и 3 полученные точки можно визуализировать на диаграмме рассеяния .
Формально можно задачу многомерного шкалирования сформулировать следующим образом. Имеется обучающая выборка объектов ${\bf X}^p = \{ x_1 ,...,x_p \} \subset {\bf X}$. Заданы расстояния $R_{ij} = \rho (x_i ,x_j )$ для некоторых пар обучающих объектов $(i,j) \in D$ Требуется для каждого объекта $x_i \in {\bf X}^p$ построить его признаковое описание вектор $x_i = (x_i^1 ,...,x_i^n )$ в евклидовом пространстве $\Re ^n$ так, чтобы евклидовы расстояния $d_{ij}$ между объектами $x_i$ и $x_j$:
$$d_{ij}^2 = \sum\limits_{d = 1}^n {(x_i^d } - x_j^d )^2 {\rm \;\;\;\;(1)}$$
как можно точнее приближали исходные расстояния $R_{ij}$ для всех $(i,j) \in D$.
Данное требование можно формализовать по-разному; один из наиболее распространённых
способов через минимизацию функционала, называемого стрессом:
$$S({\bf X}^p ) = \sum\limits_{(i,j) \in D} {w_{ij} (d_{ij} } - R_{ij} )^2 \to \min {\rm \;\;\;\;(2)}$$
где минимум берётся по совокупности $pn$ переменных $(x_i^d )_{i = 1,p}^{d = 1,n}$
Размерность n обычно задаётся небольшая. В частности, при $n = 2$ многомерное шкалирование позволяет отобразить выборку в виде множества точек на плоскости. Плоское представление, как правило, искажено ($S > 0$), но в целом отражает основные структурные особенности многомерной выборки, в частности, её кластерную структуру. Поэтому двумерное шкалирование часто используют как инструмент предварительного анализа и понимания данных.
Веса $w_{ij}$ задаются исходя из целей шкалирования. Обычно берут $w_{ij} = (R_{ij} )^\gamma$. При $\gamma < 0$ приоритет отдаётся более точному приближению малых расстояний; при $\gamma > 0$ больших расстояний. Наиболее адекватным считается значение $\gamma = -2$, когда функционал стресса приобретает физический смысл потенциальной энергии системы $p$ материальных точек, связанных упругими связями; требуется найти равновесное состояние системы, в котором потенциальная энергия минимальна. Функционал стресса $S({\bf X}^p )$ сложным образом зависит от $pn$ переменных, имеет огромное количество локальных минимумов, и его вычисление довольно трудоёмко.Поэтому многие алгоритмы многомерного шкалирования основаны на итерационном размещении объектов по одному. На каждой итерации оптимизируются евклидовы координаты только одного из объектов, а координаты остальных объектов, вычисленные на предыдущих итерациях, полагаются фиксированными.
Кратко формально опишим варианты реализации MDS
Классическое многомерное масштабирование¶
$MDS$ также известен как масштабирование Торгерсона – Гауэра. Он, как уже говорилось выше, принимает входную матрицу, определяющую различия между парами элементов, и выводит координатную матрицу, конфигурация которой минимизирует функцию потерь, называемую деформацией. На практике $MDS$ стремится аппроксимировать исходное пространство данных его представлением пространством более низкой размерности, минимизируя функцию потерь. Общие формы функций потерь называются напряжением на расстоянии $MDS$ и деформацией в классической $MDS$. Напряжение определяется:
$$S_{train_D } (x_1 ,x_2 ,...,x_N ) = (\frac{{\sum\nolimits_{i,j} {(b_{ij} - {\bf x}_i^T {\bf x}_j )^2 } }}{{\sum\nolimits_{i,j} {b_{ij}^2 } }})^{1/2} {\rm \;\;\;\;(3)}$$
где ${\bf x}_i$ вектор в $N$ - мерном пространстве; ${{\bf x}_i^T {\bf x}_j }$ - скалярное произведение векторов ${\bf x}_i$ и ${\bf x}_j$; $b_{ij}$ - элементы матрицы ${\bf B}$ определенные на шаге 2 следующего алгоритма, которые вычисляются из расстояний.
Шаги классического алгоритма $MDS$:
Классическая $MDS$ использует тот факт, что координатная матрица ${\bf X}$ сможет быть получена разложением на собственные значения из ${\bf B} = {\bf XX}^T$. Матрица ${\bf B}$ получается из матрицы ,близости ${\bf D}$ с помощью двойного центрирования.
Получить квадратную матрицу близости ${\bf D}^{(2)} = [d_{ij}^2 ]$.
Применить двойное центрирование: ${\bf B} = \frac{1}{2}{\bf CD}^{(2)}$, здесь ${\bf C} = {\bf I} - \frac{1}{p}{\bf J}_p$ где $p$ - количество объектов; ${\bf I}$ -это единичная матрица размерности $p \times p$; ${\bf J}_p$ также единичная матрица размерности $p \times p$.
Из матрицы ${\bf B}$ получаем $m$ наибольших собственных значений $\lambda _1 ,\lambda _2 ,...,\lambda _m$ и соответствующие собственные вектора ${\bf e}_1 ,{\bf e}_2 ,...,{\bf e}_m$ ($m$ - требуемая размерность редуцированного пространства объектов).
Получение ${\bf X} = {\bf E}_m {\bf \Lambda }_m^{1/2}$ , где ${\bf E}_m$ матрица их $m$ собственных векторов; ${\bf \Lambda }_m$ -диагональная матрица из $m$ собственных значений матрицы ${\bf B}$
Классическая $MDS$ предполагает евклидовы расстояния.
Метрическое многомерное масштабирование ($mMDS$)¶
Это надмножество классической MDS, которое обобщает процедуру оптимизации на множество функций потерь и входных матриц известных расстояний с весами и т. Д. Полезная функция потерь в этом контексте называется стрессом (см. выше) , который часто минимизируется с помощью процедуры, называемой мажоризацией стресса . Метрика MDS минимизирует функцию затрат, называемую «стресс», которая представляет собой остаточную сумму квадратов:
$$S_{tress_D } (x{}_1,x{}_2,...,x_N ) = (\sum\limits_{i \ne j = 1,...N} {(d_{ij} - \left\| {{\bf x}_i - {\bf x}_j } \right\|} )^2 )^{1/2} {\rm \;\;\;\;(4)}$$
При масштабировании показателей используется преобразование степени с показателем степени, управляемым пользователем. $\gamma$ :$d_{ij}^{\gamma}$ и $d_{ij}^{2\gamma}$.В классическом масштабировании $\gamma =1$.
Неметрическое многомерное масштабирование ($nMDS$)¶
В отличие от метрической $MDS$, неметрическая $MDS$ находит как непараметрическую монотонную связь между различиями в матрице элемент-элемент и евклидовыми расстояниями между элементами, так и расположением каждого элемента в низкоразмерном пространстве. Взаимосвязь обычно определяется с помощью изотонической регрессии : пусть ${\bf x}$ обозначим вектор близости, ${\bf f}({\bf x})$ монотонное преобразование ${\bf x}$, а также $d$ точечные расстояния; затем необходимо найти координаты, которые минимизируют так называемое напряжение:
$$S_{tress} = \sqrt {\frac{{\sum {({\bf f}({\bf x}) - d)^2 } }}{{\sum {d^2 } }}} {\rm \;\;\;\;(5)}$$
Существует несколько вариантов этой функции затрат. Программы $MDS$ автоматически минимизируют стресс, чтобы получить решение. Ядро неметрического алгоритма $MDS$ - это двойной процесс оптимизации. Сначала нужно найти оптимальное монотонное преобразование близости. Во-вторых, точки конфигурации должны быть расположены оптимальным образом, чтобы их расстояния как можно ближе соответствовали масштабируемой близости. Основные шаги неметрического алгоритма $MDS$:
Найдти случайную конфигурацию точек, например, путем выборки из нормального распределения.
Вычислить расстояния $d$ между точками.
Найдти оптимальное монотонное преобразование близости, чтобы получить оптимально масштабированные данные ${\bf f}({\bf x})$.
Минимизировать напряжение между оптимально масштабированными данными и расстояниями, найдя новую конфигурацию точек.
Сравнить напряжение с некоторым критерием. Если напряжение достаточно мало, выйдти из алгоритма, иначе вернуться к 2.
Анализ наименьшего пространства ($SSA$) Луи Гутмана является примером неметрической процедуры $MDS$.
Обобщенное многомерное масштабирование ($GMD$)¶
Расширение метрического многомерного масштабирования, в котором целевым пространством является произвольное гладкое неевклидово пространство. В случаях, когда различия - это расстояния на поверхности, а целевое пространство - это другая поверхность, GMDS позволяет найти вложение одной поверхности в другую с минимальным искажением.
Анализируемые данные представляют собой совокупность $M$ объектов, для которых определена функция расстояния, $d_ {i, j}$: дистанция между $i$-тым и $j$-ым объекектами. Эти расстояния являются элементами матрицы несходства $D$.
Целью $MDS$ является зная $D$, найти $M$ векторов ${\bf x}{}_1,...{\bf x}{}_M \in \Re ^N$ таких,что $\left\| {{\bf x}{}_i - {\bf x}{}_j} \right\| \approx d_{ij}$ для всех $i,j \in 1,...M$
где $\left\| . \right\|$ - векторная норма. В классическом $MDS$ эта норма является евклидовым расстоянием, но, в более широком смысле, это может быть метрическая или произвольная функция расстояния.
Другими словами, $MDS$ пытается найти отображение $M$ объектов в $\Re ^N$ таким образом, что расстояния сохраняются.
Если размер $N$ выбран 2 или 3, то можно построить вектора ${{\bf x}{}_i}$ чтобы получить визуализацию сходства между $M$ объекты. При этом важно, что эти векторы не уникальны пр данном евклидовым расстоянием они могут произвольно перемещаться, вращаться и отражаться, поскольку эти преобразования не изменяют попарные расстояния $\left\| {{\bf x}{}_i - {\bf x}{}_j}\right\|$
Существуют различные подходы к определению векторов ${{\bf x}{}_i}$.Обычно МДС формулируется как задача оптимизации,где ${\bf x}{}_1,...{\bf x}_M$ достовляют минимум некоторой функции стоимости:
$$\mathop {\arg \min }\limits_{{\bf x}_1 ,....,{\bf x}_M } \sum\limits_{i < j} {(\left\| {{\bf x}_i - {\bf x}_j } \right\|} - d_{ij} )^2 {\rm \;\;\;\;(6)}$$
Затем решение может быть найдено с помощью методов численной оптимизации. Для некоторых специально выбранных функций стоимости минимизаторы могут быть сформулированы аналитически в терминах разложения собственных матриц.
$\href{https://en.wikipedia.org/wiki/Multidimensional_scaling}{originalsource}$
Пример реализации алгоритма $MDS$ на $python$ и $R$.¶
Для рачетов использовались данный о Российских регионах. В $python$ реализации исходным было $3D$ пространство, регионы размечены на три класса. Для R реализаци исходное пространство $4D$, а регионы размечены на четыре класса.
В scikit-learn мы задаем два параметра n_components = 2 (размерность выходного редуцируемого пространства) и metric = True (метрический MDS) или False (неметрический MDS) остальные параметры принимаются по умолчанию
Код $python$ :
