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

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

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

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

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

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

Типы [ править ]

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

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

Он также известен как анализ основных координат (PCoA), масштабирование Торгерсона или масштабирование Торгерсона – Гауэра. Он принимает входную матрицу, определяющую различия между парами элементов, и выводит координатную матрицу, конфигурация которой минимизирует функцию потерь, называемую деформацией. ^[2] Например, учитывая евклидовы воздушные расстояния между различными городами, индексированные i и j , вы хотите найти координаты городов, такие, что ${\ textstyle d_ {ij}}$ ${\ textstyle (x_ {i}, y_ {i})}$ ${\ textstyle d_ {ij} = {\ sqrt {(x_ {i} -x_ {j}) ^ {2} + (y_ {i} -y_ {j}) ^ {2}}}}$ . В этом примере возможно точное решение (при условии, что евклидовы расстояния точны). На практике это обычно не так, и поэтому MDS стремится аппроксимировать представление более низкой размерности, минимизируя функцию потерь. Общие формы функций потерь называются напряжением на расстоянии МДС и деформацией в классической МДС. Деформация задается выражением:, где теперь обозначают векторы в 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:

Классическая МДС использует тот факт , что координата матрица может быть получена с помощью собственного значения разложения с . И матрица может быть вычислена из матрицы близости с помощью двойного центрирования. ^[3]

{\ displaystyle X}

