Многомерное шкалирование

Материал из MachineLearning.

Версия от 07:11, 16 июня 2026; Platon Usaсhev (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

Статья написана с использованием LLM OpenAI GPT-5 и проверена участником Platon Usaсhev 11:11, 16 июня 2026 (MSD)

Многомерное шкалирование (англ. multidimensional scaling, MDS) — семейство методов снижения размерности, строящих низкоразмерное представление объектов по заданной матрице попарных близостей или различий. В отличие от метода главных компонент, MDS может работать не с исходными признаковыми описаниями, а только с расстояниями между объектами: например, с расстояниями между текстами, городами, профилями пользователей или результатами экспертных сравнений.

Типичная цель MDS — расположить объекты точками на плоскости или в трёхмерном пространстве так, чтобы расстояния между точками были как можно ближе к исходным различиям. Поэтому метод используется не только как алгоритм уменьшения размерности, но и как инструмент визуального анализа матриц расстояний.

Постановка задачи

Пусть заданы $n$ объектов и симметричная матрица различий

$\Delta=(\delta_{ij})_{i,j=1}^{n},$

где $\delta_{ij}\geq 0$ , $\delta_{ii}=0$ . Элементы $\delta_{ij}$ могут быть евклидовыми расстояниями, расстояниями графа, мерой несходства документов, экспертными оценками различия или значениями, полученными из функции близости.

Требуется найти точки

$y_1,\ldots,y_n\in R^p, p\ll n,$

такие, чтобы евклидовы расстояния

$d_{ij}(Y)=\sqrt{(y_i-y_j)^T(y_i-y_j)}$

хорошо согласовывались с исходными $\delta_{ij}$ . Конфигурация точек определена не единственным образом: перенос, поворот и зеркальное отражение не меняют попарных расстояний. Поэтому смысл обычно имеют взаимные положения объектов, а не абсолютные координаты и не названия осей.

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

Классическое MDS, также называемое методом главных координат, решает задачу точно, если исходная матрица различий является матрицей евклидовых расстояний между некоторыми точками. Основная идея состоит в восстановлении центрированной матрицы скалярных произведений по квадратам расстояний.

Пусть $D^{(2)}$ — матрица с элементами $\delta_{ij}^2$ , а

$J=I-\frac{1}{n}uu^T, u=(1,\ldots,1)^T$

— матрица центрирования. Тогда матрица Грама вычисляется по формуле двойного центрирования

$B=-\frac{1}{2}JD^{(2)}J.$

Если $B$ неотрицательно определена, то она может быть представлена как $B=YY^T$ , где строки $Y$ являются координатами объектов. На практике берут спектральное разложение

$B=V\Lambda V^T$

и оставляют $p$ наибольших положительных собственных значений:

$Y_p=V_p\Lambda_p^{1/2}.$

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

Отрицательные собственные значения матрицы $B$ показывают, что заданные различия не являются точными евклидовыми расстояниями. Визуализация всё равно возможна: положительная часть спектра даёт евклидову аппроксимацию, но часть информации неизбежно искажается.

Метрическое MDS

В метрическом MDS координаты подбираются как решение оптимизационной задачи. Часто минимизируют функционал напряжения (англ. stress)

$\sigma(Y)=\sum_{i<j} w_{ij}(d_{ij}(Y)-\delta_{ij})^2,$

где $w_{ij}\geq 0$ — веса пар. Нулевые веса позволяют игнорировать отсутствующие или ненадёжные расстояния. Для сравнения решений разного масштаба используют нормированную форму, например stress Краскала:

$Stress_1(Y)=\sqrt{\frac{\sum_{i<j} w_{ij}(d_{ij}(Y)-\delta_{ij})^2}{\sum_{i<j} w_{ij}\delta_{ij}^2}}.$

Такой подход не требует, чтобы исходная матрица была строго евклидовой. Он допускает произвольные функции потерь, веса и ограничения, но приводит к невыпуклой задаче. Результат может зависеть от начальной конфигурации, поэтому на практике используют несколько запусков и сравнивают значения stress.

Один из стандартных алгоритмов оптимизации — SMACOF (англ. scaling by majorizing a complicated function). Он строит последовательность более простых квадратичных задач, каждая из которых гарантированно не увеличивает stress. Это делает поведение алгоритма устойчивым, хотя не устраняет проблему локальных минимумов.

Неметрическое MDS

Неметрическое MDS применяется, когда численные значения $\delta_{ij}$ нельзя интерпретировать как расстояния, но их порядок информативен. Например, эксперт может сказать, что пара объектов $a,b$ похожа сильнее, чем пара $c,d$ , не задавая точной величины различия.

В этом случае ищут не сами расстояния $\delta_{ij}$ , а монотонное преобразование

$\hat d_{ij}=f(\delta_{ij}),$

сохраняющее порядок различий. Затем минимизируют stress между $d_{ij}(Y)$ и $\hat d_{ij}$ . Обычно чередуют два шага: оценивают монотонное преобразование с помощью изотонической регрессии и обновляют координаты объектов. Неметрическое MDS полезно в психометрике, анализе предпочтений и задачах, где шкала измерения условна.

Связь с другими методами

Многомерное шкалирование тесно связано с несколькими методами анализа данных.

В классическом MDS исходной информацией является матрица расстояний; в PCA — матрица объект-признак. При евклидовых расстояниях между центрированными объектами результаты совпадают.
В ядерных методах исходной информацией служит матрица скалярных произведений или ядро. Двойное центрирование в классическом MDS фактически переводит расстояния в такую матрицу.
Алгоритм Isomap сначала оценивает геодезические расстояния на графе ближайших соседей, а затем применяет классическое MDS. Поэтому его можно понимать как нелинейное MDS на приближённых расстояниях вдоль многообразия.
Методы t-SNE и UMAP также строят низкоразмерные визуализации, но оптимизируют другие критерии и сильнее ориентированы на сохранение локальной структуры соседства, а не глобальных расстояний.

Практическое использование

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

При использовании MDS важно проверять несколько обстоятельств:

как построена матрица различий: разные метрики могут давать разные карты одних и тех же объектов;
есть ли выбросы: одна группа дальних объектов может сильно исказить масштаб визуализации;
насколько мала итоговая размерность: двумерная карта удобна, но иногда трёх или четырёх измерений нужно существенно меньше искажений;
каково значение stress и как выглядит диаграмма Шепарда, сравнивающая исходные различия и полученные расстояния;
устойчиво ли решение при изменении инициализации, весов и небольших возмущениях исходных данных.

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

Ограничения

MDS требует хранения матрицы попарных различий, что даёт сложность $O(n^2)$ по памяти. Классическое MDS дополнительно требует спектрального разложения матрицы размера $n\times n$ , что ограничивает прямое применение на больших выборках. Для больших данных используют приближённые методы, выбор опорных объектов, итеративные алгоритмы или предварительное сжатие выборки.

Другая проблема — отсутствие естественного правила для добавления нового объекта. Если MDS строилось только по матрице расстояний обучающей выборки, то для нового объекта нужно либо пересчитывать конфигурацию, либо использовать специальное out-of-sample продолжение.

Наконец, красивая двумерная визуализация не является доказательством наличия кластеров или низкоразмерной структуры. MDS показывает приближённую геометрию выбранной матрицы различий; качество вывода зависит от того, насколько эта матрица отражает содержательные отношения между объектами.

См. также

Литература

Torgerson W. S. Multidimensional scaling: I. Theory and method // Psychometrika. — 1952. — Vol. 17, No. 4. — P. 401–419.
Kruskal J. B. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis // Psychometrika. — 1964. — Vol. 29, No. 1. — P. 1–27.
Gower J. C. Some distance properties of latent root and vector methods used in multivariate analysis // Biometrika. — 1966. — Vol. 53, No. 3–4. — P. 325–338.
Cox T. F., Cox M. A. A. Multidimensional Scaling. — 2nd ed. — Chapman and Hall/CRC, 2001.
Borg I., Groenen P. J. F. Modern Multidimensional Scaling: Theory and Applications. — 2nd ed. — Springer, 2005.
Borg I., Groenen P. J. F., Mair P. Applied Multidimensional Scaling. — Springer, 2013.

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%BD%D0%BE%D0%B3%D0%BE%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D1%88%D0%BA%D0%B0%D0%BB%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5»

Категории: Машинное обучение | Анализ данных | Визуализация данных | Энциклопедия анализа данных