🔴 Сложный ⏱️ 50 минут

k-Nearest Neighbors

📋 Содержание урока

k-Nearest Neighbors

Открой любой курс по рекомендательным системам, и через несколько минут наткнёшься на одну и ту же фразу: «найди пользователей, похожих на текущего, и посмотри, что понравилось им». Или другой вариант: «найди товары, похожие на тот, что человек только что просмотрел». За этой формулировкой стоит один из самых старых и при этом до сих пор рабочих методов машинного обучения — метод k ближайших соседей (k-Nearest Neighbors, kNN). Идея настолько прямолинейна, что кажется почти нечестной по сравнению с линейной и логистической регрессией из последних двух уроков: никакого градиентного спуска, никакой функции потерь, никаких весов, которые нужно подбирать итеративно. Просто запомни все обучающие примеры, а когда придёт новый объект — посмотри, кто из уже известных объектов находится ближе всего к нему, и ориентируйся на них.

Это принципиально другой взгляд на «обучение». В линейной регрессии (урок 310), полиномиальной регрессии (урок 311), Ridge и Lasso (урок 312) и логистической регрессии (урок 313) модель в процессе обучения строит явную математическую функцию — вектор весов $w$, который затем применяется к любому новому объекту без обращения к исходным обучающим данным. После обучения датасет можно выбросить: вся «выжимка» знаний уже упакована в коэффициенты. kNN устроен ровно наоборот: он не извлекает из данных никакой сжатой функции, а хранит их целиком и обращается к ним заново при каждом новом предсказании. Это различие — не техническая деталь, а фундаментально другая философия обучения, и в этом уроке ты разберёшь, что она означает на практике: как считаются расстояния между объектами, как выбрать число соседей $k$, почему перед использованием kNN почти всегда обязательно масштабировать признаки и что происходит с методом, когда признаков становится очень много.

kNN — один из тех алгоритмов, с которых начинается практическая работа в Data Science, потому что sklearn.neighbors.KNeighborsClassifier и KNeighborsRegressor требуют буквально нескольких строк кода и не имеют собственной сложной математики обучения, из-за чего метод часто становится первым baseline-решением, с которым сравнивают более сложные модели. Но у этой простоты есть цена — и в первую очередь она проявляется именно в рекомендательных системах, где kNN исторически был одним из первых промышленных подходов: чтобы порекомендовать пользователю фильм, алгоритм коллаборативной фильтрации ищет k пользователей с максимально похожими историями оценок (или k товаров с похожими профилями оценок) и агрегирует их поведение. Тот же самый принцип — «посмотри на ближайших соседей» — работает и в детекции мошенничества, и в системах поиска похожих изображений, и в геномике при классификации образцов ткани.

История

Метод ближайших соседей появился заметно раньше, чем оформилось само понятие «машинное обучение» как отдельной дисциплины. В 1951 году американские статистики Эвелин Фикс (Evelyn Fix) и Джозеф Ходжес (Joseph Hodges) подготовили технический отчёт для школы авиационной медицины ВВС США (USAF School of Aviation Medicine), в котором формально описали непараметрический метод дискриминантного анализа — предсказание класса нового объекта через голосование по k ближайшим к нему объектам из обучающей выборки. Отчёт долгое время оставался внутренним военным документом с ограниченным распространением и стал широко известен статистическому сообществу лишь спустя годы, хотя сегодня Фикс и Ходжес по праву считаются авторами идеи, которая легла в основу всего семейства методов ближайших соседей.

Настоящий теоретический прорыв случился в 1967 году, когда Томас Ковер (Thomas Cover) и Питер Харт (Peter Hart) опубликовали статью «Nearest neighbor pattern classification» («Классификация образов методом ближайшего соседа»), доказав удивительный результат: при бесконечно большом объёме обучающих данных ошибка классификатора методом одного ближайшего соседа (1-NN) асимптотически не превышает удвоенной ошибки идеального байесовского классификатора — теоретического предела, лучше которого в принципе невозможно классифицировать объекты при данном распределении признаков. Иными словами, даже предельно простое правило «посмотри на ближайшего соседа» гарантированно не хуже чем в два раза уступает лучшему возможному классификатору — редкая по силе теоретическая гарантия для настолько наивного на первый взгляд алгоритма.

С тех пор kNN не потерял актуальности: он стал стандартным baseline-инструментом в статистике распознавания образов задолго до нейросетевого бума, лёг в основу первых промышленных рекомендательных систем на рубеже 1990-2000-х годов (в том числе коллаборативной фильтрации на Amazon и ранних версиях Netflix) и продолжает использоваться сегодня — уже не столько как финальная промышленная модель, сколько как быстрый интерпретируемый baseline и как строительный блок более сложных систем поиска похожих объектов, векторных баз данных и рекомендательных движков.

Ленивое обучение и принцип метода

Интуиция

Представь два способа подготовки к экзамену по вождению. Первый — выучить общие правила: как тормозить на скользкой дороге, как парковаться параллельно, как проезжать перекрёсток. Эти правила — компактная «модель», которую можно применить к любой новой ситуации, даже никогда не встречавшейся раньше. Второй способ — просто запомнить наизусть тысячи конкретных ситуаций с правильными действиями и на экзамене искать среди них максимально похожую на текущую, а затем действовать так же, как в этой похожей ситуации. Линейная и логистическая регрессия действуют по первому сценарию — они извлекают общее правило. kNN действует строго по второму: он не формулирует никакого общего правила, а хранит все примеры и ищет похожие на лету.

