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

Question

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

Алгоритм выполнения поиска KNN с деревом KD, однако, переключает языки и не совсем ясен. Английское объяснение начинает иметь смысл, но его части (такие как область, где они «расслабляют рекурсию», чтобы проверять другие узлы листа) на самом деле не имеют для меня никакого смысла.

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

Answer 1

Эта book introduction, страница 3:

Учитывая набор из п точек в г-мерном пространстве, кД-дерево строится рекурсивно следующим образом. Во-первых, получается медиана значений 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, рекурсия останавливается.

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

Или, здесь original 1975 paper by Jon Bentley.

EDIT: Я хотел бы добавить, что SciPy имеет реализацию kdtree:

• scipy.spatial
• another Stack Overflow question

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, мы можем просто «проецировать» точку вниз на ось, скопировав соответствующую координату в качестве осей все ортогональные (горизонтальные или вертикальные).