Метод ближайших соседей

Заметка о валидации дала способ честно измерить любую модель; пока единственными моделями были мысленные эксперименты. Запоминающая модель из вводной заметки верно отвечает на вопросы об уже виденных объектах и ничего не может сказать об остальных. Наименьшее изменение, которое делает её полезной, — отвечать на новый вопрос ответами на самые похожие из виденных вопросов. Это метод ближайших соседей (nearest neighbours; Fix and Hodges, 1951). Ему не нужно никакого обучения, кроме хранения данных, он работает для любой целевой переменной и состоятелен, когда число соседей растёт вместе с объёмом обучающей выборки (но медленнее): тогда при достаточном объёме данных он приближается к наилучшему возможному прогнозу, а один сосед даёт в пределе ошибку не больше удвоенной наименьшей возможной. Кроме того, он характерным образом ломается, когда растёт число признаков, и этот провал мотивирует остальную часть курса.

Обозначения. $\rho(x, z) \ge 0$ — расстояние между объектами. Для запроса $u$ обучающие объекты, упорядоченные по расстоянию, — $x_{(1)}(u), x_{(2)}(u), \dots$ со значениями целевой переменной $y_{(1)}(u), \dots$; $N_k(u)$ — множество $k$ ближайших. Для двух классов $\eta(x) = P(Y = 1 \mid X = x)$, а $R^*$ — байесовская ошибка из вводной заметки.

Правило#

Классификация: предсказать класс, самый частый среди $k$ ближайших соседей,

$$\hat f(u) = \arg\max_{c} \sum_{i \in N_k(u)} [y_i = c] .$$

Регрессия: предсказать среднее их целевых значений, $\hat f(u) = \frac1k \sum_{i \in N_k(u)} y_i$. Это локальная оценка условного математического ожидания $E[Y \mid X = u]$, наилучшего прогноза для квадратичной потери: среднее $Y$ по обучающим точкам, у которых $X$ близко к $u$. Точно так же доли голосов оценивают вероятности классов $P(Y = c \mid X = u)$.

Разобранный пример. Запрос $u = (0, 0)$ и пять обучающих точек: $A = (1, 0)$ и $C = (-2, 0)$ класса $+$ и $B = (0, 2)$, $D = (2, 2)$, $E = (0, -3)$ класса $-$. Расстояния до $A, B, C, D, E$ равны $1$, $2$, $2$, $2.83$ и $3$. При $k = 1$ прогноз $+$ (сосед $A$); при $k = 3$ он $+$ ($A$, $B$, $C$: два голоса против одного); при $k = 5$ он $-$ (три голоса против двух). Ответ зависит от $k$, и его качество тоже.

Выбор k: смещение против разброса#

Малое $k$ близко следует данным; большое $k$ усредняет по широкой окрестности. Для регрессии с дисперсией шума $\sigma^2$ среднее $k$ независимых зашумлённых целевых значений имеет дисперсию $\sigma^2/k$, так что большее $k$ снижает разброс; но $k$-й сосед лежит дальше, там, где $E[Y \mid X]$ отличается от своего значения в $u$, так что большее $k$ увеличивает смещение. При $k = 1$ каждая обучающая точка — сама себе ближайший сосед, и ошибка на обучении равна нулю; при $k = n$ каждый запрос получает класс, преобладающий во всей выборке. Рисунок показывает три режима на данных, для которых наилучшее правило известно:

Рисунок

Граница метода k ближайших соседей при трёх значениях k

При $k = 1$ граница обводит отдельные точки «чужого» цвета: ошибка на обучении 0, риск 0.188. При $k = 15$ граница близко повторяет байесовскую, и риск, 0.141, близок к байесовской ошибке 0.135. При $k = 101$ голосование усредняет по половине обучающей выборки, граница слишком гладкая, и риск вырастает до 0.204. Лучшее $k$ выбирают кросс-валидацией, а поскольку кросс-валидация тогда сообщает лучший из многих кандидатов, вложенная схема честно оценивает результат: на данных breast cancer, входящих в scikit-learn, перебор по сетке значений $k$ выбирает $k = 5$ с долей правильных ответов (accuracy) по кросс-валидации 0.965 и вложенной оценкой 0.968 для стандартизованных признаков (раздел «Код»).

