K ближайших соседей и расстояния

Храните всё. Предсказывайте, глядя на соседей. Простейший алгоритм, который действительно работает.

Тип: Практика Язык: Python Предварительные требования: Фаза 1 (урок 14 «Нормы и расстояния») Время: ~90 минут

Цели обучения

• Реализовать с нуля классификацию и регрессию KNN с настраиваемым K и голосованием со взвешиванием по расстоянию
• Сравнить метрики расстояния L1, L2, косинусную и Минковского, а также выбрать подходящую для конкретного типа данных
• Объяснить проклятие размерности и показать, почему KNN ухудшается в пространствах высокой размерности
• Построить KD-дерево для эффективного поиска ближайших соседей и проанализировать, когда оно превосходит полный перебор

Проблема

У вас есть набор данных. Появляется новая точка данных. Вам нужно классифицировать её или предсказать её значение. Вместо обучения параметров по данным (как в линейной регрессии или SVM) вы просто находите K обучающих точек, ближайших к новой точке, и позволяете им проголосовать.

Это метод K ближайших соседей (K-nearest neighbors, KNN). В нём нет фазы обучения. Нет параметров для изучения. Нет функции потерь, которую нужно минимизировать. Вы храните весь обучающий набор и вычисляете расстояния во время предсказания.

Это кажется слишком простым, чтобы работать. Но KNN удивительно конкурентоспособен во многих задачах, особенно на малых и средних наборах данных; глубокое понимание метода раскрывает фундаментальные концепции: выбор метрики расстояния (связанный с уроком 14 фазы 1), проклятие размерности и различие между ленивым и активным обучением.

KNN также встречается повсюду в современном AI, только под другими названиями. Векторные базы данных выполняют KNN-поиск по эмбеддингам. Генерация с дополненным поиском (retrieval-augmented generation, RAG) находит K ближайших фрагментов документов. Рекомендательные системы находят похожих пользователей или объекты. Алгоритм остаётся тем же. Меняются масштаб и структуры данных.

Концепция

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

Даны набор размеченных точек и новая точка запроса:

1. Вычислите расстояние от запроса до каждой точки в наборе данных.
2. Отсортируйте по расстоянию.
3. Возьмите K ближайших точек.
4. Для классификации: выполните голосование большинством среди K соседей.
5. Для регрессии: возьмите среднее (или взвешенное среднее) значений K соседей.

Вот и весь алгоритм. Никакой подгонки. Никакого градиентного спуска. Никаких эпох.

Выбор K

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

K	Поведение
K = 1	Граница решения повторяет каждую точку. Нулевая ошибка на обучении. Высокая дисперсия. Переобучение
Малое K (3–5)	Чувствительно к локальной структуре. Может захватывать сложные границы
Большое K	Более гладкие границы. Устойчивее к шуму. Может недообучаться
K = N	Предсказывает класс большинства для каждой точки. Максимальное смещение

Обычная отправная точка — K = sqrt(N) для набора из N точек. Для бинарной классификации используйте нечётное K, чтобы избежать ничьих.

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

Функция расстояния определяет, что означает «близко». Разные метрики дают разных соседей и разные предсказания.

L2 (евклидово) — вариант по умолчанию. Это расстояние по прямой.

d(a, b) = sqrt(sum((a_i - b_i)^2))

Оно чувствительно к масштабу признаков. Всегда стандартизируйте признаки перед применением L2 с KNN.

L1 (манхэттенское) суммирует абсолютные разности. Оно устойчивее к выбросам, чем L2, поскольку не возводит разности в квадрат.

d(a, b) = sum(|a_i - b_i|)

Косинусное расстояние измеряет угол между векторами, игнорируя модуль. Оно необходимо для текстовых данных и эмбеддингов.

d(a, b) = 1 - (a . b) / (||a|| * ||b||)

Расстояние Минковского обобщает L1 и L2 параметром p.

d(a, b) = (sum(|a_i - b_i|^p))^(1/p)

p=1: Manhattan
p=2: Euclidean
p->inf: Chebyshev (max absolute difference)

Выбор метрики зависит от данных:

