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

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

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

Приложения

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

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

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

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

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

Виды целей

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

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

Алгоритмы

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

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

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

См. также

Ссылки

Yury Lifshits. Algorithms for Nearest Neighbors: Theoretical Aspects
Могилко А. А. Параллельный алгоритм поиска ближайшей точки в радиусе