Сегодня мы узнаем об алгоритме KNN, его приложениях, интуиции за ним и его реализации с набором данных MNIST.

Вступление

KNN или K-Nearest Neighbours - это контролируемый алгоритм классификации, который так же прост в отношении алгоритма, как и его название. Этот алгоритм классифицирует данный экземпляр на основе групп окружающих его «K» соседей. Например,

Предположим, вам даны 2 группы: еда и средство передвижения. Вам была поставлена ​​задача классифицировать яблоко в любой из групп, тогда расстояние между яблоком и другими продуктами питания будет меньше по сравнению с группой транспортных средств. Это потому, что они будут иметь большее сходство по характеристикам, чем по сравнению с группой транспортных средств. Если не понимаешь, не волнуйся. Мы выясним это позже. А пока вы можете полюбоваться красивыми визуальными эффектами, приведенными ниже:

Где это используется?

Его лучше всего использовать, если набор данных:

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

Приложения:

  • Используется при распознавании лиц. Вы можете использовать этот алгоритм, чтобы оценить сходство между вашими тестовыми примерами и обучающим набором и, соответственно, «пометить» или «классифицировать» тестовое изображение.
  • Используется в системах рекомендаций: во время покупок в Интернете он сортирует для вас похожие товары на основе ваших прошлых покупок или поисковых запросов.
  • Используется в розничной торговле для распознавания образов, чтобы избежать мошенничества с кредитными картами и краж.
  • Классификация изображений

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

Почему это называется «обучение на основе экземпляров»?

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

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

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

Точно так же в алгоритме KNN мы сравниваем тестовый набор и обучающий набор на основе их характеристик. Это сравнение производится математически путем вычисления евклидовых расстояний между ними.

Что такое К и как его найти?

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

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

Значение K не должно быть слишком большим, поскольку это приведет к увеличению объема вычислений и увеличению времени обработки. Однако, если мы возьмем его слишком маленьким, это может привести к нестабильным прогнозам.

Реализация и шаги

Давайте перейдем к шагам, которые помогут лучше понять реализацию:

  • Нам дается набор данных и тестовый экземпляр для классификации. Таким образом, мы должны вычислить различия в функциях для каждой строки в нашем обучающем наборе с помощью нашего тестового экземпляра.
  • Эти различия возводятся в квадрат и складываются для каждой строки, чтобы определить, насколько «близок» каждый экземпляр в обучающих данных к нашему тестовому экземпляру. Это евклидово расстояние.
  • Мы сортируем эти расстояния в порядке возрастания и выбираем первых K соседей.
  • По этим соседям мы видим, какая группа имеет большинство соседей. Эта группа - наш результат.

Ниже приведена реализация алгоритма KNN на наборе данных MNIST.

Набор данных MNIST (Модифицированный национальный институт стандартов и технологий) предоставляет нам изображения цифр от 0 до 9, написанные разными почерками. У него 60 000 изображений в наборе для обучения и 10 000 изображений в наборе для тестирования.

(скриншоты ниже взяты из google colab)

  • Сначала импортируем необходимые библиотеки для реализации.

  • Если есть нулевые значения, вы можете заполнить их нулями или средним значением от 0 до 255, то есть 128.

  • Функция KNNClassifier () вычисляет расстояние между нашим тестовым экземпляром и каждым из наших обучающих экземпляров.
  • В списке соседи хранится кортеж (метка, расстояния). Здесь метка - это число от 0 до 9, представленное значениями в этой строке.
  • Мы сортируем список соседей по расстоянию и проверяем метку, на которой находится большинство наших K соседей.
  • count - это словарь, в котором хранится количество экземпляров каждой метки среди этих K соседей.

  • testAccuracy () проверяет, сколько из наших прогнозов совпадает с нашим тестовым набором, а затем вычисляет процентную точность.
  • plotAccuracy () строит график зависимости «точности» от «K-значений» с использованием библиотеки matplotlib.

В приведенном выше фрагменте кода

  • В списке прогнозов хранятся все метки, предсказанные нашим классификатором.
  • для каждой строки в нашем тестовом наборе мы инициализируем значения в словаре count равным 0. Ключи здесь - это числа от 0 до 9.
  • После завершения всех итераций для конкретного K мы проверим его точность и сохраним в нашем списке precision_val.
  • Обратите внимание, что я использовал все нечетные значения для K.

Вывод для выше:

Матрица путаницы

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

Мы объясним приведенные выше термины на примере. Предположим, что врач ставит диагноз пациентам с сахарным диабетом. В этом сценарии

Ложноположительные результаты: врач предсказал, что у пациента диабет, хотя на самом деле это неправда.

Ложноотрицательные результаты: врач предположил, что у пациента нет диабета, но это предположение неверно.

Верно положительный: врач диагностирует у пациента диабет, и это оказывается правдой.

Верно отрицательный: врач диагностирует, что у пациента нет диабета, и это оказывается правдой.

Это все на сегодня. Я надеюсь, что вы кое-что из этого узнали. Спасибо за чтение моего блога!!!