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

Пример классического многомерного масштабирования, примененного к моделям голосования в Палате представителей США . Каждая синяя точка представляет одного члена Палаты представителей от Демократической партии, а каждая красная точка — от одного республиканца.

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

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

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

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

Типы

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

Классическое многомерное масштабирование

Он также известен как анализ главных координат (PCoA), масштабирование Торгерсона или масштабирование Торгерсона-Гауэра. Он принимает входную матрицу, дающую различия между парами элементов, и выводит координатную матрицу, конфигурация которой минимизирует функцию потерь, называемую напряжением . который дается $${\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},$$ где $x_{i}$ обозначают векторы в N -мерном пространстве, $x_{i}^{T}x_{j}$ обозначает скалярное произведение между $x_{i}$ и $x_{j}$, и $b_{ij}$ являются элементами матрицы $B$ определенные на шаге 2 следующего алгоритма, которые вычисляются на основе расстояний.

Шаги классического алгоритма MDS:

Классический MDS использует тот факт, что координатная матрица $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 предполагает метрические расстояния. Таким образом, это неприменимо для прямых оценок несходства.

Метрическое многомерное масштабирование (mMDS)

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

${\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.}$ Неметрическое масштабирование определяется использованием изотонической регрессии для непараметрической оценки трансформации несходств.

Неметрическое многомерное масштабирование (NMDS)

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

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

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

$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}}}}.$

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

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

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

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

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

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

Обобщенное многомерное масштабирование (GMD)

Основная статья: Обобщенное многомерное масштабирование

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

Подробности

Данные, подлежащие анализу, представляют собой совокупность $M$ объекты (цвета, лица, материалы и т. д.), для которых функция расстояния определена ,

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

Эти расстояния являются элементами матрицы несходства.

$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, учитывая $D$, чтобы найти $M$ векторы $x_{1},\ldots ,x_{M}\in \mathbb {R} ^{N}$ такой, что

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

где $\|\cdot \|$ является векторной нормой . В классической МДС этой нормой является евклидово расстояние , но в более широком смысле это может быть метрическая или произвольная функция расстояния. Например, при работе с данными смешанного типа, которые содержат как числовые, так и категориальные дескрипторы, расстояние Гауэра . распространённой альтернативой является

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

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

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

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

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

Процедура

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

1. Формулируем задачу : какие переменные вы хотите сравнить? Сколько переменных вы хотите сравнить? С какой целью будет использоваться исследование?
2. Получение входных данных . Например: - Респондентам задают ряд вопросов. Для каждой пары продуктов их просят оценить сходство (обычно по 7-балльной шкале Лайкерта от очень похожего до очень непохожего). Первый вопрос может быть, например, о Coke/Pepsi, следующий – о рутбире Coke/Hires, следующий – о Pepsi/Dr Pepper, следующий – о рутбире Dr Pepper/Hires и т. д. Количество вопросов зависит от количества вопросов. брендов и может быть рассчитана как $Q=N(N-1)/2$ где Q — количество вопросов, а N — количество брендов. Этот подход называется «Данные восприятия: прямой подход». Есть два других подхода. Существует «Данные восприятия: производный подход», в котором продукты разлагаются на атрибуты, которые оцениваются по семантической дифференциальной шкале. Другой вариант — «подход с данными о предпочтениях», при котором респондентам задают вопрос об их предпочтениях, а не о сходстве.
3. Запуск статистической программы MDS . Программное обеспечение для запуска процедуры доступно во многих пакетах статистического программного обеспечения. Часто существует выбор между метрическим MDS (который имеет дело с данными на уровне интервалов или отношений) и неметрическим MDS. (который имеет дело с порядковыми данными).
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. (мМДС и нМДС) и веганский (взвешенный МДС).
• scikit-learn содержит функцию sklearn.manifold.MDS .

См. также

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

Библиография

• Кокс, ТФ; Кокс, MAA (2001). Многомерное масштабирование . Чепмен и Холл.
• Коксон, Энтони П.М. (1982). Руководство пользователя по многомерному масштабированию. Со специальной ссылкой на библиотеку компьютерных программ MDS(X) . Лондон: Образовательные книги Heinemann.
• Грин, П. (январь 1975 г.). «Маркетинговые приложения MDS: оценка и перспективы». Журнал маркетинга . 39 (1): 24–31. дои : 10.2307/1250799 . JSTOR   1250799 .
• МакКьюн Б. и Грейс Дж. Б. (2002). Анализ экологических сообществ . Орегон, Гленеден-Бич: Разработка программного обеспечения MjM. ISBN  978-0-9721290-0-8 .
• Янг, Форрест В. (1987). Многомерное масштабирование: история, теория и приложения . Лоуренс Эрлбаум Ассошиэйтс. ISBN  978-0898596632 .
• Торгерсон, Уоррен С. (1958). Теория и методы масштабирования . Нью-Йорк: Уайли. ISBN  978-0-89874-722-5 .