Алгоритм UMAP: как работает снижение размерности

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

Зачем нужно снижение размерности

Реальные данные почти всегда многомерны: изображение 28×28 - это уже 784 признака, текстовый эмбеддинг - 768 и больше. Глаз воспринимает максимум три измерения, а большинство алгоритмов кластеризации деградируют в высокой размерности из-за «проклятия размерности» - расстояния между точками становятся почти одинаковыми.

Снижение размерности отображает точки из пространства $\mathbb{R}^n$ в пространство $\mathbb{R}^d$ малой размерности ($d = 2$ или $3$) с сохранением важной структуры. Линейные методы вроде метода главных компонент (PCA) проецируют данные на гиперплоскость максимальной дисперсии, но не умеют разворачивать изогнутые многообразия. UMAP относится к нелинейным методам обучения многообразия (manifold learning) и сохраняет именно локальную и частично глобальную топологию.

Идея, на которой стоит UMAP

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

Формально UMAP опирается на теорию категорий и нечёткие симплициальные комплексы, но рабочая интуиция проще: для каждой точки строится «зонтик» связей с ближайшими соседями, и сила каждой связи тем больше, чем ближе сосед. Все эти зонтики склеиваются в один взвешенный граф соседства - нечёткий граф, в котором ребро между точками имеет вес от 0 до 1.

Шаг 1. Граф ближайших соседей

Сначала для каждой точки $x_i$ ищутся $k$ ближайших соседей (параметр $n\_neighbors$). Чтобы локальная связность была одинаковой везде, расстояния нормируются: вводится локальный масштаб $\sigma_i$ и сдвиг $\rho_i$ - расстояние до самого близкого соседа. Вес направленного ребра от $x_i$ к $x_j$ задаётся убывающей экспонентой:

$$w_{i \to j} = \exp\left(-\frac{\max(0,\ d(x_i, x_j) - \rho_i)}{\sigma_i}\right)$$

Параметр $\sigma_i$ подбирается так, чтобы суммарный вес связей точки равнялся $\log_2 k$ - это гарантирует, что у каждой точки эффективно «фиксированное» число соседей независимо от плотности.

Рассчитать для своей задачи

Граф получается направленным и несимметричным: связь $i \to j$ может быть сильнее, чем $j \to i$. UMAP симметризует его через нечёткое объединение (вероятностную t-конорму):

$$w_{ij} = w_{i \to j} + w_{j \to i} - w_{i \to j} \cdot w_{j \to i}$$

Так формируется итоговый взвешенный граф высокоразмерного представления.

Шаг 2. Низкоразмерное вложение

В целевом пространстве $\mathbb{R}^d$ для пары точек вводится своя функция силы связи, гладкое семейство с параметрами $a$ и $b$:

$$\psi(y_i, y_j) = \frac{1}{1 + a\,\|y_i - y_j\|^{2b}}$$

Коэффициенты $a$ и $b$ не задаются вручную - они подбираются автоматически под значение $min\_dist$, которое контролирует, насколько плотно точки одного кластера могут слипаться. Координаты $y_i$ сначала инициализируются спектральным вложением графа (по собственным векторам лапласиана), а затем уточняются оптимизацией.

Шаг 3. Оптимизация вложения

UMAP минимизирует перекрёстную энтропию между весами связей в исходном и целевом графах. Целевая функция складывается из притяжения связанных точек и отталкивания несвязанных:

$$C = \sum_{(i,j)} \left[ w_{ij}\,\log\frac{w_{ij}}{\psi_{ij}} + (1 - w_{ij})\,\log\frac{1 - w_{ij}}{1 - \psi_{ij}} \right]$$

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

Рассчитать для своей задачи

UMAP против t-SNE

Самое частое сравнение - с t-SNE, другим популярным методом нелинейной визуализации. Ключевые различия:

