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

Набор связанных методов ординации, используемых при визуализации информации.

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

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

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

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

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

Типы

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

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

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

N ${\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 предполагает метрические расстояния. Таким образом, это не применимо к прямым оценкам несходства.

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

Это расширенный набор классической 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.}$

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

В отличие от метрического 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.

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

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

Подробности

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

${\displaystyle d_{i,j}:=}$расстояние между -th и -th объектами. ${\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}}$

где – векторная норма . В классической МДС этой нормой является евклидово расстояние , но в более широком смысле это может быть метрическая или произвольная функция расстояния. ^[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]

Процедура

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

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

Смотрите также

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

Рекомендации

1. Мид, А (1992). «Обзор развития методов многомерного масштабирования». Журнал Королевского статистического общества. Серия D (Статист) . 41 (1): 27–39. JSTOR  2348634. Аннотация. Методы многомерного масштабирования в настоящее время являются распространенным статистическим инструментом в психофизике и сенсорном анализе. Развитие этих методов показано на основе оригинального исследования Торгерсона (метрическое масштабирование), Шепарда и Краскала (неметрическое масштабирование) через масштабирование индивидуальных различий и методы максимального правдоподобия, предложенные Рамзи.
2. Борг, И.; Гроенен, П. (2005). Современное многомерное масштабирование: теория и приложения (2-е изд.). Нью-Йорк: Springer-Verlag. стр. 207–212. ISBN 978-0-387-94845-4.
3. Дженест, Кристиан; Нешлехова, Йоханна Г.; Рамзи, Джеймс О. (2014). «Разговор с Джеймсом О. Рамзи». Международное статистическое обозрение/Revue Internationale de Statistique . 82 (2): 161–183. JSTOR  43299752 . Проверено 30 июня 2021 г.
4. Викельмайер, Флориан. «Введение в MDS». Отдел исследования качества звука, Ольборгский университет, Дания (2003 г.): 46
5. Бронштейн А.М., Бронштейн М.М., Киммел Р. (январь 2006 г.). «Обобщенное многомерное масштабирование: основа для изометрически-инвариантного частичного сопоставления поверхностей». Учеб. Натл. акад. наук. США . 103 (5): 1168–72. Бибкод : 2006PNAS..103.1168B. дои : 10.1073/pnas.0508601103 . ПМЦ 1360551 . ПМИД  16432211. 
6. Крускал, Дж. Б. , и Виш, М. (1978), Многомерное масштабирование , Серия статей Университета Сейджа о количественном применении в социальных науках, 07-011. Беверли-Хиллз и Лондон: Sage Publications.
7. Краскал, JB (1964). «Многомерное масштабирование путем оптимизации соответствия неметрической гипотезе». Психометрика . 29 (1): 1–27. дои : 10.1007/BF02289565. S2CID  48165675.
8. Леув, Ян де; Майр, Патрик (2009). «Многомерное масштабирование с использованием мажорирования: SMACOF в R». Журнал статистического программного обеспечения . 31 (3). дои : 10.18637/jss.v031.i03 . ISSN  1548-7660.

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

• Кокс, ТФ; Кокс, 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.