Понижение размерности

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

Перейти к: навигация, поиск
Статья написана с использованием LLM Gemini и проверена участником Kirill Bazhutov 19:58, 7 июля 2026 (MSD)


Понижение размерности (Dimensionality reduction) — задача машинного обучения и статистики, заключающаяся в преобразовании данных из пространства высокой размерности в пространство меньшей размерности с максимальным сохранением значимых свойств исходных данных (например, дисперсии, попарных расстояний или локальной топологической структуры).

Понижение размерности является одним из ключевых инструментов предварительной обработки данных, позволяющим бороться с проклятием размерности (curse of dimensionality), снижать вычислительную сложность алгоритмов, снижать влияние мультиколлинеарности и визуализировать многомерные выборки.

Содержание

Формальная постановка задачи

Пусть задана матрица объектов-признаков X \in \mathbb{R}^{N \times D}, где N — количество объектов, а D — исходная размерность пространства признаков. Задача понижения размерности состоит в поиске отображения f: \mathbb{R}^D \to \mathbb{R}^d, где d \ll D, такого, что новое представление Y = f(X) \in \mathbb{R}^{N \times d} минимизирует некоторую функцию потерь, отражающую потерю информации при преобразовании.

Глобально методы понижения размерности делятся на две категории:

  1. Отбор признаков (Feature selection): выбор подмножества из d исходных признаков без их модификации.
  2. Извлечение признаков (Feature extraction): конструирование d новых признаков, представляющих собой комбинации исходных. Ниже рассматриваются методы именно этой категории.

Линейные методы

Линейные методы ищут отображение в виде линейной проекции Y = XW, где W \in \mathbb{R}^{D \times d} — матрица весов (проекции).

Метод главных компонент (PCA)

Метод главных компонент (Principal Component Analysis, PCA) — наиболее распространённый линейный метод обучения без учителя. Цель PCA — найти ортогональное преобразование, переводящее исходные данные в новую систему координат так, чтобы максимизировать дисперсию данных вдоль новых осей. Эквивалентно, PCA находит линейное подпространство размерности d, минимизирующее среднеквадратичную ошибку реконструкции данных.

Математически задача сводится к спектральному разложению выборочной ковариационной матрицы центрированной матрицы данных X_c в виде C = \frac{1}{N-1} X_c^T X_c. Столбцы матрицы W сформируются из d собственных векторов матрицы C, соответствующих её наибольшим собственным значениям \lambda_1 \ge \lambda_2 \ge \dots \ge \lambda_d. На практике PCA вычисляется через сингулярное разложение (SVD) центрированной матрицы данных X_c = U \Sigma V^T, что вычислительно более устойчиво.

Линейный дискриминантный анализ (LDA)

Линейный дискриминантный анализ (Linear Discriminant Analysis, LDA) — метод понижения размерности с учителем (supervised). LDA ищет проекцию, которая максимизирует разделимость классов: максимизирует межклассовую дисперсию (between-class variance) при одновременной минимизации внутриклассовой дисперсии (within-class variance).

Задача LDA обычно сводится к обобщённой задаче на собственные значения для матриц межклассового и внутриклассового разброса. Важное математическое ограничение метода: если число классов равно C, то число информативных дискриминантных направлений не превышает C-1.

Случайные проекции

Случайная проекция (Random projection) — метод понижения размерности, опирающийся на лемму Джонсона — Линденштрауса. Лемма утверждает, что для конечного набора точек в пространстве высокой размерности существует вложение в пространство значительно меньшей размерности, сохраняющее попарные расстояния с заданной небольшой погрешностью. Случайные линейные отображения реализуют такое вложение с высокой вероятностью. Для сохранения попарных расстояний с относительной ошибкой \varepsilon обычно достаточно размерности порядка d = \mathcal{O}(\log N / \varepsilon^2). Метод отличается высокой вычислительной эффективностью.

Нелинейные методы (обучение на многообразиях)

Линейные методы могут быть недостаточны, если данные лежат на нелинейном многообразии (manifold) в пространстве высокой размерности. Для таких задач применяются методы manifold learning.

t-SNE

t-SNE (t-distributed Stochastic Neighbor Embedding) — алгоритм, преобразующий евклидовы расстояния между объектами в условные вероятности сходства.

