Другие значения этого понятия см. в статье ближайший сосед

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

Приложения

Задача поиска ближайшего соседа встречается во множестве приложений, например в областях:

  • Распознавание образов
  • Классификация текстов
  • Рекомендательные и экспертные системы
  • Динамическое размещение рекламы в Интернете

Модели данных

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

  • Множества — размер пересечения множеств
  • Строки — расстояние Левенштейна
  • Граф — соответствие структур

Виды целей

Помимо классической задачи отыскания ближайшей к заданной точке, могут быть поставлены задачи:

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

Алгоритмы

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

  • Диаграммы Вороного
  • KD-деревья
  • BSP-деревья
  • Деревья покрытий
  • VP-деревья
  • R-деревья

Обратный индекс

Метод редких точек



Эта статья использует материал из статьи Wikipedia Задача поиска ближайшего соседа, которая выпущена под Creative Commons Attribution-Share-Alike License 3.0.