Определение

k ближайших соседей (k-Nearest Neighbors, kNN) — это непараметрический метод обучения с учителем, в котором предсказание для нового объекта строится не заранее обученной функцией, а непосредственно в момент запроса: алгоритм находит k объектов обучающей выборки, ближайших к запрашиваемой точке в пространстве признаков (по выбранной метрике расстояния), и возвращает результат голосования большинства классов среди них (для классификации) или среднее значение их целевой переменной (для регрессии). Такой подход называют ленивым обучением (lazy learning) — в противоположность активному обучению (eager learning), к которому относятся линейная и логистическая регрессия: у ленивых методов практически нет вычислений на этапе fit() (данные просто сохраняются), зато весь вычислительный труд переносится на этап predict().

Пример 1: полный расчёт классификации новой точки

Интернет-магазин хочет предсказать, купит ли пользователь товар, по двум признакам: $x_1$ — количество посещений сайта за неделю, $x_2$ — среднее время на сайте в минутах за визит. Обучающая выборка:

A: (2, 5)   → не купил (0)
B: (3, 7)   → не купил (0)
C: (8, 20)  → купил (1)
D: (9, 25)  → купил (1)
E: (7, 18)  → купил (1)
F: (1, 3)   → не купил (0)

Новый пользователь: $(6, 17)$. Берём $k=3$ и евклидово расстояние $d(x,y)=\sqrt{\sum_i (x_i-y_i)^2}$:

до A: sqrt(4² + 12²) = sqrt(160)  ≈ 12.65
до B: sqrt(3² + 10²) = sqrt(109)  ≈ 10.44
до C: sqrt(2² + 3²)  = sqrt(13)   ≈ 3.61
до D: sqrt(3² + 8²)  = sqrt(73)   ≈ 8.54
до E: sqrt(1² + 1²)  = sqrt(2)    ≈ 1.41
до F: sqrt(5² + 14²) = sqrt(221)  ≈ 14.87

Три ближайших соседа — E (1.41), C (3.61) и D (8.54), и все трое помечены как «купил». Голосование единогласное: 3 против 0, предсказание — пользователь купит товар. Обрати внимание: никакой модели, никаких весов — только прямой перебор расстояний в момент запроса, ровно то, что делает kNN ленивым методом.

Пример 2: kNN как регрессия — усреднение вместо голосования

Тот же принцип работает и для непрерывной целевой переменной. Пусть известна зависимость цены квартиры (млн руб.) от площади (м²):

(40, 5)  (45, 5.5)  (50, 6)  (70, 9)  (75, 9.5)

Нужно оценить цену квартиры площадью 48 м² при $k=3$. Поскольку признак один, расстояние — это просто модуль разности площадей: $|48-40|=8$, $|48-45|=3$, $|48-50|=2$, $|48-70|=22$, $|48-75|=27$. Три ближайших соседа по площади — 50 м² (цена 6), 45 м² (цена 5.5) и 40 м² (цена 5). Вместо голосования kNN-регрессия берёт среднее значений: $(6+5.5+5)/3 = 5.5$. Предсказанная цена — 5.5 млн рублей. Формула для регрессии: $\hat{y} = \frac{1}{k}\sum_{i \in N_k(x)} y_i$, где $N_k(x)$ — множество индексов k ближайших соседей.

Пример 3: kNN в рекомендательных системах

sklearn.neighbors.NearestNeighbors и KNeighborsClassifier часто применяются как быстрый baseline и как ядро коллаборативной фильтрации: для пользователя строится вектор его оценок фильмов или товаров, находятся k пользователей с максимально похожими векторами, а рекомендация формируется на основе того, что понравилось этим соседям, но ещё не видел текущий пользователь. Точно так же item-based подход ищет k товаров, ближайших к уже просмотренному, — именно на этом принципе работают блоки «похожие товары» и «с этим товаром покупают» во многих интернет-магазинах. Ключевое отличие от примеров 1 и 2 в том, что здесь «ближайшие» вычисляются не столько по прямому евклидову расстоянию, сколько по специализированным метрикам сходства профилей — об этом пойдёт речь в следующем разделе.

Почему это важно

Ленивое обучение — это осознанный компромисс, а не недостаток метода. У kNN практически нулевое время обучения (fit() — это в буквальном смысле сохранение данных в памяти), что удобно для быстрых прототипов и baseline-сравнений. Но вся цена откладывается на момент предсказания: чтобы classифицировать один новый объект, наивная реализация должна вычислить расстояние до каждого из $n$ объектов обучающей выборки — то есть застройка модели «бесплатна», а каждый запрос стоит $O(n)$. Для регрессии и линейных моделей всё наоборот — дорогое обучение, почти мгновенное предсказание. Выбор между «дорого один раз при обучении» и «дорого при каждом запросе» — это архитектурное решение, которое приходится делать осознанно при проектировании реальной ML-системы.

Выбор метрики расстояния

Интуиция

Всё, что делает kNN, зависит от одного ключевого вопроса: что значит «близко»? По умолчанию используется евклидово расстояние — «по прямой», как летит ворона. Но это далеко не единственный разумный вариант, и выбор метрики — не формальность, а решение, которое может напрямую изменить итоговое предсказание.