Взвешенное голосование и ядерная регрессия#

Простое голосование не учитывает, насколько близки соседи: в разобранном примере $A$ на расстоянии 1 весит столько же, сколько $E$ на расстоянии 3. Взвешенный kNN (weighted kNN) даёт каждому соседу вес, убывающий с расстоянием. С весами $1/\rho$ и $k = 5$ класс $+$ получает $1 + 0.5 = 1.5$, а класс $-$ получает $0.5 + 0.354 + 0.333 = 1.187$, так что прогноз возвращается к $+$.

Если брать веса из ядра (kernel) $K$ с шириной окна (bandwidth) $h$, получается оценка Надарая–Ватсона (Nadaraya–Watson estimator; Nadaraya, 1964; Watson, 1964):

$$\hat f(u) = \frac{\sum_i K\big(\rho(u, x_i)/h\big)\, y_i}{\sum_i K\big(\rho(u, x_i)/h\big)} ,$$

взвешенное среднее, которое минимизирует $\sum_i K(\rho(u, x_i)/h)\,(c - y_i)^2$ по константе $c$. С гауссовским ядром $K(t) = e^{-t^2/2}$ и $h = 1$ пять точек примера получают веса $0.607, 0.135, 0.135, 0.018, 0.011$, и доля класса $+$ равна $(0.607 + 0.135)/0.906 = 0.818$. Ширина окна играет роль $k$: малое $h$ даёт локальную и шумную оценку, большое $h$ — гладкую и смещённую. Ядра вернутся в этом курсе как функции сходства в методе опорных векторов, и там это слово означает другое. Здесь ядро — сглаживающий вес: неотрицательная функция расстояния, убывающая при удалении от нуля. Там это положительно полуопределённая функция сходства, скалярное произведение отображений в пространство признаков. Гауссовское ядро — пример и того, и другого.

Расстояния и масштабирование#

Всё держится на расстоянии. Распространённые варианты:

Расстояние	Формула	Типичное применение
Евклидово	$\sqrt{\sum_j (x_j - z_j)^2}$	числовые признаки сравнимых масштабов
Манхэттенское	$\sum_j \lvert x_j - z_j \rvert$	меньше зависит от одного большого различия по координате
Косинусное	$1 - \frac{x^\top z}{\lVert x \rVert\, \lVert z \rVert}$	счётчики слов, эмбеддинги: важно направление, а не длина
Хэмминга, Жаккара	доля различающихся координат; $1 - \frac{\lvert A \cap B \rvert}{\lvert A \cup B \rvert}$	бинарные признаки, множества тегов

Евклидово расстояние складывает квадраты разностей признаков в их собственных единицах, поэтому признак с наибольшим разбросом решает, кто кому сосед. На данных wine kNN на сырых столбцах подчиняется одному признаку со стандартным отклонением 314 и достигает доли правильных ответов 0.663 против 0.961 на стандартизованных столбцах, как показала заметка о данных. Но и стандартизация не всегда верна: на данных digits, где каждый признак — интенсивность пикселя в одной и той же шкале, 1-NN достигает 0.988 на сырых пикселях и 0.973 после стандартизации, которая раздувает шум почти постоянных краевых пикселей. Нерелевантные признаки хуже плохо отмасштабированных, поскольку каждый добавляет шум в каждое расстояние; помогают отбор признаков или расстояние, выученное по данным. Для текстов классический выбор — косинус между векторами мешка слов, и эти векторы строит курс NLP.

Проклятие размерности#

Метод ближайших соседей рассчитывает на то, что рядом с запросом есть обучающие точки. Во многих измерениях их нет (Hastie, Tibshirani and Friedman, 2009, раздел 2.5):

