k-NN: пишем код

01 Реализация с нуля

Лучший способ убедиться, что ты понимаешь алгоритм — написать его руками. k-NN для этого идеален: на чистом Python он умещается в десяток строк. Никаких хитрых формул, никакого градиентного спуска — только сортировка и подсчёт голосов.

Начнём с маленькой выборки. Пусть у нас есть точки на плоскости с метками классов 0 и 1:

import math
from collections import Counter

# Обучающая выборка: каждая точка — (x, y, класс)
train = [
    (1, 2, 0), (2, 1, 0), (2, 3, 0), (3, 2, 0),
    (6, 5, 1), (7, 6, 1), (7, 4, 1), (8, 5, 1),
]

# Новая точка, класс которой нужно предсказать
new_point = (5, 4)

Восемь точек: четыре в левом нижнем углу с классом 0, четыре в правом верхнем с классом 1. Новая точка где-то между ними. Куда её отнести?

Шаг 1: функция расстояния

def euclidean(a, b):
    """Евклидово расстояние между двумя точками."""
    return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

Прямо по теореме Пифагора. Берём разности по координатам, возводим в квадрат, складываем, извлекаем корень.

Шаг 2: сам алгоритм k-NN

def knn_predict(train, new_point, k):
    # 1. Считаем расстояние от новой точки до каждой обучающей
    distances = []
    for point in train:
        d = euclidean(new_point, point[:2])  # берём только x, y
        distances.append((d, point[2]))   # сохраняем (расстояние, класс)

    # 2. Сортируем по расстоянию и берём k ближайших
    distances.sort()
    k_nearest = distances[:k]

    # 3. Голосуем большинством
    classes = [cls for _, cls in k_nearest]
    most_common = Counter(classes).most_common(1)
    return most_common[0][0]

Вот и весь алгоритм. Давай разберём построчно, потому что здесь важна каждая деталь.

• Список distances — туда складываем пары: расстояние от новой точки до обучающей и класс этой обучающей точки. Класс нужно сохранить, чтобы потом проголосовать.
• point[:2] — берём только координаты, без метки класса. Иначе расстояние посчиталось бы по трём числам.
• distances.sort() — Python сортирует список кортежей по первому элементу, то есть по расстоянию. Это именно то, что нам нужно.
• distances[:k] — срез: первые k элементов отсортированного списка. Это и есть «k ближайших соседей».
• Counter(classes).most_common(1) — считает, сколько раз встречается каждый класс, возвращает самый частый. Это голосование большинством одной строкой.

Запускаем

for k in [1, 3, 5]:
    pred = knn_predict(train, new_point, k)
    print(f"k={k}: предсказанный класс = {pred}")

На этой выборке все три значения k дают одинаковый ответ — точка ближе к синим. Если хочешь увидеть, как ответ меняется с k, добавь в обучающую выборку выброс — например, синюю точку (4, 3, 1) прямо посреди красного облака. Тогда при k=1 новая точка может «поймать» этот выброс, а при k=5 он уже не повлияет.

02 То же самое через sklearn

Писать k-NN с нуля полезно для понимания. Но в реальной работе ты будешь брать готовую реализацию из библиотеки. Она быстрее (внутри использует структуры данных типа KD-дерева), отлажена и работает с массивами numpy.

from sklearn.neighbors import KNeighborsClassifier
import numpy as np

# Признаки и метки отдельно — так требует sklearn
X_train = np.array([
    [1, 2], [2, 1], [2, 3], [3, 2],
    [6, 5], [7, 6], [7, 4], [8, 5],
])
y_train = np.array([0, 0, 0, 0, 1, 1, 1, 1])

# Создаём модель и "обучаем" (на самом деле просто запоминаем)
model = KNeighborsClassifier(n_neighbors=3)
model.fit(X_train, y_train)

# Предсказываем
new_point = np.array([[5, 4]])
print("Класс:", model.predict(new_point)[0])
print("Вероятности:", model.predict_proba(new_point)[0])

Несколько важных моментов про API sklearn:

• Признаки и метки разделены. X_train — двумерный массив (по строке на каждый объект, по столбцу на каждый признак). y_train — одномерный массив с метками. Это стандарт для всего sklearn, не только для k-NN.
• fit(X, y) у k-NN не «обучает» в обычном смысле — он просто запоминает данные внутри объекта модели. Метод называется так для единообразия со всеми другими алгоритмами sklearn.
• predict ожидает двумерный массив, даже если ты предсказываешь одну точку. Поэтому [[5, 4]] с двойными скобками, а не [5, 4].
• predict_proba возвращает «вероятности» классов — на самом деле просто доли голосов соседей. Если из 3 соседей все 3 — класс 1, то вероятность [0, 1]. Это та самая грубая оценка, о которой мы говорили в теории.

