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

Как KNN работает под капотом?

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

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

Обратите внимание на графике выше, как большинство похожих точек данных расположены близко друг к другу. Алгоритм KNN основан на том, что это предположение достаточно верно для того, чтобы алгоритм был полезен при выполнении прогнозов.

Итак, давайте начнем с внедрения KNN всего за 3 шага:

  1. Вычислите расстояние d между точкой данных запроса q и каждой точкой данных обучения xᵢ. Евклидово расстояние является наиболее распространенной мерой расстояния, используемой в KNN (также по умолчанию предоставляется библиотекой scikit learn), но расстояния Манхэттена, Минковского или Хэмминга работают так же.

2. Отсортируйте расстояния в массиве по возрастанию и выберите K ближайших расстояний (первых Kentries) из этого массива. Это будут K ближайшие соседи к заданной точке данных запроса q.

3. Получите метки классов выбранных K соседей (значения yᵢ). Наиболее распространенная метка (метка с большинством голосов) будет прогнозируемой меткой для нашей точки данных запроса q.

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

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

Реализация Python без scikit-learn:

Я буду использовать надежный набор данных iris и Google Colab. Набор данных диафрагмы можно скачать здесь.

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

Давайте сравним этот код с реализацией sklearn:

Результат при k = 5 с использованием sklearn будет точно таким же. В обоих случаях прогнозируемое значение - Iris-virginica, а соседние - [141, 139, 120, 145, 144].

Как найти оптимальное значение K?

Одна из наиболее важных вещей, которые следует учитывать при реализации алгоритма KNN, - это то, как выбрать k значение и как разные k значения влияют на производительность модели.

На приведенном выше графике, когда k=16 предсказанная метка класса равна X, в то же время, когда k=8 предсказанная метка класса равна Y. Итак, теперь мы можем сделать вывод, что значение k оказывает значительное влияние на производительность модели.

Малое значение k означает, что шум будет сильнее влиять на результат, а большое значение делает его дорогостоящим в вычислительном отношении.

Специалисты по данным обычно выбирают:

  1. Нечетное число в случае проблем с двоичной классификацией.

2. Другой простой способ выбора k установлен k=sqrt(n). где n = количество точек данных в обучающих данных.

Вот замечательная статья Эйми Бэнд о том, как выбрать оптимальное значение k, если вы хотите глубоко погрузиться:



Как найти оптимальное значение K в KNN?
Визуализируйте график зависимости коэффициента ошибок от K, чтобы найти наиболее подходящее значение K. todatascience.com



Это все на сегодня. Увидимся в следующей статье.

Вы можете найти код и данные для этого руководства в моем GitHub здесь.

Использованная литература:

[1] https://towardsdatascience.com/how-to-find-the-optimal-value-of-k-in-knn-35d936e554eb

[2] https://www.analyticsvidhya.com/blog/2018/03/introduction-k-neighbours-algorithm-clustering/

Я учусь и пишу то, что узнал о машинном обучении, статистике и глубоком обучении. Следуйте за мной в моем путешествии в мир искусственного интеллекта Twitter, LinkedIn, Medium.