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

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

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

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

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

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

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

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

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

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

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

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

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

Эта страница в последний раз была отредактирована 18 июня 2024 в 10:06.