С перекрестной проверкой k-Fold (с нуля)

В этой статье мы поймем, как работает алгоритм k-ближайших соседей (kNN), и построим алгоритм kNN с нуля. Мы также оценим наш алгоритм с помощью перекрестной проверки k-Fold, которая также разработана с нуля.

После прохождения этого урока вы будете знать:

  • Пошаговое кодирование алгоритма k-Nearest Neighbours
  • Как использовать k-ближайших соседей, чтобы сделать прогноз для новых данных
  • Пошаговое руководство по кодированию перекрестной проверки k-Fold
  • Как оценить k-ближайших соседей в реальном наборе данных с помощью k-кратной перекрестной проверки

Предварительные требования: базовое понимание Python и концепции классов и объектов из объектно-ориентированного программирования (ООП).

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

k-Ближайшие соседи, сокращенно kNN, — это очень простой, но мощный метод, используемый для прогнозирования. Принцип kNN заключается в использовании «наиболее похожих исторических примеров на новые данные».

‘k’ – это число, используемое для идентификации похожих соседей для новой точки данных.

Изначально сохраняется весь набор обучающих данных. Когда для новых данных требуются прогнозы, kNN рассматривает k-наиболее похожих соседей (записей), чтобы решить, где новая точка данных будет принадлежать на основе подобия признаков.

Как только мы находим расстояние или сходство, мы выбираем первые k ближайших записей. После обнаружения k ближайших записей мы делаем прогноз, возвращая наиболее распространенный результат или взяв среднее значение. Таким образом, kNN можно использовать для задач классификации или регрессии.

kАлгоритм NN не имеет фазы обучения. Модель просто хранит данные до тех пор, пока не потребуется прогноз, и она не работает. По этой причине kNN часто называют «ленивым методом обучения».

k-ближайшие соседи за 4 простых шага

  1. Выберите значение для k
  2. Найти расстояние от новой точки до каждой записи обучающих данных
  3. Получить k ближайших соседей
  4. Для проблемы классификации новая точка данных принадлежит к классу, к которому принадлежит большинство соседей. Для задачи регрессии прогноз может быть средним или средневзвешенным значением метки k — ближайших соседей.

Создание kNN с нуля с использованием Python

Вы можете продолжить, используя код, доступный в моем GitHub.

Вы также можете установить его, используя:

pip install simple-kNN

Репозиторий GitHub для версии пакета PyPI: https://github.com/chaitanyakasaraneni/simple-kNN

Шаг 1. Выбор значения k

Выбор K сильно влияет на результаты, которые мы получаем из kNN. Лучше выберите нечетное число.

Шаг 2: Расчет расстояния

Следующим шагом является вычисление расстояния между двумя строками в наборе данных.

Методы, специфичные для проблемы или данных, используются для расчета расстояния или сходства между двумя записями. Обычно для табличных или векторных данных евклидово расстояние считается отправной точкой. Есть несколько других показателей сходства или расстояния, таких как манхэттенское расстояние, расстояние Хэмминга и т. д.

Евклидово расстояние определяется как квадратный корень из суммы квадратов расстояния (разности) между двумя точками. Он также известен как норма L2.

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

Расстояние Хэмминга используется для категориальных переменных. Проще говоря, это говорит нам, одинаковы ли две категориальные переменные или нет.

где «δ» используется для проверки равенства двух элементов.

В python мы создаем отдельный класс, который содержит методы для вычисления расстояния между двумя векторами.

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

Шаг 3: Получите ближайших соседей

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

Чтобы найти соседей для новой части данных в наборе данных, мы должны сначала вычислить расстояние между каждой записью в наборе данных и новой частью данных. Мы можем сделать это, создав объект для класса DistanceMetric, который мы определили выше.

После расчета расстояний мы должны отсортировать все записи в обучающем наборе данных по их расстоянию до новых данных. Затем мы можем выбрать верхние k для возврата в качестве наиболее похожих соседей.

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

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

Шаг 4: Прогнозы

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

В случае классификации мы можем вернуть наиболее представленный класс среди соседей.

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

Ниже приведен полный класс kNN:

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

k Сложите перекрестную проверку

Этот метод включает случайное разделение набора данных на k-группы или складки примерно одинакового размера. Первая складка сохраняется для тестирования, а модель обучается на оставшихся k-1 сгибах.

Существует множество вариантов k-Fold Cross Validation. Подробнее о них можно прочитать здесь.

В нашем подходе после каждой кратности мы вычисляем точность, и, таким образом, точность k-Cold CV вычисляется путем усреднения точности по k-кратностям.

Создание kFCV с нуля с использованием Python

В качестве первого шага мы разделяем набор данных на k-сгибов.

Затем для каждой складки в k-складках мы выполняем алгоритм kNN, получаем прогнозы и оцениваем производительность, используя точность в качестве метрики оценки.

Метод разделения данных на k-Folds:

Метод оценки:

Оба метода объединены в один класс:

Мы можем выполнить это, создав объект для метода перекрестной проверки k-Fold и вызвав метод оценки, как показано ниже.

kfcv = kFoldCV()
kfcv.kFCVEvaluate(data, foldCount, neighborCount, distanceMetric)

Затем kfcv.kFCVEvaluate() затем разбивает данные на заданное количество раз и оценивает kалгоритм NN, рассматривая k лучших соседей, используя метод указано расстояниеМетрика.

Примеры и реализацию можно увидеть в моем репозитории GitHub.

Вывод

В этом блоге мы увидели:

  • kNN-алгоритм
  • Некоторые метрики расстояния, используемые в алгоритме kNN
  • Прогнозы с использованием алгоритма kNN
  • Оценка алгоритма kNN с использованием перекрестной проверки kFold

Надеюсь, вы получили некоторые знания, читая эту статью. Пожалуйста, помните, что эта статья является просто обзором и моим пониманием алгоритма kNN и метода перекрестной проверки kFold, которые я прочитал из различных онлайн-источников.