Что такое алгоритм K-Nearest Neighbors (K-Nearest Neighbors), в одной статье

Определение алгоритма K ближайших соседей

Алгоритм K-Nearest Neighbors (K-Nearest Neighbors) - это алгоритм контролируемого обучения на основе экземпляров, который может быть использован для задач классификации и регрессии. Основная идея алгоритма очень интуитивно понятна: при поступлении нового образца найти K обучающих образцов, ближайших к нему в пространстве признаков, и сделать прогноз на основе информации об этих соседях. Для задач классификации используется механизм голосования, в результате которого в качестве прогноза берется категория, наиболее часто встречающаяся среди K соседей; для задач регрессии в качестве прогноза берется среднее значение целевых значений K соседей. K в названии алгоритма означает количество рассматриваемых соседей и является ключевым параметром, который может быть настроен пользователем. Алгоритм K-nearest neighbour - это непараметрический метод, который не делает никаких предположений о распределении данных и является очень адаптируемым. Выбор метрики расстояния имеет решающее значение, распространенными являются евклидово расстояние, манхэттенское расстояние, расстояние Минковского и т. д. Различные метрики расстояния подходят для разных типов данных. На производительность алгоритма также влияет масштабирование признаков, которое обычно требует предварительной обработки нормализации. Алгоритм K ближайших соседей, также известный как обучение на основе памяти, по сути, хранит обучающие данные и извлекает их путем вычисления сходства в момент предсказания. Преимущество метода заключается в том, что модель проста и интуитивно понятна, а недостаток - в том, что вычислительные затраты на этапе предсказания значительно возрастают с увеличением объема данных.

Историческое происхождение алгоритма K-nearest neighbour

• Раннее концептуальное прорастание: В 1950-х годах Фикс и Ходжес впервые ввели базовую концепцию классификации ближайших соседей в непараметрическом дискриминантном анализе. Эта работа заложила основу для формализации последующего алгоритма K-ближайших соседей.
• Создание теоретической системы: В 1967 году Ковер и Харт опубликовали работу "Классификация шаблонов ближайших соседей", в которой систематически анализировались границы ошибок классификаторов ближайших соседей. Эта основополагающая работа обеспечила теоретические гарантии для алгоритма.
• Развертывание усовершенствования алгоритма: В 1970-х годах, когда начался бум исследований в области распознавания образов, алгоритмы K ближайших соседей стали широко использоваться в различных областях. Исследователи начали изучать влияние различных метрик расстояния и выбора K-значения на производительность.
• Проблемы в эпоху больших данных: В XXI веке традиционный алгоритм K-ближайших соседей сталкивается с проблемой низкой вычислительной эффективности в условиях огромного объема данных. Это побудило исследователей разработать различные методы оптимизации, такие как KD-деревья, шаровые деревья и другие ускоренные структуры данных.
• Современная интеграционная разработка: В последние годы алгоритмы K-nearest neighbour были объединены с глубоким обучением для создания новых методов, таких как глубокое метрическое обучение. Кроме того, распределенные реализации на платформах больших данных расширили спектр применения алгоритмов.

Основные принципы алгоритма K Nearest Neighbour

• Основа допущений подобия: Алгоритм построен на предположении о локальной непрерывности, т.е. соседние точки в пространстве признаков имеют схожие свойства. Это предположение соответствует интуитивному восприятию мира людьми и является основополагающим для эффективности алгоритма.
• Важнейшая роль метрик расстояния: Различные метрики расстояния определяют разные определения "близости", что напрямую влияет на производительность алгоритма. Евклидово расстояние подходит для непрерывных признаков, манхэттенское расстояние более устойчиво к выбросам, а косинусоидальное сходство подходит для высокоразмерных разреженных данных.
• Искусство К-балансировкиСлишком маленькое значение K подвержено влиянию шумовых помех, что приводит к чрезмерной подгонке; слишком большое значение K сглаживает границу принятия решения и может игнорировать локальные особенности. Оптимальное значение K должно обеспечивать баланс между смещением и дисперсией.
• Геометрические свойства пространства признаков: Производительность алгоритмов тесно связана с геометрической структурой пространства признаков. Проблема катастрофы размерности особенно остро стоит в высокоразмерных пространствах, где разница в расстоянии между точками становится несущественной.
• Стратегия взвешивания голосов: В то время как в стандартном алгоритме K-ближайших соседей каждый сосед голосует с одинаковым весом, взвешенный K-ближайший сосед присваивает разные веса в зависимости от расстояния. Чем ближе соседи, тем большее влияние они оказывают на решение, что повышает точность алгоритма.

