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

Вы можете видеть на изображении выше, тестовый образец (зеленый кружок) должен быть отнесен либо к первому классу синих квадратов, либо ко второму классу красных треугольников. два треугольника и только один квадрат внутри внутреннего круга. Если K=5 (штриховая линия круга), он относится к первому классу (3 квадрата против 2 треугольников внутри внешнего круга).

k-NN — это тип обучения на основе экземпляров или ленивого обучения, при котором функция только аппроксимируется локально, а все вычисления откладываются до классификации. Алгоритм k-NN — один из самых простых из всех алгоритмов машинного обучения.

Выбор параметра (значение K)

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

На приведенном выше изображении вы можете видеть, что граница становится более гладкой с увеличением значения K. Когда K увеличивается до бесконечности, она, наконец, становится полностью синей или полностью красной в зависимости от общего большинства. Частота ошибок обучения и частота ошибок проверки — это два параметра, к которым нам нужно получить доступ для разных значений K. Частота ошибок при K = 1 всегда равна нулю для обучающей выборки. Это связано с тем, что ближайшая точка к любой точке обучающих данных — это она сама. Следовательно, прогноз всегда точен при K = 1. Если бы кривая ошибок валидации была бы аналогичной, наш выбор K был бы равен 1. Один классификатор ближайших соседей гарантирует частоту ошибок не хуже, чем удвоенная байесовская частота ошибок (минимально достижимая частота ошибок с учетом распределения данных). .

Точность алгоритма k-NN может сильно снизиться из-за наличия зашумленных или нерелевантных признаков или если шкалы признаков не соответствуют их важности. Много усилий было направлено на выбор или масштабирование признаков для улучшения классификации. Особенно популярным подходом является использование эволюционных алгоритмов для оптимизации масштабирования признаков. Другой популярный подход заключается в масштабировании функций с помощью взаимной информации обучающих данных с обучающими классами.[требуется цитирование]

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

Алгоритм

Пусть m будет количеством выборок обучающих данных. Пусть p неизвестная точка.

  1. Сохраните обучающие образцы в массиве точек данных arr[]. Это означает, что каждый элемент этого массива представляет кортеж (x, y).
for i=0 to m: Calculate Euclidean distance d(arr[i], p).

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

3. Вернуть метку большинства среди S.

Реализация на питоне

Здесь 0 и 1 - две группы классификатора.

На наборе данных Iris вы можете выполнить построение модели KNN. Вы можете найти набор данных здесь. Ниже приведена реализация для этого на Python.

Плюсы и минусы

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

Недостатком является ленивый алгоритм обучения.

Счастливого обучения… 😄