Формула

Евклидово расстояние: $d_{\text{eucl}}(x,y) = \sqrt{\sum_i (x_i-y_i)^2}$. Манхэттенское (городское, taxicab) расстояние: $d_{\text{man}}(x,y) = \sum_i |x_i-y_i|$ — сумма расстояний вдоль каждой оси по отдельности, как если бы приходилось двигаться по прямоугольной сетке улиц. Обе метрики — частные случаи расстояния Минковского: $d_p(x,y) = \left(\sum_i |x_i-y_i|^p\right)^{1/p}$, где $p=2$ даёт евклидово расстояние, $p=1$ — манхэттенское, а $p\to\infty$ — расстояние Чебышёва $\max_i |x_i-y_i|$. Для текстов, эмбеддингов и рекомендательных систем часто используют косинусное расстояние $1 - \frac{x \cdot y}{\|x\|\|y\|}$, которое измеряет не разницу в величине векторов, а разницу в их направлении.

Пример 1: «по прямой» против «по улицам города»

Точки $(0,0)$ и $(3,4)$. Евклидово расстояние: $\sqrt{3^2+4^2}=\sqrt{25}=5$. Манхэттенское расстояние: $|3|+|4|=7$. Разница наглядна: пешеход в реальном городе с прямоугольной сеткой улиц не может пройти «по диагонали» через квартал — ему придётся идти 7 условных единиц, хотя расстояние по прямой всего 5.

Пример 2: выбор метрики может изменить, кто ближайший сосед

Точка запроса $Q=(0,0)$, два кандидата $P_1=(4,4)$ и $P_2=(0,7)$. Евклидово расстояние: $d(Q,P_1)=\sqrt{32}\approx5.66$, $d(Q,P_2)=7$ — по евклидовой метрике ближе $P_1$. Манхэттенское расстояние: $d(Q,P_1)=4+4=8$, $d(Q,P_2)=0+7=7$ — а по манхэттенской метрике ближе уже $P_2$! Ранжирование соседей буквально переворачивается в зависимости от выбранной метрики, а значит, при $k=1$ два разумных способа считать расстояние дадут два разных предсказания на одних и тех же данных.

Пример 3: косинусное сходство против евклидова расстояния в рекомендациях

Пусть три пользователя оценили фильмы по трём жанрам (в баллах от 0 до 5): $A=(5,0,5)$, $D=(1,0,1)$, $C=(0,5,0)$. Пользователь $D$ ставит оценки заметно скромнее (может, он просто строгий рецензент), но пропорции те же, что у $A$. Косинусное сходство $A$ и $D$: $\cos = \frac{5\cdot1+0\cdot0+5\cdot1}{\sqrt{50}\cdot\sqrt{2}} = \frac{10}{10} = 1{,}0$ — направления векторов полностью совпадают, вкус идентичен. А вот евклидово расстояние между ними: $\sqrt{(5-1)^2+0+(5-1)^2}=\sqrt{32}\approx5{,}66$ — довольно далеко! Евклидова метрика ошибочно «наказывает» $D$ просто за более скромную шкалу оценок, тогда как косинусное сходство корректно распознаёт совпадающий вкус. Для контраста: $A$ и $C=(0,5,0)$ дают $\cos=0$ — векторы ортогональны, вкусы никак не пересекаются. Именно поэтому в рекомендательных системах и при работе с текстовыми эмбеддингами почти всегда предпочитают косинусную метрику, а не евклидову.

Почему это важно

Метрика расстояния кодирует неявное предположение о геометрии пространства признаков, и это предположение либо соответствует задаче, либо нет. Евклидово расстояние подразумевает изотропное непрерывное пространство без каких-либо особых направлений; манхэттенское лучше подходит, когда движение по отдельным координатам действительно независимо и не может «срезать по диагонали»; косинусное — когда важна не абсолютная величина вектора признаков, а его направление (доли, пропорции, профили интересов). В sklearn.neighbors.KNeighborsClassifier параметр metric явно управляет этим выбором ('euclidean', 'manhattan', 'chebyshev', 'cosine', 'minkowski' с параметром p), и от него зависит, какие объекты алгоритм вообще сочтёт похожими.

Выбор числа соседей k и связь с переобучением

Интуиция

Число соседей $k$ — это единственный по-настоящему важный гиперпараметр kNN, и он напрямую воспроизводит компромисс bias-variance из урока 304 о переобучении и недообучении. При $k=1$ прогноз для новой точки целиком определяется одним-единственным ближайшим объектом — если этот объект оказался шумом или ошибкой разметки, ошибка беспрепятственно попадёт в предсказание. При очень большом $k$, наоборот, голос каждого отдельного соседа размывается среди множества других, и модель начинает сглаживать любые локальные закономерности, скатываясь к предсказанию «в среднем по больнице».

Формула

Формальной формулы для «правильного» $k$ не существует — общее эмпирическое правило $k \approx \sqrt{n}$ (где $n$ — размер обучающей выборки) даёт лишь отправную точку, а не готовый ответ. Как и для других гиперпараметров (урок 304), оптимальное значение $k$ подбирается через кросс-валидацию (урок 306): перебираются несколько кандидатов, для каждого измеряется ошибка на валидационных фолдах, и выбирается значение с наименьшей ошибкой. Для бинарной классификации $k$ обычно берут нечётным, чтобы избежать точных ничьих при голосовании.

