Поиск ближайшего соседа

• Основы поиска ближайших соседей

  • Поиск ближайших соседей (NN) – это задача нахождения точек в пространстве, которые находятся ближе всего к заданной точке. 
  • Задача поиска ближайшего соседа является фундаментальной в машинном обучении и обработке данных. 

• Методы поиска ближайших соседей

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

• Точные алгоритмы поиска ближайших соседей

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

• Приближенные алгоритмы поиска ближайших соседей

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

• Поиск на основе сжатия/кластеризации

  • Методы сжатия включают VA-файлы и векторное квантование. 
  • VA-файлы используют сжатие векторов признаков, а векторное квантование – кластеризацию. 

• Варианты задачи поиска ближайших соседей

  • Существуют различные варианты задачи поиска ближайших соседей, включая поиск k-ближайших соседей и ε-приближенный поиск. 
  • Поиск k-ближайших соседей определяет k ближайших соседей по запросу. 
  • ε-приближенный поиск позволяет получить “верное предположение” о ближайшем соседе в обмен на скорость или экономию памяти. 

• Соотношение расстояний до ближайшего соседа

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

• Ближайшие соседи с фиксированным радиусом действия

  • Задача ближайших соседей с фиксированным радиусом действия требует эффективного поиска всех точек на заданном расстоянии от заданной точки. 

• Все ближайшие соседи

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