Можно ли найти KNN для узла, который является * IN * деревом KD?

Question

Попытка создать поиск KNN с использованием KD-дерева. Я могу хорошо сформировать KD-дерево (или, по крайней мере, я верю, что могу!). Моя проблема в том, что я ищу, чтобы найти ближайших 2 соседей к каждой точке в списке точек.

Итак, есть ли способ найти K ближайших соседей к точке, используя дерево KD, даже если точка на самом деле находится в дереве, или мне нужно построить отдельное дерево KD для каждой точки, оставив точку что я хочу найти?

Мой язык реализации - C ++, но я больше ищу либо алгоритм, либо общую помощь, спасибо!

Спасибо, Стивен

Answer 1

Если вы хотите, чтобы K точно ближайших соседей в вашем дереве, просто запросите дерево для K + 1 соседей (очевидно, начиная с первого ближайшего соседа) будет ваш запрос).

Answer 2

Это не очень хороший ответ, но я не могу уместить то, что хочу вставить в комментарий. Во всяком случае, вот соответствующий текст из Википедии:

Алгоритм может быть расширен в несколько способов простыми модификациями. Это может обеспечить k-Ближайшие соседи в точку, поддерживая к току лучше, чем один. ветви устраняются только тогда, когда они не могут есть точки ближе, чем любой из к текущие рекорды.

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

Полезен примерный сосед в приложениях реального времени, таких как робототехника благодаря значительной скорости увеличение прибыли, не ища лучший момент исчерпывающе. Один из его реализация - Best Bin First.

Answer 3

Я бы порекомендовал взглянуть на ANN для деталей реализации http://www.cs.umd.edu/~mount/ANN/

Он предназначен для приблизительного поиска ближайших соседей, но также может выполнять точный поиск ближайших соседей.Это также один из самых ясных и лучших написанных кодов, которые я когда-либо обнаруживал, и он должен дать вам некоторое представление, даже если вы хотите собственную реализацию.