Пример 1: как один шумный пример меняет предсказание при малом k

Возьмём датасет из примера 1 предыдущего раздела и добавим ещё одну точку — $G=(6,16)$ с меткой «не купил» (0), которая на самом деле выглядит как случайная ошибка разметки, поскольку находится буквально рядом с кластером «купивших». Для запроса $(6,17)$ расстояние до $G$: $\sqrt{0^2+1^2}=1{,}0$ — это даже ближе, чем расстояние до $E$ (1.41 из предыдущего примера). При $k=1$ ближайшим соседом окажется именно $G$, и модель предскажет «не купит» — ошибка, целиком спровоцированная одной шумной точкой. При $k=5$ пятёрка ближайших соседей — $G(0)$, $E(1)$, $C(1)$, $D(1)$, $B(0)$ — даёт голосование 3 против 2 в пользу класса 1: более крупная выборка соседей «разбавила» влияние шума и вернула правильный прогноз.

Пример 2: крайний случай k = n

Если взять $k$, равное всему размеру обучающей выборки, голосование всегда учитывает буквально всех обучающих соседей — то есть прогноз для абсолютно любой новой точки будет одинаковым: классом, который встречается чаще всего в обучающей выборке, независимо от признаков самой точки. Это крайний случай недообучения в точности по логике урока 304: модель с $k=n$ обладает максимальным смещением (bias) и нулевой дисперсией (variance) — она вообще перестаёт учитывать индивидуальные особенности объекта.

Пример 3: подбор k через кросс-валидацию

Типичный рабочий процесс — перебрать диапазон нечётных $k$ (например, от 1 до 19) через GridSearchCV с кросс-валидацией и построить кривую точности по фолдам:

k=1: accuracy ≈ 0.78     k=9:  accuracy ≈ 0.89
k=3: accuracy ≈ 0.84     k=11: accuracy ≈ 0.86
k=5: accuracy ≈ 0.88     k=13: accuracy ≈ 0.83
k=7: accuracy ≈ 0.90

Кривая растёт до $k=7$, а затем начинает падать — классическая U-образная (точнее, перевёрнутая U-образная) форма зависимости качества от сложности модели. Малые $k$ — область переобучения (высокая дисперсия), большие $k$ — область недообучения (высокое смещение), а оптимум где-то посередине. Ровно такую же форму кривой ты уже видел в уроке 304 применительно к степени полинома и к силе регуляризации.

Почему это важно

Число соседей $k$ — это тот самый параметр, который нужно настраивать, чтобы получить от kNN приемлемое качество, и ошибка в его выборе — самая частая причина, по которой у новичков «kNN плохо работает». Понимание, что $k$ управляет ровно тем же компромиссом смещение-дисперсия, что и глубина дерева, степень полинома или сила L2-регуляризации, экономит массу времени: вместо того чтобы удивляться поведению модели, можно сразу применить знакомый инструментарий — кросс-валидацию и график ошибки в зависимости от сложности.

Масштабирование признаков перед kNN

Интуиция

kNN целиком построен на расстояниях, а расстояние в физическом смысле складывает величины, измеренные в совершенно разных единицах. Если один признак — зарплата в рублях (диапазон значений — десятки тысяч) а второй — возраст в годах (диапазон — пара десятков), то в сумме квадратов разностей вклад зарплаты будет численно подавлять вклад возраста в тысячи раз, даже если по смыслу задачи возраст важнее. Модель не «знает», что рубли и годы измеряют разные вещи — она видит только голые числа.

Формула

Стандартизация (z-score, StandardScaler): $x' = \frac{x - \mu}{\sigma}$, где $\mu$ — среднее, $\sigma$ — стандартное отклонение признака по обучающей выборке. Нормализация в диапазон (MinMaxScaler): $x' = \frac{x - x_{\min}}{x_{\max} - x_{\min}}$, приводящая значения к отрезку $[0,1]$.

Пример 1: полный расчёт — как масштабирование меняет ближайшего соседа

Клиент со значениями «доход = 70 000 руб., возраст = 30 лет». Два кандидата: $A$ — доход 71 000, возраст 50 (доход почти совпадает, возраст сильно отличается); $B$ — доход 40 000, возраст 31 (доход сильно отличается, возраст почти совпадает).

Без масштабирования: $d(Q,A) = \sqrt{1000^2+20^2} = \sqrt{1\,000\,400} \approx 1000{,}2$; $d(Q,B) = \sqrt{30000^2+1^2} \approx 30000{,}0$. Кандидат $A$ «ближе» почти в 30 раз — доход полностью подавил возраст в расчёте, хотя по возрасту $A$ отличается от клиента на целых 20 лет, а $B$ — всего на 1 год.

После стандартизации (пусть среднее и стандартное отклонение по выборке: доход $\mu=70000$, $\sigma=40000$; возраст $\mu=35$, $\sigma=12$): $Q_z=(0; -0{,}417)$, $A_z=(0{,}025; 1{,}25)$, $B_z=(-0{,}75; -0{,}333)$. Теперь $d(Q,A)_z = \sqrt{0{,}025^2+1{,}667^2} \approx 1{,}667$, а $d(Q,B)_z = \sqrt{0{,}75^2+0{,}084^2} \approx 0{,}755$. Ближайшим соседом стал $B$ — результат полностью перевернулся после масштабирования, и новый результат гораздо логичнее: клиент, совпадающий по возрасту почти день в день, действительно похож больше, чем клиент с почти идентичной зарплатой, но на 20 лет старше.

