Files

2026-06-30 15:17:40 +03:00

23 KiB

Raw Permalink Blame History

UMAP — кластеризация и визуализация признаков по классам

Раздел методички. Научный руководитель — мнс Павленко Б.В. Задача-носитель: анализ эмбеддингов классификатора EdgeNeXt на датасете жестов Naruto Sign.

1. Что такое UMAP и интуиция

UMAP (Uniform Manifold Approximation and Projection) — алгоритм нелинейного снижения размерности, предложенный в McInnes, Healy, Melville, 2018, arXiv:1802.03426. Теоретическая база — риманова геометрия и алгебраическая топология: предполагается, что данные лежат на многообразии (manifold) равномерно распределённой плотности, а локальная метрика искажается так, чтобы это допущение выполнялось.

Интуиция (два шага):

Построение взвешенного графа соседства в высокой размерности. Для каждой точки x_i берутся её k = n_neighbors ближайших соседей. Вес ребра — «вероятность» связи, спадающая с расстоянием. Локальный радиус нормируется на расстояние до 1-го соседа \rho_i (так гарантируется связность) и масштаб \sigma_i (калибруется так, чтобы сумма весов соответствовала \log_2 k):


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

Ориентированные веса симметризуются (fuzzy-union): w_{ij} = w_{i\to j} + w_{j\to i} - w_{i\to j}\,w_{j\to i}. Получается «нечёткий топологический граф».

Оптимизация низкоразмерного вложения. Ищется расположение точек y_i \in \mathbb{R}^{d} (n_components), при котором граф соседства в низкой размерности максимально похож на исходный. Минимизируется кросс-энтропия между нечёткими множествами рёбер; притяжение тянет соседей друг к другу, отталкивание (через negative sampling) разводит несоседей. Низкоразмерное ядро задаётся семейством \frac{1}{1 + a\,\|y_i-y_j\|^{2b}}, где a,b подбираются под min_dist.

Инициализация по умолчанию — спектральная (Laplacian eigenmaps), что важно для сохранения глобальной структуры (см. ниже).

Сравнение PCA / t-SNE / UMAP

Критерий	PCA	t-SNE	UMAP
Тип	линейный	нелинейный	нелинейный (топологический)
Локальная структура	слабо	очень хорошо	очень хорошо
Глобальная структура	хорошо (дисперсия)	слабо	умеренно лучше t-SNE*
Сложность	`O(n d^2)`	`\sim O(n^2)` (Barnes-Hut `O(n\log n)`)	`\approx O(n^{1.14})`, на практике `O(n\log n)`
Скорость на $10^5$–`10^6` точек	высокая	низкая	высокая
Стохастичность	детерминирован	стохастичен	стохастичен (нужен `random_state`)
Размерность выхода	любая	практично 2–3	любая (хорошо масштабируется)
Интерпретируемость расстояний	оси = главные компоненты, расстояния значимы	расстояния/размеры НЕ значимы	абсолютные расстояния/размеры НЕ значимы
Глобальные оси	да	нет	нет

* Важная оговорка: преимущество UMAP по глобальной структуре во многом обусловлено спектральной инициализацией, а не самим алгоритмом оптимизации. При случайной инициализации UMAP сохраняет глобальную структуру не лучше t-SNE — см. Kobak & Linderman, Nature Biotechnology 2021 и интерактивный разбор «Understanding UMAP», pair-code.

Практический вывод для нашей задачи: PCA — быстрый baseline и шаг предобработки (денойзинг до 50–100 компонент); t-SNE/UMAP — визуальный разведочный анализ; UMAP предпочтителен из-за скорости, масштабируемости и возможности давать промежуточные вложения для кластеризации.

2. Ключевые гиперпараметры UMAP

Определения и эффекты — по официальной документации umap-learn (Basic Parameters).

