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

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

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

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

Ответы

Ответ 1

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

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

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

Или, вот оригинальная статья 1975 года Джона Бентли.

EDIT: я должен добавить, что SciPy имеет реализацию kdtree:

Ответ 2

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

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

Вместо того, чтобы просто вернуть лучший node найденный резервную копию стека вызовов, вторая фаза проверяет, может ли быть более близкий node на стороне "away": (ASCII art diagram)

            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

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

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

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