Тип данных	Лучшая метрика	Почему
Числовые признаки сходного масштаба	L2 (евклидова)	Вариант по умолчанию; подходит для пространственных данных
Числовые признаки с выбросами	L1 (манхэттенская)	Устойчива; не усиливает большие различия
Текстовые эмбеддинги	Косинусная	Модуль является шумом, направление несёт смысл
Разреженные данные высокой размерности	Косинусная или L1	L2 страдает от проклятия размерности
Смешанные типы	Пользовательское расстояние	Объединяйте метрики для каждого типа признака

Взвешенный KNN

Стандартный KNN придаёт одинаковый вес всем K соседям. Но сосед на расстоянии 0.1 должен иметь большее значение, чем сосед на расстоянии 5.0.

KNN со взвешиванием по расстоянию назначает каждому соседу вес, обратно пропорциональный расстоянию:

weight_i = 1 / (distance_i + epsilon)

For classification: weighted vote
For regression:     weighted average = sum(w_i * y_i) / sum(w_i)

epsilon предотвращает деление на ноль, когда точка запроса в точности совпадает с обучающей точкой.

Взвешенный KNN менее чувствителен к выбору K, поскольку дальние соседи в любом случае вносят очень малый вклад.

Проклятие размерности

Качество KNN ухудшается в высоких размерностях. Это не расплывчатая проблема, а математический факт.

Проблема 1: расстояния сходятся. С ростом размерности отношение максимального расстояния к минимальному приближается к 1. Все точки становятся почти одинаково «далёкими» от запроса.

In d dimensions, for random uniform points:

d=2:    max_dist / min_dist = varies widely
d=100:  max_dist / min_dist ~ 1.01
d=1000: max_dist / min_dist ~ 1.001

When all distances are nearly equal, "nearest" is meaningless.

Проблема 2: объём взрывается. Чтобы охватить K соседей в фиксированной доле данных, нужно расширить радиус поиска так, чтобы он покрывал значительно большую долю пространства признаков. «Окрестность» в высокой размерности охватывает большую часть пространства.

Проблема 3: доминируют углы. В единичном гиперкубе размерности d большая часть объёма сосредоточена около углов, а не в центре. Вписанная в куб сфера содержит исчезающе малую долю объёма по мере роста d.

Практическое следствие: KNN хорошо работает примерно до 20–50 признаков. После этого перед применением KNN нужны методы снижения размерности (PCA, UMAP, t-SNE), либо структуры поиска на основе деревьев, использующие внутреннюю меньшую размерность данных.

KD-деревья: быстрый поиск ближайших соседей

Полный перебор в KNN вычисляет расстояние от запроса до каждой обучающей точки. Это O(n * d) на один запрос. Для больших наборов данных это слишком медленно.

KD-дерево рекурсивно разбивает пространство вдоль осей признаков. На каждом уровне оно делит по одному измерению на медианном значении.

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

Среднее время запроса: O(log n) в малых размерностях. Но KD-деревья деградируют до O(n) в высоких размерностях (d > 20), поскольку обратный обход отбрасывает всё меньше ветвей.

Шаровые деревья: лучше для умеренных размерностей

Шаровые деревья разбивают данные на вложенные гиперсферы, а не на выровненные по осям прямоугольники. Каждый узел определяет шар (центр + радиус), содержащий все точки своего поддерева.

Преимущества перед KD-деревьями:

• Лучше работают в умеренных размерностях (примерно до 50)
• Обрабатывают структуры, не выровненные по осям
• Более тесные ограничивающие объёмы позволяют отсечь больше ветвей при поиске

И KD-деревья, и шаровые деревья — точные алгоритмы. Для действительно крупномасштабного поиска (миллионы точек, сотни измерений) вместо них применяют приближённые методы поиска ближайших соседей (HNSW, IVF, квантование произведений). Они рассматриваются в уроке 14 фазы 1.

Ленивое и активное обучение

KNN — ленивый обучающийся алгоритм (lazy learner): во время обучения он не выполняет работы, и вся работа происходит при предсказании. Большинство других алгоритмов (линейная регрессия, SVM, нейронные сети) — активные обучающиеся алгоритмы (eager learners): они выполняют тяжёлые вычисления во время обучения, чтобы построить компактную модель, а затем делают быстрые предсказания.