03 Реальный пример: важность масштабирования

Возьмём настоящую задачу и покажем, почему нельзя забывать про масштабирование признаков. Классифицируем людей на «спортсмены» и «не спортсмены» по двум признакам: пульс в покое (40–90 ударов в минуту) и годовой доход (от 30 000 до 5 000 000 рублей).

Заметь подвох: пульс и доход — это совершенно разные шкалы. Доход в десятки тысяч раз больше по абсолютному значению.

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.model_selection import train_test_split
import numpy as np

# Генерируем синтетические данные
np.random.seed(42)
n = 200

# Спортсмены: низкий пульс, доход случайный
pulse_sport = np.random.normal(55, 5, n)
income_sport = np.random.normal(800000, 300000, n)

# Не спортсмены: высокий пульс, доход тоже случайный
pulse_other = np.random.normal(75, 5, n)
income_other = np.random.normal(800000, 300000, n)

X = np.vstack([
    np.column_stack([pulse_sport, income_sport]),
    np.column_stack([pulse_other, income_other]),
])
y = np.array([1] * n + [0] * n)

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

Обрати внимание: классы различаются только пульсом. Доход у обеих групп одинаковый — это «информационный шум». Идеальная модель должна научиться смотреть на пульс и игнорировать доход.

Без масштабирования

model_raw = KNeighborsClassifier(n_neighbors=5)
model_raw.fit(X_train, y_train)
acc_raw = model_raw.score(X_test, y_test)
print(f"Без масштабирования: {acc_raw:.1%}")

Около 52% — это почти как монетка. Алгоритм провалился. Почему? Потому что пульс отличается на единицы, а доход — на сотни тысяч. В формуле расстояния разница в доходе полностью «съедает» вклад пульса. K-NN, по сути, считает расстояние только по доходу — а доход не несёт никакой информации о классе.

С масштабированием

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.transform(X_test)

model_scaled = KNeighborsClassifier(n_neighbors=5)
model_scaled.fit(X_train_scaled, y_train)
acc_scaled = model_scaled.score(X_test_scaled, y_test)
print(f"С масштабированием: {acc_scaled:.1%}")

97.5% против 52%. Один и тот же алгоритм, одни и те же данные — разница только в том, что мы сделали StandardScaler перед обучением.

04 Подбираем оптимальное k

Мы говорили в теории: правильное значение k нужно подбирать. Маленькое k — переобучение, большое — недообучение, где-то посередине оптимум. Покажем это на коде.

from sklearn.model_selection import cross_val_score

k_values = range(1, 31, 2)  # нечётные от 1 до 29
scores = []

for k in k_values:
    model = KNeighborsClassifier(n_neighbors=k)
    # Кросс-валидация: 5 разбиений, среднее по точности
    cv_score = cross_val_score(model, X_train_scaled, y_train, cv=5).mean()
    scores.append(cv_score)
    print(f"k={k:2d}: {cv_score:.3f}")

best_k = k_values[np.argmax(scores)]
print(f"\nЛучшее k: {best_k}")

Видно характерную картину: на маленьких k точность ниже (модель переобучается на отдельных точках), потом она растёт, достигает максимума где-то в районе 11–15, и при дальнейшем увеличении k начинает медленно падать (модель переусредняется). Это та самая U-образная зависимость из теории — только перевёрнутая, потому что мы смотрим на точность, а не на ошибку.

Что такое cross_val_score

Это удобная функция для кросс-валидации. Что она делает под капотом:

• Разбивает обучающую выборку на 5 равных частей (потому что мы указали cv=5).
• Тренирует модель на 4 частях, проверяет на пятой. Записывает точность.
• Повторяет это 5 раз — каждая часть один раз побывает в роли тестовой.
• Возвращает массив из 5 точностей. Мы берём их среднее через .mean().

Зачем так сложно? Чтобы оценка была устойчивой. Если просто разбить данные на train/test один раз, можно случайно попасть на удобное (или неудобное) разбиение и получить обманчивую цифру. Кросс-валидация усредняет и даёт более честный результат.