k-Nearest Neighbors: учимся у ближайших соседей

🎯 Зачем это нужно?

Представь, что ты переехал в новый район и хочешь найти хорошую пиццерию 🍕. Что ты сделаешь? Скорее всего, спросишь у соседей! И чем ближе сосед живёт к тебе, тем больше ты доверишь его мнению.

Именно так работает алгоритм k-Nearest Neighbors (kNN) - один из самых интуитивно понятных алгоритмов машинного обучения:

📱 Рекомендательные системы: Spotify предлагает музыку, основываясь на вкусах похожих пользователей 🛒 E-commerce: “Покупатели, похожие на вас, также покупали…”
🏥 Медицина: Диагностика заболеваний по сходству симптомов с известными случаями 🎯 Распознавание изображений: Классификация объектов по похожести с образцами

📚 История вопроса

kNN изобрели в 1951 году, но популярным стал только в 1960-х с развитием компьютеров. Интересный факт: это “ленивый” алгоритм (lazy learning) - он НЕ обучается заранее, а просто запоминает все данные и думает только во время предсказания!

Как студент, который не готовится к экзамену, а на самом экзамене ищет ответы в шпаргалках 😅

💡 Интуиция

[МЕДИА: image_01] Описание: Визуализация концепции kNN на плоскости с точками разных классов и новым объектом Промпт: “educational illustration showing kNN concept, 2D scatter plot with blue and red points representing different classes, one green point as query object, circles showing k=3 and k=5 neighborhoods, clean modern style, suitable for technical audience”

Представь класс, где ученики сидят за партами. Красные кружочки - любители математики, синие - гуманитарии. Приходит новый ученик (зелёный кружок). Как понять, кто он?

Идея kNN: Посмотри на k ближайших соседей и реши “голосованием”!

• При k=3: смотрим на 3 ближайших → 2 красных + 1 синий → скорее всего, математик
• При k=5: смотрим на 5 ближайших → может быть 3 синих + 2 красных → гуманитарий

Ключевая идея: Объекты одного класса должны быть близко друг к другу в пространстве признаков.

📐 Формальное определение

Для классификации нового объекта x алгоритм kNN:

1️⃣ Вычисляет расстояние до всех объектов в обучающей выборке 2️⃣ Находит k ближайших соседей
3️⃣ Проводит голосование среди этих соседей

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

• Евклидово: d(x,y) = √[(x₁-y₁)² + (x₂-y₂)² + … + (xₙ-yₙ)²]
• Манхэттенское: d(x,y) = |x₁-y₁| + |x₂-y₂| + … + |xₙ-yₙ|
• Чебышёвское: d(x,y) = max(|x₁-y₁|, |x₂-y₂|, …, |xₙ-yₙ|)

Для регрессии: усредняем значения k ближайших соседей ŷ = (1/k) × Σyᵢ, где yᵢ - значения k ближайших соседей

🔍 Примеры с разбором

Пример 1: Классификация студентов

Данные: студенты и их предпочтения

• Время учёбы (часы/день): x₁
• Время в соцсетях (часы/день): x₂
• Класс: “отличник” или “троечник”

[МЕДИА: image_02] Описание: Пошаговое решение задачи kNN с таблицей данных и визуализацией на плоскости Промпт: “step-by-step kNN solution diagram, table with student data showing study hours vs social media hours, 2D plot with classification result, arrows showing distance calculations, educational style with clear annotations”

Обучающая выборка:

Новый студент: Учёба=5, Соцсети=3

Шаг 1: Вычисляем расстояния (евклидово)

• До А: √[(5-6)² + (3-2)²] = √[1+1] = √2 ≈ 1.41
• До Б: √[(5-4)² + (3-4)²] = √[1+1] = √2 ≈ 1.41
• До В: √[(5-7)² + (3-1)²] = √[4+4] = √8 ≈ 2.83
• До Г: √[(5-3)² + (3-5)²] = √[4+4] = √8 ≈ 2.83
• До Д: √[(5-8)² + (3-2)²] = √[9+1] = √10 ≈ 3.16