• Окрестности перестают быть локальными. Для данных, равномерно распределённых в единичном кубе $[0, 1]^d$, подкуб, содержащий 1% данных, имеет ребро $0.01^{1/d}$: 0.1 при $d = 2$, но 0.63 при $d = 10$ и 0.95 при $d = 100$. «Окрестность» с 1% данных охватывает бо́льшую часть диапазона каждого признака.
• Объём сосредоточен у поверхности. Доля объёма $d$-мерного шара, лежащая в пределах 5% радиуса от поверхности, равна $1 - 0.95^d$: 0.098 при $d = 2$, 0.401 при $d = 10$, 0.994 при $d = 100$. Та же концентрация помещает гауссовские сэмплы на тонкую оболочку вдали от центра распределения.
• Все расстояния становятся похожими. Beyer et al. (1999), теорема 1, показывают, что при фиксированном числе точек, если относительная дисперсия расстояния от запроса до точки данных стремится к нулю с ростом размерности (а это выполняется для независимых одинаково распределённых координат), то отношение самого большого расстояния к самому малому стремится к 1 по вероятности. Ближайший сосед тогда почти не ближе любой другой точки.

Рисунок

В большой размерности все точки далеко и все одинаково далеко

При 1000 равномерно распределённых точек ближайшая точка в двух измерениях в 50 раз ближе самой дальней (отношение 0.02), а в тысяче — лишь в 1.1 раза (отношение 0.89). Число точек, нужное, чтобы соседи оставались локальными, растёт экспоненциально с $d$.

Две вещи смягчают проклятие размерности (curse of dimensionality) на практике. Реальные данные редко распределены равномерно по всем своим измерениям: изображения, текстовые эмбеддинги и показания датчиков лежат вблизи низкоразмерных структур, и важна именно эта внутренняя размерность (intrinsic dimension), а не число столбцов. Кроме того, хорошее представление меняет расстояния: kNN на сырых пикселях посредственен, а kNN на эмбеддингах обученной сети лежит в основе современного поиска. И всё же для обычных табличных признаков проклятие реально, и это тот провал, на который следующие заметки отвечают глобальными моделями, которым не нужен сосед поблизости.

Оптимальность: две байесовские ошибки#

Насколько хорошим может быть такое простое правило? Cover and Hart (1967) ответили на этот вопрос для правила одного ближайшего соседа при росте обучающей выборки. При $n \to \infty$ ближайший сосед $u$ сходится к $u$, поэтому его метка становится независимым наблюдением из того же условного распределения, что и метка $u$. Для двух классов правило тогда ошибается в $u$ с вероятностью $\eta(u)(1 - \eta(u)) + (1 - \eta(u))\eta(u) = 2\eta(u)(1 - \eta(u))$. Обозначив $r(u) = \min(\eta(u), 1 - \eta(u))$ условную байесовскую ошибку, получаем, что ошибка 1-NN в пределе большой выборки равна $R_{1\mathrm{NN}} = E[2 r(X)(1 - r(X))]$, и поскольку $E[r(X)^2] \ge (E\,r(X))^2 = (R^*)^2$,

$$R^* \le R_{1\mathrm{NN}} \le 2R^*(1 - R^*) \le 2R^* .$$

Для $K$ классов оценка равна $R^*\big(2 - \frac{K}{K-1}R^*\big)$ (Cover and Hart, 1967, раздел VI). Утверждение точно в трёх отношениях. Это предел ожидаемой ошибки при $n \to \infty$, а не гарантия для конечных выборок, на которых 1-NN может быть намного хуже (панель рисунка с $k = 1$: 0.188 против байесовской ошибки 0.135 при 200 точках). Ему нужны мягкие условия: сепарабельное метрическое пространство и, с вероятностью единица, либо непрерывность условных плотностей классов в точке запроса, либо положительная вероятность самой этой точки. И верхняя оценка точна: она достигается ровно тогда, когда $r(x)$ постоянна. Разобранный пример. На $[0, 1]$ с $\eta = 0.1$ на левой половине и $0.7$ на правой $R^* = \frac12(0.1 + 0.3) = 0.2$, $R_{1\mathrm{NN}} = \frac12(2 \cdot 0.1 \cdot 0.9 + 2 \cdot 0.3 \cdot 0.7) = 0.30$, а оценка равна $2 \cdot 0.2 \cdot 0.8 = 0.32$. Обученный на 20 000 точек, 1-NN имеет ошибку на тесте 0.306 (раздел «Код»).