Пример 2: MinMaxScaler для ограниченных диапазонов

Если признак заведомо ограничен снизу и сверху (например, рост человека в диапазоне 150-200 см), часто удобнее MinMaxScaler: при росте 170 см и границах [150, 200] получаем $x' = (170-150)/(200-150) = 20/50 = 0{,}4$. MinMaxScaler предпочтителен, когда данные не подчиняются нормальному распределению или когда важно жёстко ограничить диапазон (например, для признаков вроде интенсивности пикселя изображения от 0 до 255).

Пример 3: защита от утечки данных через Pipeline

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

model = Pipeline([
    ("scaler", StandardScaler()),
    ("knn", KNeighborsClassifier(n_neighbors=7)),
])
model.fit(X_train, y_train)

Обёртывание масштабирования и модели в единый Pipeline — не просто удобство, а необходимость: если считать среднее и стандартное отклонение по всей выборке до разбиения на train/test (урок 305), информация о тестовых данных незаметно просочится в обучение через статистики масштабирования. Pipeline гарантирует, что StandardScaler обучается (fit) только на тренировочной части, а к тестовой применяется уже готовое преобразование (transform).

Почему это важно

Забытое масштабирование — самая частая практическая ошибка при использовании kNN, и она особенно коварна тем, что модель не выдаёт явной ошибки или предупреждения — она просто тихо работает не так, как задумано, отдавая почти весь вес признакам с большим числовым диапазоном. В отличие от линейной регрессии, где масштабирование в первую очередь влияет на скорость сходимости градиентного спуска, в kNN немасштабированные признаки искажают сам смысл понятия «расстояние», а значит — саму суть алгоритма.

Проклятие размерности и ускорение через KD-деревья

Интуиция

С ростом числа признаков (измерений) пространство стремительно «расширяется» — объём, доступный для размещения точек, растёт экспоненциально быстрее, чем количество самих точек. В результате в пространствах высокой размерности точки перестают быть по-настоящему «близкими» друг к другу: расстояние до ближайшего соседа и расстояние до самого дальнего объекта начинают отличаться совсем незначительно, и само понятие «ближайший сосед» теряет содержательный смысл.

Формула

Наивная реализация kNN требует вычислить расстояние от запроса до каждого из $n$ объектов обучающей выборки — сложность $O(n \cdot d)$ на один запрос, где $d$ — число признаков. Для иллюстрации проклятия размерности рассмотрим долю «внутреннего» объёма $d$-мерного гиперкуба, который остаётся внутри уменьшенного на 10% по каждой стороне куба: эта доля равна $0{,}9^d$.

Пример 1: как тает объём с ростом размерности

$0{,}9^2 = 0{,}81$ (81% объёма остаётся «внутри» при 2 признаках), $0{,}9^{10} \approx 0{,}349$ (уже только 35% при 10 признаках), $0{,}9^{100} \approx 0{,}0000266$ (практически 0% при 100 признаках). При росте числа измерений почти весь объём пространства «выдавливается» на внешнюю границу, а не концентрируется рядом с любой конкретной точкой — именно поэтому в пространствах высокой размерности почти все точки оказываются примерно одинаково (и одинаково плохо) удалены друг от друга.

Пример 2: KD-дерево вместо полного перебора

Из урока 257 ты уже знаешь принцип KD-дерева: пространство рекурсивно делится по очереди на разные координаты, а не по единственному ключу, как в обычном бинарном дереве поиска. Возьмём шесть точек из первого примера этого урока: $F(1,3)$, $A(2,5)$, $B(3,7)$, $E(7,18)$, $C(8,20)$, $D(9,25)$. Отсортируем по $x$: $F(1), A(2), B(3), E(7), C(8), D(9)$ — и построим корневое разбиение по $x=5$: слева от разбиения попадают $\{F, A, B\}$, справа — $\{E, C, D\}$.

Для запроса $(6,17)$ координата $x=6 \ge 5$, значит поиск сразу уходит в правое поддерево $\{E, C, D\}$ — то есть в точности к тем трём соседям, которые оказались реально ближайшими в примере 1 этого урока. Расстояние от запроса до разделяющей плоскости $x=5$ равно $1$; если после просмотра правого поддерева текущий худший из $k$ найденных соседей уже ближе, чем $1$, алгоритм может вообще не заглядывать в левое поддерево $\{F, A, B\}$, гарантированно не пропустив более близкого кандидата. В этом маленьком примере экономия — всего три сравнения расстояний, но на выборке из миллионов объектов та же логика отсечения целых веток превращает поиск из $O(n)$ в $O(\log n)$ в среднем случае.

Пример 3: где KD-дерево перестаёт помогать

Как уже разбиралось в задании 27 урока 257, отсечение веток KD-дерева работает благодаря тому, что в низкой размерности разделяющая гиперплоскость реально «отсекает» большие области пространства, заведомо не содержащие более близкого соседа. При росте числа измерений до десятков и сотен этот эффект слабеет вместе с самим проклятием размерности: почти любая ветка может содержать точку чуть ближе текущей лучшей, и дерево на практике вырождается почти до полного перебора. Поэтому sklearn.neighbors.KNeighborsClassifier по умолчанию (algorithm='auto') сам выбирает между 'brute' (полный перебор), 'kd_tree' и 'ball_tree' (более гибкая версия для умеренно высокой размерности) в зависимости от числа объектов и признаков, а для по-настоящему высокоразмерных эмбеддингов (сотни-тысячи измерений, как в поиске похожих изображений или текстов) на практике переходят к приближённым методам поиска соседей вроде HNSW, жертвуя точностью ради скорости.

