Задача поиска ближайшего соседа является задачей оптимизации, которая заключается в отыскании в множестве элементов, расположенных в многомерном метрическом пространстве, элементов, близких к заданному, в соответствии с заданной функции близости. Формально эта задача относится следующим образом: предоставлено множество точек S в пространстве M и точку q ∈ M, необходимо найти ближайшую к q точку в M. Дональд Кнут в Искусстве программирования (том 3, 1973) назвал это проблемой почтового отделения, ссылаясь на применение этой задачи на поиск ближайшего почтового отделения. Прямым обобщением задачи поиска ближайшего соседа алгоритм поиска k -NN, который предназначен для поиска k ближайших точек.

Чаще M является метрическим пространством и вводится функция близости, определяется как метрика, которая является симметричной и удовлетворяет неравенству треугольника. Еще более общее, M — это d -вимирний векторное пространство, в котором близость берется в качестве Евклидовой метрики, уличной метрики или других метрик. Однако функция близости может быть произвольной. Одним из примеров может быть метрика Брегман, для которой неравенство треугольника не выполняется.

Применение

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

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

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

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

  • множественного числа — размер сечения множеств;
  • строки — расстояние Левенштейна;
  • граф — соответствие структур.

Родственные задачи

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

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

Одним из самых известных вариантов является k-NN поиск.

Алгоритм k -NN

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

Алгоритмы

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

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

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

Обратная индекс

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

Другие

  • Хеширования;
  • Алгоритм Клейнберг.