Параметр	По умолч.	Что контролирует	Эффект
`n_neighbors`	15	баланс локальное ↔ глобальное	малые (2–5) — тонкая локальная детализация, рвёт глобальную картину; большие (50–200) — общая структура за счёт деталей
`min_dist`	0.1	минимальное расстояние между точками в выходе	малые (0.0–0.1) — плотные «комки», чёткие границы (для кластеризации); большие (0.5–0.99) — равномернее, для топологии/визуала
`n_components`	2	размерность вложения	2–3 — визуализация; 10–50 — препроцессинг под кластеризацию (UMAP хорошо масштабируется по размерности, в отличие от t-SNE)
`metric`	`euclidean`	метрика в исходном пространстве	для L2-нормированных эмбеддингов `cosine` эквивалентен углу; см. ниже
`random_state`	`None`	фиксация ГСЧ	задание делает результат воспроизводимым (но отключает параллелизм → медленнее)

n_neighbors (локальное vs глобальное). Это число точек, формирующих локальную окрестность. Малое значение — UMAP «смотрит» только на ближайшее окружение; большое — усредняет по широкой области.

min_dist (плотность кластеров). Управляет ТОЛЬКО раскладкой в выходном пространстве (через a,b), не топологией графа. Для последующей кластеризации авторы рекомендуют min_dist = 0.0.

metric. Для эмбеддингов CNN после L2-нормализации косинусное расстояние монотонно связано с евклидовым:


\|u - v\|_2^2 = 2 - 2\cos(u,v),\quad \text{при } \|u\|=\|v\|=1.

Поэтому на нормированных признаках metric='euclidean' и metric='cosine' дают близкие, но не идентичные результаты (различие в нормировках весов и n_neighbors-калибровке). Рекомендация: для эмбеддингов брать metric='cosine' (или сначала L2-нормировать и оставить euclidean).

random_state. UMAP стохастичен (negative sampling, инициализация). Для отчётов/методички ОБЯЗАТЕЛЬНО фиксировать seed; форма «облака» при разных seed меняется, выводы — не должны.

3. Пайплайн: извлечение признаков EdgeNeXt → UMAP → раскраска по классам

Логика: forward_features → global pooling → L2-norm → матрица [N, D] → UMAP → 2D scatter, цвет = истинный класс Naruto Sign.

# deps: torch, timm, umap-learn, scikit-learn, matplotlib, numpy
import numpy as np
import torch
import torch.nn.functional as F
import timm
import umap
import matplotlib.pyplot as plt

device = "cuda" if torch.cuda.is_available() else "cpu"

# --- 1. EdgeNeXt feature extractor (pooled embedding, no classifier head) ---
# num_classes=0 -> timm returns pooled features from forward()
model = timm.create_model("edgenext_small", pretrained=True, num_classes=0)
model.eval().to(device)


@torch.no_grad()
def extract_embeddings(loader):
    """Return L2-normalized embeddings [N, D] and integer labels [N]."""
    feats, labels = [], []
    for imgs, ys in loader:                      # loader yields (image, class_idx)
        imgs = imgs.to(device, non_blocking=True)
        emb = model.forward_features(imgs)       # spatial feature map [B, C, H, W]
        emb = model.forward_head(emb, pre_logits=True)  # pooled embedding [B, D]
        emb = F.normalize(emb, p=2, dim=1)       # L2-norm: cosine == euclidean geometry
        feats.append(emb.cpu().numpy())
        labels.append(ys.numpy())
    return np.concatenate(feats), np.concatenate(labels)


X, y = extract_embeddings(val_loader)            # X: [N, D], y: [N]
print("embeddings:", X.shape)

# --- 2. UMAP -> 2D for VISUALIZATION (seed fixed!) ---
reducer_2d = umap.UMAP(
    n_neighbors=15,
    min_dist=0.1,
    n_components=2,
    metric="cosine",        # X already L2-normalized
    random_state=42,        # reproducibility
)
emb_2d = reducer_2d.fit_transform(X)             # [N, 2]

# --- 3. Scatter colored by TRUE class ---
class_names = val_loader.dataset.classes         # list[str], len == n_classes
fig, ax = plt.subplots(figsize=(9, 8))
sc = ax.scatter(emb_2d[:, 0], emb_2d[:, 1], c=y, cmap="tab20", s=8, alpha=0.7)
handles, _ = sc.legend_elements(num=len(class_names))
ax.legend(handles, class_names, title="Naruto Sign", loc="best",
          fontsize=7, ncol=2, markerscale=1.5)
