Часто нас путают с K-NN, K-means и K-medoids, поскольку эти три используются для дистанционных методов для кластеризации и классификации входных данных. K-ближайший сосед (K-NN) — это контролируемый метод обучения, который объединяет классификацию K ближайших точек для определения классификации точки данных. Его можно использовать как для задач классификации, так и для задач регрессии. Он популярен для задач классификации, поскольку более эффективен для классификации.
Принимая во внимание, что K-means и K-Mediods — это методы обучения без учителя, используемые для группировки группы немаркированных точек данных в небольшие кластеры. Первый учитывает минимизацию общей квадратичной ошибки, а второй фокусируется на минимизации суммы различий между точками, помеченными как находящиеся в кластере.
Ленивый и непараметрический алгоритм
Алгоритм K-NN называется ленивым алгоритмом, потому что в нем отсутствует этап обучения, не создается компактная модель и не выполняются вычисления на обучающих данных. Алгоритм сохраняет только все данные, которые он получает на этапе обучения. Он непараметрический, так как не делает никаких предположений о распределении данных и предсказывает k наиболее похожих шаблонов из обучающего набора данных. Подобные шаблоны могут иметь аналогичные выходные переменные. Если параметрические алгоритмы, например, линейная регрессия, будут иметь предположения о функциях и придерживаться этого предположения. Другими примерами непараметрических алгоритмов являются деревья решений, наивный байесовский подход, SVM, нейронные сети и т. д.
На этапе тестирования используется только метка узлов, и она настраивает несколько параметров. K-NN гибкая и мощная, но поскольку она непараметрическая, она требует большого количества данных, в отличие от параметрической модели, количество параметров не является фиксированным по отношению к размеру выборки, количество параметров может растут с размером выборки, что приводит к сложности и может привести к чрезмерному соответствию модели. Масштабирование функций должно быть выполнено до применения алгоритма KKN, в противном случае точность модели будет скомпрометирована. Масштабирование функций масштабирует все функции, чтобы убедиться, что все они принимают значения в одном масштабе. Это предотвращает доминирование одного признака над другим.
Механизм голосования
Алгоритм KNN использует мажоритарное голосование или механизм взвешенного голосования.
Голосование большинством
В классификации k-NN результатом является членство в классе. Объект классифицируется по множеству голосов его соседей, при этом объект присваивается классу, наиболее распространенному среди его k ближайших соседей (k — положительное целое число, обычно небольшой). Если k = 1, то объект просто присваивается классу этого единственного ближайшего соседа. В регрессии k-NN выходом является значение свойства объекта. Это значение является средним значением k ближайших соседей.
Расчет расстояния
Для голосования по большинству чаще всего используется метрика расстояния Евклидово расстояние. В евклидовом пространстве (евклидово пространство — это основное пространство геометрии, предназначенное для представления физического пространства), евклидово расстояние между двумя точками — это длина отрезка прямой между двумя точками. Его можно вычислить из декартовых координат точек с помощью теоремы Пифагора.
Если мы рассмотрим две точки в евклидовом пространстве, чьи декартовы координаты равны (x1,y1) и (x2,y2), их можно представить следующим образом.
Тогда расстояние между ними можно вычислить, используя теорему Пифагора,
Другими популярными методами измерения расстояний являются манхэттенское расстояние, расстояние Чебышева и расстояние Минковского.
Подробнее о метрике расстояния обучения в scikit и параметре metrics можно прочитать здесь.
Часть кода для настройки классификатора K-NN
Но когда мы используем метрику расстояния как расстояние Минковского и устанавливаем для метрики значение параметра равное 1, это эквивалентно использованию manhattan_distance, а когда значение параметра равно 2, тогда оно эквивалентно используя евклидово_расстояние.
Взвешенное голосование
Здесь функция ядра используется для придания веса точкам данных. Это придаст больший вес близлежащим точкам и меньший вес точкам, которые находятся далеко. В scikit Learn мы можем использовать метрики как «wminkowski» и использовать metric_param для передачи весов.
Переоснащение и недообучение
K-NN универсален, но становится медленнее по мере увеличения признаков, хотя значение k не определяется количеством предсказываемых признаков и классов. Выбор k очень важен и напрямую связан с частотой ошибок. Небольшое значение k означает, что это приведет к переоснащению, а значительное значение make приведет к недообучению, потребует больших вычислительных затрат и противоречит основной идее, лежащей в основе KNN, то есть близкие точки могут иметь одинаковые плотности или классы.
К значение
Параметр по умолчанию для числа соседей k равен 5, и для k всегда предпочтительнее нечетное число. Значение k можно установить с помощью уравнения
Частота ошибок
Частота ошибок — лучший способ проверить K-NN для выбора значения k. Код Python для набора данных Social Network Advertisement от Kaggle можно посмотреть здесь. Мы находим error_rate для разных значений k, используя приведенный ниже код.
После того, как мы нанесем частоту ошибок, мы можем визуально проанализировать error_rate.
Из графика видно, что от К = 5 до К = 18 частота ошибок самая низкая, а при К = 35 частота ошибок максимальная.
Граница решения K-NN
В предсказании K-NN граница не будет выглядеть как гладкая кривая, так как она основана на распределении данных и их относительном расстоянии.
Базовая классификация ближайших соседей использует простое большинство голосов ближайших соседей, где значение весов по умолчанию единообразно. Но когда приходится использовать взвешенное голосование, то присваивается значение параметра weights. Когда веса установлены как расстояние, он будет назначать веса, пропорциональные обратному расстоянию от точки запроса. Мы также можем предоставить определяемую пользователем функцию расстояния для вычисления весов.
Базовая регрессия ближайших соседей использует единые веса, то есть каждая точка в локальном соседстве вносит одинаковый вклад в классификацию точки запроса. Здесь также значение весов по умолчанию является единым, и для использования взвешенного алгоритма веса должны быть назначены как расстояние или предоставлены определяемой пользователем функцией.
Проклятие размерности
В машинном обучении проклятие размерности используется как синоним феномен пика, который также известен как феномен Хьюза. Это явление гласит, что при фиксированном количестве обучающих выборок средняя (ожидаемая) прогностическая способность классификатора или регрессора сначала увеличивается по мере увеличения количества используемых измерений или признаков, но после определенной размерности она начинает ухудшаться, а не постоянно улучшаться. В абстрактном смысле, по мере роста количества признаков или измерений объем данных, которые нам необходимо точно обобщить, растет экспоненциально.
Классификатор k-NN делает предположение, что похожие точки имеют одинаковые метки. Но в многомерных данных близкие точки могут быть далеко, что противоречит предположению K-NN. Таким образом, здесь можно использовать отбор признаков и уменьшение размерности, чтобы преодолеть проклятие размерности.
Ссылка
https://github.com/SandKrish/Classification/blob/main/knn-svm-svm-with-kernel-hyperparameter.ipynb
