267 lines
23 KiB
Markdown
267 lines
23 KiB
Markdown
# UMAP — кластеризация и визуализация признаков по классам
|
||
|
||
> Раздел методички. Научный руководитель — мнс Павленко Б.В.
|
||
> Задача-носитель: анализ эмбеддингов классификатора **EdgeNeXt** на датасете жестов **Naruto Sign**.
|
||
|
||
---
|
||
|
||
## 1. Что такое UMAP и интуиция
|
||
|
||
**UMAP** (Uniform Manifold Approximation and Projection) — алгоритм нелинейного снижения размерности, предложенный в [McInnes, Healy, Melville, 2018, arXiv:1802.03426](https://arxiv.org/abs/1802.03426). Теоретическая база — риманова геометрия и алгебраическая топология: предполагается, что данные лежат на многообразии (manifold) равномерно распределённой плотности, а локальная метрика искажается так, чтобы это допущение выполнялось.
|
||
|
||
**Интуиция (два шага):**
|
||
|
||
1. **Построение взвешенного графа соседства в высокой размерности.** Для каждой точки $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}$. Получается «нечёткий топологический граф».
|
||
|
||
2. **Оптимизация низкоразмерного вложения.** Ищется расположение точек $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](https://www.nature.com/articles/s41587-020-00809-z) и интерактивный разбор [«Understanding UMAP», pair-code](https://pair-code.github.io/understanding-umap/).
|
||
|
||
**Практический вывод для нашей задачи:** PCA — быстрый baseline и шаг предобработки (денойзинг до 50–100 компонент); t-SNE/UMAP — визуальный разведочный анализ; UMAP предпочтителен из-за скорости, масштабируемости и возможности давать промежуточные вложения для кластеризации.
|
||
|
||
---
|
||
|
||
## 2. Ключевые гиперпараметры UMAP
|
||
|
||
Определения и эффекты — по [официальной документации umap-learn (Basic Parameters)](https://umap-learn.readthedocs.io/en/latest/parameters.html).
|
||
|
||
| Параметр | По умолч. | Что контролирует | Эффект |
|
||
|---|---|---|---|
|
||
| `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.
|
||
|
||
```python
|
||
# 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](https://umap-learn.readthedocs.io/en/latest/clustering.html)): кластеризовать НЕ на 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**.
|
||
|
||
```python
|
||
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:**
|
||
1. UMAP-2D не сохраняет плотность полностью — плотностные алгоритмы (HDBSCAN) делают ложные выводы.
|
||
2. UMAP может создавать **ложные разрывы** («false tears») внутри кластеров → переоценка числа кластеров.
|
||
3. Геометрия 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](https://scikit-learn.org/stable/modules/clustering.html) |
|
||
| AMI | $\sim[0, 1]$ | да | теория информации | [Vinh, Epps, Bailey, JMLR 2010](https://jmlr.csail.mit.edu/papers/volume17/15-627/15-627) |
|
||
|
||
- **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](https://jmlr.csail.mit.edu/papers/volume17/15-627/15-627).
|
||
|
||
**Trustworthiness** ([sklearn.manifold.trustworthiness](https://scikit-learn.org/stable/modules/generated/sklearn.manifold.trustworthiness.html)) — мера сохранения локальной структуры при снижении размерности: $\in [0,1]$, выше = меньше ложных близких соседей в проекции. Применяется к самому вложению (а не к кластеризации).
|
||
|
||
```python
|
||
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):**
|
||
1. **Целевая аугментация трудных классов** — для перекрывающихся жестов усилить аугментации, разводящие их (ракурс/освещение/фон), чтобы увеличить межклассовую дистанцию.
|
||
2. **Class-balanced / hard-class семплирование** — повысить вес/частоту трудноразделимых классов в батче.
|
||
3. **Метрик-обучение** — добавить contrastive/triplet/ArcFace-член, явно растягивающий перекрывающиеся пары.
|
||
4. **Ревизия разметки** — точки одного класса в чужом кластере могут быть mislabeled / out-of-distribution кадрами.
|
||
|
||
> Важно: UMAP здесь — **инструмент генерации гипотез**, а не доказательство. Любой вывод о разделимости подтверждается метриками (§5) и confusion matrix.
|
||
|
||
---
|
||
|
||
## 7. Предостережения
|
||
|
||
1. **Не интерпретировать абсолютные расстояния.** Расстояние между двумя кластерами на UMAP-картинке НЕ отражает их реальную близость в исходном пространстве. Глобальные дистанции искажены ([umap-learn parameters](https://umap-learn.readthedocs.io/en/latest/parameters.html), [pair-code](https://pair-code.github.io/understanding-umap/)).
|
||
2. **Не интерпретировать размеры/плотность кластеров.** UMAP, как и t-SNE, не сохраняет плотность полностью; размер «облака» не равен дисперсии класса.
|
||
3. **Стохастичность — фиксировать seed.** Без `random_state` форма меняется от запуска к запуску. Фиксируйте seed и в идеале проверяйте устойчивость выводов на 2–3 разных seed.
|
||
4. **Параметры формируют картину.** Сильное изменение `n_neighbors`/`min_dist` радикально меняет вид; нельзя подбирать параметры под желаемый результат. Показывайте использованные значения.
|
||
5. **Ложные разрывы.** UMAP может «разорвать» один класс на несколько сгустков — это артефакт, не subclass. Проверяйте на промежуточном вложении и метриками.
|
||
6. **Не «доказывать» кластерами то, чего нет.** Наличие визуальных сгустков ≠ наличие классов. Кластеризация на 2D особенно подвержена артефактам — кластеризуйте на 10–50-мерном вложении (§4) и валидируйте ARI/AMI/silhouette.
|
||
7. **UMAP перед кластеризацией — спорно.** Сами авторы советуют делать это «с осторожностью» и сравнивать с кластеризацией в исходном (или PCA-сжатом) пространстве как sanity-check.
|
||
|
||
---
|
||
|
||
### Источники
|
||
|
||
- [McInnes, Healy, Melville. UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction. arXiv:1802.03426 (2018)](https://arxiv.org/abs/1802.03426)
|
||
- [umap-learn — Basic Parameters](https://umap-learn.readthedocs.io/en/latest/parameters.html)
|
||
- [umap-learn — Using UMAP for Clustering](https://umap-learn.readthedocs.io/en/latest/clustering.html)
|
||
- [Kobak & Linderman. Initialization is critical for preserving global data structure. Nature Biotechnology (2021)](https://www.nature.com/articles/s41587-020-00809-z)
|
||
- [pair-code — Understanding UMAP](https://pair-code.github.io/understanding-umap/)
|
||
- [Vinh, Epps, Bailey. Information Theoretic Measures for Clusterings Comparison. JMLR (2010)](https://jmlr.csail.mit.edu/papers/volume17/15-627/15-627)
|
||
- [scikit-learn — Clustering metrics](https://scikit-learn.org/stable/modules/clustering.html)
|
||
- [scikit-learn — trustworthiness](https://scikit-learn.org/stable/modules/generated/sklearn.manifold.trustworthiness.html)
|