K-ближайших соседей

K-ближайших соседей (KNN) — один из простейших и наиболее интуитивных алгоритмов машинного обучения. Для классификации нового элемента алгоритм находит K ближайших обучающих примеров и проводит голосование — побеждает класс большинства. Для регрессии вместо этого вычисляется среднее значение K соседей.

В этой главе рассматривается:

• Пошаговая работа алгоритма KNN
• Метрики расстояния: евклидова, манхэттенская и Минковского
• Почему масштабирование признаков критически важно для KNN
• Как выбрать правильное значение K
• Классификация и регрессия с помощью scikit-learn
• Оценка классификатора KNN с матрицей ошибок
• Преимущества, ограничения и случаи применения KNN

Как работает KNN

KNN — это ленивый обучающийся алгоритм: он не выполняет никакого реального «обучения». Вместо этого он запоминает весь датасет и откладывает все вычисления на момент предсказания.

Для нового элемента алгоритм:

1. Вычисляет расстояние от нового элемента до каждого обучающего элемента.
2. Выбирает K обучающих элементов с наименьшими расстояниями («ближайших соседей»).
3. Агрегирует их метки:
   • Классификация — новый элемент получает наиболее часто встречающуюся метку класса.
   • Регрессия — новый элемент получает среднее (или взвешенное среднее) целевых значений соседей.

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

Метрики расстояния

«Ближайший» в KNN определяется функцией расстояния. По умолчанию в scikit-learn используется евклидово расстояние — расстояние по прямой в n-мерном пространстве:

d(p, q) = sqrt( (p1-q1)² + (p2-q2)² + … + (pn-qn)² )

Две распространённые альтернативы:

Метрику в scikit-learn можно изменить с помощью параметра metric:

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=5, metric='manhattan')

Почему масштабирование признаков критически важно

KNN вычисляет «сырые» расстояния. Признак, измеряемый тысячами (например, зарплата), полностью вытеснит признак, измеряемый единицами (например, годы опыта), даже если меньший признак более информативен.

Всегда масштабируйте признаки перед использованием KNN. Подробное объяснение приведено в главе масштабирование признаков; краткий вариант:

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)   # fit on training data only
X_test_scaled  = scaler.transform(X_test)         # apply same transform to test data

Никогда не вызывайте fit_transform на тестовом наборе — это приведёт к утечке статистики тестового набора в скейлер.

Выбор K

K управляет компромиссом между смещением и дисперсией:

• Малое K (например, K=1) — очень гибкое, точно подстраивается под обучающие данные, но чувствительно к шуму и склонно к переобучению. Один выброс среди соседей может изменить предсказание.
• Большое K — более гладкая граница решения, меньшая дисперсия, но может недообучиться и размыть реальные границы классов.

Стандартный подход — перебрать диапазон значений K и выбрать то, которое даёт наилучшую точность при кросс-валидации:

import numpy as np
from sklearn.neighbors import KNeighborsClassifier
from sklearn.model_selection import cross_val_score
from sklearn.datasets import load_iris
from sklearn.preprocessing import StandardScaler

iris = load_iris()
X, y = iris.data, iris.target

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

k_range = range(1, 31)
cv_scores = []

for k in k_range:
    knn = KNeighborsClassifier(n_neighbors=k)
    scores = cross_val_score(knn, X_scaled, y, cv=5, scoring='accuracy')
    cv_scores.append(scores.mean())

best_k = k_range[np.argmax(cv_scores)]
print(f"Best K: {best_k}, CV Accuracy: {max(cv_scores):.4f}")

Ожидаемый вывод:

Best K: 6, CV Accuracy: 0.9667

Подробнее о кросс-валидации см. в главе кросс-валидация.

Практические правила:

• Предпочитайте нечётное K для бинарной классификации во избежание ничьей.
• Распространённая отправная точка — K = sqrt(n), где n — количество обучающих примеров.
• Всегда проверяйте с помощью кросс-валидации, а не угадывайте.

Классификация KNN с scikit-learn

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

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import accuracy_score, classification_report

# 1. Load a real dataset
iris = load_iris()
X, y = iris.data, iris.target

# 2. Split into training and test sets
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

# 3. Scale features — critical for KNN
scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled  = scaler.transform(X_test)

# 4. Train the classifier
knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_scaled, y_train)

# 5. Predict and evaluate
y_pred = knn.predict(X_test_scaled)
print(f"Accuracy: {accuracy_score(y_test, y_pred):.2f}")
print()
print(classification_report(y_test, y_pred, target_names=iris.target_names))

Ожидаемый вывод:

Accuracy: 0.93

              precision    recall  f1-score   support

      setosa       1.00      1.00      1.00        10
  versicolor       0.83      1.00      0.91        10
   virginica       1.00      0.80      0.89        10

    accuracy                           0.93        30
   macro avg       0.94      0.93      0.93        30
weighted avg       0.94      0.93      0.93        30

