Задача поиска ближайшего соседа

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

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

Приложения

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

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

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

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

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

Виды целей

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

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

Алгоритмы

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

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

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

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

См. также

• Метод k ближайших соседей
• Диаграммы Вороного

Ссылки

• Yury Lifshits. Algorithms for Nearest Neighbors: Theoretical Aspects