K-ближайшие соседи (KNN): что это такое и как оно используется в машинном обучении

K-ближайшие соседи (KNN) — это основополагающий метод машинного обучения (ML). Это руководство поможет вам понять KNN, как он работает, а также его применение, преимущества и проблемы.

Оглавление

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

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

Разница между k-ближайшими соседями и другими алгоритмами

Как KNN используется в машинном обучении?

Приложения КНН

Преимущества КНН

Недостатки КНН

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

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

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

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

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

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

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

• Евклидово расстояние— это расстояние по прямой между двумя точками в пространстве, которое является наиболее часто используемой метрикой. Его лучше всего использовать для данных с меньшим количеством измерений и без значительных выбросов.
• Манхэттенское расстояниепредставляет собой сумму абсолютных разностей между координатами измеряемых точек данных. Эта метрика полезна, когда данные многомерны или когда точки данных образуют структуру, подобную сетке.
• Расстояние Минковского— это настраиваемая метрика, которая может действовать как евклидово или манхэттенское расстояние в зависимости от значения настраиваемого параметра. Настройка этого параметра контролирует способ расчета расстояния, что полезно для адаптации KNN к различным типам данных.

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

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

Разница между k-ближайшими соседями и другими алгоритмами

KNN является частью более крупного семейства контролируемых методов машинного обучения, ориентированных на классификацию и регрессию, которое включает в себя деревья решений/случайные леса, логистическую регрессию и машины опорных векторов (SVM). Однако KNN отличается от этих методов, среди прочего, своей простотой и прямым подходом к обработке данных.

Деревья решений и случайные леса

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

Логистическая регрессия

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

Машины опорных векторов

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

Как KNN используется в машинном обучении?

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

Классификация

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

Регрессия

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

Применение алгоритма KNN в машинном обучении

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

Распознавание изображений

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

Рекомендательные системы

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

Классификация текста

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

Преимущества алгоритма KNN в ML

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

Простота

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

Универсальность

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

Явная фаза обучения

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

Недостатки алгоритма KNN в ML

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

Вычислительная стоимость прогнозирования

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

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

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

Интенсивная память

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

Чувствительность к шуму и несущественным функциям

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