Как работает KD-дерево поиска ближайшего соседа?

Question

Я смотрю на странице Википедии для деревьев KD.В качестве примера я реализовал в Python алгоритм построения дерева kd в списке.

Алгоритм поиска KNN с деревом KD, однако, переключает языки и не совсем понятен.Английское объяснение начинает иметь смысл, но его части (например, область, в которой они «раскручивают рекурсию» для проверки других узлов листа) не имеют для меня никакого смысла.как можно искать KNN с деревом KD в python?Это не вопрос типа "send me the code!", и я этого не ожидаю.Просто краткое объяснение, пожалуйста:)

Answer 1

Это введение в книгу , стр. 3:

Учитывая набор из n точек в d-мерном пространстве, kd-дерево строится рекурсивно следующим образом.Сначала определяется медиана значений i-х координат точек (изначально i = 1).Таким образом, значение M вычисляется так, что по меньшей мере 50% точек имеют свою i-ю координату, большую или равную M, в то время как по меньшей мере 50% точек имеют свою i-ю координату, меньшую или равную M.значение x сохраняется, и множество P разбивается на PL и PR, где PL содержит только точки с их i-й координатой, меньшей или равной M, и | PR |= | PL | ± 1.Затем процесс повторяется рекурсивно как для PL, так и для PR, с заменой i на i + 1 (или 1, если i = d).Когда набор точек в узле имеет размер 1, рекурсия останавливается.

В следующих параграфах обсуждается ее использование при решении ближайшего соседа.

Или, вот это оригинальный документ 1975 года Джона Бентли .

РЕДАКТИРОВАТЬ: я должен добавить, что SciPy имеет реализацию kdtree:

• scipy.spatial
• другой вопрос переполнения стека

Answer 2

Я просто потратил некоторое время на то, чтобы разобраться с описанием алгоритма Wikipedia , и придумал следующую реализацию Python, которая может помочь: https://gist.github.com/863301

Первый этап closest_point - это простой поиск в глубину, чтобы найти наилучший подходящий листовой узел.

Вместо того, чтобы просто возвращать лучший узел, найденный в стеке вызовов, на втором этапе проверяется, не может ли быть более близкий узел на стороне «выезда»: (художественная схема ASCII)

            n     current node
 b          |     best match so far
 |      p   |     point we're looking for
 |<    >|   |     error
        |< >|     distance to "away" side
        |<  | >|  error "sphere" extends to "away" side
            | x   possible better match on the "away" side

Текущий узел n разделяет пробел вдоль линии, поэтому нам нужно смотреть на сторону «вдали» только в том случае, если «ошибка» между точкой p и наилучшим соответствием b больше, чем расстояние от точки p до линии n. Если это так, то мы проверяем, есть ли какие-либо точки на стороне «подальше», которые находятся ближе.

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

Чтобы вычислить расстояние между точкой p и линией, разделяющей пространство через узел n, мы можем просто «спроецировать» точку вниз на ось, скопировав соответствующую координату, поскольку все оси ортогональны ( горизонтальный или вертикальный).

Answer 3

давайте рассмотрим пример, для простоты рассмотрим d = 2, а результат дерева Kd показан ниже

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

Вышеуказанное дерево представляет собой kd-дерево
мы будем искать в дереве, чтобы попасть в одну из областей. В kd-дереве каждая область представлена ​​одной точкой.

тогда мы узнаем расстояние между этой точкой и точкой запроса

Затем мы нарисуем круг с радиусом этого расстояния, чтобы убедиться, есть ли какая-либо точка, которая ближе к точке запроса.

Затем ось, которая находится в этой области круга, мы возвращаемся к этой оси и находим вблизи точки