Как мне пересечь KDTree, чтобы найти k ближайших соседей?

-1

Этот вопрос касается реализации KNN-поиска KDTrees. Обход KDTree для поиска единственного наилучшего соответствия (ближайший сосед) является простым, похожим на модифицированный двоичный поиск.Как мне пересечь KDTree, чтобы найти k ближайших соседей?

Как обход, модифицированный для исчерпывающего и эффективного поиска k-наилучших совпадений (KNN)?

Редактировать для разъяснения: После нахождения ближайшего узла M к входному запросу I, как алгоритм обхода продолжает находить оставшиеся K-1 ближайшие совпадения с запросом? Существует ли шаблон обхода, который гарантирует, что узлы будут посещены в порядке наилучшего для худшего соответствия запросу?

источник

2016-01-09 user2647513

Возможного дубликат [Как реализовать ближайший сосед поиск с помощью KDTrees?] (Http://stackoverflow.com/questions/4093392/how-to-implement-nearest-neighbor -search-using-kdtrees) –

Это не дубликат [link] (http://stackoverflow.com/questions/4093392/how-to-implement-nearest-neighbor-search-using-kdtrees); Я прямо заявил, что я понял, что обход одного ближайшего соседа. Вопрос задает вопрос о том, как изменить обход, чтобы исчерпывающе найти k ближайших соседей одного запроса. Я подозреваю, что есть эффективный путь назад вниз по дереву из первоначального наилучшего соответствия, которое может последовательно найти более отдаленных соседей. – user2647513

Просто продолжайте поиск таким же образом. –

В настоящее время я решил использовать неоптимальное решение для выполнения серии последовательно расширенных поисковых запросов до тех пор, пока не будут найдены узлы K.

источник

2016-01-11 19:00:05 user2647513

Вы можете поддерживать максимальную кучу размера k (k - количество ближайших соседей, которое мы хотели найти).

Начните с корневого узла и вставьте значение расстояния в узел максимальной кучи. Продолжайте поиск в дереве k-d с использованием разбиения на размер, критерии и продолжайте обновлять Max Heap tree.

https://gopalcdas.wordpress.com/2017/05/24/construction-of-k-d-tree-and-using-it-for-nearest-neighbour-search/

~ Ashish

источник

2017-10-20 08:09:12

Как мне пересечь KDTree, чтобы найти k ближайших соседей?

ответ

Смежные вопросы