Почему это важно

Связка «проклятие размерности плюс вычислительная стоимость» определяет, где kNN реально применим в продакшне, а где нет. При малом числе признаков и умеренном размере датасета KD-дерево из урока 257 превращает наивный $O(n)$-перебор в быстрый $O(\log n)$-поиск, и kNN становится вполне жизнеспособным промышленным решением. Но при сотнях признаков — типичная ситуация для эмбеддингов из нейросетей — те же самые деревья теряют преимущество, и разумной стратегией становится либо снижение размерности через PCA (урок 323), либо переход к специализированным библиотекам приближённого поиска ближайших соседей.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1. Вычисли евклидово расстояние между точками $(1,2)$ и $(4,6)$.

Задание 2. Вычисли манхэттенское расстояние между теми же точками $(1,2)$ и $(4,6)$.

Задание 3. Датасет интернет-магазина: «дней с последней покупки ($x_1$), сумма корзины в тыс. руб. ($x_2$)» → «вернётся (1) / не вернётся (0)»: $P_1(5,2){:}0$, $P_2(8,3){:}0$, $P_3(30,15){:}1$, $P_4(35,20){:}1$, $P_5(28,12){:}1$, $P_6(3,1){:}0$. Для запроса $(25,11)$ найди метку методом $k=1$.

Задание 4. Тот же датасет и запрос, что в задании 3. Найди предсказание при $k=3$.

Задание 5. Зависимость «стаж работы (лет) → зарплата (тыс. руб.)»: $(2,50)$, $(3,55)$, $(9,90)$, $(10,100)$, $(4,60)$. Оцени зарплату при стаже 5 лет методом kNN-регрессии с $k=3$.

Задание 6. Объясни одной фразой, почему kNN называют «ленивым» методом обучения.

Задание 7. Стандартизируй значение $x=130$, если среднее по признаку $\mu=100$, стандартное отклонение $\sigma=15$.

Задание 8. Вычисли расстояние Минковского с $p=3$ между точками $(0,0)$ и $(2,3)$.

Задание 9. При $k=1$ два кандидата оказались на в точности одинаковом расстоянии от запроса, но принадлежат к разным классам. Как разумно поступить?

Задание 10. По таблице точности кросс-валидации ($k$: accuracy) — $1{:}0{,}78$, $3{:}0{,}84$, $5{:}0{,}88$, $7{:}0{,}90$, $9{:}0{,}89$, $11{:}0{,}86$ — выбери лучшее значение $k$.

Средние задания (11–20)

Задание 11. Используя датасет из задания 3, найди предсказание при $k=5$.

Задание 12. Используя датасет из задания 5, оцени зарплату при стаже 5 лет с $k=4$ и сравни с ответом задания 5.

Задание 13. Запрос $Q=(0,0)$, кандидаты $P_1=(5,1)$ и $P_2=(2,4)$. Вычисли евклидово и манхэттенское расстояние до обоих и проверь, меняется ли ранжирование.

Задание 14. Клиент $Q$: доход 1200 тыс. руб./год, возраст 40 лет. Кандидат $A$: доход 1250, возраст 60. Кандидат $B$: доход 600, возраст 41. Вычисли евклидово расстояние без масштабирования и определи, какой кандидат окажется «ближе» и почему это нелогично.

Задание 15. Тот же запрос и кандидаты, что в задании 14. Стандартизируй по $\mu_{доход}=1200$, $\sigma_{доход}=500$, $\mu_{возраст}=40$, $\sigma_{возраст}=12$ и пересчитай расстояния.

Задание 16. Вычисли $0{,}8^d$ для $d=1$, $d=5$ и $d=20$ и объясни, что это иллюстрирует.

Задание 17. Дано разбиение KD-дерева по $x=5$ (левое поддерево — $x<5$, правое — $x \ge 5$). В какое поддерево попадёт запрос $(2,9)$?

Задание 18. Наивный kNN без ускоряющей структуры обрабатывает 100 запросов на датасете из 10 000 объектов с 20 признаками. Сколько всего элементарных операций (сравнений координат) потребуется приблизительно, если на одно вычисление расстояния между парой объектов уходит порядка $d$ операций?

Задание 19. В коде ниже есть ошибка:

from sklearn.neighbors import KNeighborsClassifier

model = KNeighborsClassifier(n_neighbors=5)
model.fit(X_train, y_train)
predictions = model.predict(X_test)

Найди проблему, зная, что признаки в X_train измерены в сильно разных единицах.

Задание 20. Векторы оценок фильмов (жанры: фантастика, мелодрама, боевик) пользователей $X=(2,0,2)$ и $Y=(1,4,1)$. Вычисли косинусное сходство и интерпретируй результат.

Продвинутые задания (21–30)

Задание 21. Датасет содержит только категориальные признаки: пол, город, семейное положение. Объект 1: (муж., Москва, женат). Объект 2: (жен., Москва, не женат/не замужем). Предложи способ измерить «расстояние» между ними и вычисли его.