KNN с K=5 достигает 93% точности на этом тестовом наборе из 30 образцов. Setosa классифицируется идеально, поскольку линейно отделима от двух других; versicolor и virginica частично перекрываются, что приводит к нескольким ошибкам классификации.

Обратите внимание на аргумент stratify=y в train_test_split — он сохраняет пропорции классов в каждой части разбивки, что особенно важно для несбалансированных датасетов. Подробнее см. в главе разбивка на обучающую и тестовую выборки.

Оценка с матрицей ошибок

Матрица ошибок показывает, какие именно классы модель путает друг с другом:

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import confusion_matrix

iris = load_iris()
X, y = iris.data, iris.target

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn = KNeighborsClassifier(n_neighbors=5)
knn.fit(X_train_s, y_train)
y_pred = knn.predict(X_test_s)

cm = confusion_matrix(y_test, y_pred)
print(cm)

Ожидаемый вывод:

[[10  0  0]
 [ 0 10  0]
 [ 0  2  8]]

Каждая строка — истинный класс; каждый столбец — предсказанный класс. Диагональные значения — правильные предсказания; внедиагональные — ошибки классификации. Здесь 2 образца virginica были ошибочно классифицированы как versicolor. Подробное объяснение приведено в главе матрица ошибок.

Регрессия KNN с scikit-learn

Для регрессии KNN предсказывает среднее значений целевой переменной у K ближайших соседей. Замените KNeighborsClassifier на KNeighborsRegressor:

from sklearn.datasets import fetch_california_housing
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsRegressor
from sklearn.metrics import mean_squared_error, r2_score
import numpy as np

# Load a real regression dataset (a subset for speed)
housing = fetch_california_housing()
X, y = housing.data[:2000], housing.target[:2000]

X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn_reg = KNeighborsRegressor(n_neighbors=5)
knn_reg.fit(X_train_s, y_train)
y_pred = knn_reg.predict(X_test_s)

rmse = np.sqrt(mean_squared_error(y_test, y_pred))
r2   = r2_score(y_test, y_pred)
print(f"RMSE: {rmse:.4f}")
print(f"R²:   {r2:.4f}")

Ожидаемый вывод:

RMSE: 0.4217
R²:   0.8053

RMSE выражается в тех же единицах, что и целевая переменная (медианная стоимость жилья в $100 тыс.). R² равный 0.81 означает, что модель объясняет около 81% дисперсии на этом подмножестве из 2 000 образцов — сильный результат для ненастроенного базового KNN.

Взвешенный KNN

По умолчанию все K соседей имеют одинаковый вес независимо от расстояния до них. Установка weights='distance' делает ближайших соседей более влиятельными:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import accuracy_score

iris = load_iris()
X, y = iris.data, iris.target
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

scaler = StandardScaler()
X_train_s = scaler.fit_transform(X_train)
X_test_s  = scaler.transform(X_test)

knn_uniform  = KNeighborsClassifier(n_neighbors=5, weights='uniform')
knn_distance = KNeighborsClassifier(n_neighbors=5, weights='distance')

knn_uniform.fit(X_train_s, y_train)
knn_distance.fit(X_train_s, y_train)

print(f"Uniform weights accuracy:  {accuracy_score(y_test, knn_uniform.predict(X_test_s)):.2f}")
print(f"Distance weights accuracy: {accuracy_score(y_test, knn_distance.predict(X_test_s)):.2f}")

Ожидаемый вывод:

Uniform weights accuracy:  0.93
Distance weights accuracy: 0.97

Взвешивание по расстоянию улучшает точность с 0.93 до 0.97 — ближайшие соседи оказывают большее влияние, что помогает разрешить неоднозначные пограничные случаи.

Преимущества и ограничения

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

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

Когда избегать KNN

• Большие датасеты. Время предсказания масштабируется с количеством обучающих образцов (O(n·d) на запрос). Для миллионов образцов рассмотрите библиотеки приближённого поиска ближайших соседей (Faiss, Annoy) или переключитесь на более быстрый алгоритм.
• Многомерные данные. В большом числе измерений все точки становятся примерно равноудалёнными — «проклятие размерности». KNN быстро деградирует при более ~20 признаках. Сначала примените снижение размерности (PCA, отбор признаков).
• Нерелевантные признаки. Каждый признак участвует в расчёте расстояния. Шумные или нерелевантные признаки размывают сигнал. Удалите или сократите их до обучения.
• Среды с ограниченной памятью. KNN хранит весь обучающий набор; датасет с миллионами строк занимает значительный объём RAM.

Итоги

Связанные главы:

• Масштабирование признаков — зачем и как масштабировать перед KNN
• Разбивка на обучающую и тестовую выборки — правильное разбиение данных
• Кросс-валидация — выбор K с помощью k-кратной кросс-валидации
• Матрица ошибок — интерпретация результатов классификации
• Поиск по сетке — систематическая настройка гиперпараметров