Введение

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

В этом алгоритме K означает, что мы хотим спрогнозировать, сколько ближайших соседей должны проверить, чтобы назначить новую точку.

Это один из простейших алгоритмов. Он не имеет никаких математических предположений и не требует сложной математики. Также расслабьтесь! В этой статье будет рассмотрена вся математика, которая вам понадобится.

Следует помнить о двух важных вещах:

  1. Вы должны знать, как рассчитать расстояние на самолете.
  2. Мы предполагаем, что точки, расположенные ближе друг к другу, похожи друг на друга.

Чтобы вычислить расстояние до точки на плоскости, мы будем использовать евклидово расстояние. Давайте посмотрим, как рассчитать расстояние между двумя точками.

d - это евклидово расстояние между двумя точками (x1, y1) и (x2, y2). Для расчета расстояния в n-мерном формате формула принимает следующий вид:

Это формула расстояния, которую мы будем использовать для построения алгоритма. Теперь давайте посмотрим алгоритм с простой схемой и разберемся с ним.

Как вы все можете видеть, у нас есть две функции x1 и x2 и две цели - категория A и категория B. Новая точка данных будет видеть, кто находится рядом с ней, а затем в соответствии с новыми точками ей будет назначена категория.

Перед обучением ваши данные должны быть уже масштабированы. Чтобы вычисления были быстрыми, а данные также были нормализованы.

Давайте закодируем KNN!

Хорошо использовать библиотеки машинного обучения, такие как sci-kit, но понимание того, что происходит за кулисами, упрощает достижение того, что мы хотели бы получить. Здесь мы будем использовать несколько библиотек, включая NumPy, sklearn и matplotlib.

  • Numpy - NumPy привносит в Python вычислительную мощность таких языков, как C и Fortran. Это в 50 раз быстрее, чем списки в Python для вычислений.
  • Sklearn - Scikit Learn - это библиотека, в которую встроено множество алгоритмов машинного обучения, а также полезные функции.
  • Matplotlib - используется для построения графика для визуализации данных.

Импорт библиотек

Теперь мы создадим наш тестовый и обучающий набор данных.

Создадим класс для KNN, который будет состоять в основном из трех функций:

  1. Функция Fit - чтобы уместить данные в нашем классе.
  2. Функция расстояния - для расчета расстояния до точек.
  3. Функция прогнозирования - для прогнозирования набора тестов.

Функция расстояния проста, как мы видели в приведенной выше формуле.

Функция соответствия также принимает и назначает набор обучающих данных в классе.

Self.X_train и self.y_train - это обучающие данные, которые мы будем использовать для прогнозирования.

Теперь давайте создадим функцию прогнозирования.

Что такое функция прогнозирования

  1. В одной строке 4 мы вычисляем расстояние со всеми точками на X_train.
  2. Затем он сортирует список расстояний и берет только k ближайших точек.
  3. Затем наиболее распространенная метка берется из выбранных k ближайших точек в строках 6 и 7.

Объединение всех элементов

Постройте график данных в matplotlib с помощью следующего кода:

Точность кода в наборе данных следующая.

Результат для приведенного выше кода будет следующим:

Мы видим, что k = 3 работает лучше всего в нашем случае.

Вы можете попробовать различные значения k и найти оптимальное значение в зависимости от набора данных. Существует несколько методов определения значения k. Один из них - извлечение квадратного корня из числа точек данных (sqrt (n)).

Заключение

KNN - один из самых распространенных алгоритмов, но не лучший из тех, что у нас есть. В нем есть свои плюсы и минусы. Выбирайте алгоритм, помня об этом.

Плюсы

  1. Он будет постоянно развиваться вместе с имеющимися у нас данными. Нам не нужно тренировать его снова и снова, поскольку у нас есть новые точки данных.
  2. KNN не требует обучения и допущений.
  3. Только один набор гиперпараметров (значение k).

Минусы

  1. Его легко реализовать, но он замедляется по мере увеличения объема данных.
  2. Трудно найти оптимальное значение k, так как нам приходится пробовать много значений.
  3. Одной из наиболее важных проблем с K-NN является выбор оптимального количества соседей, которые следует учитывать при классификации новой записи данных.
  4. Требуется много памяти, так как все точки данных тренировки находятся в памяти для расчета расстояния.

Ресурсы

  1. Википедия - KNN
  2. Судешна Саркар - ИИТК - Видео-лекция для понимания алгоритма
  3. Стэнфорд - Временная сложность и оптимальность kNN

Эта статья опубликована в рамках серии ML в веб-среду Клуба исследований и развития пауков, NIT Trichy!