KNN с нуля на Python: реализация и разбор

Зачем реализовывать KNN вручную?

В продакшене мы часто импортируем scikit-learn и не задумываемся о внутренностях. Но когда абстракции дают сбой, чёрный ящик может подвести. Построение K-Nearest Neighbors (KNN) с нуля — отличный способ понять, как алгоритм работает на самом деле. Вы столкнётесь с ключевыми инженерными задачами: вычисление геометрии в пространстве, управление голосованием, обработка граничных случаев. В этой статье мы пройдём путь от математики до рабочего кода.

1. Метрика расстояния: евклидово расстояние

KNN основан на простой геометрической идее: объект, скорее всего, принадлежит к тому же классу, что и его ближайшие соседи. Первое, что нужно — уметь измерять расстояние между точками. Используем евклидово расстояние, которое обобщается на любое количество измерений:

import math

def _check_length(x, y):
    """Проверяет, что векторы одинаковой длины."""
    if len(x) != len(y):
        raise ValueError("Векторы должны быть одной длины")

def euclidean_distance(x, y):
    """Вычисляет евклидово расстояние между двумя векторами."""
    _check_length(x, y)
    sum_of_sq = sum((i - j) ** 2 for i, j in zip(x, y))
    return math.sqrt(sum_of_sq)

В функции euclidean_distance используется генераторное выражение внутри sum(). Оно вычисляется лениво, не создавая промежуточный список квадратов разностей — это важно для производительности на больших данных. Проверка _check_length критична: zip() молча обрезает до короткого вектора, и без неё ошибка может остаться незамеченной.

2. Механизм голосования и разрешение связок

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

def _get_majority_vote(neighbors):
    """Определяет класс по голосованию соседей, разрешая связки по минимальному расстоянию."""
    vote_count = {}
    min_distance_per_label = {}

    for neighbor in neighbors:
        label = neighbor["label"]
        distance = neighbor["distance"]
        vote_count[label] = vote_count.get(label, 0) + 1
        min_distance_per_label[label] = min(distance, min_distance_per_label.get(label, float("inf")))

    best_label = None
    best_vote = -1
    best_distance = float("inf")

    for label in vote_count:
        votes = vote_count[label]
        dist = min_distance_per_label[label]
        if votes > best_vote or (votes == best_vote and dist < best_distance):
            best_label = label
            best_vote = votes
            best_distance = dist

    return best_label

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

3. Оркестратор: сборка всего вместе

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

import numpy as np

def knn_predict(training_data, labels, query_point, k):
    """Предсказывает класс для одной точки запроса."""
    # Вычисляем расстояния до всех обучающих образцов
    distances = [euclidean_distance(sample, query_point) for sample in training_data]
    # Находим индексы k ближайших соседей
    nearest_idx = np.argsort(distances)[:k]
    # Формируем список соседей с расстояниями и метками
    neighbors = [
        {"distance": distances[i], "label": labels[i]}
        for i in nearest_idx
    ]
    return _get_majority_vote(neighbors)

Ключевой момент — использование np.argsort(). Он возвращает индексы, которые отсортируют массив, позволяя получить ближайшие точки без изменения исходных данных. Это распространённый паттерн в научных вычислениях.

Практический вывод

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