Метод k ближайших соседей (kNN): как работает алгоритм

Метод k ближайших соседей (k-nearest neighbors, kNN) - один из самых простых и при этом рабочих алгоритмов классификации в машинном обучении: чтобы определить класс нового объекта, он просто смотрит, какие объекты из уже размеченной выборки находятся к нему ближе всего, и присваивает класс большинства среди них. Никакого обучения модели в привычном смысле не происходит - вся обучающая выборка хранится целиком, а вся работа делается в момент предсказания. Именно поэтому kNN называют «ленивым» алгоритмом (lazy learning): он не строит явную разделяющую формулу, а голосует по соседям каждый раз заново. Ниже разберём, как считается расстояние между объектами, почему число соседей k критично для качества и как всё это выглядит на конкретных числах - а прочувствовать голосование соседей можно сразу в калькуляторе ниже: подвигайте новую точку и число k и посмотрите, как меняется предсказанный класс.

Идея метода: классификация голосованием соседей

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

1. Посчитать расстояние от новой точки до каждой точки обучающей выборки.
2. Отобрать k точек с наименьшим расстоянием - это и есть «k ближайших соседей».
3. Присвоить новой точке класс, который среди этих k соседей встречается чаще всего (голосование большинством).

Ключевое предположение метода - гипотеза компактности: объекты одного класса в пространстве признаков обычно располагаются рядом друг с другом, а не вперемешку с чужим классом. Если это предположение хотя бы приблизительно верно, ближайшие соседи действительно подскажут правильный класс.

Как измеряется расстояние между объектами

Признаки объекта - это координаты точки в многомерном пространстве, поэтому расстояние между объектами считается как обычное расстояние между точками. Чаще всего используют евклидово расстояние - прямую «по линейке» между двумя точками с координатами $(x_1, x_2)$ и $(y_1, y_2)$:

$d_{евкл}(x, y) = \sqrt{(x_1 - y_1)^2 + (x_2 - y_2)^2}.$

Формула легко обобщается на любое число признаков - под корнем просто добавляются такие же слагаемые для каждого следующего измерения. Второй по популярности вариант - манхэттенское расстояние (расстояние городских кварталов): вместо диагонали считается сумма расстояний по каждой оси отдельно:

$d_{манх}(x, y) = |x_1 - y_1| + |x_2 - y_2|.$

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

Рассчитать для своей задачи

Как выбрать число соседей k

Число k - единственный настраиваемый параметр метода, и от него сильно зависит результат. Возьмём пример: обучающая выборка из 14 точек на плоскости, семь помечены классом A (в основном сгруппированы в углу (1-3; 1-3)) и семь - классом B (сгруппированы в углу (7-9; 6-9)), но одна точка класса A - «выброс» с координатами (6; 6) - лежит прямо рядом с облаком класса B. Новая точка стоит в (6; 5).

Рассчитать для своей задачи

При k = 1 в игру вступает только ближайшая точка - это как раз «чужой» выброс класса A на расстоянии 1,0, и алгоритм ошибочно предсказывает класс A. Уже при k = 3 в тройку ближайших добавляются две точки класса B (расстояния 2,236 и 2,236), голосование даёт 1 против 2, и предсказание переключается на правильный класс B. При дальнейшем росте k - 5, 7, 9, 11 - предсказание остаётся классом B, хотя перевес голосов постепенно сокращается: при k = 13 счёт становится 6 против 7 - совсем близко к ничьей. Это иллюстрирует главный компромисс выбора k: слишком маленький k делает алгоритм чувствительным к шуму и выбросам (одна случайная точка решает исход), а слишком большой k начинает захватывать точки из чужих, далёких областей и «размывает» границу между классами.

Голосование большинством и правило нечётного k

Когда классов всего два, голосование большинством может закончиться ничьей, если голоса разделились поровну - например, при k = 4 и счёте 2 на 2 непонятно, какой класс присвоить. Поэтому для бинарной классификации k принято брать нечётным: тогда при чётном числе классов ничья математически невозможна. Если классов больше двух, нечётность k ничьей не гарантирует, и тогда используют дополнительные правила - например, при равенстве голосов присваивают класс ближайшего из спорных соседей.

Ещё один рабочий приём - взвешенное голосование: голос каждого соседа учитывается не как единица, а с весом, обратно пропорциональным расстоянию (обычно $w_i = 1 / d_i^2$). Так более близкий сосед «весит» в голосовании больше, чем дальний, и метод меньше страдает от соседей на границе окна из k точек.