По выражению Кавера и Харта, половина информации бесконечной выборки содержится в одном ближайшем соседе. Для другой половины нужна растущая окрестность: если $k \to \infty$ и $k/n \to 0$, правило $k$-NN сходится к байесовской ошибке для любого распределения $(X, Y)$ с $X \in \mathbb R^d$ и евклидовым расстоянием (равноудалённые точки упорядочиваются случайно) — это результат об универсальной состоятельности (universal consistency), принадлежащий Stone (1977). Для регрессии среднее по $k$ соседям сходится в среднеквадратичном, если $E\,Y^2 \lt \infty$. Результат относится к конечномерным входам; для произвольного метрического пространства нужны дополнительные условия. В примере 101-NN на тех же 20 000 точек ошибается в 0.206 случаев, близко к $R^* = 0.2$.

Быстрый поиск соседей#

Платить kNN приходится при прогнозе: полный перебор вычисляет на каждый запрос $n$ расстояний в $d$ измерениях, $O(nd)$, что слишком медленно для миллионов объектов и тысяч запросов в секунду.

• Деревья, разбивающие пространство. kd-дерево (kd-tree; Bentley, 1975) делит пространство по одной координате за раз и отсекает ветви, в которых не может быть более близкой точки. В малой размерности запрос стоит примерно $O(\log n)$; в большой отсечение перестаёт работать, и поиск вырождается в проверку почти каждой точки — ещё одно лицо проклятия размерности.
• Хеширование, чувствительное к близости (locality-sensitive hashing; Indyk and Motwani, 1998), хеширует объекты так, что близкие объекты с высокой вероятностью попадают в одну корзину, а далёкие — редко, и ищет только в корзинах запроса.
• Графовые индексы. HNSW (Malkov and Yashunin, 2020) связывает каждый хранимый вектор с несколькими близкими соседями, образуя граф близости (proximity graph), и строит несколько таких слоёв на вложенных подмножествах, как в списке с пропусками (skip list): каждый вектор входит в слои вплоть до случайного максимального уровня, выбранного из экспоненциально убывающего распределения, так что верхние слои разрежены, а связи в них длинные. Поиск начинается сверху, жадно идёт к хранимому вектору, ближайшему к запросу, спускается на слой ниже и повторяет; в нижнем слое он держит список кандидатов размера $ef$, и большее $ef$ меняет скорость на полноту (recall). В экспериментах авторов число шагов растёт примерно логарифмически с $n$, и поиск возвращает настоящих ближайших соседей в большинстве случаев, а не всегда.

Приближённый поиск — то, что делает ближайших соседей ядром современного поиска: заметка о семантическом поиске курса NLP переводит фрагменты в эмбеддинги нейросетевым энкодером и находит ближайшие к запросу фрагменты в таком индексе, а курс генеративных моделей использует шары $k$ ближайших соседей, чтобы оценивать носитель распределения в своей метрике точности и полноты.

Что изменилось#

	Запоминающая модель	$k$ ближайших соседей
Новый объект	ответ по умолчанию	ответы $k$ самых похожих объектов
Обучение	хранить данные	хранить данные
Стоимость прогноза	поиск в таблице	$O(nd)$ полным перебором; дерево или графовый индекс
Управление сложностью	нет	$k$ (или ширина окна $h$), выбранное кросс-валидацией
Ошибка на большой выборке	ошибка ответа по умолчанию	у 1-NN не больше $2R^*(1 - R^*)$; при $k \to \infty$, $k/n \to 0$ достигает $R^*$
Слабое место	всё новое	много измерений, масштабирование, нерелевантные признаки

