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

редактировать

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

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

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

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

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

СОДЕРЖАНИЕ

1 Типы
- 1.1 Классическое многомерное масштабирование
- 1.2 Метрическое многомерное масштабирование (mMDS)
- 1.3 Неметрическое многомерное масштабирование (nMDS)
- 1.4 Обобщенное многомерное масштабирование (GMD)
2 Детали
3 Процедура
4 реализации
5 См. Также
6 Ссылки
7 Библиография

Типы

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

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

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

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

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

{\ displaystyle X}

Икс

{\ textstyle B = XX '}

{\ textstyle B = XX '}

{\ textstyle B}

{\ textstyle B}

{\ textstyle D}

{\ textstyle D}

Настройте квадратную матрицу близости ${\ textstyle D ^ {(2)} = [d_ {ij} ^ {2}]}$ ${\ textstyle D ^ {(2)} = [d_ {ij} ^ {2}]}$
Примените двойное центрирование: используя

матрицу центрирования, где - количество объектов, является единичной матрицей и является матрицей всех единиц.

{\ textstyle B = - {\ frac {1} {2}} CD ^ {(2)} C}

{\ textstyle B = - {\ frac {1} {2}} CD ^ {(2)} C}

{\ textstyle C = I - {\ frac {1} {n}} J_ {n}}

{\ textstyle C = I - {\ frac {1} {n}} J_ {n}}

{\ textstyle n}

{\ textstyle n}

{\ textstyle I}

{\ textstyle I}

{\ textstyle п \ раз п}

{\ textstyle п \ раз п}

{\ textstyle J_ {n}}

{\ textstyle J_ {n}}

{\ textstyle п \ раз п}

{\ textstyle п \ раз п}

Определить наибольшие

собственные значения и соответствующие собственные векторы из (там, где этого числа измерений требуемых для выхода).

{\ textstyle m}

{\ textstyle m}

{\ textstyle \ lambda _ {1}, \ lambda _ {2},..., \ lambda _ {m}}

{\ textstyle \ lambda _ {1}, \ lambda _ {2},..., \ lambda _ {m}}

{\ textstyle e_ {1}, e_ {2},..., e_ {m}}

{\ textstyle e_ {1}, e_ {2},..., e_ {m}}

{\ textstyle B}

{\ textstyle B}

{\ textstyle m}

{\ textstyle m}

Теперь, где есть матрица собственных векторов и является

диагональной матрицей из собственных значений.

{\ textstyle X = E_ {m} \ Lambda _ {m} ^ {1/2}}

{\ textstyle X = E_ {m} \ Lambda _ {m} ^ {1/2}}

{\ textstyle E_ {m}}

{\ textstyle E_ {m}}

{\ textstyle m}

{\ textstyle m}

{\ textstyle \ Lambda _ {m}}

{\ textstyle \ Lambda _ {m}}

{\ textstyle m}

{\ textstyle m}

{\ textstyle B}

{\ textstyle B}

Классическая MDS предполагает евклидовы расстояния. Таким образом, это не применимо для оценок прямого несходства.

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

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

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

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

{\ textstyle p}

{\ textstyle p}

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

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

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

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

{\ textstyle p = 1}

{\ textstyle p = 1}

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

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

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

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

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

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

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

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

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

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

Подробности

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

{\ displaystyle d_ {i, j}: =}

{\ displaystyle d_ {i, j}: =}

расстояние между -ым и -м объектами.

{\ displaystyle i}

я

{\ displaystyle j}

j

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

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

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

Задача MDS состоит в том, чтобы найти такие векторы, что ${\ displaystyle D}$ $D$ ${\ displaystyle M}$ $M$ ${\ Displaystyle x_ {1}, \ ldots, x_ {M} \ in \ mathbb {R} ^ {N}}$ ${\ Displaystyle x_ {1}, \ ldots, x_ {M} \ in \ mathbb {R} ^ {N}}$

{\ displaystyle \ | x_ {i} -x_ {j} \ | \ приблизительно d_ {i, j}}

{\ displaystyle \ | x_ {i} -x_ {j} \ | \ приблизительно d_ {i, j}}

для всех,

{\ displaystyle i, j \ in {1, \ dots, M}}

{\ displaystyle i, j \ in {1, \ dots, M}}

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

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

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

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

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

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

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

Процедура

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

Формулировка проблемы - Какие переменные вы хотите сравнить? Сколько переменных вы хотите сравнить? С какой целью будет использоваться исследование?
Получение исходных данных - Например: - Респондентам задается ряд вопросов. Для каждой пары продуктов их просят оценить сходство (обычно по 7-балльной шкале Лайкерта от очень похожего до очень непохожего). Первый вопрос может быть, например, для Coke / Pepsi, следующий - для рутбива Coke / Hires, следующий - для Pepsi / Dr Pepper, следующий - для rootbeer Dr Pepper / Hires и т. Д. Количество вопросов зависит от количества бренды и могут быть рассчитаны как где Q - количество вопросов, а N - количество брендов. Этот подход называется «Восприятие данных: прямой подход». Есть два других подхода. Существует «Данные восприятия: производный подход», в котором продукты разбиваются на атрибуты, которые оцениваются по шкале семантического дифференциала. Другой - это «подход на основе данных о предпочтениях», при котором респондентов спрашивают о их предпочтениях, а не о сходстве. ${\ Displaystyle Q = N (N-1) / 2}$ $Q = N (N-1) / 2$
Запуск статистической программы MDS - Программное обеспечение для выполнения процедуры доступно во многих пакетах статистического программного обеспечения. Часто есть выбор между Metric MDS (который имеет дело с данными на уровне интервалов или отношений) и Nonmetric MDS (который имеет дело с порядковыми данными).
Определите количество измерений - исследователь должен решить, какое количество измерений он хочет, чтобы компьютер создавал. Интерпретируемость решения 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.

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

использованная литература

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

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.