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

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

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

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

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

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

Типы

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

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

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

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

Классическая МДС использует тот факт , что координата матрица может быть получена с помощью собственного значения разложения с . И матрица может быть вычислена из матрицы близости с помощью двойного центрирования. ${\ 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 п \ раз п}$${\ textstyle J_ {n}}$${\ textstyle п \ раз п}$

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

собственные значения и соответствующие собственные векторы из (там , где этого числа измерений требуемых для выхода).${\ 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 минимизирует функцию затрат, называемую «стресс», которая представляет собой остаточную сумму квадратов:

${\ 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 d_ {ij} ^ {p}}$${\ textstyle -d_ {ij} ^ {2p}}$${\ textstyle p = 1}$

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

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

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

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

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

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

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

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

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

Подробности

Анализируемые данные - это набор объектов (цвета, лица, приклады и т. Д.), Для которых определена функция расстояния, ${\ 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} \ | \ приблизительно d_ {i, j}}$для всех ,${\ displaystyle i, j \ in {1, \ dots, M}}$

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

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

Процедура

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

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

Реализации

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

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

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

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

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