K-ближайшие соседи

K Nearest Neighbor (KNN) — это очень простой, понятный и универсальный алгоритм машинного обучения. Он используется во многих различных областях, таких как обнаружение рукописного ввода, распознавание изображений и распознавание видео. KNN наиболее полезен, когда размеченные данные слишком дороги или их невозможно получить, и он может обеспечить высокую точность в самых разных задачах прогнозирования.

KNN — это простой алгоритм, основанный на локальном минимуме целевой функции, который используется для изучения неизвестной функции с желаемой точностью и правильностью. Алгоритм также находит окрестности неизвестного входа, его диапазон или расстояние от него и другие параметры. Он основан на принципе «прироста информации» — алгоритм выясняет, что лучше всего подходит для предсказания неизвестного значения. K-Nearest Neighbor — один из простейших алгоритмов машинного обучения, основанный на методе контролируемого обучения. Алгоритм K-ближайших соседей (KNN) можно использовать как для классификации, так и для задач прогнозирования регрессии.

Важные факты о КНН

K-Nearest Neighbor — один из простейших алгоритмов машинного обучения, основанный на методе контролируемого обучения.
Алгоритм K-NN предполагает сходство между новым случаем/данными и доступными случаями и помещает новый случай в категорию, наиболее похожую на доступные категории.
Алгоритм K-NN сохраняет все доступные данные и классифицирует новую точку данных на основе сходства. Это означает, что когда появляются новые данные, их можно легко отнести к категории набора скважин с помощью алгоритма K-NN.
Алгоритм K-NN можно использовать как для регрессии, так и для классификации, но в основном он используется для задач классификации.
K-NN — это непараметрический алгоритм, что означает, что он не делает никаких предположений относительно исходных данных.
Его также называют алгоритмом ленивого обучения, потому что он не обучается сразу на обучающем наборе, а сохраняет набор данных и во время классификации выполняет действие над набором данных.
Алгоритм KNN на этапе обучения просто сохраняет набор данных, а когда он получает новые данные, он классифицирует эти данные в категорию, которая очень похожа на новые данные.

КНН работает

Работу K-NN можно объяснить на основе следующего алгоритма:

Шаг 1. Выберите число K соседей.
Шаг 2. Назначьте точку данных, для которой нам нужно предсказать ее класс.
Шаг 3. Вычислите евклидово расстояние для K соседей.
Шаг 4. Возьмите K ближайших соседей в соответствии с вычисленным евклидовым расстоянием.
Шаг 5. Среди этих k соседей подсчитайте количество точек данных в каждой категории.
Шаг 6. Назначьте новые точки данных той категории, для которой максимальное количество соседей.
Шаг 7. Наша модель готова.

Посмотрите на гифку ниже, легко понять, как работает KNN.

Масштабирование данных

K-ближайших соседей (KNN) с евклидовой мерой расстояния чувствителен к величинам и, следовательно, должен масштабироваться, чтобы все объекты имели одинаковый вес. K-Means использует евклидову меру расстояния, здесь имеет значение масштабирование объекта.

Выбор правильного значения для k

Не существует простого метода вычисления значения K в KNN. Вы должны поиграть с различными значениями, чтобы выбрать оптимальное значение K. Выбор правильного значения K — это процесс, называемый настройкой гиперпараметров.

Значение оптимального K полностью зависит от набора данных, который вы используете. Лучшее значение K для KNN сильно зависит от данных. В разных сценариях оптимум К может различаться. Это более или менее метод удара и следа.

Вам нужно соблюдать баланс при выборе значения K в KNN. K не должен быть слишком маленьким или слишком большим.

Небольшое значение K означает, что шум будет иметь большее влияние на результат.

Чем больше значение К, тем выше точность. Если K слишком велико, вы недооцениваете свою модель. В этом случае ошибка снова вылезет. Таким образом, в то же время вам также необходимо предотвратить подгонку вашей модели. Ваша модель должна сохранять возможности обобщения, в противном случае есть большая вероятность того, что ваша модель может хорошо работать с обучающими данными, но резко потерпеть неудачу с реальными данными. Большее K также увеличит вычислительные затраты алгоритма.

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

1. Метод квадратного корня: возьмите квадратный корень из числа выборок в обучающем наборе данных.

2. Метод перекрестной проверки: мы также должны использовать перекрестную проверку, чтобы найти оптимальное значение K в KNN. Начните с K=1, запустите перекрестную проверку (от 5 до 10 раз), измерьте точность и продолжайте повторять, пока результаты не станут согласованными. K=1, 2, 3... При увеличении K ошибка обычно уменьшается, затем стабилизируется, а затем снова возрастает. Выберите оптимум K в начале стабильной зоны. Это также называется методом локтя.

Проклятие размерности

Проклятие размерности означает, что KNN лучше всего работает с небольшим количеством функций. Когда количество функций увеличивается, требуется больше данных. Когда данных больше, это создает проблему переобучения, потому что никто не знает, какая часть шума внесет свой вклад в модель. KNN лучше работает с низкой размерностью (как показало исследование Гу и Шао в 2014 году).

Преимущества KNN

1. Нет периода обучения: KNN называется Lazy Learner (обучение на основе экземпляров). Он ничему не учится в период обучения. Он не выводит какую-либо дискриминационную функцию из обучающих данных. Другими словами, для него не существует периода обучения. Он хранит набор обучающих данных и учится на нем только во время прогнозирования в реальном времени. Это делает алгоритм KNN намного быстрее, чем другие алгоритмы, требующие обучения, например. SVM, линейная регрессия и т. д.

2. Поскольку алгоритм KNN не требует обучения перед выполнением прогнозов, новые данные могут добавляться легко, что не повлияет на точность алгоритма.

3. KNN очень проста в реализации. Для реализации KNN требуются только два параметра, т. е. значение K и функция расстояния (например, евклидова или манхэттенская и т. д.).

Недостатки KNN

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

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

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

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

Заключение

В этой статье объясняются концепции алгоритма KNN. Его классификация и реализация регрессии объясняются в статье «Полное руководство по внедрению классификатора и регрессора KNN».