K-Nearest Neighbors

Отчёт ВВС 1951 года и точная граница ошибки

Классификация по ближайшим соседям началась с неопубликованного технического отчёта 1951 года, написанного Эвелин Фикс и Джозефом Ходжесом для Школы авиационной медицины ВВС США. Они изучали непараметрическую дискриминацию: классификацию точки по ближайшим к ней размеченным примерам, без предположений о распределении данных. Идея оставалась в тени до 1967 года, когда Томас Ковер и Питер Харт доказали поразительный результат: с ростом объёма данных частота ошибок простого правила одного ближайшего соседа никогда не превышает удвоенную минимально возможную (байесовскую) ошибку. Эта гарантия показала, что столь простой метод может быть доказуемо конкурентоспособным, и закрепила за KNN постоянное место в арсенале.

Представьте: вы переехали в новый район и хотите понять, дорогой он или дешёвый. Самый естественный способ - посмотреть на соседние дома. Если три ближайших дома стоят 15, 18 и 16 миллионов, ваш, скорее всего, тоже где-то в этом диапазоне. Вы только что применили алгоритм KNN - K-Nearest Neighbors. Без формул, без нейросетей, без обучения. Просто посмотрели на соседей и сделали вывод. Но почему такой наивный подход работает? Как выбрать, сколько соседей смотреть? И почему в 100-мерном пространстве он вдруг ломается?

• **Рекомендательные системы** (Amazon, Spotify) используют KNN-подобные алгоритмы: если пользователи с похожими вкусами купили товар X, вам он тоже может понравиться - collaborative filtering основан на поиске «ближайших соседей» среди пользователей
• **Обнаружение аномалий** в банковских транзакциях: если транзакция «далеко» от K ближайших нормальных операций клиента, она подозрительна - KNN-based anomaly detection используется в fraud detection системах
• **Медицинская диагностика:** при редких заболеваниях, когда данных мало для обучения сложных моделей, KNN по анализам крови и симптомам находит похожих пациентов с известным диагнозом - и часто оказывается точнее, чем более сложные модели

Предварительные знания

• Data Preparation and Cleaning

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

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

**Евклидово расстояние (Euclidean)** - самая интуитивная метрика. Это расстояние «по прямой» между двумя точками, знакомое со школы. Для двух точек с координатами (x1, y1) и (x2, y2) формула: sqrt((x1-x2)^2 + (y1-y2)^2). В общем случае для N признаков: sqrt(sum((xi - yi)^2)). Евклидова метрика хорошо работает, когда признаки имеют одинаковый масштаб и когда пространство не слишком многомерное.

**Манхэттенское расстояние (Manhattan)** - расстояние «по улицам города». Представьте, что вы в Нью-Йорке: нельзя пройти «наискосок» через квартал, только по улицам - вправо и вверх. Формула: sum(|xi - yi|). Manhattan distance более устойчива к выбросам, чем Euclidean: один экстремальный признак не так сильно раздувает общее расстояние, потому что нет возведения в квадрат.

**Расстояние Минковского (Minkowski)** - обобщение обеих метрик. Формула: (sum(|xi - yi|^p))^(1/p). При **p=1** получаем Manhattan, при **p=2** - Euclidean. При p -> infinity метрика превращается в Chebyshev distance - максимальную разницу по одному из признаков. Minkowski позволяет плавно настраивать «характер» расстояния через параметр p.

**Косинусное сходство (Cosine Similarity)** измеряет не расстояние, а **угол** между векторами. Два документа с одинаковыми словами, но разной длиной будут «далеко» по Euclidean, но «близко» по Cosine, потому что их направления совпадают. Формула: cos(theta) = (A . B) / (|A| * |B|). Cosine similarity незаменима для текстов и высокоразмерных разреженных данных - там, где абсолютные значения менее важны, чем пропорции.

**Нормализация критична для KNN!** Представьте два признака: зарплата (30000-150000 рублей) и возраст (18-65 лет). Без нормализации зарплата будет полностью доминировать в расстоянии - разница в 10000 рублей «перевесит» разницу в 20 лет. KNN будет фактически игнорировать возраст. **Решение:** StandardScaler (z-score) или MinMaxScaler перед подачей данных в KNN - всегда.