Процесс работы алгоритма K Nearest Neighbour

• Этап предварительной обработки данных: Нормализуйте признаки, чтобы устранить влияние различий в величине разных признаков. Обеспечить справедливость метрики расстояния и избежать доминирования некоторых признаков при расчете расстояния.
• Расчет матрицы расстояний: Расстояние между тестируемым образцом и всеми обучающими образцами вычисляется в процессе предсказания для формирования матрицы расстояний. Этот шаг имеет высокую вычислительную сложность и является основным узким местом в эффективности алгоритма.
• Процесс поиска ближайших соседей: Найдите обучающие выборки, соответствующие K наименьшим расстояниям из матрицы расстояний. Эффективные алгоритмы поиска, такие как KD-дерево, могут значительно снизить временную сложность этого шага.
• Применение правил принятия решений: Голосование по большинству голосов используется для решения задач классификации, а усреднение - для решения задач регрессии. В случае равенства голосов обычно выбирается та категория, к которой относится более близкий образец.
• Оптимизация оценки результатов: Оцените эффективность алгоритма с помощью кросс-валидации и настройте параметры K-value и метрики расстояния. При выборе модели необходимо учитывать специфику проблемной области и характеристики данных.

Преимущества алгоритма K ближайших соседей

• Интуитивные и понятные принципы: Логика алгоритма проста и не требует сложной математической подготовки для понимания, и эта интуитивность делает алгоритм ближайшего соседа K наиболее подходящим примером для преподавания вводного курса машинного обучения.
• Не требуется процесс обучения: Как инертный алгоритм обучения, K-nearest neighbours не имеет явного этапа обучения, и новые данные могут быть добавлены в модель в любое время, что позволяет алгоритму быстро адаптироваться к изменениям в распределении данных.
• Естественная обработка Мультиклассификация: Алгоритм естественным образом поддерживает многокатегорийные задачи классификации без необходимости строить несколько классификаторов, как это делают некоторые алгоритмы бинарной классификации, и алгоритм стабильно работает в многокатегорийных сценариях.
• Верхняя граница теоретического коэффициента ошибокКогда обучающих выборок бесконечно много, коэффициент ошибок классификатора ближайших соседей не превышает байесовского коэффициента ошибок более чем в два раза, что обеспечивает надежность усовершенствованного алгоритма.
• Адаптация к сложным границам принятия решенийПринятие решений на основе локальной информации, алгоритм K-nearest neighbour способен обучаться сложным нелинейным границам принятия решений, что позволяет алгоритму добиваться превосходства при работе со сложными данными реального мира.

Ограничения алгоритма K ближайших соседей

• Узкое место вычислительной эффективностиПредсказание требует вычисления расстояния до всех обучающих образцов, а временная сложность линейно растет с увеличением объема данных, что затрудняет применение алгоритма к большим наборам данных.
• Проблема размерной катастрофы: В высокоразмерном пространстве признаков расстояние между точками становится недостаточно дифференцированным, и производительность алгоритма значительно снижается, поэтому выделение признаков или снижение размерности становится необходимым этапом предварительной обработки.
• Чувствительность к коэффициенту шума: Шумы и выбросы в обучающих данных могут напрямую влиять на результаты прогнозирования, особенно когда значение K невелико, качество данных оказывает большее влияние на производительность алгоритма.
• Зависимость масштабирования характеристик: Работа алгоритма сильно зависит от того, как масштабируются признаки, и предварительная обработка нормализации необходима, если при расчете расстояния доминирует большой диапазон значений некоторых признаков.
• Задачи, связанные с несбалансированными даннымиКогда размеры выборок по категориям сильно различаются, категория большинства может оказывать непропорционально большое влияние на классификацию категории меньшинства, что должно быть исправлено с помощью взвешенного голосования или методов выборки.