Ограничения#

• Расстояние и есть модель. Плохое масштабирование или нерелевантные признаки делают соседей бессмысленными, и у kNN нет механизма, чтобы выучить, какие признаки важны.
• Большая размерность. Без низкой внутренней размерности или выученного представления объём данных, нужный, чтобы окрестности оставались локальными, растёт экспоненциально с $d$.
• Стоимость при прогнозе. Всю обучающую выборку нужно хранить и просматривать; приближённые индексы меняют точность поиска на скорость.
• Нет экстраполяции и нет сводки. Вдали от данных прогноз определяется теми точками, которые случайно оказались ближайшими, и нет коэффициентов, которые можно было бы изучить.
• Несбалансированные классы. Редкий класс, перекрывающийся с остальными, проигрывает голосование везде, где он в меньшинстве локально, если голоса не взвешены или $k$ не мало. Голосование зависит от локальной доли класса среди соседей, а не от его общей редкости: редкий класс, образующий плотный и хорошо отделённый кластер, всё равно побеждает внутри этого кластера, пока $k$ не превосходит его размер.

Что нужно запомнить#

• kNN предсказывает самый частый класс или среднее целевое значение $k$ ближайших обучающих объектов; это локальная оценка $E[Y \mid X]$ или вероятностей классов.
• Малое $k$: низкое смещение, высокий разброс (у 1-NN нулевая ошибка на обучении); большое $k$: наоборот. Выбирайте $k$ кросс-валидацией, отчитывайтесь вложенной кросс-валидацией.
• Взвешенное голосование и ядерная регрессия (Надарая–Ватсона) заменяют жёсткую окрестность весами; ширина окна играет роль $k$.
• Масштабируйте признаки перед вычислением евклидовых расстояний, если у них ещё нет общей единицы; для счётчиков и эмбеддингов предпочитайте косинусное расстояние.
• Проклятие размерности: окрестность с 1% данных при $d = 10$ охватывает 63% каждой оси; расстояния до ближайшего и самого дальнего соседа становятся похожими.
• При $n \to \infty$ для двух классов $R^* \le R_{1\mathrm{NN}} \le 2R^*(1 - R^*)$; $k$-NN с $k \to \infty$, $k/n \to 0$ универсально состоятелен в $\mathbb R^d$.
• Крупномасштабный поиск использует приближённые индексы вроде HNSW — механизм, на котором работает семантический поиск.

Код#

Выбор $k$, масштабирование, концентрация расстояний, оболочка и предел Кавера–Харта в симуляции:

import numpy as np
from sklearn.datasets import load_breast_cancer, load_digits
from sklearn.model_selection import GridSearchCV, StratifiedKFold, cross_val_score
from sklearn.neighbors import KNeighborsClassifier
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

rng = np.random.default_rng(0)
cv = StratifiedKFold(5, shuffle=True, random_state=0)

# choosing k by cross-validation on the breast-cancer data (30 features on very different scales)
X, y = load_breast_cancer(return_X_y=True)
for name, model in [('raw', KNeighborsClassifier()), ('scaled', make_pipeline(StandardScaler(), KNeighborsClassifier()))]:
    key = 'n_neighbors' if name == 'raw' else 'kneighborsclassifier__n_neighbors'
    search = GridSearchCV(model, {key: list(range(1, 50, 4))}, cv=cv).fit(X, y)
    nested = cross_val_score(search, X, y, cv=StratifiedKFold(5, shuffle=True, random_state=1)).mean()
    print(name, search.best_params_[key], round(search.best_score_, 3), round(nested, 3))
# raw 5 0.932 0.937 | scaled 5 0.965 0.968: best k, its CV accuracy, the nested estimate

