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