Задача поиска ближайшего соседа: различия между версиями
Материал из Поле цифровой дидактики
(Спасено источников — 1, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0) |
Patarakin (обсуждение | вклад) |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Задача поиска ближайшего соседа''' заключается в отыскании среди множества элементов, расположенных в [[метрическое пространство|метрическом пространстве]], элементов близких к заданному, согласно некоторой заданной функции близости, определяющей это метрическое пространство. | '''Задача поиска ближайшего соседа''' заключается в отыскании среди множества элементов, расположенных в [[метрическое пространство|метрическом пространстве]], элементов близких к заданному, согласно некоторой заданной функции близости, определяющей это метрическое пространство. | ||
| Строка 25: | Строка 24: | ||
* Найти ближайших соседей в динамически меняющейся среде | * Найти ближайших соседей в динамически меняющейся среде | ||
[[Категория:Алгоритмы поиска]] | [[Категория:Алгоритмы поиска]] | ||
Текущая версия на 20:59, 19 октября 2022
Задача поиска ближайшего соседа заключается в отыскании среди множества элементов, расположенных в метрическом пространстве, элементов близких к заданному, согласно некоторой заданной функции близости, определяющей это метрическое пространство.
Приложения
Задача поиска ближайшего соседа встречается во множестве приложений, например в областях:
- Распознавание образов
- Классификация текстов
- Рекомендательные и экспертные системы
- Динамическое размещение рекламы в Интернете
Модели данных
Перед решением прикладной задачи, необходимо выбрать форму представления объектов и функцию близости. В большинстве случаев, объекты представляются в виде многомерных векторов, а в качестве функции близости используется скалярное произведение векторов, но могут быть и другие формы представления данных, например:
- Множества — размер пересечения множеств
- Строки — расстояние Левенштейна
- Граф — соответствие структур
Виды целей
Помимо классической задачи отыскания ближайшей к заданной точке, могут быть поставлены задачи:
- Найти приблизительных ближайших соседей (не обязательно наиболее близкого)
- Найти ближайшего соседа для группы элементов
- Найти несколько ближайших соседей
- Найти все пары элементов, расстояние между которыми меньше некоторого заданного
- Найти ближайших соседей в динамически меняющейся среде
