Многомерное масштабирование

Многомерное шкалирование ( MDS ) — это средство визуализации уровня сходства отдельных случаев набора данных. MDS используется для перевода расстояний между каждой парой объектов в наборе в конфигурацию точек, отображенных в абстрактном декартовом пространстве . ^[1]${\textstyle n}$${\textstyle n}$

Более технически, MDS относится к набору связанных методов ординации , используемых в визуализации информации , в частности, для отображения информации, содержащейся в матрице расстояний . Это форма нелинейного снижения размерности .

При наличии матрицы расстояний с расстояниями между каждой парой объектов в наборе и выбранного числа измерений N алгоритм MDS помещает каждый объект в N - мерное пространство (представление с меньшей размерностью) таким образом, чтобы расстояния между объектами сохранялись как можно лучше. Для N = 1, 2 и 3 полученные точки можно визуализировать на диаграмме рассеяния . ^[2]

Основной теоретический вклад в MDS внес Джеймс О. Рэмси из Университета Макгилла , которого также считают основателем функционального анализа данных . ^[3]

Алгоритмы MDS делятся на таксономию в зависимости от значения входной матрицы:

Он также известен как анализ главных координат (PCoA), масштабирование Торгерсона или масштабирование Торгерсона–Гауэра. Он берет входную матрицу, дающую различия между парами элементов, и выводит координатную матрицу, конфигурация которой минимизирует функцию потерь, называемую strain , ^[2] , которая задается как , где обозначают векторы в N -мерном пространстве, обозначает скалярное произведение между и , и являются элементами матрицы, определенной на шаге 2 следующего алгоритма, которые вычисляются из расстояний.$${\displaystyle {\text{Strain}}_{D}(x_{1},x_{2},...,x_{n})={\Biggl (}{\frac {\sum _{i,j}{\bigl (}b_{ij}-x_{i}^{T}x_{j}{\bigr )}^{2}}{\sum _{i,j}b_{ij}^{2}}}{\Biggr )}^{1/2},}$$${\displaystyle x_{i}}$${\displaystyle x_{i}^{T}x_{j}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle b_{ij}}$${\displaystyle B}$

Этапы классического алгоритма MDS:

