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

На приведенном выше графике (рис. 1) показаны 28 выборок данных, представляющих 28 человек и их цветовые предпочтения. Красная точка - это человек, которому нравится красный цвет, зеленый цвет точки и синий цвет синей точки. Для каждого человека мы знаем годовую зарплату и возраст, чтобы мы могли нарисовать приведенный выше график рассеяния. Цель состоит в том, чтобы предсказать, какой цвет больше всего нравится человеку в возрасте 55 лет с годовым доходом 80 тысяч. Если мы на мгновение задумаемся о том, как получить решение, я предполагаю, что мы посмотрим на ближайшие точки на графике, посчитаем большинство цветов рядом с новой точкой данных и назначим ей этот цвет. В этом случае он будет красным. KNN работает таким же образом для задач классификации и будет делать то же самое, но вычислять среднее значение соседей в задачах регрессии.

Рассмотрим простой пример на рисунке 2. В нашем наборе данных есть 2 зеленых квадрата и 3 красных треугольника. Мы хотим предсказать класс новой точки данных серым цветом. Во-первых, KNN вычислит расстояния от новой точки данных до всех других точек данных и сохранит во внутреннем словаре (расстояния 3, 2,8, 0,5, 2,4 и 5,5). После вычисления расстояния KNN возьмет словарь и сначала отсортирует его с более короткими расстояниями и соответствующим связанным элементом (0,5: квадрат, 2,4: треугольники, 2,8: треугольники, 3: квадрат, 5.5: треугольники). В этом примере пользователь решил реализовать KNN с k, равным 3. Это означает, что KNN будет смотреть на первые 3 элемента отсортированного словаря и подсчитывать элементы по классам. В первых 3 элементах отсортированного словаря есть 1 квадрат и 2 треугольника, поэтому KNN назначит треугольник класса новой точке данных, потому что треугольник является классом большинства в 3 выбранных образцах.

Может возникнуть вопрос: какое число K использовать правильно? В этом примере всего 6 квадратов и 5 треугольников. Вероятность того, что новая точка может быть квадратом, немного выше, и если мы выберем очень большое количество K, которое будет учитывать все обучающие данные, на выходе KNN всегда будет большинство классов, учитывающих весь набор данных. Если мы возьмем небольшое число K, прогноз будет чувствителен к выбросам. Если мы выберем 5, прогноз будет квадратным, но если мы выберем 3, прогноз будет треугольником. Предполагая, что два красных треугольника в центре являются выбросами, выбор k, равного 3, может быть не лучшим выбором. На практике лучший способ выбрать правильное значение K - это попробовать разные значения и выбрать то, которое дает наиболее стабильную точность по сравнению с различными испытаниями. Обратите внимание, что сравнение проводится между тестированием, а не обучением и тестированием, поскольку в KNN (как непараметрическом алгоритме) нет реальной фазы обучения. Обучение и прогнозирование с помощью KNN происходит одновременно, когда KNN выполняет все шаги, упомянутые ранее.

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

Выше есть функция, которую можно использовать для вычисления расстояний до точек в пространстве функций. Длина - это номер измерения набора данных, который будет включать целевую переменную. Итак, ниже мы вычитаем длину на 1. Евклидово расстояние - это один из вариантов, но есть несколько других альтернатив: Scikit Learn предоставляет параметр, называемый p, для изменения метрик расстояния в зависимости от задач.

«getNeighbours» - это функция, которая будет использовать расстояния для создания отсортированного словаря с числом k точек, отсортированных на основе их расстояний до новой точки данных, которую мы хотим спрогнозировать.

Функция getResponse заглянет в словарь, вычислит большинство голосов и выведет прогнозируемое значение. Ключ первого элемента отсортированного ответа.

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

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

* Https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html

* Https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsRegressor.html