K-Nearest Neighbors (KNN)

Метод k ближайших соседей (KNN) — это алгоритм обучения с учителем, который предсказывает метку нового примера по k ближайшим к нему размеченным примерам: для классификации используется голосование большинства среди соседей, а для регрессии — их среднее значение. KNN — непараметрический и «ленивый» алгоритм: он не обучает веса, а просто хранит обучающие данные и выполняет всю работу при запросе предсказания. Эвелин Фикс и Джозеф Ходжес представили этот метод в 1951 году, а в 1967 году Томас Ковер и Питер Харт доказали, что при неограниченном объёме данных правило ближайшего соседа дает ошибку не более чем вдвое выше, чем лучший возможный классификатор. Сейчас такой же поиск ближайших соседей выполняется в больших масштабах в векторных базах данных и системах поиска изображений, сравнивающих эмбеддинги, полученные нейронными сетями.

Как KNN делает предсказание#

Для каждой точки запроса KNN выполняет три шага:

1. Измерение расстояния: алгоритм вычисляет расстояние от точки запроса до каждого сохранённого примера. Евклидово расстояние используется по умолчанию; распространённые альтернативы — расстояния Манхэттена и Минковского, а для эмбеддингов стандартом является косинусное сходство, поскольку смысл вектора определяется его направлением.
2. Выбор соседей: алгоритм выбирает k примеров с наименьшими расстояниями.
3. Объединение меток: при классификации выбирается наиболее частый класс среди соседей, а при регрессии — среднее их значений. При взвешивании по расстоянию (параметр weights="distance" в scikit-learn) ближайшие соседи имеют больший вес.

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

Выбор k#

Значение k задаёт баланс между переобучением и недообучением. При k = 1 каждая обучающая точка, включая зашумлённые и неправильно размеченные, занимает собственную область, а граница принятия решений становится изрезанной. При очень большом k каждый голос учитывает точки далеко от запроса, размывая реальные границы классов. Для двух классов нечётное k исключает равенство голосов, а стандартный способ выбрать k — перекрёстная проверка. На зашумлённом наборе данных «две луны» из scikit-learn компромисс виден на трёх значениях:

from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.neighbors import KNeighborsClassifier

# Two interleaving half-moons with overlapping, noisy points
X, y = make_moons(n_samples=1000, noise=0.35, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0)

# Fitting only stores the points; each prediction is a vote among the k nearest ones
for k in (1, 15, 300):
    knn = KNeighborsClassifier(n_neighbors=k)
    knn.fit(X_train, y_train)
    print(f"k={k}: train {knn.score(X_train, y_train):.2f}, test {knn.score(X_test, y_test):.2f}")

При k = 1 классификатор запоминает обучающие точки и получает на них 1.00, а на отложенных точках — 0.83. При k = 15 оценки составляют 0.90 и 0.89 — лучший результат на тестовой выборке из трёх вариантов. А k = 300, почти половина из 700 обучающих точек, сглаживает границу настолько, что обе оценки падают до 0.84 и 0.81.

Ускорение поиска соседей#

При полном переборе точка запроса сравнивается со всеми n сохранёнными точками в d измерениях, поэтому стоимость каждого предсказания составляет порядка n × d операций, а объём памяти растёт вместе с набором данных. Структуры разбиения пространства, такие как k-d-деревья и ball-деревья, пропускают большинство сравнений в пространствах низкой размерности, а algorithm="auto" в scikit-learn выбирает между полным перебором, k-d-деревом и ball-деревом. В пространствах высокой размерности проклятие размерности приводит к тому, что расстояния между точками становятся почти одинаковыми, эффективность отсечения ветвей деревьев падает, а крупные системы переходят на индексы приближённого поиска ближайших соседей (ANN), например графы HNSW и индексы инвертированных файлов (IVF) с продуктовым квантованием, реализованные в таких библиотеках, как FAISS. Эти индексы находят большинство действительно ближайших соседей, сравнивая точку запроса лишь с небольшой долей сохранённых векторов:

KNN и родственные методы#

• Кластеризация методом k-средних: алгоритм без учителя, который группирует неразмеченные точки в k кластеров вокруг обученных центроидов. Сходство названий случайно: в k-средних k обозначает число кластеров.
• Векторный поиск: вариант той же операции для поиска: он возвращает сохранённые элементы, ближайшие к эмбеддингу запроса, обычно с помощью приближённого индекса, а приложение непосредственно использует эти элементы.
• Метод опорных векторов и логистическая регрессия: параметрические модели, которые во время обучения находят границу принятия решений, поэтому стоимость предсказания остаётся постоянной по мере увеличения обучающего набора.

Примеры применения в реальных условиях#

• Рекомендательные системы: основанная на элементах коллаборативная фильтрация рекомендует товары, векторы оценок или покупок которых ближе всего к векторам товаров, уже понравившихся пользователю.
• Обнаружение аномалий: расстояние от точки до её k-го ближайшего соседа используется как оценка аномальности, поэтому транзакции или показания датчиков, удалённые от всех нормальных примеров, выделяются.
• Заполнение пропущенных значений: KNNImputer в scikit-learn заполняет каждый пропуск средним значением этого признака в k наиболее похожих строках.
• Поиск изображений и повторная идентификация: системы сравнивают эмбеддинг изображения с галереей, чтобы найти тот же товар, лицо или человека, попавшего на другую камеру. Решение Ultralytics для поиска по сходству строит эмбеддинги изображений из папки с помощью CLIP от OpenAI, сравнивает каждое индексированное изображение с текстовым запросом, например «красная машина», по косинусному сходству при точном полном переборе и возвращает ближайшие результаты — по умолчанию до 30.