Поделиться через

kNN и ANN

  • Статья
  • Применяется к:
    ✅ NoSQL, ✅ MongoDB vCore, ✅ PostgreSQL

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

Как работает kNN

  1. Векторизация: каждая точка данных в наборе данных представляется вектором в многомерном пространстве.
  2. Вычисление расстояния. Чтобы классифицировать новую точку данных (точку запроса), алгоритм вычисляет расстояние между точкой запроса и всеми другими точками в наборе данных с помощью функции расстояния.
  3. Поиск соседей: алгоритм определяет ближайшие точки данных (соседи) к точке запроса на основе вычисляемых расстояний. Значение k (число соседей) имеет решающее значение. Небольшой k может быть чувствительным к шуму, в то время как большой k может сгладить детали.
  4. Создание прогнозов:
  • Классификация: для задач классификации kNN назначает метку класса точке запроса, которая наиболее распространена среди соседей k. По сути, он выполняет "большинство голосов".
  • Регрессия: для задач регрессии kNN прогнозирует значение точки запроса в качестве среднего (или иногда взвешенный средний) значений соседей k.

Как работает ANN

  1. Векторизация: каждая точка данных в наборе данных представляется вектором в многомерном пространстве.
  2. Индексирование и структуры данных: алгоритмы ANN используют расширенные структуры данных (например, KD-trees, хэширование с учетом локальности или методы на основе графов) для индексирования точек данных, что позволяет быстрее выполнять поиск.
  3. Вычисление расстояния. Вместо вычисления точного расстояния к каждой точке алгоритмы ANN используют эвристики для быстрого определения регионов пространства, которые, скорее всего, содержат ближайших соседей.
  4. Поиск соседей: алгоритм определяет набор точек данных, которые, скорее всего, будут близки к точке запроса. Эти соседи не гарантированно являются точными ближайшими точками, но достаточно близки для практических целей.
  5. Создание прогнозов:
  • Классификация. Для задач классификации ANN назначает метку класса точке запроса, которая наиболее распространена среди идентифицированных соседей, аналогично kNN.
  • Регрессия. Для задач регрессии ANN прогнозирует значение точки запроса в качестве среднего (или взвешированного среднего) значений определенных соседей.

Связанный контент