ax.set_title("EdgeNeXt embeddings — UMAP 2D (seed=42)")
ax.set_xlabel("UMAP-1"); ax.set_ylabel("UMAP-2")
ax.set_xticks([]); ax.set_yticks([])            # axes are not interpretable
plt.tight_layout()
plt.savefig("umap_edgenext_naruto.png", dpi=200)

Примечание: точные имена методов извлечения признаков зависят от версии timm. Для EdgeNeXt подходит связка forward_features → forward_head(..., pre_logits=True); альтернатива — timm.create_model(..., num_classes=0, global_pool='avg') и затем просто model(imgs).

4. Кластеризация в пространстве признаков / на UMAP

Главная рекомендация авторов (umap-learn → Clustering): кластеризовать НЕ на 2D-картинке, а на промежуточном вложении (например, 10 компонент), либо параметрами, заточенными под кластеризацию.

Параметры под кластеризацию (рекомендация документации):

Параметр	Визуализация	Кластеризация
`n_components`	2	10 (исследовать диапазон)
`n_neighbors`	15	30 (больше — меньше шумовых «разрывов»)
`min_dist`	0.1	0.0 (плотные кластеры)

Два алгоритма:

k-means — требует заранее знать k, ищет сферические кластеры одинаковой плотности, относит ВСЕ точки (нет «шума»). Уместен, если число классов известно (а здесь оно известно — это число жестов Naruto Sign).
HDBSCAN — плотностный, не требует k, выделяет шум/выбросы, работает с кластерами произвольной формы и разной плотности. Авторы UMAP в туториале демонстрируют связку UMAP(intermediate) + HDBSCAN.

import hdbscan
from sklearn.cluster import KMeans

# UMAP -> intermediate (NOT 2D) embedding for clustering
reducer_clu = umap.UMAP(
    n_neighbors=30, min_dist=0.0, n_components=10,
    metric="cosine", random_state=42,
)
emb_clu = reducer_clu.fit_transform(X)           # [N, 10]

# HDBSCAN (no need to set k; label -1 == noise)
hdb = hdbscan.HDBSCAN(min_cluster_size=15, min_samples=5)
labels_hdb = hdb.fit_predict(emb_clu)

# k-means with known number of gesture classes
k = len(np.unique(y))
labels_km = KMeans(n_clusters=k, n_init=10, random_state=42).fit_predict(emb_clu)

Риски кластеризации прямо на 2D:

UMAP-2D не сохраняет плотность полностью — плотностные алгоритмы (HDBSCAN) делают ложные выводы.
UMAP может создавать ложные разрывы («false tears») внутри кластеров → переоценка числа кластеров.
Геометрия 2D искажена сильнее, чем у 10–50-мерного вложения; 2D — только для глаз, не для алгоритма.

Авторы прямо предупреждают, что использование UMAP перед кластеризацией «несколько спорно и требует осторожности».

5. Метрики качества

Внутренние (без меток) — оценивают саму геометрию кластеров:

Метрика	Диапазон	Лучше	Идея
Silhouette	`[-1, 1]`	выше	`(b-a)/\max(a,b)`: внутрикласт. сплочённость `a` vs разделимость `b`
Davies-Bouldin	`[0, \infty)`	ниже	средн. отношение внутрикласт. разброса к межкласт. расстоянию

Внешние (с истинными метками) — согласованность кластеров с классами Naruto Sign:

Метрика	Диапазон	Adj. for chance	Основа	Источник
ARI	`[-0.5, 1]`	да	подсчёт пар	[Hubert & Arabie 1985]
NMI	`[0, 1]`	нет	теория информации	scikit-learn clustering
AMI	`\sim[0, 1]`	да	теория информации	Vinh, Epps, Bailey, JMLR 2010

ARI и AMI скорректированы на случайность (≈0 для случайной разметки) — предпочтительны как итоговые. NMI не скорректирован: при малом числе точек/большом числе кластеров завышается.
Формула AMI: \mathrm{AMI} = \dfrac{\mathrm{MI} - \mathbb{E}[\mathrm{MI}]}{\overline{H} - \mathbb{E}[\mathrm{MI}]}, где \overline{H} — среднее энтропий разбиений.
Подробно о выборе ARI vs AMI: Vinh et al. 2010.

