Матрица расстояний

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

Версия от 22:38, 9 июля 2026; Iurii Patrakov (Обсуждение | вклад)

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

Статья написана с использованием LLM GPT-5.5 и проверена участником Iurii Patrakov 02:38, 10 июля 2026 (MSD)

Матрица расстояний — это квадратная матрица $D=(d_{ij})$ , элементы которой задают расстояния или меры несходства между парами объектов: $d_{ij}=d(x_i,x_j)$ . Обычно на диагонали стоят нули, $d_{ii}=0$ , а для симметричной метрики выполняется $d_{ij}=d_{ji}$ ; однако в прикладных задачах под «матрицей расстояний» нередко понимают и более общий массив попарных несходств, не обязательно удовлетворяющий всем аксиомам метрики.

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

Определение и основные свойства

Пусть задано множество объектов $X=\{x_1,\ldots,x_n\}$ и функция расстояния $d:X\times X\to \mathbb{R}$ . Тогда матрица расстояний имеет вид:

$D = \begin{pmatrix} 0 & d_{12} & \ldots & d_{1n}\\ d_{21} & 0 & \ldots & d_{2n}\\ \vdots & \vdots & \ddots & \vdots\\ d_{n1} & d_{n2} & \ldots & 0 \end{pmatrix}.$

Если $d$ является метрикой, то выполняются:

неотрицательность: $d_{ij}\geq 0$ ;
тождественность: $d_{ij}=0$ тогда и только тогда, когда $x_i=x_j$ ;
симметрия: $d_{ij}=d_{ji}$ ;
неравенство треугольника: $d_{ij}\leq d_{ik}+d_{kj}$ .

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

Евклидовы матрицы расстояний

Особый класс составляют евклидовы матрицы расстояний: они возникают, когда существуют точки $z_1,\ldots,z_n$ в евклидовом пространстве, такие что

$d_{ij}=\|z_i-z_j\|$ .

В литературе по геометрии расстояний часто рассматривают матрицу квадратов расстояний $d_{ij}^2$ , поскольку она напрямую связана с матрицей Грама скалярных произведений. Эта связь лежит в основе классического многомерного шкалирования: по матрице попарных расстояний можно восстановить координаты точек с точностью до сдвига, поворота и отражения, если такая евклидова реализация существует.

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

Исторический контекст

Идея описывать объекты через попарные расстояния возникла задолго до современной науки о данных. В геометрии она связана с вопросом: можно ли восстановить конфигурацию точек, зная только расстояния между ними? В XX веке эта линия получила развитие в работах по геометрии расстояний и психометрике.

В 1930-е годы результаты Исаака Шёнберга дали критерии вложимости конечных метрических пространств в евклидово пространство. В психологии и статистике похожие идеи привели к многомерному шкалированию: методам, которые строят пространственную карту объектов по матрице их несходств. Работы Уоррена Торгерсона в 1950-е годы сформировали классическое метрическое шкалирование, а работы Джозефа Краскала в 1960-е годы развили неметрическое шкалирование, где важно сохранить не сами значения расстояний, а их порядок.

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

Суть подхода

Матрица расстояний переводит задачу из пространства признаков в пространство отношений. Вместо вопроса «каковы признаки объекта?» задаётся вопрос «насколько объект похож на другие?». Это даёт несколько преимуществ:

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

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

Связь с машинным обучением

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

Типичные применения:

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

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

Примеры расстояний

В зависимости от природы объектов используют разные меры:

евклидово расстояние — для числовых признаков в сопоставимых шкалах;
манхэттенское расстояние — для признаков, где важна сумма абсолютных отклонений;
косинусное расстояние — для текстовых и высокоразмерных векторных представлений;
расстояние Хэмминга — для бинарных строк и категориальных кодировок;
расстояние редактирования — для строк и биологических последовательностей;
расстояние Жаккара — для множеств и разреженных бинарных признаков;
расстояние между распределениями — для вероятностных представлений;
графовое расстояние — для вершин графа.

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

Вычислительные аспекты

Для $n$ объектов полная матрица расстояний содержит $n^2$ элементов, а при симметрии — $n(n-1)/2$ различных внедиагональных значений. Поэтому память и время становятся ограничением уже при сотнях тысяч объектов.

Основные проблемы:

квадратичный рост памяти;
высокая стоимость вычисления всех пар расстояний;
необходимость нормализации и предобработки признаков;
чувствительность к шуму и выбросам;
трудность интерпретации расстояний в высоких размерностях;
неполные матрицы расстояний в реальных измерениях.

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

Ограничения и типичные ошибки

Матрица расстояний полезна только настолько, насколько осмысленна выбранная функция расстояния. Частые ошибки включают:

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

Особенно осторожно следует работать с высокоразмерными данными: в больших размерностях расстояния между объектами могут становиться близкими друг к другу, а понятие «ближайший сосед» теряет устойчивость. Это проявление проклятия размерности.

Современные направления

В современных исследованиях матрицы расстояний встречаются в нескольких активных направлениях.

Обучение представлений. Глубокие модели строят скрытые векторы объектов, а матрица расстояний между ними помогает анализировать, какие классы, смыслы или состояния модель считает близкими.

Контрастивное обучение. В таких методах модель обучается сближать представления похожих объектов и отдалять непохожие. Фактически оптимизируется геометрия расстояний в скрытом пространстве.

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

Графовые методы. Матрица расстояний может задавать взвешенный граф, а граф ближайших соседей становится основой для кластеризации, распространения меток и анализа многообразий.

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

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

Практическая интерпретация

Матрицу расстояний удобно рассматривать как «геометрический снимок» набора данных. Если расстояние выбрано удачно, близкие объекты действительно похожи по смыслу, а дальние — различаются. Но сама матрица не объясняет, какие признаки отвечают за близость. Поэтому её часто используют вместе с методами интерпретации: анализом признаков, визуализацией, кластерными профилями, экспертной проверкой и сравнением нескольких мер расстояния.

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

См. также

Литература

Schoenberg I. J. Remarks to Maurice Fréchet’s article “Sur la définition axiomatique d’une classe d’espaces vectoriels distanciés applicables vectoriellement sur l’espace de Hilbert” // Annals of Mathematics. 1935. Vol. 36. P. 724–732.
Torgerson W. S. Multidimensional scaling: I. Theory and method // Psychometrika. 1952. Vol. 17. 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.
Gower J. C. A general coefficient of similarity and some of its properties // Biometrics. 1971. Vol. 27. No. 4. P. 857–871.
Borg I., Groenen P. J. F. Modern Multidimensional Scaling: Theory and Applications. 2nd ed. New York: Springer, 2005.
Deza M. M., Deza E. Encyclopedia of Distances. 4th ed. Berlin; Heidelberg: Springer, 2016.
Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. 2nd ed. New York: Springer, 2009.
Dokmanić I., Parhizkar R., Ranieri J., Vetterli M. Euclidean Distance Matrices: Essential Theory, Algorithms, and Applications // IEEE Signal Processing Magazine. 2015. Vol. 32. No. 6. P. 12–30.

Ссылки

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%82%D1%80%D0%B8%D1%86%D0%B0_%D1%80%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9»

Категории: Машинное обучение | Анализ данных | Математические методы | Кластеризация | Снижение размерности