Как в учебнике
Метод $k$ ближайших соседей хранит размеченные обучающие объекты. Для нового $x$ он вычисляет расстояния до них, выбирает $k$ ближайших и предсказывает класс, набравший большинство голосов. Требуется $1\le k\le n$, где $n$ — размер обучающей выборки.
Расстояние, представление признаков и правила разрешения равенств нужно задать заранее. В бинарной задаче нечётное $k$ исключает ничью голосов, но одинаковые расстояния на границе набора соседей всё равно требуют соглашения. В примере расстояние задано как $|x-z|$ на числовой прямой.
При $k=1$ ответ определяет один ближайший объект. Малое $k$ делает предсказание чувствительным к отдельным наблюдениям, большое учитывает более широкое окружение и может сгладить полезные локальные различия. Метод не строит границу решений явным образом до запроса: ответ получается из расстояний до сохранённых примеров.
При проверке на самих обучающих объектах $k=1$ даёт нулевую ошибку, если каждый объект выбирает себя ближайшим соседом. Совпавшие признаки с противоречивыми метками могут нарушить это условие. Даже нулевая обучающая ошибка ничего не обещает новому объекту.
Связанные понятия: Классификация с учителем, Выбор гиперпараметров.
При равных весах каждый выбранный сосед даёт один голос независимо от точного расстояния до запроса. Ближайший объект не обязан принадлежать победившему классу при $k>1$. Масштаб признаков влияет на расстояния: изменение единиц одной координаты может изменить состав соседей без изменения меток. Поэтому правило предсказания включает не только $k$, но и способ представления данных до вычисления расстояний.
На пальцах
Ближайшие соседи напоминают прохожих, голосующих за направление дороги. Один знаток способен уверенно отправить к закрытому мосту, а несколько голосов уменьшают зависимость от него. Опрос всего города, наоборот, способен стереть местные подробности. В обычном голосовании прохожие в ста и двухстах метрах получают по одному голосу, если оба вошли в выбранную группу. Поэтому расстояние, масштабы признаков и размер группы должны быть определены заранее: смешение кварталов с сантиметрами превращает точный подсчёт в неожиданное путешествие.
Пример
Учебные объекты на прямой: координата 0 с меткой 0, координаты 2 и 3 с меткой 1. Новый объект $x=0.8$. Равных расстояний нет; пример сравнивает $k=1$ и $k=3$.
Метод ближайших соседей
Расстояния до соседей
До координат 0, 2 и 3 расстояния равны 0.8, 1.2 и 2.2 соответственно.
Шаг 1 из 3: Расстояния до соседей
Все шаги текстом
Расстояния до соседей
До координат 0, 2 и 3 расстояния равны 0.8, 1.2 и 2.2 соответственно.
- Координаты
- 023
- Расстояния
- 0.8текущий1.22.2
Один сосед
Ближе всех объект в точке 0. Его метка 0 становится ответом.
- Соседи
- 0 → класс 0включён2 → класс 13 → класс 1
- Ответ
- 0включён
Три соседа
Два соседа голосуют за 1, один за 0. Изменение k меняет ответ на том же входе.
- Голоса
- 0исключён1включён1включён
- Ответ
- 1включён
Порядок соседей здесь однозначен: сначала точка 0, затем 2, затем 3. При $k=3$ ближайший носитель класса 0 проигрывает двум более далёким носителям класса 1, потому что считаются голоса. Изменение ответа с 0 на 1 не доказывает улучшения: истинная метка запроса в примере не задана. Демонстрация проверяет механизм применения двух настроек, а не выбирает победителя по качеству.
Источник исходного конспекта: материал лекции.