Аспект	Ленивый (KNN)	Активный (SVM, нейросеть)
Время обучения	O(1), только хранение данных	O(n * epochs)
Время предсказания	O(n * d) на запрос	O(d) или O(parameters)
Память при предсказании	Хранит весь обучающий набор	Хранит только параметры модели
Адаптация к новым данным	Мгновенно добавляет точки	Требует переобучения модели
Граница решения	Неявная, вычисляется на лету	Явная, фиксирована после обучения

Ленивое обучение идеально, когда:

• Набор данных часто меняется (можно добавлять и удалять точки без переобучения)
• Предсказания нужны для очень малого числа запросов
• Требуется нулевое время обучения
• Набор данных достаточно мал, чтобы полный перебор был быстрым

KNN для регрессии

Вместо голосования большинством KNN для регрессии усредняет целевые значения K соседей.

prediction = (1/K) * sum(y_i for i in K nearest neighbors)

Or with distance weighting:
prediction = sum(w_i * y_i) / sum(w_i)
where w_i = 1 / distance_i

KNN-регрессия даёт кусочно-постоянные предсказания (или кусочно-гладкие при взвешивании). Она не способна экстраполировать за пределы диапазона обучающих данных. Если все обучающие целевые значения лежат между 0 и 100, KNN никогда не предскажет 200.

knn-smoothness

Постройте это

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

Реализуйте расстояния L1, L2, косинусное и Минковского. Они напрямую связаны с уроком 14 фазы 1.

import math

def l2_distance(a, b):
    return math.sqrt(sum((ai - bi) ** 2 for ai, bi in zip(a, b)))

def l1_distance(a, b):
    return sum(abs(ai - bi) for ai, bi in zip(a, b))

def cosine_distance(a, b):
    dot_val = sum(ai * bi for ai, bi in zip(a, b))
    norm_a = math.sqrt(sum(ai ** 2 for ai in a))
    norm_b = math.sqrt(sum(bi ** 2 for bi in b))
    if norm_a == 0 or norm_b == 0:
        return 1.0
    return 1.0 - dot_val / (norm_a * norm_b)

def minkowski_distance(a, b, p=2):
    if p == float('inf'):
        return max(abs(ai - bi) for ai, bi in zip(a, b))
    return sum(abs(ai - bi) ** p for ai, bi in zip(a, b)) ** (1 / p)

Шаг 2: классификатор и регрессор KNN

Постройте полноценный KNN с настраиваемыми K, метрикой расстояния и необязательным взвешиванием по расстоянию.

class KNN:
    def __init__(self, k=5, distance_fn=l2_distance, weighted=False,
                 task="classification"):
        self.k = k
        self.distance_fn = distance_fn
        self.weighted = weighted
        self.task = task
        self.X_train = None
        self.y_train = None

    def fit(self, X, y):
        self.X_train = X
        self.y_train = y

    def predict(self, X):
        return [self._predict_one(x) for x in X]

Шаг 3: KD-дерево для эффективного поиска

Постройте KD-дерево с нуля, рекурсивно разбивающее данные по медиане каждого измерения.

class KDTree:
    def __init__(self, X, indices=None, depth=0):
        # Recursively partition the data
        self.axis = depth % len(X[0])
        # Split on median of the current axis
        ...

    def query(self, point, k=1):
        # Traverse to leaf, then backtrack
        ...

Полную реализацию со всеми вспомогательными методами и демонстрациями смотрите в code/knn.py.

Шаг 4: масштабирование признаков

KNN требует масштабирования признаков, поскольку расстояния чувствительны к их величинам. Признак в диапазоне от 0 до 1000 будет доминировать над признаком в диапазоне от 0 до 1.

def standardize(X):
    n = len(X)
    d = len(X[0])
    means = [sum(X[i][j] for i in range(n)) / n for j in range(d)]
    stds = [
        max(1e-10, (sum((X[i][j] - means[j]) ** 2 for i in range(n)) / n) ** 0.5)
        for j in range(d)
    ]
    return [[((X[i][j] - means[j]) / stds[j]) for j in range(d)] for i in range(n)], means, stds

Используйте это

Со scikit-learn:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline

clf = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(n_neighbors=5, metric="euclidean")),
])
clf.fit(X_train, y_train)
print(f"Accuracy: {clf.score(X_test, y_test):.4f}")