Шаг 2: При k=3 ближайшие соседи: А, Б, В

Шаг 3: Голосование: 2 отличника + 1 троечник → предсказание: “отличник”

Пример 2: Влияние выбора k

Рассмотрим тот же случай с разными k:

• k=1: Ближайший сосед А (“отличник”) → “отличник”
• k=3: А, Б, В (2 отличника, 1 троечник) → “отличник”
• k=5: Все 5 соседей (3 отличника, 2 троечника) → “отличник”

Общее правило:

• Малые k → модель более чувствительна к шуму (переобучение)
• Большие k → модель более устойчива, но может упускать детали (недообучение)

🎮 Практика

Базовый уровень 🟢

Задание 1: Даны точки: A(1,1), B(2,3), C(4,1), D(3,4). Новая точка X(2,2). Найди 2 ближайших соседа используя евклидово расстояние.

Задание 2: У тебя есть данные о росте и весе спортсменов-баскетболистов и футболистов. Новый спортсмен: рост 180см, вес 75кг. При k=3 получили: 2 баскетболиста, 1 футболист. К какому классу отнесём?

Задание 3: Почему в kNN обычно выбирают нечётные значения k?

Задание 4: Объясни, почему kNN называют “ленивым” алгоритмом?

Продвинутый уровень 🟡

Задание 5: Реализуй функцию для вычисления манхэттенского расстояния между двумя точками в Python:

def manhattan_distance(point1, point2):
    # Твой код здесь
    pass

Задание 6: Студенты описываются тремя признаками: оценки (0-100), посещаемость (0-100%), активность (0-10). Нормализация нужна или нет? Почему?

Задание 7: В задаче регрессии у нас есть точки: (1,2), (2,4), (3,6), (4,8). Предскажи значение для x=2.5 используя kNN с k=2.

Задание 8: Как изменится работа алгоритма, если один из признаков измеряется в километрах, а другой в миллиметрах?

Челлендж 🔴

Задание 9: Придумай случай, когда kNN будет работать плохо, и предложи решение.

Задание 10: Объясни “проклятие размерности” в контексте kNN. Почему в 1000-мерном пространстве все точки кажутся одинаково далёкими?

Задание 11: Сравни временную сложность kNN с деревом решений. Когда что выгоднее использовать?

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

❌ Ошибка: Забывают нормализовать признаки ✅ Правильно: Приводим все признаки к одной шкале (например, 0-1)
💡 Почему: Признак с большими значениями будет доминировать в расчёте расстояния

❌ Ошибка: Выбирают чётные k для классификации ✅ Правильно: Используем нечётные k (1, 3, 5, 7…) 💡 Почему: Избегаем ничьих при голосовании

❌ Ошибка: Думают, что kNN быстро предсказывает
✅ Правильно: kNN медленный на этапе предсказания 💡 Почему: Нужно вычислить расстояние до всех объектов в выборке

❌ Ошибка: Используют kNN при большом количестве признаков ✅ Правильно: Применяем отбор признаков или понижение размерности 💡 Почему: В высокоразмерных пространствах расстояния теряют смысл

❌ Ошибка: Не учитывают дисбаланс классов ✅ Правильно: Используем взвешенное голосование или балансировку данных 💡 Почему: Мажоритарный класс может подавить миноритарный

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

✅ kNN классифицирует объект по большинству голосов среди k ближайших соседей ✅ Ключевая формула: d(x,y) = √Σ(xᵢ-yᵢ)² для евклидова расстояния ✅ Применяется в рекомендательных системах, поиске похожих объектов, классификации

🔗 Связь с другими темами

Назад: Метрики и расстояния (урок 313) - основа для вычисления близости объектов Вперёд: Кластеризация k-means - тоже использует расстояния, но для группировки данных Связано: Методы ансамблей - kNN можно комбинировать с другими алгоритмами