Практические применения алгоритма K-nearest neighbour

• Построение рекомендательной системы: Совместная фильтрация на основе пользователей - это, по сути, применение алгоритма K-nearest neighbour для создания рекомендаций путем поиска похожих пользователей или предметов. Эта техника широко используется в электронной коммерции и на платформах потокового вещания.
• Сопутствующая диагностика: Помогает врачам в диагностике заболеваний на основе сходства симптомов пациента с историческими случаями. Алгоритмы могут объединять множество клинических проявлений для поддержки принятия решений.
• Задачи классификации изображений: В компьютерном зрении алгоритм K-nearest neighbour может быть использован для простой классификации изображений, например, для распознавания рукописных цифр. Хотя глубокое обучение лучше, K-nearest neighbour по-прежнему используется в качестве эталонного метода.
• Оценка кредитного риска: Банки используют алгоритм K Nearest Neighbour для анализа сходства между клиентами и клиентами, которые в прошлом допускали просрочки по кредитным рейтингам. Алгоритм способен объединить множество факторов риска.
• Анализ географической информации: Аналитическое прогнозирование на основе географической близости в ГИС-системах, например, оценка цен на жилье, экологический мониторинг. Естественная близость пространственных данных подходит для алгоритма K ближайших соседей.

Улучшенный вариант алгоритма K-nearest neighbour

• Взвешенный алгоритм K-ближайших соседей: Присвоение различных весов соседям в зависимости от расстояния, причем чем ближе расстояние, тем больше вес. Это улучшение повышает чувствительность алгоритма к локальным структурам и увеличивает точность предсказания.
• Дистанционное метрическое обучение: Методы машинного обучения используются для автоматического обучения метрической функции расстояния, которая наилучшим образом подходит для конкретных данных. К этому направлению относятся такие методы, как крупномасштабный компонентный анализ окрестностей.
• приблизительный поиск ближайшего соседа: Разработка аппроксимационных алгоритмов для ускорения поиска ближайших соседей в больших данных, например, локально чувствительное хеширование, иерархические навигационные графы малого мира.
• Ядерный алгоритм k-nearest neighbour: Внедрение трюков ядра для отображения данных в высокоразмерное пространство признаков, где выполняется алгоритм K-nearest neighbour, способный решать более сложные нелинейные задачи.
• Выбор признаков с учетом расстояния: Комбинирование методов выбора признаков для оптимизации весов признаков в метрике расстояния. Соответствующий метод позволяет автоматически определять важные признаки и улучшать производительность алгоритма.

Настройка параметров алгоритма K-nearest neighbour

• Стратегия выбора K-значения: Оптимальное значение K обычно выбирается путем перекрестного валидирования, начиная с небольшого значения и постепенно увеличивая его, чтобы наблюдать за изменениями в производительности модели. Как правило, рекомендуется выбирать нечетное число K-значений, чтобы избежать случаев плоских голосов.
• Выбор метрики расстояния: Выберите подходящую метрику расстояния в зависимости от типа данных и характеристик признаков. Евклидово расстояние обычно используется для непрерывных признаков, расстояние Хэмминга подходит для категориальных признаков, а косинусное сходство обычно используется для текстовых данных.
• Разработка весовой функции: Во взвешенных K-ближайших соседях выбирается разумная весовая функция, например, обратно пропорциональная квадрату расстояния. Весовая функция влияет на чувствительность алгоритма к локальной структуре.
• Применение методов уменьшения размерности: Перед лицом высокоразмерных данных признаки предварительно обрабатываются с помощью методов снижения размерности, таких как анализ главных компонент. Уменьшение размерности повышает эффективность вычислений и снимает проблему катастрофы размерности.
• Оптимизация параллельных вычислений: Ускорение процесса вычисления расстояний с помощью многоядерных процессоров или фреймворков распределенных вычислений. Современные платформы для работы с большими данными обеспечивают техническую поддержку для применения алгоритмов в масштабе.