Выбор K: нечётные числа и cross-validation

Параметр **K** в KNN - это количество ближайших соседей, по которым алгоритм принимает решение. Казалось бы, мелочь - но от выбора K зависит, будет ли модель запоминать шум или игнорировать реальные паттерны. Это классическая дилемма **bias-variance tradeoff**, и KNN демонстрирует её максимально наглядно.

**K=1** означает: «предскажи класс ровно того одного объекта, который ближе всего». Это делает модель **чрезвычайно чувствительной к шуму**. Один неправильно размеченный пример - и все новые точки рядом с ним будут классифицированы неверно. Граница решений при K=1 становится рваной и извилистой, обхватывая каждую отдельную точку - типичный **overfitting**.

**K=N** (равно общему числу объектов в обучающей выборке) - другая крайность. Каждая новая точка будет классифицирована как класс большинства во всей выборке, вне зависимости от её положения. Если 60% обучающих данных - класс A, то модель *всегда* предскажет A. Это **underfitting** - модель не учитывает локальную структуру данных вообще.

Для **бинарной классификации** (два класса) K выбирают нечётным - 3, 5, 7... Причина проста: при чётном K возможна ничья (2 соседа класса A и 2 класса B), и алгоритм не знает, что предсказать. Нечётное K гарантирует, что один класс всегда в большинстве. Для задач с 3+ классами ничья возможна и при нечётном K, но реже.

**Эмпирическое правило для стартового K:** попробуйте K = sqrt(N), где N - количество обучающих примеров. Для 1000 примеров: sqrt(1000) ~ 31. Затем проверьте нечётные значения вокруг: 29, 31, 33. Это правило не оптимально, но даёт разумную отправную точку для дальнейшего подбора через cross-validation.

**Cross-validation** - единственный надёжный способ выбрать K. Идея: разбить данные на, например, 5 частей (folds). Для каждого кандидата K (скажем, от 1 до 30): обучить на 4 частях, проверить на 5-й, повторить 5 раз, усреднить точность. K с лучшей средней точностью - победитель. Это **GridSearchCV** в scikit-learn.

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

KNN отлично работает в 2-3 измерениях, но с ростом числа признаков происходит нечто контринтуитивное: **в высокоразмерных пространствах все точки становятся одинаково далеко друг от друга**. Это явление называется **проклятие размерности (curse of dimensionality)**, и оно ставит под вопрос саму идею «ближайших соседей».

Представьте единичный квадрат [0,1]x[0,1]. Сфера (круг) радиусом 0.5 занимает pi/4 ~ 78.5% площади квадрата. Теперь возьмём единичный куб [0,1]^3 - сфера радиусом 0.5 занимает уже только 52.4% объёма. В 10 измерениях гиперсфера занимает всего **0.25%** объёма гиперкуба. В 100 измерениях - число настолько мало, что оно фактически ноль. Данные «растекаются» по углам гиперкуба, и центральная область пустеет.

Более формально: в пространстве размерности d расстояние до ближайшего соседа (d_min) и до самого далёкого (d_max) сближаются. Отношение (d_max - d_min) / d_min стремится к нулю с ростом d. Это значит, что понятие «ближайший сосед» теряет смысл - все соседи примерно «одинаково далеко». KNN начинает деградировать примерно при **20-30 признаках**, хотя точный порог зависит от объёма данных.

**Решения проблемы размерности для KNN:** 1. **PCA (Principal Component Analysis)** - сжать 100 признаков до 10-20 главных компонент, сохранив 95% дисперсии 2. **Feature Selection** - выбрать только самые информативные признаки (mutual information, chi-squared test) 3. **Увеличить объём данных** - но для d измерений нужно экспоненциально больше данных: N ~ exp(d) 4. **Использовать другой алгоритм** - деревья решений, Random Forest, градиентный бустинг не страдают от проклятия размерности так сильно

Взвешенный KNN и практика

В стандартном KNN все K соседей имеют равный голос: ближайший на расстоянии 0.1 и дальний на расстоянии 5.0 влияют одинаково. Это несправедливо - ближний сосед должен быть важнее. **Взвешенный KNN** решает эту проблему: каждый сосед голосует с весом, обратно пропорциональным расстоянию. Сосед на расстоянии 0.1 получает вес 10, а на расстоянии 5.0 - вес 0.2.