Задание 22. Опиши шаги (без чисел) для корректного подбора kNN-модели на датасете с признаками «доход» (0–1 000 000) и «возраст» (0–100), включая выбор $k$.

Задание 23. Если оценить точность kNN с $k=1$ прямо на обучающей выборке (без отдельного валидационного набора), какой будет точность и почему это бесполезная оценка?

Задание 24. Три ближайших соседа найдены на расстояниях 1, 8 и 9 с метками 0, 1 и 1 соответственно. Сравни результат обычного (равновесного) голосования и голосования, взвешенного по $1/d$.

Задание 25. Объясни, почему kNN плохо масштабируется на эмбеддинги с 512 измерениями, даже если использовать KD-дерево из урока 257.

Задание 26. В каких ситуациях kNN стоит предпочесть другим алгоритмам, а в каких — наоборот, избегать?

Задание 27. Таблица train/val ошибок для датасета из 200 объектов: $k{=}1$: train 0%, val 22%; $k{=}10$: train 9%, val 11%; $k{=}50$: train 18%, val 19%. Определи режим (переобучение/норма/недообучение) для каждого $k$ и выбери лучшее значение.

Задание 28. В задаче с тремя классами при $k=6$ голоса разделились 2:2:2 — точная трёхсторонняя ничья, хотя $k$ чётное было выбрано специально, чтобы не совпадать с числом классов. Объясни, почему одного лишь выбора нечётного $k$ недостаточно для многоклассовой задачи, и предложи решение.

Задание 29. Банк предсказывает одобрение кредита по признакам «доход, тыс. руб./мес.» и «число открытых кредитов»: $K_1(40,1){:}1$, $K_2(35,4){:}0$, $K_3(90,1){:}1$, $K_4(30,5){:}0$, $K_5(85,2){:}1$. Запрос: доход 80, кредиты 2. Стандартизируй признаки (посчитав среднее и стандартное отклонение по пяти точкам) и найди прогноз при $k=3$.

Задание 30. Сравни три подхода к задаче бинарной классификации: наивный kNN (полный перебор), kNN с KD-деревом, логистическая регрессия (урок 313) — по времени обучения, времени предсказания и интерпретируемости.

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

Ошибка 1: забыть масштабировать признаки. Самая частая и самая коварная ошибка при работе с kNN — обучить модель на признаках без предварительного StandardScaler или MinMaxScaler. Как показано в заданиях 14–15 и 29, немасштабированный признак с большим числовым диапазоном (доход, население города, годовой оборот) способен полностью подавить вклад всех остальных признаков в расчёт расстояния, и модель молча выдаёт результат, основанный фактически на одном-единственном признаке.

Ошибка 2: выбирать k = 1 «для точности» и не проверять на отложенных данных. Малое $k$ действительно даёт идеальную точность на обучающей выборке (задание 23), но это иллюзия — реальное качество нужно проверять исключительно на валидации или тесте, никогда не полагаясь на точность, измеренную прямо на train.

Ошибка 3: оценивать k=1 модель на обучающей выборке. Отдельная методологическая ловушка: при $k=1$ каждый объект обучающей выборки — свой собственный ближайший сосед, так что train accuracy для такой модели всегда равна 100% и не несёт никакой информации о реальном качестве.

Ошибка 4: применять kNN «в лоб» к большому датасету без учёта стоимости предсказания. Наивная реализация масштабируется как $O(n)$ на каждый запрос — на выборках в миллионы строк и при частых запросах в реальном времени это быстро превращается в узкое место; нужно явно продумать ускоряющую структуру (KD-дерево, Ball Tree или приближённый поиск) заранее, а не после того, как система начала тормозить в продакшне.

Ошибка 5: игнорировать проклятие размерности. Применение kNN к сотням признаков без снижения размерности (PCA, урок 323) или отбора признаков часто даёт результат не лучше случайного угадывания — в высокой размерности «ближайший» сосед перестаёт быть по-настоящему близким.

Ошибка 6: использовать чётное k в бинарной классификации. Чётное $k$ создаёт риск точных ничьих при голосовании, для которых нет однозначного разрешения без дополнительных правил — простое правило «бери нечётный $k$» для двух классов снимает эту проблему почти полностью, хотя не спасает от ничьих в многоклассовых задачах (задание 28).

Главное запомнить

  • kNN — метод ленивого обучения (lazy learning): обучение — это сохранение данных ($O(1)$), а вся вычислительная работа переносится на момент предсказания.

  • Предсказание строится через голосование большинства по $k$ ближайшим соседям (классификация) или усреднение их целевых значений (регрессия).

  • Евклидово расстояние $\sqrt{\sum(x_i-y_i)^2}$ — метрика по умолчанию, но манхэттенское, косинусное и другие метрики Минковского могут давать другое ранжирование соседей и менять итоговый прогноз (задания 2, 13, 20).

  • Число соседей $k$ — главный гиперпараметр: малое $k$ ведёт к переобучению (высокая дисперсия, чувствительность к шуму), большое $k$ — к недообучению (высокое смещение, сглаживание границ), ровно та же логика, что и в уроке 304.

  • Оптимальный $k$ подбирается через кросс-валидацию (урок 306), обычно перебором нечётных значений для бинарной классификации.

  • Масштабирование признаков перед kNN обязательно — расстояние без масштабирования почти всегда доминируется признаком с наибольшим числовым диапазоном, независимо от его реальной значимости.

  • Наивная реализация требует $O(n \cdot d)$ вычислений на один запрос; KD-дерево (урок 257) в среднем ускоряет поиск до $O(\log n)$ в низкой и умеренной размерности.

  • Проклятие размерности разрушает как саму идею «близости» (все точки становятся примерно равноудалёнными), так и эффективность KD-деревьев — при высокой размерности нужны снижение размерности или приближённый поиск соседей.

  • kNN широко используется как быстрый интерпретируемый baseline и как ядро коллаборативной фильтрации в рекомендательных системах через sklearn.neighbors.KNeighborsClassifier и NearestNeighbors.

