Смотрите видео пояснения к этой статье здесь.

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

Мы начнем с классификации, потому что она в основном используется для решения задач классификации.

KNN для классификации:

Проблема классификации может быть бинарной классификацией или многоклассовой классификацией. Здесь для простоты мы берем бинарную классификацию, но идея будет такой же и для многоклассовой классификации.

Предположим, что набор обучающих данных имеет распределение данных, как показано на изображении выше, есть два класса: положительный класс (желтые точки) и отрицательный класс (красные точки). Теперь, когда новая точка данных поступает в KNN, она должна сообщить, что новая точка данных принадлежит к какому классу?. На изображении выше q — это новая точка данных.

Как работает КНН?

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

Теперь мы знаем, как работает knn, но для чего в алгоритме используется K?

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

Посмотрим визуально, как это работает.

На изображении выше мы можем видеть новую точку данных «q» с K = 3, мы получили 2 точки положительного класса рядом с ней и 1 отрицательный класс, и, поскольку большинство относится к положительному классу, мы назовем эту новую точку данных a положительная точка данных класса. Точно так же мы можем попробовать разные значения K, чтобы увидеть, какое из них хорошо работает для набора данных.

Теперь на ум приходит один вопрос: что, если K = 2 и 1 ближайшая точка данных принадлежит к положительному классу, а другая принадлежит к отрицательному классу, то как мы можем разорвать связь?

Таким образом, лучший способ решить эту проблему — установить K числами, которые не делятся на количество классов в наборе данных.

Неудачи KNN:

  1. Если точка запроса (новая точка данных) очень далека от фактических точек данных, не очевидно, чтобы решить, является ли класс большинства правильным или нет.

На изображении выше мы видим, что точка запроса «q» очень далека от всех точек данных, поэтому очень сложно решить, является ли мажоритарный класс, который в данном случае является Отрицательным, правильным или нет.

2. Если точки данных всех классов смешаны вместе. Классифицировать будет практически невозможно.

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

Мы много говорили о работе knn, значении «K» и случаях отказа knn. Но как knn решить, какая точка данных ближе к ней? Для этого knn использует некоторые методы измерения расстояния.

Давайте посмотрим на некоторые методы измерения расстояния, используемые KNN:

Меры расстояния:

Евклидово расстояние:

Поскольку евклидово расстояние использует простую теорему Пифагора для вычисления расстояния между двумя точками, оно также известно как «расстояние Пифагора».

Евклидово расстояние также известно как норма L2.

Манхэттен Расстояние:

В манхэттенском расстоянии мы берем абсолютное расстояние между двумя точками. Манхэттенское расстояние похоже на добавление расстояния блоков между двумя точками.

Он добавляет расстояние |P1 →Q1| и |P2 →Q2|.

Манхэттенское расстояние также известно как норма L1.

Расстояние Минковского:

Расстояние Минковского — это обобщенная форма, с помощью которой мы можем достичь как евклидова расстояния, так и манхэттенского расстояния.

Он также известен как Lp-Норма.

В формуле расстояния Минковского, если мы поместим значение p = 1, оно станет формулой манхэттенского расстояния, аналогично, если мы положим p = 2, оно станет формулой евклидова расстояния.

KNN В пакете scikit-learn есть параметр p, который используется для изменения метрики расстояния по умолчанию. Метрика расстояния Минковского используется с p = 2, поэтому расстояние становится евклидовым. Поэтому, если вы не измените параметр p в классификаторе KNN, он будет использовать евклидово расстояние.

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

Случаи переобучения и недообучения в KNN:

Переоснащение:

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

Поэтому, если значение K меньше, это приведет к переоснащению.

Недооснащение:

Если значение K очень велико, это приведет к недообучению.

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

Таким образом, большое значение K никогда не является хорошей идеей в KNN.

Мы всегда должны пытаться найти компромисс между переоснащением и недообучением.

Регрессия в KNN:

Регрессия в KNN также очень проста.

Шаг 1: Получите ближайших соседей точки запроса. Допустим, целевые метки ближайших точек данных (y1, y2, y3).

Шаг 2. Вычислите среднее значение (y1,y2,y3) и получите результаты регрессии для точки запроса. Здесь мы рассматриваем K=3, поэтому у нас есть только три зависимые точки (y1,y2,y3)

Теперь давайте посмотрим на некоторые ограничения KNN.

Ограничения КНН:

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

Надеюсь, вам понравилось читать! 🤗