Что такое K-ближайший сосед? Алгоритм машинного обучения для классификации данных

Алгоритмы управляют миром машинного обучения.

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

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

Что такое алгоритм k ближайших соседей?

Алгоритм k-ближайших соседей (KNN) — это метод классификации данных для оценки вероятности того, что точка данных станет членом той или иной группы на основе того, к какой группе принадлежат ближайшие к ней точки данных.

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

KNN — это алгоритм с ленивым обучением и непараметрическим алгоритмом.

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

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

Предположим, что есть две группы: А и В.

Чтобы определить, находится ли точка данных в группе A или группе B, алгоритм просматривает состояния точек данных рядом с ней. Если большинство точек данных находится в группе A, весьма вероятно, что рассматриваемая точка данных находится в группе A, и наоборот.

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

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

Как работает КНН?

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

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

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

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

Чтобы представить это в перспективе, рассмотрим неклассифицированную точку данных X. На точечной диаграмме есть несколько точек данных с известными категориями A и B.

Предположим, что точка данных X расположена рядом с группой A.

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

В этом случае точка данных X принадлежит к группе A, поскольку ее ближайший сосед находится в той же группе. Если группа A имеет более десяти точек данных и значение K равно 10, то точка данных X по-прежнему будет принадлежать группе A, поскольку все ее ближайшие соседи находятся в одной группе.

Предположим, что еще одна неклассифицированная точка данных Y помещена между группой A и группой B. Если K равно 10, мы выбираем группу, получившую наибольшее количество голосов, что означает, что мы относим Y к группе, в которой она имеет наибольшее количество соседей. Например, если у Y семь соседей в группе B и три соседа в группе A, он принадлежит к группе B.

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

Вам может быть интересно, как рассчитывается метрика расстояния, чтобы определить, является ли точка данных соседней или нет.

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

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

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

Зачем использовать алгоритм KNN?

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

Вот некоторые области, в которых можно использовать алгоритм k-ближайших соседей:

• Кредитный рейтинг: Алгоритм KNN помогает определить кредитный рейтинг человека, сравнивая его с людьми с аналогичными характеристиками.
• Одобрение ссуды: Подобно кредитному рейтингу, алгоритм k-ближайшего соседа полезен для выявления лиц, которые с большей вероятностью не выплатят ссуду, путем сравнения их характеристик с аналогичными людьми.
• Предварительная обработка данных: в наборах данных может быть много пропущенных значений. Алгоритм KNN используется для процесса, называемого вменением отсутствующих данных , который оценивает отсутствующие значения.
• Распознавание образов: Способность алгоритма KNN идентифицировать закономерности создает широкий спектр приложений. Например, он помогает обнаруживать закономерности в использовании кредитных карт и выявлять необычные закономерности. Обнаружение закономерностей также полезно для выявления закономерностей в покупательском поведении клиентов.
• Прогноз цен на акции: поскольку алгоритм KNN умеет прогнозировать стоимость неизвестных объектов, он полезен для прогнозирования будущей стоимости акций на основе исторических данных.
• Системы рекомендаций: поскольку KNN может помочь найти пользователей со схожими характеристиками, его можно использовать в системах рекомендаций. Например, его можно использовать на онлайн-платформе потокового видео, чтобы предлагать контент, который пользователь с большей вероятностью посмотрит, анализируя то, что смотрят похожие пользователи.
• Компьютерное зрение: алгоритм KNN используется для классификации изображений. Так как он способен группировать схожие точки данных, например, объединяя кошек и собак в разные классы, он полезен в нескольких случаях.   компьютерное зрение   Приложения.

Как выбрать оптимальное значение K

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

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

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

Другой способ выбрать оптимальное значение K — вычислить sqrt(N), где N обозначает количество выборок в наборе обучающих данных.

Однако K с более низкими значениями, такими как K=1 или K=2, может быть зашумленным и подвергаться влиянию выбросов. Вероятность переобучения в таких случаях также высока.

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

Преимущества и недостатки КНН

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

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

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

KNN и проклятие размерности

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

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

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

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

KNN не работает, если функций слишком много. Следовательно, методы уменьшения размерности, такие как анализ основных компонентов (PCA) и выбор признаков , должны выполняться на этапе подготовки данных.

KNN: ленивый алгоритм, покоривший сердца

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

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