Связь с темами курса

Этот урок напрямую опирается на урок 257 о бинарных деревьях поиска, где уже был подробно разобран принцип KD-дерева: обобщение идеи упорядоченного бинарного дерева на несколько измерений через чередование координаты разбиения на разных уровнях. Там же (задание 27 урока 257) впервые обсуждалось, почему эффективность KD-дерева резко падает при высокой размерности признаков — в этом уроке та же самая идея получила прямое практическое применение: именно KD-дерево на практике превращает наивный $O(n)$-перебор kNN в быстрый $O(\log n)$-поиск, а его деградация в высокой размерности — это и есть проклятие размерности, разобранное здесь подробно с числовым примером.

Выбор числа соседей $k$ — это прямое продолжение урока 304 о переобучении и недообучении: малое $k$ и большое $k$ воспроизводят ровно тот же компромисс между смещением и дисперсией, что и степень полинома в полиномиальной регрессии (урок 311) или сила регуляризации в Ridge и Lasso (урок 312), только выраженный через другой параметр. А сам процесс подбора оптимального $k$ методом перебора кандидатов и сравнения по фолдам — это прямое применение техники кросс-валидации из урока 306.

По философии обучения kNN — почти полная противоположность логистической регрессии из урока 313: там модель в процессе обучения извлекает явную функцию (вектор весов), а kNN вообще не строит никакой обобщённой функции, откладывая всю работу на момент предсказания. Это различие между «ленивым» и «активным» обучением — ключевая линия водораздела, к которой ты будешь возвращаться, разбирая каждый следующий алгоритм курса: деревья решений (урок 316) и случайный лес (урок 317) снова строят явную структуру во время обучения, а вот кластеризация методом k-средних (урок 320) вновь опирается на расстояния между объектами почти так же, как kNN. В следующем уроке ты познакомишься с наивным байесовским классификатором — ещё одним быстрым и простым baseline-алгоритмом, но устроенным принципиально иначе: вместо расстояний он использует вероятностную модель, основанную на теореме Байеса.

Интересные факты

  • Технический отчёт Фикс и Ходжеса 1951 года, впервые формально описавший метод ближайших соседей, был подготовлен для школы авиационной медицины ВВС США и долгое время оставался малоизвестным военным документом — широкое признание в статистическом сообществе пришло к идее лишь спустя годы после её первой формулировки.

  • Теорема Ковера и Харта (1967) доказывает, что при бесконечном объёме данных ошибка простейшего 1-NN классификатора асимптотически не превышает удвоенной ошибки теоретически идеального байесовского классификатора — редчайшая по силе гарантия для алгоритма, в котором вообще нет обучаемых параметров.

  • kNN-регрессия по сути формализует «метод аналогов» (analog method), которым синоптики предсказывали погоду задолго до появления машинного обучения как дисциплины: искали в архивах исторический день с максимально похожими условиями и предполагали, что завтрашняя погода будет похожа на то, что случилось после того «дня-аналога».

  • Ранние промышленные рекомендательные системы конца 1990-х — начала 2000-х годов, включая первые версии коллаборативной фильтрации на Amazon, строились именно на user-based и item-based kNN задолго до того, как матричная факторизация и нейросетевые подходы стали индустриальным стандартом.

Лайфхаки

  • Всегда оборачивай StandardScaler и KNeighborsClassifier/KNeighborsRegressor в единый sklearn.pipeline.Pipeline — это не только защищает от утечки статистик масштабирования из теста в обучение, но и делает код короче и надёжнее.

  • При переборе $k$ через GridSearchCV тестируй одновременно weights=['uniform', 'distance'] — взвешенное по расстоянию голосование часто даёт заметный прирост качества почти бесплатно, особенно на границах классов (см. задание 24).

  • Для больших датасетов явно указывай algorithm='kd_tree' или 'ball_tree' вместо 'brute', если размерность признаков умеренная (примерно до нескольких десятков); при algorithm='auto' sklearn выбирает стратегию сам, но явное указание помогает понимать, что происходит под капотом.

  • Перед применением kNN к данным с большим числом признаков проверь размерность и, если она велика, сначала примени PCA (урок 323) — часто снижение до 10-50 главных компонент возвращает kNN осмысленную способность различать «близкие» и «далёкие» объекты.

  • Используй kNN как быстрый первый baseline перед тем, как переходить к градиентному бустингу или нейросетям — если простая модель с k ближайших соседей уже даёт приемлемое качество, это ценный сигнал о структуре данных, а если результат откровенно плохой даже после подбора $k$ и масштабирования — тоже полезная информация о сложности задачи.

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

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

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку
💬 Есть вопрос? Спроси бота!