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

Коротко

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

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

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

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

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

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

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

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

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

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

Важно

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

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

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

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

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

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

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

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

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

Число 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) и Сергей Добров.

Попробуйте ENGRAM на своих данных

Нейросеть на ваших встречах, документах и переписке: отвечает со ссылкой на источник. Это ваша вторая память на базе ИИ. Данные хранятся в России, старт бесплатный.

Зарегистрироваться бесплатно