• Скорость. UMAP быстрее на больших выборках за счёт приближённого поиска соседей и негативного сэмплирования. t-SNE с точным вычислением масштабируется хуже.
• Глобальная структура. UMAP заметно лучше сохраняет взаимное расположение кластеров, тогда как t-SNE фокусируется почти исключительно на локальной близости и расстояния между кластерами у него мало интерпретируемы.
• Параметры. В t-SNE главный рычаг - perplexity, в UMAP - $n\_neighbors$ и $min\_dist$, и они интуитивнее: первый управляет масштабом «локальное против глобального», второй - плотностью упаковки.
• Новые точки. Обученный UMAP умеет проецировать новые данные без полного пересчёта (трансформация), у классического t-SNE этого нет.

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

Подбор параметров

Два параметра определяют почти весь результат:

• $n\_neighbors$ - сколько соседей учитывать. Малые значения (5–15) подчёркивают мелкую локальную структуру, большие (50–100) - общую форму данных. По сути это баланс между локальным и глобальным взглядом на многообразие.
• $min\_dist$ - минимальное допустимое расстояние между точками во вложении. Малое (0.0–0.1) даёт плотные, чётко очерченные комки - удобно для кластеризации; большое (0.5–0.99) разносит точки и лучше показывает общую топологию.

Третий важный выбор - метрика расстояния ($metric$): евклидова по умолчанию, но для эмбеддингов часто берут косинусную, а для бинарных признаков - Хэмминга или Жаккара. Метрика влияет на то, какие точки вообще считаются соседями, поэтому смена метрики иногда меняет картину сильнее, чем правка $n\_neighbors$.

Параметр $n\_components$ задаёт целевую размерность: 2 для визуализации, но 10–50 - если UMAP используется как препроцессинг перед кластеризацией. Полезный приём отладки - менять параметры по одному и смотреть на устойчивость: если кластеры разваливаются при крошечном сдвиге $n\_neighbors$, скорее всего, это шум, а не реальная группа. Хорошая практика - начинать с дефолтов ($n\_neighbors = 15$, $min\_dist = 0.1$) и двигаться маленькими шагами, фиксируя $random\_state$, чтобы изменения картинки объяснялись параметрами, а не случайной инициализацией.

Частые ошибки

• Интерпретировать размер и расстояние кластеров буквально. Площадь скопления и зазоры между группами в UMAP не пропорциональны реальной плотности или различию - они зависят от $min\_dist$ и оптимизации.
• Кластеризовать прямо по 2D-вложению. Снижение до двух измерений теряет информацию; кластеризацию лучше делать в исходном пространстве или в UMAP-проекции большей размерности, а 2D оставить для глаза.
• Считать UMAP детерминированным. Из-за стохастической инициализации и SGD прогоны различаются; для воспроизводимости фиксируйте $random\_state$.
• Слепо менять $n\_neighbors$, не глядя на данные. Слишком малое значение дробит единый кластер на ложные осколки, слишком большое - сливает разные группы.
• Подавать сырые признаки разного масштаба. Без нормировки одна переменная с большим разбросом подавит остальные в евклидовой метрике.

FAQ

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

Можно ли применять UMAP до кластеризации? Да, это распространённый приём: UMAP снижает размерность до 10–50 компонент, убирая шум, а затем по этой проекции запускают HDBSCAN или k-means. Но для финальной кластеризации не стоит использовать именно 2D-картинку - она слишком сжата.

Сохраняет ли UMAP глобальную структуру данных? Лучше, чем t-SNE, но не идеально. Взаимное расположение кластеров обычно осмысленно, однако абсолютные расстояния между ними доверия не заслуживают. Для более надёжной глобальной геометрии увеличивают $n\_neighbors$.

Коротко

Алгоритм UMAP снижает размерность в три шага: строит нечёткий граф ближайших соседей в исходном пространстве, задаёт гладкую функцию связи в целевом и минимизирует перекрёстную энтропию между ними градиентным спуском с негативным сэмплированием. Главные рычаги - $n\_neighbors$ (локальное против глобального) и $min\_dist$ (плотность упаковки). UMAP быстрее t-SNE и лучше держит глобальную структуру, но размеры и расстояния кластеров на картинке буквально читать нельзя.