KNN (K-Nearest Neighbors — метод k-ближайших соседей)

KNN (K-Nearest Neighbors — метод k-ближайших соседей) — это простой, интуитивно понятный алгоритм машинного обучения, используемый для задач классификации и регрессии. Его основная идея: “скажи мне, кто твои соседи, и я скажу, кто ты”.

Основная концепция

Алгоритм основан на предположении, что похожие объекты (близкие в пространстве признаков) имеют схожие значения целевой переменной.

Для классификации:

Объект относится к тому классу, к которому принадлежит большинство из его k ближайших соседей.

Для регрессии:

Значение объекта — это среднее (или медиана) значений его k ближайших соседей.

Как работает алгоритм (шаги)

Загрузить данные: Имеем размеченный набор данных (обучающую выборку)
Выбрать метрику расстояния: Определить, как измерять “близость” объектов
Выбрать k: Количество соседей для рассмотрения
Для нового объекта:
- Вычислить расстояние от этого объекта до всех объектов в обучающей выборке
- Найти k объектов с наименьшими расстояниями (ближайших соседей)
- Для классификации: подсчитать количество соседей каждого класса, назначить наиболее частый класс
- Для регрессии: вычислить среднее значение соседей

Ключевые компоненты

1. Метрики расстояния (как измеряем близость):

Метрика	Формула	Особенности
Евклидово	$\sqrtΣ (x_{i} - y_{i})^{2}$	Наиболее распространённая, чувствительна к масштабу
Манхэттенское	$Σ∥ x_{i} - y_{i} ∥$	Подходит для данных с выбросами, быстрее вычисляется
Минковского	$(Σ∥ x_{i} - y_{i} ∥^{p})^{(} 1/ p)$	Обобщение (p=1 — Манхэттен, p=2 — Евклид)
Косинусное	$(x \cdot y) / (∥ x ∥∥ y ∥)$	Для текстов, игнорирует длину векторов

2. Выбор параметра k:

Слишком маленькое k (k=1):
- Высокая чувствительность к шуму и выбросам
- Сложная граница решений, риск переобучения
- Низкое смещение, высокая дисперсия
Слишком большое k:
- Сглаживание границы решений
- Учёт далёких (нерелевантных) объектов
- Высокое смещение, низкая дисперсия
- Риск недообучения
Оптимальное k:
- Обычно выбирается через кросс-валидацию
- Часто нечётное (чтобы избежать ничьей в классификации)
- Практическое правило: k ≈ √n, где n — размер обучающей выборки

3. Взвешивание соседей:

Единичные веса: Все соседи равноправны
Взвешенные по расстоянию: Более близкие соседи имеют больший вес
- Например: вес = 1 / расстояние или вес = exp(-расстояние)

Реализация в Python

from sklearn.neighbors import KNeighborsClassifier, KNeighborsRegressor
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score
 
# Для классификации
knn_classifier = KNeighborsClassifier(
    n_neighbors=5,        # k соседей
    weights='uniform',    # или 'distance' для взвешивания
    metric='euclidean',   # метрика расстояния
    algorithm='auto'      # алгоритм поиска соседей
)
 
# Для регрессии
knn_regressor = KNeighborsRegressor(
    n_neighbors=5,
    weights='uniform',
    metric='euclidean'
)
 
# Важный этап: масштабирование признаков!
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)
 
# Обучение и предсказание
knn_classifier.fit(X_train, y_train)
predictions = knn_classifier.predict(X_test)

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

Простота реализации и понимания
Не требует обучения (ленивый алгоритм): Модель “запоминает” данные, вычисления происходят только при предсказании
Адаптивность: Легко добавлять новые данные
Универсальность: Работает для классификации и регрессии
Непараметрический: Не делает предположений о распределении данных
Естественная обработка многоклассовых задач

Недостатки и ограничения

Вычислительная сложность:
- Хранит весь набор данных (проблема памяти)
- Время предсказания O(n) для наивной реализации
- Не подходит для больших данных (>50-100 тыс. объектов)
Чувствительность к масштабу и шуму:
- Требует масштабирования признаков
- Чувствителен к выбросам и нерелевантным признакам
Проклятие размерности:
- Эффективность резко падает при большом количестве признаков (>20-30)
- В высоких размерностях все объекты становятся “одинаково далекими”
Выбор метрики и k: Требует тонкой настройки и кросс-валидации
Неравномерные данные: Плохо работает, когда плотность классов сильно различается

Оптимизации и улучшения

Структуры данных для быстрого поиска:
- KD-деревья
- Ball trees
- LSH (Locality Sensitive Hashing)
Методы уменьшения размерности:
- PCA, t-SNE для борьбы с проклятием размерности
Отбор признаков: Удаление нерелевантных признаков
Дискретизация непрерывных признаков

Практические рекомендации

Когда использовать KNN:

✅ Хорошо работает, когда:

Небольшой или средний набор данных (до 50 тыс. объектов)
Небольшое количество признаков (<20)
Данные очищены от шума и нормализованы
Нужен простой baseline для сравнения
Интерпретируемость важнее точности

❌ Стоит избегать, когда:

Большие объемы данных
Высокая размерность признаков
Требуется быстрое предсказание
Данные зашумлены или содержат много выбросов

Важные шаги при использовании:

Масштабирование признаков (StandardScaler, MinMaxScaler)
Обработка пропусков и выбросов
Отбор/преобразование признаков
Кросс-валидация для выбора k и метрики
Балансировка классов (если нужно)

Пример выбора k через кросс-валидацию

from sklearn.model_selection import GridSearchCV
 
param_grid = {
    'n_neighbors': list(range(1, 31)),
    'weights': ['uniform', 'distance'],
    'metric': ['euclidean', 'manhattan', 'minkowski']
}
 
grid_search = GridSearchCV(
    KNeighborsClassifier(),
    param_grid,
    cv=5,
    scoring='accuracy'
)
grid_search.fit(X_scaled, y)
print(f"Лучшие параметры: {grid_search.best_params_}")

Интересные модификации

Radius Neighbors: Использует всех соседей в пределах заданного радиуса
KNN с ядрами: Использует ядерные функции для взвешивания
Взвешенный KNN: Разные веса для разных признаков
Адаптивный KNN: k меняется в зависимости от плотности данных

KNN — отличный алгоритм для начала изучения машинного обучения, демонстрирующий фундаментальные концепции близости и сходства объектов. Несмотря на простоту, при правильной подготовке данных и настройке параметров может показывать конкурентоспособные результаты, особенно на небольших и средних наборах данных с явной пространственной структурой.

LDS