Метод 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). В малых или высокоразмерных выборках доминирует проклятие размерности — расстояния до соседей становятся неинформативными — и параметрическая модель, такая как логистическая регрессия или наивный байесовский классификатор, является лучшим выбором.
Ограничения и замечания
- Чувствителен к масштабированию признаков; без стандартизации крупномасштабные признаки доминируют в расстоянии.
- Быстро деградирует в высоких размерностях («проклятие размерности»), где расстояния до соседей теряют смысл.
- Каждое предсказание требует сканирования всего обучающего набора, что медленно при предсказании на больших данных.
- Требуется как минимум умеренный размер выборки; в малых выборках расстояния до ближайших соседей не имеют смысла.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Концептуально прост и легко объясним: нет уравнения, подгоняемого на этапе обучения, данные являются моделью.
- Непараметрический — не делает предположений о базовом распределении.
- Естественным образом обрабатывает многоклассовые задачи и сложные, нелинейные границы решений.
- Работает как для классификации, так и для регрессии с одной и той же базовой идеей.
Применение
- Классификация табличных данных на две или более категории.
- Численное предсказание (регрессия) путем усреднения ближайших примеров.
- Простая, интерпретируемая базовая модель перед попыткой более сложных моделей.
- Распознавание образов, где сходство с известными примерами определяет решение.
Как это работает
Как это работает
Для нового наблюдения KNN измеряет его расстояние до каждого обучающего примера, обычно используя евклидово расстояние по всем признакам. Поскольку расстояние чувствительно к масштабу, признаки должны быть сначала стандартизированы — в противном случае переменная, измеренная в большом числовом масштабе, будет доминировать в расчете и искажать выбор ближайших соседей.
Формула
d(x, x_i) = \sqrt{\sum_{j=1}^{p}(x_j - x_{ij})^2}k обучающих точек с наименьшими расстояниями до нового наблюдения выбираются в качестве его соседей. Значение k контролирует локальность решения: малое k точно следует данным, но чувствительно к шуму, тогда как большее k сглаживает границу. k следует выбирать с помощью перекрестной проверки (например, методом «локтя»), а не угадывать.
Соседи определяют предсказание: для классификации новая точка принимает наиболее распространенный класс среди своих 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 основан на прецедентах (ленивый): он просто хранит обучающие данные и выполняет всю работу на этапе предсказания, когда вычисляет расстояния для поиска ближайших соседей новой точки.
Похожие методы
Источники
Cover, T.M. & Hart, P.E. (1967). Nearest Neighbor Pattern Classification. IEEE Transactions on Information Theory, 13(1), 21–27.
Открыть ссылку DOIСкопировано.