Trustworthiness (sklearn.manifold.trustworthiness) — мера сохранения локальной структуры при снижении размерности: \in [0,1], выше = меньше ложных близких соседей в проекции. Применяется к самому вложению (а не к кластеризации).

from sklearn.metrics import (silhouette_score, davies_bouldin_score,
                             adjusted_rand_score, normalized_mutual_info_score,
                             adjusted_mutual_info_score)
from sklearn.manifold import trustworthiness

# internal (geometry); exclude HDBSCAN noise points (label == -1)
mask = labels_hdb != -1
print("silhouette :", silhouette_score(emb_clu[mask], labels_hdb[mask]))
print("davies-bouldin:", davies_bouldin_score(emb_clu[mask], labels_hdb[mask]))

# external (agreement with true Naruto Sign labels)
print("ARI:", adjusted_rand_score(y, labels_km))
print("NMI:", normalized_mutual_info_score(y, labels_km))
print("AMI:", adjusted_mutual_info_score(y, labels_km))

# embedding quality vs original feature space
print("trustworthiness:", trustworthiness(X, emb_2d, n_neighbors=15))

6. Что покажет анализ и какие гипотезы мотивирует

Хорошо отделимые классы — компактные, изолированные «острова» на UMAP; высокие per-class silhouette; кластер HDBSCAN ≈ один класс. Ожидание: классификатор EdgeNeXt уверенно их различает.
Путающиеся классы — перекрывающиеся облака, точки одного класса распределены по нескольким кластерам или один кластер содержит метки 2–3 классов. Это прямой предиктор ошибок классификатора: перекрытие в эмбеддинге → confusion в матрице ошибок.
Сверка с confusion matrix: пары классов с высоким перекрытием в UMAP должны коррелировать с off-diagonal-массой матрицы ошибок. Совпадение валидирует, что причина ошибок — в признаковом представлении, а не в голове-классификаторе.

Мотивируемые гипотезы (для HPO/обучения EdgeNeXt):

Целевая аугментация трудных классов — для перекрывающихся жестов усилить аугментации, разводящие их (ракурс/освещение/фон), чтобы увеличить межклассовую дистанцию.
Class-balanced / hard-class семплирование — повысить вес/частоту трудноразделимых классов в батче.
Метрик-обучение — добавить contrastive/triplet/ArcFace-член, явно растягивающий перекрывающиеся пары.
Ревизия разметки — точки одного класса в чужом кластере могут быть mislabeled / out-of-distribution кадрами.

Важно: UMAP здесь — инструмент генерации гипотез, а не доказательство. Любой вывод о разделимости подтверждается метриками (§5) и confusion matrix.

7. Предостережения

Не интерпретировать абсолютные расстояния. Расстояние между двумя кластерами на UMAP-картинке НЕ отражает их реальную близость в исходном пространстве. Глобальные дистанции искажены (umap-learn parameters, pair-code).
Не интерпретировать размеры/плотность кластеров. UMAP, как и t-SNE, не сохраняет плотность полностью; размер «облака» не равен дисперсии класса.
Стохастичность — фиксировать seed. Без random_state форма меняется от запуска к запуску. Фиксируйте seed и в идеале проверяйте устойчивость выводов на 2–3 разных seed.
Параметры формируют картину. Сильное изменение n_neighbors/min_dist радикально меняет вид; нельзя подбирать параметры под желаемый результат. Показывайте использованные значения.
Ложные разрывы. UMAP может «разорвать» один класс на несколько сгустков — это артефакт, не subclass. Проверяйте на промежуточном вложении и метриками.
Не «доказывать» кластерами то, чего нет. Наличие визуальных сгустков ≠ наличие классов. Кластеризация на 2D особенно подвержена артефактам — кластеризуйте на 10–50-мерном вложении (§4) и валидируйте ARI/AMI/silhouette.
UMAP перед кластеризацией — спорно. Сами авторы советуют делать это «с осторожностью» и сравнивать с кластеризацией в исходном (или PCA-сжатом) пространстве как sanity-check.

23 KiB Raw Permalink Blame History Unescape Escape