Условие

В обучающей выборке 10 000 точек в [0,1]^d. Аналитик хочет использовать kNN. Почему алгоритм качественно ломается при d = 100 даже при таком N? Опишите три фундаментальные проблемы и предложите альтернативы.

Решение

Проблема 1 — рост объёма пустого пространства

Доля объёма единичного гиперкуба, лежащая в его «ободке» (расстояние от границы ≤ ε):

V_obod = 1 − (1 − 2ε)^d

При d=100, ε=0.05: V_obod = 1 − 0.9^100 ≈ 1 − 0.0000027 ≈ 1. То есть почти все точки лежат у границы. Внутренний регион практически пуст.

Расстояние от точки до ближайшего соседа в d=100 при N=10⁴ сопоставимо с расстоянием до дальнего соседа. «Близость» теряет смысл.

Проблема 2 — концентрация норм

Для x_1, x_2 ~ U([0,1]^d):

||x_1 - x_2||² ~ (d/6, d/180)        (mean, variance евклидова² расстояния)

Стандартное отклонение растёт как √d, а среднее — как d. Относительный разброс σ/μ → 0 при d → ∞. Все попарные расстояния «прижимаются» друг к другу.

import numpy as np
rng = np.random.default_rng(0)
for d in [2, 10, 50, 200]:
    X = rng.random((1000, d))
    D = np.linalg.norm(X[:, None] - X[None, :], axis=-1)
    np.fill_diagonal(D, np.nan)
    ratio = np.nanmin(D) / np.nanmax(D)
    print(f"d={d:3d}  min/max ratio = {ratio:.3f}")
# d=2 → 0.001;  d=10 → 0.10;  d=50 → 0.30;  d=200 → 0.55

При d=200 ближайший сосед в среднем всего в 2× ближе дальнего. У kNN нет сигнала.

Проблема 3 — экспоненциальная потребность в данных

Чтобы покрыть [0,1]^d равномерно с сеткой шага 0.1, нужно 10^d точек. При d=100 — 10^100, что физически невозможно (атомов во Вселенной ~10^80).

Альтернативы

1. Снижение размерности: PCA, t-SNE, UMAP. Свести 100 фич к 10-20 информативным компонентам.

2. Селекция фич: оставить только релевантные (см. mutual_info, L1).

3. Embeddings из NN: для текста/картинок — извлечь 128/256-мерные эмбеддинги, в которых уже учтена близость.

4. Approximate NN: FAISS, Annoy, HNSW. Работают и в высоких размерностях, но сами не «исправляют» проблему — только ускоряют.

5. Метрики, специфичные для домена: Cosine для текста, Mahalanobis для коррелированных фич.

6. Tree-based модели: random forest / gradient boosting устойчивы к нерелевантным фичам, не используют евклидово расстояние.

Когда kNN всё ещё работает

Низкие размерности (d < 20).
Эмбеддинги обученные на той же задаче (например, ArcFace для лиц).
После PCA до d = 30-50.
Manifold hypothesis: данные лежат на низкоразмерном многообразии внутри высокомерного пространства (классические картинки лиц на multilinear manifold).

from sklearn.neighbors import KNeighborsClassifier
from sklearn.decomposition import PCA
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import StandardScaler
 
pipe = Pipeline([
    ('scaler', StandardScaler()),
    ('pca',    PCA(n_components=30)),
    ('knn',    KNeighborsClassifier(n_neighbors=10))
])

Тест на «работает ли kNN»

# отношение mean distance к ближайшему к среднему расстоянию
from sklearn.neighbors import NearestNeighbors
nn = NearestNeighbors(n_neighbors=5).fit(X_train)
dists, _ = nn.kneighbors(X_test)
mean_neighbor   = dists[:, 1:].mean()
mean_all        = np.linalg.norm(X_test[:, None] - X_train[None, :], axis=-1).mean()
print("ratio :", mean_neighbor / mean_all)
# если > 0.5 — kNN не работает: ближайший сосед почти такой же, как любая точка

Подводные камни

«kNN на 100 фич с N=1000» — частая ошибка джунов. AUC будет почти как у случайного.
MinMaxScaler ≠ снижение размерности — нормализация не решает curse.
PCA на one-hot encoded разрушает категории (PCA — линейная). Лучше target encoding + PCA или fastTextentbed.
t-SNE / UMAP для предсказаний — нет: они нестабильны на новых точках, нужны для визуализации.
Cosine vs Euclidean: на текстах / нормализованных эмбеддингах Cosine стабильнее.
HNSW решает скорость, не точность: при curse of dimensionality «ближайший сосед» — всё равно почти случайный.
Manifold hypothesis не работает на «свалке фич» без структуры — нужно проверять (PCA scree plot).

Эталонный ответ

Три фундаментальные проблемы:

Концентрация в «ободке»: при d=100 почти все точки находятся у границы куба.
Концентрация расстояний: min/max расстояний → 1 → kNN теряет сигнал.
Экспоненциальная потребность в данных: для покрытия d-мерного куба нужно O(c^d) точек.

Альтернативы: PCA/UMAP → kNN; selection до 10-30 фич; tree-based модели; учиться embeddings (через NN) и работать в них; ANN-индексы (FAISS) не решают, а только ускоряют.

Sanity-check: если mean_neighbor / mean_all > 0.5 — kNN на этих фичах бесполезен.

zadachi_ds: Почему kNN ломается в высоких размерностях