Как построить KNN с нуля на Python

… Ну, по крайней мере, без KNeighborsClassifier от sklearn.

k-Ближайшие соседи

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

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

Для упрощенного примера см. Рисунок ниже. На левой панели показан двухмерный график шестнадцати точек данных - восемь отмечены зеленым цветом, а восемь - фиолетовым. Теперь правая панель показывает, как мы классифицируем новую точку (черный крест), используя KNN, когда k = 3. Мы находим три ближайших точки и подсчитываем, сколько «голосов» у каждого цвета в пределах этих трех точек. В этом случае две из трех точек будут фиолетовыми, поэтому черный крест будет помечен как фиолетовый.

Расчет расстояния

Расстояние между точками определяется с помощью одной из нескольких версий уравнения расстояния Минковского. Обобщенную формулу для расстояния Минковского можно представить следующим образом:

где X и Y - точки данных, n - количество измерений, а p - параметр мощности Минковского. . Когда p = 1, расстояние известно на манхэттенском расстоянии (или в такси), а когда p = 2, расстояние известно как евклидово расстояние. В двух измерениях манхэттенские и евклидовы расстояния между двумя точками легко визуализировать (см. График ниже), однако при более высоких порядках p расстояние Минковского становится более абстрактным.

KNN в Python

Чтобы реализовать мою собственную версию классификатора KNN в Python, я сначала хочу импортировать несколько распространенных библиотек, которые помогут.

Загрузка данных

Чтобы протестировать классификатор KNN, я собираюсь использовать набор данных радужной оболочки глаза из sklearn.datasets. В наборе данных есть измерения (длина чашелистики, ширина чашелистиков, длина лепестков, ширина лепестков) для 150 растений ириса, поровну разделенных между тремя видами (0 = сетоза, 1 = разноцветный и 2 = вирджиника). Ниже я загружаю данные и сохраняю их во фрейме данных.

Я также разделю данные на характеристики (X) и целевую переменную (y), которая является обозначением вида для каждого растения.

Создание структуры KNN

Создание функционирующего классификатора KNN можно разбить на несколько этапов. Хотя KNN включает в себя немного больше нюансов, вот мой краткий список дел:

1. Определите функцию для вычисления расстояния между двумя точками
2. Используйте функцию расстояния, чтобы получить расстояние между контрольной точкой и всеми известными точками данных.
3. Отсортируйте измерения расстояний, чтобы найти точки, ближайшие к контрольной точке (т. Е. Найти ближайших соседей)
4. Используйте метки большинства классов ближайших точек, чтобы предсказать метку контрольной точки.
5. Повторите шаги с 1 по 4, пока не будут классифицированы все точки тестовых данных.

1. Определите функцию для вычисления расстояния между двумя точками.

Сначала я определяю функцию под названием minkowski_distance, которая принимает на входе две точки данных (a и b) и параметр мощности Минковского p, и возвращает расстояние между двумя точками. Обратите внимание, что эта функция вычисляет расстояние точно так же, как формула Минковского, о которой я упоминал ранее. Сделав p регулируемым параметром, я могу решить, хочу ли я рассчитать Манхэттенское расстояние (p = 1), Евклидово расстояние (p = 2) или расстояние Минковского более высокого порядка.

0.6999999999999993

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

На шаге 2 я просто повторяю вычисление minkowski_distance для всех отмеченных точек в X и сохраняю их во фрейме данных.

3. Отсортируйте измерения расстояний, чтобы найти точки, ближайшие к контрольной.

На шаге 3 я использую метод pandas .sort_values ​​() для сортировки по расстоянию и возвращаю только 5 лучших результатов.

4. Используйте метки классов большинства ближайших точек, чтобы предсказать метку контрольной точки.

На этом этапе я использую collections.Counter, чтобы отслеживать метки, совпадающие с ближайшими соседними точками. Затем я использую метод .most_common (), чтобы получить наиболее часто встречающуюся метку. Примечание: если есть связь между двумя или более метками для заголовка «наиболее распространенной» метки, будет возвращена метка, с которой первым столкнулся объект Counter ().

1

5. Повторяйте шаги с 1 по 4, пока не будут классифицированы все контрольные точки данных.

На этом этапе я использую уже написанный код и пишу функцию для классификации данных с помощью KNN. Сначала я выполняю train_test_split для данных (75% поезд, 25% тест), а затем масштабирую данные с помощью StandardScaler (). Поскольку KNN основан на расстоянии, важно убедиться, что функции правильно масштабированы, прежде чем вводить их в алгоритм.

Кроме того, чтобы избежать утечки данных, рекомендуется масштабировать функции после выполнения train_test_split. Сначала масштабируйте только данные из обучающего набора (scaler.fit_transform (X_train)), а затем используйте эту информацию для масштабирования тестового набора (scaler.tranform (X_test)). Таким образом, я могу гарантировать, что для создания модели не будет использоваться никакая информация за пределами обучающих данных.

Затем я определяю функцию под названием knn_predict, которая принимает все данные обучения и тестирования, k и p, и возвращает мои прогнозы. Классификатор KNN составляет набор тестов (y_hat_test). Эта функция на самом деле не содержит ничего нового - она ​​просто применяет то, что я уже проработал выше. Функция должна возвращать список подсказок ярлыков, содержащий только 0, 1 и 2.

[0, 1, 1, 0, 2, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 0, 1, 1, 0, 0, 1, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 2, 1, 2, 2, 0, 1, 0]

И вот они! Это прогнозы, которые этот домашний классификатор KNN сделал на тестовом наборе. Посмотрим, насколько хорошо это сработало:

0.9736842105263158

Похоже, классификатор на тестовой выборке достиг точности 97%. Совсем неплохо! Но как мне узнать, правильно ли оно сработало? Давайте проверим результат KNeighborsClassifier sklearn на тех же данных:

Sklearn KNN Accuracy: 0.9736842105263158

Отлично! Реализация классификатора KNN в sklearn дает нам точно такую ​​же оценку точности.

Изучение эффекта изменения k

Мой классификатор KNN работал достаточно хорошо с выбранным значением k = 5. KNN не имеет такого количества настраиваемых параметров, как другие алгоритмы, такие как деревья решений или случайные леса, но k оказался одним из них. Давайте посмотрим, как меняется точность классификации при изменении k:

В этом случае использование почти любого значения k меньше 20 приводит к высокой (›95%) точности классификации на тестовом наборе. Однако, когда k становится больше примерно 60, точность действительно начинает падать. Это имеет смысл, потому что набор данных содержит только 150 наблюдений - когда k настолько велик, классификатор, вероятно, рассматривает помеченные точки обучающих данных, которые находятся слишком далеко от контрольных точек.

У каждого соседа есть голос - или нет?

При написании моего собственного классификатора KNN я решил упустить одну явную возможность настройки гиперпараметров: вес, который каждая из ближайших k точек имеет при классификации точки. В KNeighborsClassifier sklearn это параметр weights, и для него может быть установлено значение 'uniform', 'distance' или другую пользовательскую функцию.