KNN (k-Nearest Neighbors, k ближайших соседей)

KNN (k-Nearest Neighbors, «k ближайших соседей») — это один из самых простых и интуитивных алгоритмов машинного обучения. Он используется как для классификации, так и для регрессии. Иногда его называют «ленивым» алгоритмом (lazy learner), потому что он не строит явную модель во время обучения, а просто запоминает обучающие данные и делает вывод при появлении нового объекта.

Основная идея

Для нового объекта алгоритм:

1. Находит $k$ наиболее похожих на него объектов из обучающей выборки (соседей).
2. Смотрит на их ответы.
3. Выдаёт итоговый прогноз:
   • Классификация: выбирается класс, который чаще всего встречается среди $k$ соседей (голосование большинством).
   • Регрессия: берётся среднее (или взвешенное среднее) значений целевой переменной у $k$ соседей.

Как измеряется «похожесть»

Чаще всего используется расстояние между объектами:

• Евклидово расстояние: $\sqrt{\sum (x_i-y_i{)}^2}$
• Манхэттенское расстояние: $\sum |x_i-y_i|$
• Косинусное расстояние, расстояние Говера и другие — в зависимости от типов признаков.

Важно: перед применением KNN признаки нужно масштабировать (стандартизация или нормализация), иначе признаки с большими единицами измерения будут доминировать в расстоянии.

Параметр $k$

• Маленькое $k$ (например, 1): модель чувствительна к шуму и выбросам, может переобучаться.
• Большое $k$: модель становится более гладкой, но может недообучаться и размывать границы классов.
• Часто выбирают нечётное $k$ для классификации, чтобы избежать ничьих.
• Оптимальное $k$ подбирают по кросс-валидации.

Веса соседей

Можно учитывать расстояние: чем ближе сосед, тем больше его вклад.

• weights='uniform' — все соседи равны.
• weights='distance' — вес обратно пропорционален расстоянию.

Преимущества

• Очень прост в понимании и реализации.
• Не требует обучения (нет этапа подгонки параметров).
• Естественно работает с многоклассовой классификацией.
• Может улавливать нелинейные зависимости.
• Непараметрический: не делает предположений о распределении данных.

Недостатки

• Медленное предсказание: нужно сравнивать новый объект со всеми обучающими.
• Большая память: хранит всю обучающую выборку.
• Проклятие размерности: в пространствах высокой размерности расстояния теряют смысл, качество падает.
• Чувствительность к масштабу, выбросам и несбалансированным классам.
• Плохо работает с категориальными признаками без специального кодирования.
• Нет интерпретируемой модели (нельзя сказать, какие признаки важны).

Пример на Python (scikit-learn)

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import make_pipeline
 
model = make_pipeline(
    StandardScaler(),
    KNeighborsClassifier(n_neighbors=5, weights='distance')
)
model.fit(X_train, y_train)
pred = model.predict(X_test)