Задача поиска ближайшего соседа
Задача поиска ближайшего соседа заключается в отыскании среди множества элементов, расположенных в метрическом пространстве, элементов близких к заданному, согласно некоторой заданной функции близости, определяющей это метрическое пространство.
- Другие значения этого понятия см. в статье ближайший сосед
Приложения
Задача поиска ближайшего соседа встречается во множестве приложений, например в областях:
- Распознавание образов
- Классификация текстов
- Рекомендательные и экспертные системы
- Динамическое размещение рекламы в Интернете
Модели данных
Перед решением прикладной задачи, необходимо выбрать форму представления объектов и функцию близости. В большинстве случаев, объекты представляются в виде многомерных векторов, а в качестве функции близости используется скалярное произведение векторов, но могут быть и другие формы представления данных, например:
- Множества — размер пересечения множеств
- Строки — расстояние Левенштейна
- Граф — соответствие структур
Виды целей
Помимо классической задачи отыскания ближайшей к заданной точке, могут быть поставлены задачи:
- Найти приблизительных ближайших соседей (не обязательно наиболее близкого)
- Найти ближайшего соседа для группы элементов
- Найти несколько ближайших соседей
- Найти все пары элементов, расстояние между которыми меньше некоторого заданного
- Найти ближайших соседей в динамически меняющейся среде
Алгоритмы
Разбиение пространства
Обратный индекс
Метод редких точек
См. также
Ссылки
- Yury Lifshits. Algorithms for Nearest Neighbors: Theoretical Aspects
- Могилко А. А. Параллельный алгоритм поиска ближайшей точки в радиусе