Пример решения задачи

Возьмём ту же выборку и новую точку (6; 5), метрика - евклидова, k = 3. Считаем расстояния до каждой точки обучающей выборки по формуле $d = \sqrt{(x_1-y_1)^2+(x_2-y_2)^2}$ и сортируем по возрастанию - вот первые пять:

$$\begin{aligned} d\big((6,5),(6,6)\big) &= \sqrt{0^2+1^2} = 1{,}000 \quad \text{класс A} \\ d\big((6,5),(8,6)\big) &= \sqrt{2^2+1^2} = 2{,}236 \quad \text{класс B} \\ d\big((6,5),(7,7)\big) &= \sqrt{1^2+2^2} = 2{,}236 \quad \text{класс B} \\ d\big((6,5),(9,6)\big) &= \sqrt{3^2+1^2} = 3{,}162 \quad \text{класс B} \\ d\big((6,5),(8,8)\big) &= \sqrt{2^2+3^2} = 3{,}606 \quad \text{класс B} \end{aligned}$$

При k = 3 берём первые три строки: (6;6) класс A, (8;6) класс B, (7;7) класс B. Голосов за A - один, за B - два, значит новая точка получает класс B. Обратите внимание: если бы мы взяли k = 1, ответом был бы класс A - из-за случайного соседа-выброса. Это ровно тот случай, который стоит проверять калькулятором выше: подставьте свои координаты и k и посмотрите список соседей с их расстояниями.

Плюсы, минусы и применение kNN

У метода почти нет параметров, которые нужно подбирать заранее (кроме k и метрики), он одинаково хорошо работает с многоклассовой классификацией и легко переносится на задачу регрессии - тогда вместо голосования берётся среднее значение признака среди k соседей. Из минусов: на каждое предсказание нужно пересчитать расстояние до всех точек обучающей выборки, поэтому метод медленный на больших датасетах (ускоряют его структурами данных вроде KD-дерева или Ball-дерева); он также чувствителен к масштабу признаков - если один признак измеряется в тысячах, а другой в долях единицы, расстояние будет определяться почти исключительно первым. На практике kNN используют как базовую модель для сравнения, в рекомендательных системах («похожие товары»/«похожие пользователи»), для распознавания рукописного текста и в задачах, где важна интерпретируемость решения через конкретные похожие примеры.

Частые ошибки

• Признаки разного масштаба без нормализации. Если один признак принимает значения 0-1, а другой - 0-10000, расстояние фактически определяется вторым признаком. Перед расчётом расстояний признаки нужно привести к одному масштабу (нормализация или стандартизация).
• Чётное k при бинарной классификации. При k = 4, 6, 8... возможна ничья голосов. Для двух классов берите нечётное k.
• Слишком маленький k. k = 1 делает предсказание чувствительным к единичному шумовому объекту или выбросу - ровно как в примере выше с точкой (6; 6).
• Слишком большой k. При k, близком к размеру всей выборки, алгоритм фактически всегда предсказывает самый многочисленный класс, теряя чувствительность к локальной структуре данных.
• Путаница метрики расстояния. Евклидово и манхэттенское расстояния дают разные ранжирования соседей на одних и тех же данных - метрику нужно выбирать осознанно, а не по умолчанию.

FAQ

Нужно ли обучать модель kNN заранее, как в других алгоритмах машинного обучения? Нет. kNN относится к «ленивым» алгоритмам: он просто хранит всю обучающую выборку и делает все вычисления в момент предсказания, а не заранее.

Как выбрать оптимальное значение k? Чаще всего перебирают несколько значений k (обычно нечётных, от 1 до корня из числа объектов выборки) и выбирают то, при котором доля верных предсказаний на отложенной выборке максимальна - это называется кросс-валидацией.

Можно ли использовать kNN не только для классификации, но и для регрессии? Да. В задаче регрессии вместо голосования классов берут среднее (или взвешенное среднее) значение целевой переменной среди k ближайших соседей.

Коротко

Метод k ближайших соседей классифицирует новый объект по большинству голосов среди k ближайших к нему точек обучающей выборки, где расстояние обычно считается евклидовой формулой $d = \sqrt{(x_1-y_1)^2+(x_2-y_2)^2}$. Малое k делает алгоритм чувствительным к шуму и выбросам, большое - размывает границу между классами, поэтому k подбирают, а для бинарной классификации берут нечётным, чтобы исключить ничьи. Перед расчётом расстояний признаки нужно нормализовать, иначе один признак с широким диапазоном значений подавит остальные.