K ближайших соседей (KNN) — один из самых простых алгоритмов машинного обучения с учителем. Первоначально алгоритм был разработан для задач классификации, но позже был расширен и для выполнения задач регрессии.
В отличие от других контролируемых алгоритмов машинного обучения, KNN не имеет базовой модели, и алгоритм работает исключительно с сохраненными обучающими данными.
KNN пытается предсказать значения на основе расстояний каждой точки тестовых данных от набора обучающих данных. Следовательно, алгоритм не делает никаких предположений относительно функций или вывода данных.
Из-за такой природы алгоритма, когда он начинает работать и делает прогноз только после введения тестовых данных, он также известен как Ленивый ученик.
Помимо задач классификации и регрессии, алгоритм KNN также используется для вменения пропущенных значений, повторной выборки наборов данных, обнаружения выбросов и т. д. Некоторые из промышленных приложений KNN включают создание системы рекомендаций, распознавание рукописного ввода, распознавание изображений и т. д.
Существует несколько подходов к поиску K ближайших соседей, таких как K-мерное дерево, в котором для классификации точек данных используется прямоугольная граница решения, Ball-tree, в котором используется сферическая граница решения и т. д. В этой статье мы реализуем подход грубой силы к KNN с использованием Python с нуля.
Алгоритм
Итак, шаги по созданию модели KNN следующие:
- Для начала нам нужно оптимальное значение K.
- Рассчитайте расстояние между каждой точкой данных в тестовом наборе и каждой точкой в обучающем наборе.
- Отсортируйте рассчитанные расстояния вместе с соответствующими целевыми значениями из обучающих данных в порядке возрастания.
- Из этих отсортированных значений выберите K верхних значений.
- Для задач классификации режим точек данных, соответствующих K верхним строкам, будет прогнозируемым результатом, а для задач регрессии прогнозируемым результатом будет среднее/медиана.
Реализация с нуля
Давайте создадим базовую структуру нашего алгоритма KNN. Мы будем следовать подходу Scikit-learn и определим класс с методом подгонки и прогнозирования.
Мы инициализируем наш экземпляр класса, используя количество соседей, тип проблемы и метрику оценки.
Тип проблемы решит, будет ли это регрессия или задача классификации, а метрика решит, какую метрику расстояния следует использовать для расчета расстояний.
На данный момент мы назначим тип проблемы 0 для регрессии и 1 для классификации. И метрика 0 для евклидова расстояния и 1 для манхэттенского расстояния.
В нашем методе подгонки мы подгоним алгоритм к функциям обучающих данных и цели.
Внутри нашего метода прогнозирования, который принимает данные тестовых функций в качестве аргумента, нам нужно выполнить 3 дополнительных шага.
- Сначала рассчитаем расстояния.
- Затем вычисляем соседей.
- Наконец, мы делаем прогноз.
Код говорит сам за себя.
Собрав все вместе, у нас есть алгоритм BruteForceKNN.
Давайте теперь попробуем реализовать KNN, используя библиотеку обучения Scikit, и рассчитаем показатели классификации. Затем мы реализуем наш BruteForceKNN для тех же данных и сравним, как он работает с реализацией обучения Scikit.
Тестирование с реализацией Scikit-learn
Давайте импортируем необходимые библиотеки и зависимости.
Теперь давайте загрузим данные радужной оболочки из наборов данных обучения Scikit. Затем мы разделим данные и используем стандартное масштабирование для масштабирования наших данных.
Теперь нам нужно найти оптимальное значение «k».
Для этого мы создадим экземпляр базового классификатора KNN с настройками по умолчанию и сделаем прогнозы для значений «k» в диапазоне от 1 до 31.
Затем мы рассчитаем ошибки поезда и теста и построим кривую ошибок. С помощью кривой ошибок мы найдем оптимальное значение «k».
Из кривой ошибок мы находим, что k=14 хорошо подходит для наших данных. Итак, мы создаем экземпляр объекта KNN с k = 14, подбираем обучающие данные и прогнозируем, используя тестовые данные.
Теперь давайте построим матрицу путаницы и проверим другие показатели классификации.
Тестирование с использованием нашего Brute Force KNN
Теперь мы создадим экземпляр нашего класса BruteForceKNN и будем делать прогнозы с теми же данными.
Отлично. Точность нашей модели соответствует реализации Scikit-learn. Теперь давайте проверим матрицу путаницы.
Мы обнаружили, что производительность нашей модели BruteForceKNN точно соответствует реализации классификатора KNN, разработанной Scikit-learn.
На этом мы подошли к концу этой статьи.
Надеюсь, вам понравилось изучать и реализовывать алгоритм KNN с нуля в Python и сравнивать производительность модели с API Scikit-learn.
Если вам понравилась эта статья, подпишитесь на меня, чтобы получать больше интересных и действенных постов.
