Метод ближайших соседей простыми словами

Коротко

Метод ближайших соседей - это способ предсказать ответ для нового объекта, просто посмотрев на самые похожие объекты, для которых ответ уже известен. Идея укладывается в поговорку «скажи, кто твои соседи». Алгоритм не строит сложную модель заранее: он запоминает примеры и при каждом запросе ищет ближайшие из них. На этом принципе во многом держатся рекомендации товаров и музыки. Разберём, что значит «похожий», как выбрать число соседей и где метод подводит.

Главная идея: похожее тянется к похожему

Представьте, что вы переехали в новый дом и хотите понять, насколько здесь спокойный район. Самый простой ход - расспросить ближайших соседей. Если почти все рядом говорят «тихо и безопасно», вы делаете тот же вывод про себя. Если мнения разделились, вы прислушаетесь к большинству.

Ровно так рассуждает метод ближайших соседей (по-английски k-NN, от k-nearest neighbors). У нас есть набор объектов, для которых ответ уже известен: эти фильмы человеку понравились, а эти - нет; это письмо спам, а это нет. Появляется новый объект без ответа. Алгоритм находит несколько самых похожих на него примеров из прошлого и присваивает новому объекту тот ответ, который встречается у соседей чаще всего.

Важно, что никакого «обучения» в привычном смысле здесь почти нет. Модель не выводит общие правила заранее - она просто хранит примеры и обращается к ним в момент вопроса. Поэтому метод иногда называют «ленивым»: вся работа откладывается до запроса.

Признаки: как описать объект числами

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

Например, пользователя интернет-магазина можно описать набором признаков:

  • сколько заказов он сделал за месяц;
  • средняя сумма чека;
  • доля покупок в категории «электроника»;
  • как часто он возвращает товар.

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

Важно

От выбора признаков зависит почти всё. Если описать объекты неудачными или несущественными свойствами, «похожесть» получится бессмысленной, и метод ошибётся. Подбор хороших признаков - отдельная и важная часть работы, общая для всего машинного обучения.

Расстояние: чем измерять похожесть

Раз объекты стали точками, «похожесть» удобно мерить через расстояние - числовую меру того, насколько далеко друг от друга находятся два объекта. Чем меньше расстояние, тем объекты более похожи.

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

Существуют и другие способы считать близость (например, по совпадению вкусов или по направлению, а не длине), но для интуиции достаточно одной мысли: алгоритм умеет численно оценивать, насколько один объект напоминает другой.

Выбор k и голосование большинством

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

Работает это так:

  1. Берём новый объект без ответа.
  2. Считаем расстояние от него до всех известных примеров.
  3. Отбираем k ближайших.
  4. Смотрим, какой ответ у них встречается чаще, - это и есть прогноз. Такой «подсчёт голосов» называют голосованием большинством.

Число k мы выбираем сами, и оно заметно влияет на результат:

  • Маленькое k (например, 1). Ответ определяет один-единственный ближайший сосед. Метод чутко улавливает детали, но легко обманывается случайным «выбросом» - нетипичным примером, попавшим не туда.
  • Большое k. Голосует много соседей, ответ становится устойчивее к случайным помехам. Но если взять слишком много, в голосование попадут уже не очень похожие объекты, и тонкие различия сотрутся.

Универсального правильного k нет: его подбирают под конкретную задачу, проверяя, при каком значении прогнозы получаются точнее. Для задач с двумя классами часто берут нечётное k, чтобы голоса не делились поровну.

Зачем нормализовать признаки

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

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

Упражнение: к какому классу отнести новый объект?

Представьте плоскость с двумя признаками. На ней расставлены точки двух классов: синие кружки и красные квадраты. Появляется новый объект - зелёная звёздочка. Вокруг неё, от самого близкого к более далёким, расположены соседи в таком порядке:

1-й (ближайший) - красный квадрат 2-й - синий кружок 3-й - синий кружок 4-й - синий кружок 5-й - красный квадрат

Вопрос: к какому классу метод отнесёт звёздочку при k = 1 и при k = 5?

Разбор.

  • При k = 1 мы смотрим только на одного ближайшего соседа. Это красный квадрат - значит, прогноз: красный.
  • При k = 5 голосуют все пять соседей: три синих кружка против двух красных квадратов. Большинство за синий - прогноз: синий.

Один и тот же объект получил разные ответы только из-за выбора k. Маленькое k доверилось единственному близкому примеру (а он мог оказаться случайным выбросом), большое k опросило больше соседей и дало более устойчивый результат. В этом и состоит главный практический вывод: значение k нужно подбирать осознанно, а не наугад.

Где это работает и в чём слабости

Метод ближайших соседей ценят за наглядность, поэтому он встречается в задачах, где есть много размеченных примеров и понятная мера похожести:

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

Но у метода есть ограничения, и о них стоит знать заранее:

  • Тяжело на больших данных. При каждом запросе нужно сравнивать объект со всем хранилищем примеров. Когда примеров миллионы, это медленно и затратно.
  • Чувствительность к признакам и масштабу. Неудачные признаки или забытая нормализация легко портят результат.
  • «Проклятие размерности». Когда признаков очень много, понятие близости размывается: почти все объекты оказываются примерно одинаково далеко друг от друга, и «соседство» теряет смысл.
  • Зависимость от качества данных. Метод буквально доверяет соседям, поэтому ошибки и перекосы в исходных примерах он повторит. Это общая для ИИ тема - подробнее в уроке про этику и предвзятость.

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

Проверьте себя

Короткий тест по уроку: выберите ответ и нажмите «Проверить» - увидите счёт и разбор.

Частые вопросы

Чем метод ближайших соседей отличается от обычного обучения модели?

Большинство алгоритмов сначала «учатся» на данных и строят общую модель, а затем быстро отвечают по ней. Метод ближайших соседей почти ничего не вычисляет заранее: он хранит примеры и ищет похожие прямо в момент запроса. Поэтому его называют «ленивым» - основная работа происходит при ответе, а не при обучении.

Как правильно выбрать число k?

Единого верного значения нет, его подбирают под задачу. Слишком маленькое k делает прогноз неустойчивым к случайным примерам, слишком большое - стирает важные различия. На практике пробуют несколько значений и оставляют то, при котором прогнозы точнее. Для двух классов часто берут нечётное k, чтобы голоса не разделились поровну.

Зачем нужна нормализация признаков?

Чтобы признаки в разных единицах не «забивали» друг друга. Если один признак измеряется в десятках тысяч, а другой - в единицах, расстояние будет определять только первый. Нормализация приводит все признаки к сопоставимому масштабу, и каждый вносит честный вклад в оценку похожести.

Подходит ли метод для очень больших данных?

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

В курсе: ← Назад: Виды машинного обучения: с учителем, без учителя, с подкреплением · Дальше: Линейная регрессия: как ИИ предсказывает числа →

Авторы курса: Герман Коваленко (основатель ENGRAM) и Сергей Добров.

← Назад4.1 Виды машинного обученияДальше →4.3 Линейная регрессия
После курса - для команды

Нужно обучить не себя, а команду?

Корпоративная программа адаптирует эту методику под ваши роли и процессы: практики, диагностика, сопровождение.

Обучить команду