k-ближайших соседей
Самый честный алгоритм машинного обучения: ничему не учится, просто запоминает
01 Интуиция
Представь, что тебе показали человека и попросили угадать: спортсмен он или программист? Подсказка: ты можешь посмотреть на пятерых его ближайших друзей. Что ты сделаешь? Конечно — посмотришь, кого среди друзей больше, и ответишь так же.
Это и есть весь алгоритм k-ближайших соседей, целиком, в одном предложении. Старая поговорка «скажи мне, кто твои друзья, и я скажу, кто ты» — буквально математическая формулировка метода.
Главное отличие от того, что было раньше
В линейной и логистической регрессии мы
обучали модель: подбирали коэффициенты, минимизировали ошибку, а потом исходные данные можно было выбросить. Здесь всё наоборот.
Никакого обучения нет. Мы просто запоминаем всю размеченную выборку целиком, и когда приходит новая точка — смотрим на её соседей. Такой подход называют
ленивым обучением (lazy learning).
Звучит примитивно — и это правда так. Но именно эта примитивность даёт k-NN суперспособность, которой нет у логистической регрессии: он умеет работать с данными, которые невозможно разделить прямой линией. К этому мы вернёмся в восьмом разделе.
02 Алгоритм по шагам
Допустим, у нас есть размеченная выборка — несколько сотен точек, каждая с известным классом. Приходит новая точка, и мы хотим определить её класс. Вот что делает k-NN:
Выбираем число k. Это количество соседей, на которых будем смотреть. Для бинарной классификации берут нечётное k — иначе возможна ничья (3 vs 3, и куда тогда?). Как выбирать k правильно — отдельная большая тема, см. раздел 4.
Считаем расстояния. От новой точки — до каждой точки обучающей выборки. Если в выборке тысяча точек, делаем тысячу вычислений. Это значит, что вся работа происходит в момент предсказания, а не заранее.
Сортируем и берём k ближайших. Это и есть «соседи» новой точки.
Голосуем. Среди k соседей считаем, точек какого класса больше. Победивший класс — и есть наш ответ. Если задача регрессионная (предсказываем число, а не класс) — берём среднее значений соседей.
Маленький пример вручную
Восемь точек на плоскости: пять красных, три синих. Появляется новая, чёрная.
- При
k = 3 ближайшие соседи: 2 красных, 1 синий → ответ красный.
- При
k = 5 ближайшие соседи: 2 красных, 3 синих → ответ синий.
Уже на этом примере видно главное: ответ зависит от выбора k. Для одной и той же точки можно получить разные классы — если по-разному настроить алгоритм. Это не ошибка, это особенность.
03 Как считать расстояние
Мы всё время говорим «расстояние», но в математике расстояние можно мерить по-разному. Два самых популярных способа в k-NN:
Евклидово расстояние
То самое, школьное, по теореме Пифагора. Расстояние «по прямой» — как если бы мы летели на дроне.
d(A, B) = √((x₁ − x₂)² + (y₁ − y₂)²)
По умолчанию k-NN использует именно его. Это естественный выбор для большинства задач.
Манхэттенское расстояние
Сумма модулей разностей по координатам. Название — из-за нью-йоркского Манхэттена с его сеткой улиц: ты не можешь пройти сквозь дом по диагонали, ты идёшь по кварталам. Сначала вдоль, потом поперёк.
d(A, B) = |x₁ − x₂| + |y₁ − y₂|
Зачем это знать
Множество точек на одинаковом расстоянии от центра — это «единичный круг» данной метрики. Для евклида это настоящий круг. Для манхэттена — ромб (квадрат, поставленный на угол). Поэтому граница решений k-NN с разными метриками выглядит по-разному: в одном случае она округлая, в другом — угловатая, со ступеньками. В песочнице это видно сразу: переключи метрику на любом датасете — граница изменит характер.
На практике почти всегда берут евклид. Манхэттен полезен, когда признаки независимы и движение «по диагонали» в задаче не имеет смысла — например, в навигации по городу.
04 Параметр k — сердце алгоритма
Это самая важная часть всего, что нужно знать про k-NN. Параметр k определяет, насколько «гибкой» или «сглаженной» будет модель — и от него зависит вообще всё.
Что происходит при k = 1
Каждая новая точка получает класс своего единственного ближайшего соседа. Граница решений становится очень изломанной — она в точности обводит каждую точку выборки.
Здесь важный фокус: задай себе вопрос — какая будет точность модели на самих обучающих данных при k = 1?
Подумай прежде чем читать дальше
Ответ:
ровно 100%. Потому что ближайший сосед каждой обучающей точки — это
она сама, расстояние ноль, класс совпадает идеально. Звучит как чудо, но это
флаг переобучения: модель выучила выборку наизусть, включая весь шум.
Загрузи в песочнице «шумный» датасет и поставь k = 1 — увидишь крошечные островки одного класса посреди другого. Это и есть запомненный шум, выданный за закономерность.
Что происходит при большом k
Граница сглаживается, отдельные выбросы перестают влиять. Это хорошо, когда в данных шум. Плохо, когда в данных есть мелкие, но настоящие структуры — большие k их «съедают».
Крайний случай: k = N
Если взять k равным количеству всех точек в выборке, мы при любом запросе будем смотреть на всю выборку целиком. И ответ всегда будет один и тот же — самый частый класс. Алгоритм перестаёт быть алгоритмом и превращается в «угадай большинство». Бесполезно.
Главный график
Если построить график зависимости ошибки от k, получится характерная картина с двумя кривыми — для обучающих данных и для тестовых:
- Ошибка на обучении при k = 1 равна нулю и потом монотонно растёт.
- Ошибка на тесте сначала падает (модель перестаёт переобучаться), достигает минимума, а затем снова растёт (модель начинает недообучаться).
Между этими режимами есть оптимум — то самое «лучшее k» для конкретной задачи. Эта U-образная зависимость — фундаментальный паттерн всего машинного обучения. Ты будешь видеть её снова и снова, в самых разных алгоритмах. Запомни форму.
Как выбирают k на практике
Правильный способ — кросс-валидация: разбиваем данные на части, для каждого k тренируем на одних, проверяем на других, усредняем ошибку, выбираем k с минимальной. Грубое правило большого пальца: k ≈ √N, где N — размер выборки. Но это лишь отправная точка для перебора.
05 Масштабирование признаков
Это пункт, без которого k-NN не работает на реальных данных. Разберём на конкретном примере.
Допустим, мы классифицируем людей на «детей» и «взрослых» по двум признакам: рост в сантиметрах (от 100 до 200) и возраст в годах (от 1 до 80). Берём двух людей: один отличается от другого на 50 см роста, второй — на 50 лет возраста.
Для k-NN это будут одинаковые расстояния. А для здравого смысла — нет: 50 лет это огромная разница, 50 см — умеренная.
Где собака зарыта
Признак с большим численным диапазоном будет
доминировать в расчёте расстояния. Если бы мы вдруг записали рост в миллиметрах (1000–2000), он бы вообще полностью «съел» вклад возраста. Алгоритм не понимает единиц измерения — он видит только числа.
Как лечить
Перед применением k-NN признаки приводят к одному масштабу. Два стандартных способа:
- Стандартизация (z-score): из каждого значения вычитаем среднее, делим на стандартное отклонение. После этого у каждого признака среднее = 0 и разброс = 1.
- Min-max нормализация: приводим все значения в диапазон [0, 1] линейным преобразованием.
В Python это StandardScaler и MinMaxScaler из sklearn.preprocessing. Применять их обязательно.
Запомни как мантру
Если ты применишь k-NN к сырым, неотмасштабированным данным — он, скорее всего, будет работать плохо, и ты не поймёшь почему. Это
самая частая ошибка новичков в этом алгоритме. Сэкономь себе часы отладки в будущем: масштабируй
всегда.
06 Плюсы и минусы
+ Сильные стороны
- Простота. Алгоритм объясняется за минуту, понятен любому.
- Не требует обучения. Добавил новую точку — и модель «обновлена», без переподготовки.
- Многоклассовость из коробки. Голосование работает для любого числа классов одинаково.
- Произвольно сложная граница. Может разделять данные, через которые никакой прямой не провести.
− Слабые стороны
- Медленный на предсказании. Каждый запрос — полный обход выборки.
- Память. Хранить нужно всю обучающую выборку всегда.
- Проклятие размерности. Когда признаков много, все точки оказываются примерно одинаково далеко друг от друга, и понятие «ближайший» теряет смысл.
- Чувствителен к шуму при малых k и к масштабу признаков.
07 Где применяют
Чтобы алгоритм не казался учебной игрушкой — несколько реальных областей.
рекомендации «Пользователи, похожие на тебя, смотрели вот это». Здесь «расстояние» — мера непохожести вкусов. Один из самых ранних подходов к рекомендательным системам.
распознавание Классическая задача MNIST — распознавание рукописных цифр. Простой k-NN на голых пикселях даёт около 97% точности. Это удивительно много для такого примитивного метода — пример того, что простые алгоритмы порой работают на удивление хорошо.
данные Заполнение пропусков: если в таблице где-то пусто, посмотри на k похожих строк и возьми среднее значение в этой колонке.
аномалии Если у точки расстояние до ближайших соседей подозрительно большое — она, вероятно, аномалия (мошенническая транзакция, поломка датчика).
08 Сравнение с логистической регрессией
Логичный вопрос: если у нас уже есть логистическая регрессия для классификации, зачем нам ещё и k-NN? Ответ: эти два алгоритма решают одну задачу, но по-разному устроены изнутри, и поэтому выигрывают в разных ситуациях.
| Свойство |
Логистическая регрессия |
k-NN |
| Форма границы |
Прямая / плоскость |
Любая, как угодно изогнутая |
| Нелинейные данные |
Не справляется |
Справляется |
| Скорость предсказания |
Очень быстро |
Медленно (зависит от N) |
| Память |
Несколько коэффициентов |
Вся выборка |
| Интерпретируемость |
Высокая |
Низкая |
| Высокая размерность |
Работает нормально |
Ломается |
| Шум в данных |
Устойчива |
Чувствителен (при малом k) |
Метафора, которая всё объясняет
Логистическая регрессия — это судья, который выучил один общий закон и применяет его ко всем делам одинаково. Быстро, предсказуемо, объяснимо. Но если дело необычное — закон не подходит, и судья промахивается.
k-NN — это судья, который не знает законов, зато помнит все предыдущие дела. Перед каждым новым делом он листает архив и ищет похожие. Медленно, не объяснимо общим правилом, зато способен разобраться даже там, где общего закона нет.
Что проверить в песочнице
Включи режим «+ ЛогРег» и переключайся между датасетами. На
линейном обе модели работают почти идеально. На
лунах логистическая регрессия начинает заметно уступать. На
кольцах её точность падает примерно до 50% — это значит, что она угадывает не лучше монетки. А k-NN там же показывает почти 100%. Это и есть наглядный ответ на вопрос «зачем нам k-NN, если есть логрег».
В реальной работе data scientist'а почти всегда пробуют оба алгоритма (и ещё несколько других) на одних и тех же данных и смотрят, что лучше. Это базовый ритуал — сравнение с простыми моделями. Часто простая логистическая регрессия неожиданно выигрывает у сложных методов — и тогда её и берут в работу. А иногда наоборот: данные настолько кривые, что без нелинейного метода никуда.