KNN работает не только для классификации, но и для **регрессии**. Вместо голосования за класс алгоритм берёт среднее значение целевой переменной K ближайших соседей. Например, для предсказания цены квартиры: находим 5 ближайших по площади, этажу, району - и усредняем их цены. С весами: KNeighborsRegressor(weights='distance') - ближние квартиры влияют на предсказание сильнее.

KNN относится к алгоритмам **lazy learning (ленивое обучение)**. В отличие от линейной регрессии или нейросетей, KNN **не имеет этапа обучения**. Он просто запоминает все обучающие данные. Вся работа происходит на этапе предсказания: для каждого нового объекта нужно вычислить расстояние до *всех* обучающих примеров и найти K ближайших. Это делает **training мгновенным, но prediction медленным** - O(N*d) для каждого запроса.

**Структуры данных для ускорения KNN:** - **KD-Tree** - разбивает пространство на прямоугольные области. Ускоряет поиск до O(d * log N) вместо O(N * d). Хорошо работает при d < 20 - **Ball Tree** - разбивает на гиперсферы. Лучше KD-Tree при d > 20, но хуже в малых размерностях - **Brute Force** - полный перебор. Единственный вариант для очень больших d или специальных метрик В scikit-learn: `KNeighborsClassifier(algorithm='kd_tree')` или `algorithm='auto'` (выберет сам).

Ключевые идеи

• **Метрики расстояния** определяют, что значит «похожий»: Euclidean (по прямой), Manhattan (по улицам), Cosine (по углу) - выбор метрики и обязательная нормализация признаков критически влияют на результат
• **Выбор K** - главный гиперпараметр: K=1 запоминает шум (overfitting), K=N игнорирует структуру (underfitting), оптимальный K находится через cross-validation, а для бинарной классификации K должен быть нечётным
• **Проклятие размерности** делает KNN бесполезным при 30+ признаках - все точки становятся одинаково далеко, и PCA или feature selection необходимы для снижения размерности
• **Взвешенный KNN** (weights='distance') даёт ближним соседям больший вес, а сам алгоритм - lazy learner без обучения: мгновенный fit, но медленный predict. Как при оценке дома по соседям - метод прост и интуитивен, но именно поэтому он до сих пор используется в рекомендациях, аномалий-детекции и медицинской диагностике

Связанные темы

KNN тесно связан с предобработкой данных, оценкой моделей и другими алгоритмами классификации:

• Предобработка данных — Нормализация (StandardScaler, MinMaxScaler) критична для KNN - без неё признаки в разных масштабах искажают расстояния
• Support Vector Machines — SVM тоже использует понятие расстояния, но строит разделяющую гиперплоскость - в отличие от KNN, который решает локально по соседям
• PCA - метод главных компонент — PCA снижает размерность и решает проклятие размерности - ключевую проблему KNN при большом числе признаков
• Оценка моделей — Cross-validation, accuracy, precision, recall - инструменты для выбора оптимального K и оценки качества KNN

Вопросы для размышления

• Если KNN не имеет этапа обучения и просто запоминает данные, можно ли считать его алгоритмом машинного обучения? Где граница между «запоминанием» и «обучением»?
• В каких ситуациях простой KNN с K=5 может оказаться точнее глубокой нейросети? Подумайте о размере данных, числе признаков и сложности границы классов.
• Как бы вы применили идею «ближайших соседей» к данным, где обычные метрики расстояния не работают - например, к графам социальных сетей или последовательностям ДНК?

Связанные уроки

• ml-04-data-preprocessing — Нормализация данных критична для KNN
• ml-13-svm — SVM и KNN - оба instance-based, но разные принципы
• ml-19-pca — PCA снижает размерность перед KNN для curse of dimensionality
• ir-06 — Semantic search - это KNN в пространстве embeddings
• aie-09-embeddings — Vector search в RAG - это KNN с нейронными embeddings
• alg-10-binary-search — ANN-индексы (HNSW) ускоряют KNN как binary search ускоряет linear search