Skip to content
Назад к результатам поиска

Метод K ближайших соседей

Автор метода
Cover, T.M. & Hart, P.E.
Год
1967
Тип
Instance-based (non-parametric) learning

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Метод K ближайших соседей (KNN), формализованный Кавером и Хартом в 1967 году, является непараметрическим, основанным на прецедентах методом, который классифицирует или предсказывает новое наблюдение, основываясь на k ближайших примерах в обучающих данных.

Для классификации он использует голосование по большинству среди этих соседей; для регрессии он усредняет их значения.

Интуиция метода

Идея проста: похожие входные данные, как правило, имеют похожие выходные данные. Чтобы пометить новую точку, KNN находит несколько обучающих примеров, которые находятся ближе всего к ней в пространстве признаков, и позволяет им принимать решение. Предварительно не подгоняется никакое уравнение — сами обучающие данные являются моделью, и предсказание делается только тогда, когда появляется новая точка.

История

Классификация паттернов методом ближайшего соседа получила свое формальное статистическое обоснование от Томаса Кавера и Питера Харта в их статье 1967 года в IEEE Transactions on Information Theory, которая анализировала частоту ошибок правила ближайшего соседа. KNN стал одним из самых ранних и наиболее устойчивых методов обучения на основе прецедентов и остается стандартным базовым классификатором.

Когда применять

Используйте KNN для классификации или предсказания на табличных данных с непрерывными, бинарными или порядковыми признаками и как минимум около 30 наблюдений. Он не предполагает какого-либо конкретного распределения, но требует, чтобы признаки были нормализованы и чтобы количество признаков оставалось небольшим относительно размера выборки (предпочтительно p значительно меньше n). В малых или высокоразмерных выборках доминирует проклятие размерности — расстояния до соседей становятся неинформативными — и параметрическая модель, такая как логистическая регрессия или наивный байесовский классификатор, является лучшим выбором.

Ограничения и замечания

  • Чувствителен к масштабированию признаков; без стандартизации крупномасштабные признаки доминируют в расстоянии.
  • Быстро деградирует в высоких размерностях («проклятие размерности»), где расстояния до соседей теряют смысл.
  • Каждое предсказание требует сканирования всего обучающего набора, что медленно при предсказании на больших данных.
  • Требуется как минимум умеренный размер выборки; в малых выборках расстояния до ближайших соседей не имеют смысла.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Концептуально прост и легко объясним: нет уравнения, подгоняемого на этапе обучения, данные являются моделью.
  • Непараметрический — не делает предположений о базовом распределении.
  • Естественным образом обрабатывает многоклассовые задачи и сложные, нелинейные границы решений.
  • Работает как для классификации, так и для регрессии с одной и той же базовой идеей.

Применение

  • Классификация табличных данных на две или более категории.
  • Численное предсказание (регрессия) путем усреднения ближайших примеров.
  • Простая, интерпретируемая базовая модель перед попыткой более сложных моделей.
  • Распознавание образов, где сходство с известными примерами определяет решение.

Как это работает

Как это работает

1

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

Формула
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}
2

k обучающих точек с наименьшими расстояниями до нового наблюдения выбираются в качестве его соседей. Значение k контролирует локальность решения: малое k точно следует данным, но чувствительно к шуму, тогда как большее k сглаживает границу. k следует выбирать с помощью перекрестной проверки (например, методом «локтя»), а не угадывать.

3

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

Формула
\hat{y} = \text{mode/mean of the } k \text{ nearest neighbors}

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

  • Пропуск стандартизации признаков, так что одна крупномасштабная переменная неявно контролирует расстояние.
  • Выбор k вручную вместо выбора его с помощью перекрестной проверки.
  • Применение KNN со многими признаками и небольшим количеством наблюдений, где отношение размерности к размеру выборки нарушает его работу.
  • Сообщение только точности вместо точности, полноты, F1-меры и матрицы ошибок.

Часто задаваемые вопросы

Как выбрать значение k?

k следует выбирать с помощью перекрестной проверки, а не угадывать — например, путем перебора диапазона значений и использования метода «локтя» для определения момента, когда ошибка перестает улучшаться. Малое k точно следует данным, но чувствительно к шуму, тогда как большее k сглаживает границу решения.

Почему необходимо стандартизировать признаки?

KNN определяет, кто является «ближайшим», используя расстояние, которое чувствительно к масштабу. Если один признак имеет гораздо больший числовой масштаб, чем другие, он доминирует в расстоянии и искажает набор соседей. Стандартизация признаков (например, с помощью StandardScaler) необходима, чтобы каждый признак вносил справедливый вклад.

Почему KNN плохо работает со многими признаками?

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

Есть ли этап обучения?

Не в обычном смысле. KNN основан на прецедентах (ленивый): он просто хранит обучающие данные и выполняет всю работу на этапе предсказания, когда вычисляет расстояния для поиска ближайших соседей новой точки.

Похожие методы

Источники

  1. Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.

    Открыть ссылку DOI
    Скопировано.