{\ textstyle B = XX '}

{\ textstyle B}

{\ textstyle D}

Настройте квадратную матрицу близости ${\textstyle D^{(2)}=[d_{ij}^{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}$
Определить наибольшие собственные значения и соответствующие собственные векторы из (там , где этого числа измерений требуемых для выхода). ${\textstyle m}$ ${\textstyle \lambda _{1},\lambda _{2},...,\lambda _{m}}$ ${\textstyle e_{1},e_{2},...,e_{m}}$ ${\textstyle B}$ ${\textstyle m}$
Теперь , где есть матрица собственных векторов и является диагональной матрицей из собственных значений . ${\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})={\Biggl (}\sum _{i\neq j=1,...,N}{\bigl (}d_{ij}-\|x_{i}-x_{j}\|{\bigr )}^{2}{\Biggr )}^{1/2}$

Метрическое масштабирование использует степенное преобразование с управляемой пользователем экспонентой : и для расстояния. В классическом масштабировании . Неметрическое масштабирование определяется использованием изотонической регрессии для непараметрической оценки преобразования различий.

{\textstyle p}

{\textstyle d_{ij}^{p}}

{\textstyle -d_{ij}^{2p}}

{\textstyle p=1}

Неметрическое многомерное масштабирование (nMDS) [ править ]

В отличие от метрической MDS, неметрическая MDS находит как непараметрическую монотонную связь между различиями в матрице элемент-элемент и евклидовыми расстояниями между элементами, так и расположением каждого элемента в низкоразмерном пространстве. Взаимосвязь обычно находится с использованием изотонической регрессии : пусть обозначает вектор близости, монотонное преобразование и точечные расстояния; затем необходимо найти координаты, которые минимизируют так называемое напряжение, ${\textstyle x}$ ${\textstyle f(x)}$ ${\textstyle x}$ ${\textstyle d}$

${\text{Stress}}={\sqrt {\frac {\sum {\bigl (}f(x)-d{\bigr )}^{2}}{\sum d^{2}}}}$

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

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

Найдите случайную конфигурацию точек, например, путем выборки из нормального распределения.
Вычислите расстояния d между точками.
Найдите оптимальное монотонное преобразование близости, чтобы получить оптимально масштабированные данные . ${\textstyle f(x)}$
Минимизируйте напряжение между оптимально масштабированными данными и расстояниями, найдя новую конфигурацию точек.
Сравните напряжение с некоторым критерием. Если напряжение достаточно мало, выйдите из алгоритма, иначе вернитесь к 2.

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

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

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

Подробности [ править ]

Анализируемые данные - это набор объектов (цвета, лица, приклады и т. Д.), Для которых определена функция расстояния, $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}

где - векторная норма . В классическом MDS эта норма является евклидовым расстоянием , но, в более широком смысле, это может быть метрическая или произвольная функция расстояния. ^[5] $\|\cdot \|$

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

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

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

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

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

Процедура [ править ]

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

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

Реализации [ править ]

ELKI включает две реализации MDS.
MATLAB включает две реализации MDS (для классической ( cmdscale ) и неклассической ( mdscale ) MDS соответственно).
Язык программирования R предлагает несколько реализаций MDS.
sklearn содержит функцию sklearn.manifold.MDS .

См. Также [ править ]

Викискладе есть медиафайлы, связанные с многомерным масштабированием .

Позиционирование (маркетинг)
Перцептивное отображение
Управление продуктом
Маркетинг
Маркетинговое исследование
Обобщенное многомерное масштабирование (GMDS)
Кластеризация данных
Факторный анализ
Дискриминантный анализ
Снижение размерности
Нелинейное уменьшение размерности
Геометрия расстояния
Определитель Кэли-Менгера
Картирование Саммона

Ссылки [ править ]

Перейти ↑ Mead, A (1992). «Обзор развития методов многомерного масштабирования». Журнал Королевского статистического общества. Серия D (Статистик) . 41 (1): 27–39. JSTOR 234863 . Абстрактный. Методы многомерного масштабирования теперь являются обычным статистическим инструментом в психофизике и сенсорном анализе. Развитие этих методов показано на основе оригинальных исследований Торгерсона (метрическое масштабирование), Шепарда и Краскала (неметрическое масштабирование) через масштабирование индивидуальных различий и методы максимального правдоподобия, предложенные Рамзи.
^ а б Борг, I .; Гроенен, П. (2005). Современное многомерное масштабирование: теория и приложения (2-е изд.). Нью-Йорк: Springer-Verlag. С. 207–212. ISBN 978-0-387-94845-4.
^ Викельмайер, Флориан. «Введение в MDS». Группа исследования качества звука, Ольборгский университет, Дания (2003 г.): 46
Перейти ↑ Bronstein AM, Bronstein MM, Kimmel R (январь 2006 г.). «Обобщенное многомерное масштабирование: основа для изометрии-инвариантного частичного согласования поверхностей» . Proc. Natl. Акад. Sci. США . 103 (5): 1168–72. Bibcode : 2006PNAS..103.1168B . DOI : 10.1073 / pnas.0508601103 . PMC 1360551 . PMID 16432211 .
^ Крускали, JB , и желание, М. (1978), многомерное шкалирование , серия Sage университета документ по количественному применению в области социальных наук, 07-011. Беверли-Хиллз и Лондон: Sage Publications.
^ Крускала, JB (1964). «Многомерное масштабирование путем оптимизации согласия неметрической гипотезы». Психометрика . 29 (1): 1-27. DOI : 10.1007 / BF02289565 .

Библиография [ править ]

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

[MS_history-1] Перейти ↑ Mead, A (1992). «Обзор развития методов многомерного масштабирования». Журнал Королевского статистического общества. Серия D (Статистик) . 41 (1): 27–39. JSTOR 234863 . Абстрактный. Методы многомерного масштабирования теперь являются обычным статистическим инструментом в психофизике и сенсорном анализе. Развитие этих методов показано на основе оригинальных исследований Торгерсона (метрическое масштабирование), Шепарда и Краскала (неметрическое масштабирование) через масштабирование индивидуальных различий и методы максимального правдоподобия, предложенные Рамзи.

[borg-2] а б Борг, I .; Гроенен, П. (2005). Современное многомерное масштабирование: теория и приложения (2-е изд.). Нью-Йорк: Springer-Verlag. С. 207–212. ISBN 978-0-387-94845-4.

[3] Викельмайер, Флориан. «Введение в MDS». Группа исследования качества звука, Ольборгский университет, Дания (2003 г.): 46

[bron-4] Перейти ↑ Bronstein AM, Bronstein MM, Kimmel R (январь 2006 г.). «Обобщенное многомерное масштабирование: основа для изометрии-инвариантного частичного согласования поверхностей» . Proc. Natl. Акад. Sci. США . 103 (5): 1168–72. Bibcode : 2006PNAS..103.1168B . DOI : 10.1073 / pnas.0508601103 . PMC 1360551 . PMID 16432211 .

[Kruskal-5] Крускали, JB , и желание, М. (1978), многомерное шкалирование , серия Sage университета документ по количественному применению в области социальных наук, 07-011. Беверли-Хиллз и Лондон: Sage Publications.

[6] Крускала, JB (1964). «Многомерное масштабирование путем оптимизации согласия неметрической гипотезы». Психометрика . 29 (1): 1-27. DOI : 10.1007 / BF02289565 .

[1]