# when every feature already has the same unit (pixel intensities 0-16), standardizing can hurt
Xd, yd = load_digits(return_X_y=True)
print(round(cross_val_score(KNeighborsClassifier(1), Xd, yd, cv=cv).mean(), 3),
      round(cross_val_score(make_pipeline(StandardScaler(), KNeighborsClassifier(1)), Xd, yd, cv=cv).mean(), 3))   # 0.988 0.973

# distance concentration: 1,000 uniform points in [0, 1]^d, 100 queries; mean of nearest / farthest distance
for d in (2, 10, 100, 1000):
    P, Q = rng.random((1000, d)), rng.random((100, d))
    D = np.sqrt(np.maximum((Q ** 2).sum(1)[:, None] + (P ** 2).sum(1)[None] - 2 * Q @ P.T, 0))
    print(d, round(float((D.min(1) / D.max(1)).mean()), 2))
# 2 0.02 | 10 0.27 | 100 0.69 | 1000 0.89
# volume within 5% of the surface of a d-ball, and the edge of a cube holding 1% of uniform data
print([round(1 - 0.95 ** d, 3) for d in (2, 10, 100)], [round(0.01 ** (1 / d), 2) for d in (1, 2, 10, 100)])
# [0.098, 0.401, 0.994] [0.01, 0.1, 0.63, 0.95]

# Cover and Hart: eta = P(Y = 1 | x) is 0.1 on [0, 0.5) and 0.7 on [0.5, 1]; Bayes error 0.2
eta = lambda x: np.where(x < 0.5, 0.1, 0.7)
r = np.minimum(eta(np.array([0.25, 0.75])), 1 - eta(np.array([0.25, 0.75])))
print(round(r.mean(), 3), round((2 * r * (1 - r)).mean(), 3), round(2 * r.mean() * (1 - r.mean()), 3))   # 0.2 0.3 0.32: R*, the 1-NN limit, the bound
x, xt = rng.random((20_000, 1)), rng.random((20_000, 1))
yy, yt = rng.random(20_000) < eta(x[:, 0]), rng.random(20_000) < eta(xt[:, 0])
for k in (1, 101):
    print(k, round(float((KNeighborsClassifier(k).fit(x, yy).predict(xt) != yt).mean()), 3))
# 1 0.306 | 101 0.206: test error of 1-NN and 101-NN trained on 20,000 points

Дальше#

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

Литература#

• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций, лекция о метрических методах: ближайшие соседи, ядерная регрессия, оптимальность kNN, быстрый поиск соседей.
• E. Fix, J. L. Hodges. Discriminatory analysis. Nonparametric discrimination: consistency properties. USAF School of Aviation Medicine, report 4, 1951; reprinted in International Statistical Review, 57(3), 1989.
• T. M. Cover, P. E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1), 1967. Раздел VI (теорема для двух категорий и её обобщение на $M$ категорий).
• C. J. Stone. Consistent nonparametric regression. Annals of Statistics, 5(4), 1977.
• K. Beyer, J. Goldstein, R. Ramakrishnan, U. Shaft. When is “nearest neighbor” meaningful? ICDT, 1999. Раздел 3.4, теорема 1.
• E. A. Nadaraya. On estimating regression. Theory of Probability and Its Applications, 9(1), 1964.
• G. S. Watson. Smooth regression analysis. Sankhyā A, 26(4), 1964.
• J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9), 1975.
• P. Indyk, R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. STOC, 1998.
• Yu. A. Malkov, D. A. Yashunin. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4), 2020. Раздел 4 (алгоритм).
• T. Hastie, R. Tibshirani, J. Friedman. The Elements of Statistical Learning, 2nd ed. Springer, 2009. Раздел 2.5 (локальные методы в большой размерности), раздел 13.3 (классификаторы $k$ ближайших соседей).
• C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006. Раздел 1.4 (проклятие размерности), раздел 2.5.2 (методы ближайших соседей).