Классический MDS использует тот факт, что матрица координат может быть получена путем разложения собственных значений из . И матрица может быть вычислена из матрицы близости с использованием двойного центрирования. ^[4]${\displaystyle X}$${\textstyle B=XX'}$${\textstyle B}$${\textstyle D}$

1. Настройте квадратную матрицу близости${\textstyle D^{(2)}=[d_{ij}^{2}]}$
2. Применить двойное центрирование: использовать матрицу центрирования , где — количество объектов, — единичная матрица, а — матрица всех единиц.${\textstyle B=-{\frac {1}{2}}CD^{(2)}C}$ ${\textstyle C=I-{\frac {1}{n}}J_{n}}$${\textstyle n}$${\textstyle I}$${\textstyle n\times n}$${\textstyle J_{n}}$${\textstyle n\times n}$
3. Определите наибольшие собственные значения и соответствующие им собственные векторы (где — число измерений, требуемых для вывода).${\textstyle m}$ ${\textstyle \lambda _{1},\lambda _{2},...,\lambda _{m}}$ ${\textstyle e_{1},e_{2},...,e_{m}}$${\textstyle B}$${\textstyle m}$
4. Теперь, , где — матрица собственных векторов, а — диагональная матрица собственных значений .${\textstyle X=E_{m}\Lambda _{m}^{1/2}}$${\textstyle E_{m}}$${\textstyle m}$${\textstyle \Lambda _{m}}$${\textstyle m}$${\textstyle B}$

Классический MDS предполагает метрические расстояния. Поэтому это не применимо для оценок прямого различия.

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

${\displaystyle {\text{Stress}}_{D}(x_{1},x_{2},...,x_{n})={\sqrt {\sum _{i\neq j=1,...,n}{\bigl (}d_{ij}-\|x_{i}-x_{j}\|{\bigr )}^{2}}}.}$

Метрическое масштабирование использует степенное преобразование с контролируемой пользователем экспонентой : и для расстояния. В классическом масштабировании неметрическое масштабирование определяется использованием изотонической регрессии для непараметрической оценки преобразования различий.${\textstyle p}$${\textstyle d_{ij}^{p}}$${\textstyle -d_{ij}^{2p}}$${\textstyle p=1.}$

В отличие от метрического MDS, неметрический MDS находит как непараметрическую монотонную связь между различиями в матрице элемент-элемент и евклидовыми расстояниями между элементами, так и местоположение каждого элемента в низкоразмерном пространстве.

Пусть будет различием между точками . Пусть будет евклидовым расстоянием между вложенными точками .${\displaystyle d_{ij}}$${\displaystyle i,j}$${\displaystyle {\hat {d}}_{ij}=\|x_{i}-x_{j}\|}$${\displaystyle x_{i},x_{j}}$

Теперь для каждого выбора вложенных точек , где функция монотонно возрастает , определим функцию «напряжения»:${\displaystyle x_{i}}$${\displaystyle f}$

${\displaystyle S(x_{1},...,x_{n};f)={\sqrt {\frac {\sum _{i<j}{\bigl (}f(d_{ij})-{\hat {d}}_{ij}{\bigr )}^{2}}{\sum _{i<j}{\hat {d}}_{ij}^{2}}}}.}$

Фактор в знаменателе необходим для предотвращения "коллапса". Предположим, что мы вместо этого определяем , тогда его можно тривиально минимизировать, установив , а затем свернуть каждую точку в одну и ту же точку.${\displaystyle \sum _{i<j}{\hat {d}}_{ij}^{2}}$${\displaystyle S={\sqrt {\sum _{i<j}{\bigl (}f(d_{ij})-{\hat {d}}_{ij})^{2}}}}$${\displaystyle f=0}$

Существует несколько вариантов этой функции стоимости. Программы MDS автоматически минимизируют стресс, чтобы получить решение MDS.

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

NMDS необходимо оптимизировать две цели одновременно. Обычно это делается итеративно:

1. Инициализация случайным образом, например, путем выборки из нормального распределения.${\displaystyle x_{i}}$
2. Выполнять до критерия остановки (например, )${\displaystyle S<\epsilon }$
   1. Решить с помощью изотонической регрессии .${\displaystyle f=\arg \min _{f}S(x_{1},...,x_{n};f)}$
   2. Решите методом градиентного спуска или другими методами.${\displaystyle x_{1},...,x_{n}=\arg \min _{x_{1},...,x_{n}}S(x_{1},...,x_{n};f)}$
3. Вернуться и${\displaystyle x_{i}}$${\displaystyle f}$

Анализ наименьшего пространства (SSA) Луиса Гуттмана является примером неметрической процедуры MDS.

Расширение метрического многомерного масштабирования, в котором целевое пространство — произвольное гладкое неевклидово пространство. В случаях, когда различия — это расстояния на поверхности, а целевое пространство — другая поверхность, GMDS позволяет найти вложение одной поверхности в другую с минимальным искажением. ^[5]

Данные для анализа представляют собой набор объектов (цвета, лица, акции, ...), для которых определена функция расстояния ,${\displaystyle M}$

${\displaystyle d_{i,j}:=}$расстояние между -м и -м объектами.${\displaystyle i}$${\displaystyle j}$

Эти расстояния являются элементами матрицы различий.

${\displaystyle D:={\begin{pmatrix}d_{1,1}&d_{1,2}&\cdots &d_{1,M}\\d_{2,1}&d_{2,2}&\cdots &d_{2,M}\\\vdots &\vdots &&\vdots \\d_{M,1}&d_{M,2}&\cdots &d_{M,M}\end{pmatrix}}.}$

Целью MDS является, учитывая , нахождение векторов, таких что${\displaystyle D}$${\displaystyle M}$${\displaystyle x_{1},\ldots ,x_{M}\in \mathbb {R} ^{N}}$

${\displaystyle \|x_{i}-x_{j}\|\approx d_{i,j}}$для всех ,${\displaystyle i,j\in {1,\dots ,M}}$

где — векторная норма . В классическом MDS эта норма — евклидово расстояние , но в более широком смысле это может быть метрическая или произвольная функция расстояния. ^[6] Например, при работе с данными смешанного типа, содержащими как числовые, так и категориальные дескрипторы, расстояние Гауэра является распространенной альтернативой. ^{[ требуется цитата ]}${\displaystyle \|\cdot \|}$

Другими словами, MDS пытается найти отображение из объектов в , при котором расстояния сохраняются. Если размерность выбрана 2 или 3, мы можем построить векторы , чтобы получить визуализацию сходств между объектами. Обратите внимание, что векторы не являются уникальными: с евклидовым расстоянием их можно произвольно переводить, вращать и отражать, поскольку эти преобразования не изменяют попарные расстояния .${\displaystyle M}$${\displaystyle \mathbb {R} ^{N}}$${\displaystyle N}$${\displaystyle x_{i}}$${\displaystyle M}$${\displaystyle x_{i}}$${\displaystyle \|x_{i}-x_{j}\|}$

(Примечание: символ обозначает множество действительных чисел , а обозначение относится к декартову произведению копий , которое представляет собой -мерное векторное пространство над полем действительных чисел.)${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {R} ^{N}}$${\displaystyle N}$${\displaystyle \mathbb {R} }$${\displaystyle N}$

Существуют различные подходы к определению векторов . Обычно MDS формулируется как задача оптимизации , где находится как минимизатор некоторой функции стоимости, например,${\displaystyle x_{i}}$${\displaystyle (x_{1},\ldots ,x_{M})}$

${\displaystyle {\underset {x_{1},\ldots ,x_{M}}{\mathrm {argmin} }}\sum _{i<j}(\|x_{i}-x_{j}\|-d_{i,j})^{2}.\,}$

Решение может быть найдено с помощью методов численной оптимизации. Для некоторых специально выбранных функций стоимости минимизаторы могут быть сформулированы аналитически в терминах собственных разложений матриц . ^[2]

Проведение исследования MDS состоит из нескольких этапов:

1. Формулировка проблемы – Какие переменные вы хотите сравнить? Сколько переменных вы хотите сравнить? Для какой цели будет использоваться исследование?
2. Получение входных данных — Например, :- Респондентам задают ряд вопросов. Для каждой пары продуктов их просят оценить сходство (обычно по 7-балльной шкале Лайкерта от очень похожего до очень непохожего). Первый вопрос может быть, например, о Coke/Pepsi, следующий — о Coke/Hires rootbeer, следующий — о Pepsi/Dr Pepper, следующий — о Dr Pepper/Hires rootbeer и т. д. Количество вопросов является функцией количества брендов и может быть рассчитано как, где Q — количество вопросов, а N — количество брендов. Этот подход называется «Данные восприятия: прямой подход». Существует два других подхода. Существует «Данные восприятия: производный подход», в котором продукты разлагаются на атрибуты, которые оцениваются по семантической дифференциальной шкале. Другой — «Подход на основе данных предпочтений», в котором респондентов спрашивают об их предпочтениях, а не о сходстве.${\displaystyle Q=N(N-1)/2}$
3. Запуск статистической программы MDS – Программное обеспечение для запуска процедуры доступно во многих статистических программных пакетах. Часто есть выбор между метрической MDS (которая имеет дело с данными на уровне интервала или отношения) и неметрической MDS ^[7] (которая имеет дело с порядковыми данными).
4. Определите количество измерений – исследователь должен решить, сколько измерений он хочет, чтобы компьютер создал. Интерпретируемость решения MDS часто важна, и решения с меньшей размерностью, как правило, легче интерпретировать и визуализировать. Однако выбор размерности также является вопросом балансировки недообучения и переобучения. Решения с меньшей размерностью могут недообучать, исключая важные измерения данных о несходстве. Решения с большей размерностью могут переобучать шуму в измерениях несходства. Таким образом, инструменты выбора модели, такие как AIC , BIC , факторы Байеса или перекрестная проверка , могут быть полезны для выбора размерности, которая уравновешивает недообучение и переобучение.
5. Картирование результатов и определение измерений – статистическая программа (или связанный модуль) будет картировать результаты. Карта будет отображать каждый продукт (обычно в двумерном пространстве). Близость продуктов друг к другу указывает либо на то, насколько они похожи, либо на то, насколько они предпочтительны, в зависимости от того, какой подход использовался. Однако то, как измерения встраивания фактически соответствуют измерениям поведения системы, не обязательно очевидно. Здесь можно сделать субъективное суждение о соответствии (см. перцептивное картирование ).
6. Проверьте результаты на надежность и валидность – вычислите R-квадрат , чтобы определить, какую долю дисперсии масштабированных данных можно учесть с помощью процедуры MDS. R-квадрат 0,6 считается минимально приемлемым уровнем. ^{[ необходима цитата ]} R-квадрат 0,8 считается хорошим для метрического масштабирования, а 0,9 считается хорошим для неметрического масштабирования. Другие возможные тесты – стресс-тест Краскала, тесты с разделенными данными, тесты на стабильность данных (т. е. исключение одного бренда) и надежность повторного тестирования.
7. Отчет о результатах должен быть исчерпывающим – Вместе с отображением следует указать, по крайней мере, меру расстояния (например, индекс Соренсона , индекс Жаккара ) и надежность (например, значение напряжения). Также очень желательно указать алгоритм (например, Крускала, Мазера), который часто определяется используемой программой (иногда заменяя отчет об алгоритме), если вы указали начальную конфигурацию или имели случайный выбор, количество запусков, оценку размерности, результаты метода Монте-Карло , количество итераций, оценку устойчивости и пропорциональную дисперсию каждой оси (r-квадрат).

• ELKI включает две реализации MDS.
• MATLAB включает в себя две реализации MDS (для классического ( cmdscale ) и неклассического ( mdscale ) MDS соответственно).
• Язык программирования R предлагает несколько реализаций MDS, например, базовую функцию cmdscale , пакеты smacof ^[8] (mMDS и nMDS) и vegan (взвешенный MDS).
• scikit-learn содержит функцию sklearn.manifold.MDS.

На Викискладе есть медиафайлы по теме «Многомерное масштабирование» .

• Кластеризация данных
• t-распределенное стохастическое соседнее вложение
• Факторный анализ
• Дискриминантный анализ
• Уменьшение размерности
• Дистанционная геометрия
• Определитель Кэли–Менгера
• Картографирование Сэммона
• Иконография корреляций