Scikit-learn автоматически использует KD-деревья или шаровые деревья, когда набор данных достаточно велик, а размерность достаточно мала. Для данных высокой размерности он переходит к полному перебору. Управлять этим можно параметром algorithm.

Для крупномасштабного поиска ближайших соседей (миллионы векторов) используйте FAISS, Annoy или векторную базу данных:

import faiss

index = faiss.IndexFlatL2(dimension)
index.add(embeddings)
distances, indices = index.search(query_vectors, k=5)

Упражнения

1. Реализуйте KNN-классификацию на двумерном наборе данных с 3 классами. Постройте границу решения для K=1, K=5, K=15 и K=N. Наблюдайте переход от переобучения к недообучению.

2. Сгенерируйте 1000 случайных точек в 2, 5, 10, 50, 100 и 500 измерениях. Для каждой размерности вычислите отношение максимального попарного расстояния к минимальному попарному расстоянию. Постройте график отношения к размерности, чтобы визуализировать проклятие размерности.

3. Сравните расстояния L1, L2 и косинусное для KNN на задаче классификации текста (используйте TF-IDF-векторы). Какая метрика даёт наилучшую точность? Почему косинусное расстояние обычно выигрывает для текста?

4. Реализуйте KD-дерево и измерьте время запроса в сравнении с полным перебором для наборов данных из 1k, 10k и 100k точек в 2D, 10D и 50D. При какой размерности KD-дерево перестаёт быть быстрее полного перебора?

5. Постройте взвешенный KNN-регрессор для y = sin(x) + noise. Сравните его с невзвешенным KNN при K=3, 10, 30. Покажите, что взвешивание даёт более гладкие предсказания, особенно при большом K.

Ключевые термины

Термин	Что он на самом деле означает
K ближайших соседей	Непараметрический алгоритм, который предсказывает, находя K ближайших обучающих точек к запросу
Ленивое обучение	Нет вычислений во время обучения. Вся работа происходит во время предсказания. KNN — канонический пример
Активное обучение	Тяжёлые вычисления во время обучения для построения компактной модели. Большинство алгоритмов ML активны
Проклятие размерности	В высокой размерности расстояния сходятся, а окрестности расширяются, охватывая большую часть пространства, из-за чего KNN становится неэффективным
KD-дерево	Бинарное дерево, рекурсивно разбивающее пространство вдоль осей признаков. Запросы O(log n) в малых размерностях
Шаровое дерево	Дерево вложенных гиперсфер. Лучше KD-деревьев в умеренных размерностях (примерно до 50)
Взвешенный KNN	Соседи взвешиваются обратно пропорционально расстоянию. Близкие соседи сильнее влияют на предсказание
Масштабирование признаков	Нормализация признаков до сопоставимых диапазонов. Необходима для методов на основе расстояний, таких как KNN
Голосование большинством	Классификация подсчётом наиболее частого класса среди K соседей
Поиск полным перебором	Вычисление расстояния до каждой обучающей точки. O(n*d) на запрос. Точный, но медленный при большом n
Приближённый поиск ближайших соседей	Алгоритмы (HNSW, LSH, IVF), находящие приблизительно ближайшие точки намного быстрее точного поиска
Диаграмма Вороного	Разбиение пространства, в котором каждая область содержит все точки, более близкие к одной обучающей точке, чем к любой другой. K=1 KNN создаёт границы Вороного

Дополнительное чтение

• Cover & Hart: Nearest Neighbor Pattern Classification (1967) — основополагающая статья о KNN, доказывающая, что его частота ошибок не более чем вдвое превышает байесовский оптимум
• Friedman, Bentley, Finkel: An Algorithm for Finding Best Matches in Logarithmic Expected Time (1977) — оригинальная статья о KD-деревьях
• Beyer et al.: When Is “Nearest Neighbor” Meaningful? (1999) — формальный анализ проклятия размерности для ближайших соседей
• Документация scikit-learn о ближайших соседях — практическое руководство по выбору алгоритма
• FAISS: A Library for Efficient Similarity Search — библиотека Meta для приближённого поиска ближайших соседей миллиардного масштаба

---

Источник: K-Nearest Neighbors and Distances 02.05 — Метод опорных векторов · Фаза 2 — Основы машинного обучения · Полный каталог · 02.07 — Обучение без учителя