В исходном пространстве сначала задаются условные вероятности соседства на основе гауссовых ядер с индивидуашками масштабами, после чего они симметризуются в совместные вероятности p_{ij}. Для пространства низкой размерности вероятности q_{ij} моделируются с использованием распределения Стьюдента с одной степенью свободы (распределение Коши):

q_{ij} = \frac{(1 + \|y_i - y_j\|^2)^{-1}}{\sum_{k \neq l} (1 + \|y_k - y_l\|^2)^{-1}}

Использование распределения с «тяжёлыми хвостами» решает «проблему скученности» (crowding problem). Целевая функция минимизирует дивергенцию Кульбака — Лейблера между распределениями P и Q:

C = KL(P \| Q) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij Fluss}}{q_{ij}}

Важно отметить, что t-SNE главным образом предназначен для визуализации локальной структуры; расстояния между удалёнными кластерами и их относительные размеры не всегда имеют прямую интерпретацию.

UMAP

UMAP (Uniform Manifold Approximation and Projection) — современный алгоритм, опирающийся на риманову геометрию и алгебраическую топологию. По утверждению авторов, UMAP часто лучше сохраняет элементы глобальной структуры, чем t-SNE, при сопоставимом качестве визуализации и большей вычислительной эффективности.

Автоэнкодеры

Автоэнкодер (Autoencoder) — архитектура нейронной сети, обучаемая восстанавливать свой входной сигнал. В контексте понижения размерности используется архитектура с «узким горлышком» (bottleneck) — скрытым слоем размерности d. Линейный автоэнкодер с одним скрытым слоем и среднеквадратичной ошибкой реконструкции при определённых условиях восстанавливает то же главное подпространство, что и PCA. Однако нелинейные функции активации позволяют автоэнкодерам выучивать нелинейные представления, которые в некоторых задачах могут превосходить линейные методы.

Выбор целевой размерности

В линейных методах целевая размерность d часто выбирается по доле объяснённой дисперсии, например 90–95 % для PCA. В визуализационных методах обычно используют d=2 или d=3. В прикладных задачах значение d также может подбираться по качеству последующей модели на валидационной выборке.

Ограничения и компромиссы

  • Интерпретируемость: Большинство методов извлечения признаков (особенно нелинейных) делают новые признаки трудно интерпретируемыми для человека.
  • Вычислительная сложность: Точный PCA через полное SVD имеет сложность порядка \mathcal{O}(\min(ND^2, N^2D)); при работе с ковариационной матрицей дополнительно возникает стоимость её построения и спектрального разложения. Нелинейные методы, такие как t-SNE, требуют вычисления попарных расстояний, что ограничивает их применение на сверхбольших выборках без аппроксимаций.
  • Переобучение: При использовании гибких нелинейных методов (например, автоэнкодеров) существует риск переобучения (overfitting), когда модель «запоминает» шум, а не истинное многообразие.

См. также

Литература

  • Pearson K. On Lines and Planes of Closest Fit to Systems of Points in Space // Philosophical Magazine. — 1901. — Т. 2. — № 11. — С. 559–572.
  • Fisher R. A. The use of multiple measurements in taxonomic problems // Annals of Eugenics. — 1936. — Т. 7. — С. 179–188.
  • Johnson W. B., Lindenstrauss J. Extensions of Lipschitz mappings into a Hilbert space // Contemporary Mathematics. — 1984. — Т. 26. — С. 189–206.
  • Jolliffe I. T. Principal Component Analysis. — Springer, 2002.
  • Hinton G. E., Salakhutdinov R. R. Reducing the dimensionality of data with neural networks // Science. — 2006. — Т. 313. — № 5786. — С. 504–507.
  • van der Maaten L., Hinton G. Visualizing Data using t-SNE // Journal of Machine Learning Research. — 2008. — Т. 9. — С. 2579–2605.
  • McInnes L., Healy J., Melville J. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction // arXiv preprint arXiv:1802.03426. — 2018.
  • Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — Springer, 2009. — ISBN 978-0387848570
  • Bishop C. M. Pattern Recognition and Machine Learning. — Springer, 2006. — ISBN 978-0387310732
Источник — «http://www.machinelearning.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BD%D0%B8%D0%B6%D0%B5%D0%BD%D0%B8%D0%B5_%D1%80%D0%B0%D0%B7%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D1%81%D1%82%D0%B8»
Личные инструменты