дерево кд

Многомерное дерево поиска точек в k-мерном пространстве

В информатике k - мерное дерево (сокращение от k-мерного дерева ) — это структура данных , разбивающая пространство на разделы, для организации точек в k -мерном пространстве . K-мерное — это то, что касается ровно k ортогональных осей или пространства с любым числом измерений . ^[1] k -мерные деревья — это полезная структура данных для нескольких приложений, таких как:

• Поиски с использованием многомерного ключа поиска (например, поиск по диапазону и поиск по ближайшему соседу ) и
• Создание облаков точек .

Деревья k -d являются частным случаем деревьев разбиения двоичного пространства .

Описание

Дерево k -d — это бинарное дерево , в котором каждый узел является k -мерной точкой. ^[2] Каждый неконечный узел можно рассматривать как неявно генерирующий разделяющую гиперплоскость , которая делит пространство на две части, известные как полупространства . Точки слева от этой гиперплоскости представлены левым поддеревом этого узла, а точки справа от гиперплоскости представлены правым поддеревом. Направление гиперплоскости выбирается следующим образом: каждый узел в дереве связан с одним из k измерений, причем гиперплоскость перпендикулярна оси этого измерения. Так, например, если для конкретного разбиения выбрана ось «x», все точки в поддереве с меньшим значением «x», чем у узла, появятся в левом поддереве, а все точки с большим значением «x» будут в правом поддереве. В таком случае гиперплоскость будет задана значением x точки, а ее нормаль будет единичной осью x. ^[3]

Пример трехмерного дерева КД

Операции пок-d деревья

Строительство

Поскольку существует множество возможных способов выбора плоскостей разделения, выровненных по осям, существует множество различных способов построения деревьев k -d. Канонический метод построения деревьев k -d имеет следующие ограничения: ^[4]

• При движении вниз по дереву выполняется циклический перебор осей, используемых для выбора плоскостей разделения. (Например, в трехмерном дереве корень будет иметь плоскость, выровненную по оси x , дочерние элементы корня будут иметь плоскости, выровненные по оси y , все внуки корня будут иметь плоскости, выровненные по оси z , все правнуки корня будут иметь плоскости, выровненные по оси x , все праправнуки корня будут иметь плоскости, выровненные по оси y , и т. д.)
• Точки вставляются путем выбора медианы точек, помещаемых в поддерево , относительно их координат на оси, используемой для создания плоскости разделения. (Обратите внимание на предположение, что мы заранее вводим в алгоритм весь набор из n точек.)

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

Обратите внимание, что выбирать срединную точку не обязательно . В случае, когда срединные точки не выбраны, нет гарантии, что дерево будет сбалансированным. Чтобы избежать кодирования сложного алгоритма поиска медианы ^{[5] [6]} или использования сортировки, такой как пирамидальная сортировка или сортировка слиянием, для сортировки всех n точек, популярной практикой является сортировка фиксированного числа случайно выбранных точек и использование медианы этих точек в качестве плоскости разделения. На практике этот метод часто приводит к хорошо сбалансированным деревьям. ${\displaystyle O(n)}$ ${\displaystyle O(n\log(n))}$

При наличии списка из n точек следующий алгоритм использует сортировку с поиском медианы для построения сбалансированного k -d дерева, содержащего эти точки.

функция kdtree ( список точек pointList, int depth){ // Выбираем ось на основе глубины, чтобы ось циклически перебирала все допустимые значения  var  int axis := depth mod k; // Сортируем список точек и выбираем медиану в качестве опорного элемента  select median by axis from pointList; // Создать узел и построить поддерево узел.расположение := медиана; node.leftChild := kdtree(точки в pointList до медианы, глубина+1); node.rightChild := kdtree(точки в pointList после медианы, глубина+1); возврат узла;}

Обычно точки "после" медианы включают только те, которые строго больше медианы в текущем измерении. Для точек, которые лежат на медиане в текущем измерении, можно определить функцию, которая сравнивает их во всех измерениях. В некоторых случаях допустимо позволить точкам, равным медиане, лежать по одну сторону от медианы, например, разделив точки на подмножество "меньше чем" и подмножество "больше или равно".

Этот алгоритм создает инвариант , что для любого узла все узлы в левом поддереве находятся по одну сторону плоскости разделения , а все узлы в правом поддереве — по другую сторону. Точки, лежащие на плоскости разделения, могут появляться по обе стороны. Плоскость разделения узла проходит через точку, связанную с этим узлом (в коде именуемую node.location ).

Альтернативные алгоритмы построения сбалансированного k -d дерева предварительно сортируют данные перед построением дерева. Затем они поддерживают порядок предварительной сортировки во время построения дерева и, следовательно, устраняют затратный шаг поиска медианы на каждом уровне подразделения. Два таких алгоритма строят сбалансированное k -d дерево для сортировки треугольников, чтобы улучшить время выполнения трассировки лучей для трехмерной компьютерной графики . Эти алгоритмы предварительно сортируют n треугольников перед построением k -d дерева , а затем в лучшем случае строят дерево вовремя . ^{[7] [8]} Алгоритм, который строит сбалансированное k -d дерево для сортировки точек, имеет сложность в худшем случае . ^{[9] [10]} Этот алгоритм предварительно сортирует n точек в каждом из k измерений, используя сортировку, такую ​​как пирамидальная сортировка или сортировка слиянием, перед построением дерева. Затем он поддерживает порядок этих k предварительных сортировок во время построения дерева и, таким образом, избегает поиска медианы на каждом уровне подразделения. ${\displaystyle O(n\log n)}$ ${\displaystyle O(kn\log(n))}$ ${\displaystyle O(n\log(n))}$

Добавление элементов

Добавляется новая точка в k -d дерево таким же образом, как добавляется элемент в любое другое дерево поиска . Сначала пройдите по дереву, начиная с корня и двигаясь либо к левому, либо к правому потомку в зависимости от того, находится ли вставляемая точка на "левой" или "правой" стороне плоскости разделения. Как только вы доберетесь до узла, под которым должен располагаться потомок, добавьте новую точку как левого или правого потомка листового узла, снова в зависимости от того, какая сторона плоскости разделения узла содержит новый узел.

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

Удаление элементов

Чтобы удалить точку из существующего k -d дерева, не нарушая инварианта, проще всего сформировать набор всех узлов и листьев из дочерних узлов целевого узла и заново создать эту часть дерева. ^[11]

Другой подход заключается в поиске замены для удаленной точки. ^[12] Сначала найдите узел , содержащий удаляемую точку. Для базового случая, где R — листовой узел, замена не требуется. Для общего случая найдите точку замены, скажем , из поддерева с корнем в . Замените точку, хранящуюся в , на . Затем рекурсивно удалите . ${\displaystyle R}$ ${\displaystyle p}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle p}$ ${\displaystyle p}$

Для поиска точки замены, если дискриминирует на (скажем) и имеет правого потомка, найдите точку с минимальным значением из поддерева с корнем в правом потомке. В противном случае найдите точку с максимальным значением из поддерева с корнем в левом потомке. ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle R}$ ${\displaystyle x}$ ${\displaystyle x}$

Балансировка

Балансировка k -d дерева требует осторожности, поскольку k -d деревья сортируются по нескольким измерениям, поэтому метод поворота деревьев не может быть использован для их балансировки, поскольку это может нарушить инвариант.

Существует несколько вариантов сбалансированных k -d деревьев. Они включают в себя разделенное k -d дерево, псевдо k -d дерево, KDB-дерево , hB-дерево и Bkd-дерево . Многие из этих вариантов являются адаптивными k-d деревьями .

Поиск ближайшего соседа

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

Алгоритм поиска ближайшего соседа (NN) направлен на поиск точки в дереве, которая находится ближе всего к заданной входной точке. Этот поиск может быть выполнен эффективно, если использовать свойства дерева для быстрого исключения больших участков пространства поиска.

Поиск ближайшего соседа в дереве k -d происходит следующим образом:

1. Начиная с корневого узла, алгоритм рекурсивно перемещается вниз по дереву, так же, как если бы вставлялась точка поиска (т.е. он перемещается влево или вправо в зависимости от того, меньше или больше точка текущего узла в разделенном измерении).
2. Как только алгоритм достигает конечного узла, он проверяет узловую точку, и если расстояние лучше, чем «текущее лучшее», эта узловая точка сохраняется как «текущее лучшее».
3. Алгоритм раскручивает рекурсию дерева, выполняя следующие шаги в каждом узле:
   1. Если текущий узел ближе, чем текущий лучший, то он становится текущим лучшим.
   2. Алгоритм проверяет, могут ли быть какие-либо точки на другой стороне плоскости разделения, которые находятся ближе к точке поиска, чем текущее лучшее. В концепции это делается путем пересечения гиперплоскости разделения с гиперсферой вокруг точки поиска, радиус которой равен текущему ближайшему расстоянию. Поскольку все гиперплоскости выровнены по осям, это реализовано как простое сравнение, чтобы увидеть, меньше ли расстояние между координатой разделения точки поиска и текущим узлом, чем расстояние (общие координаты) от точки поиска до текущего лучшего.
      1. Если гиперсфера пересекает плоскость, то по другую сторону плоскости могут быть более близкие точки, поэтому алгоритм должен спуститься по другой ветви дерева от текущего узла в поисках более близких точек, следуя тому же рекурсивному процессу, что и весь поиск.
      2. Если гиперсфера не пересекает плоскость разделения, то алгоритм продолжает движение вверх по дереву, и вся ветвь по другую сторону этого узла исключается.
4. Когда алгоритм завершает этот процесс для корневого узла, поиск завершается.

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

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

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

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

Диапазон поиска

Поиск по диапазону ищет диапазоны параметров. Например, если дерево хранит значения, соответствующие доходу и возрасту, то поиск по диапазону может быть чем-то вроде поиска всех членов дерева, имеющих возраст от 20 до 50 лет и доход от 50 000 до 80 000. Поскольку деревья kd делят диапазон домена пополам на каждом уровне дерева, они полезны для выполнения поиска по диапазону.

Анализ двоичных деревьев поиска показал, что худшее время для диапазона поиска в k -мерном k -d дереве, содержащем n узлов, определяется следующим уравнением. ^[13]

${\displaystyle t_{\text{worst}}=O\left(k\cdot n^{1-{\frac {1}{k}}}\right)}$

Ухудшение производительности при работе с данными высокой размерности

Нахождение ближайшей точки в среднем является операцией в случае случайно распределенных точек, хотя анализ в целом сложен. ^[14] ${\displaystyle O(\log(n))}$

В пространствах высокой размерности проклятие размерности приводит к тому, что алгоритму необходимо посещать гораздо больше ветвей, чем в пространствах низкой размерности. В частности, когда число точек лишь немного превышает число измерений, алгоритм лишь немного лучше линейного поиска по всем точкам. Как правило, если размерность равна k , число точек в данных, n , должно быть . В противном случае, когда деревья k -d используются с данными высокой размерности, большинство точек в дереве будут оценены, и эффективность будет не лучше, чем при исчерпывающем поиске, ^[15] и, если требуется достаточно быстрый ответ, вместо этого следует использовать приближенные методы ближайшего соседа. ${\displaystyle n\gg 2^{k}}$

Ухудшение производительности, когда точка запроса находится далеко от точек вк-d дерево

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

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

Сложность

• Построение статического k- d дерева из n точек имеет следующую сложность в худшем случае:
  • O ( n log ² n ), если для нахождения медианы на каждом уровне зарождающегося дерева используется сортировка O ( n log n ) , такая как пирамидальная сортировка или сортировка слиянием ;
  • O ( n log n ), если для выбора медианы на каждом уровне зарождающегося дерева используется алгоритм медианы медиан O ( n ) ^{[5] [6] ;}
  • O ( kn log n ), если n точек предварительно отсортированы в каждом из k измерений с использованием сортировки O ( n log n ) , такой как пирамидальная сортировка или сортировка слиянием, перед построением k -d дерева . ^[10]
• Вставка новой точки в сбалансированное k -d дерево занимает O (log n ) времени.
• Удаление точки из сбалансированного k -d дерева занимает O (log n ) времени.
• Запрос диапазона, параллельного осям, в сбалансированном k -d дереве занимает O ( n ^1−1/k + m ) времени, где m — количество сообщаемых точек, а k — размерность k -d дерева.
• Поиск 1 ближайшего соседа в сбалансированном k -d дереве со случайно распределенными точками занимает в среднем O (log n ) времени.

Вариации

Объемные объекты

Вместо точек k -d дерево может также содержать прямоугольники или гиперпрямоугольники . ^{[16] [17]} Таким образом, поиск по диапазону становится проблемой возврата всех прямоугольников, пересекающих прямоугольник поиска. Дерево строится обычным способом со всеми прямоугольниками в листьях. В ортогональном поиске по диапазону противоположная координата используется при сравнении с медианой. Например, если текущий уровень разделен вдоль x _high , мы проверяем координату x _low прямоугольника поиска. Если медиана меньше координаты x _low прямоугольника поиска, то никакой прямоугольник в левой ветви никогда не сможет пересечься с прямоугольником поиска и, следовательно, может быть отсечен. В противном случае следует пройти обе ветви. См. также interval tree , которое является одномерным особым случаем.

Точки только в листьях

Также возможно определить k -d дерево с точками, хранящимися исключительно в листьях. ^[4] Эта форма k -d дерева допускает множество механик разделения, отличных от стандартного медианного разделения. Правило разделения по средней точке ^[18] выбирает середину самой длинной оси пространства, в котором выполняется поиск, независимо от распределения точек. Это гарантирует, что соотношение сторон будет не более 2:1, но глубина зависит от распределения точек. Разновидность, называемая скользящей средней точкой, разделяет только по середине, если есть точки по обе стороны от разделения. В противном случае она разделяет по точке, ближайшей к середине. Манивонгватана и Маунт показывают, что это обеспечивает «достаточно хорошую» производительность на общих наборах данных.

Используя скользящую среднюю точку, можно ответить на приблизительный запрос ближайшего соседа в . Приблизительный подсчет диапазона можно ответить с помощью этого метода. ${\displaystyle O\left({\tfrac {1}{{\epsilon \ }^{d}}}\log n\right)}$ ${\displaystyle O\left(\log n+{\left({\tfrac {1}{\epsilon \ }}\right)}^{d}\right)}$

Смотрите также

Близкие варианты:

• неявное k -d дерево , k -d дерево, определенное неявной функцией разбиения, а не явно сохраненным набором разбиений
• min/max k -d дерево , k -d дерево, которое связывает минимальное и максимальное значение с каждым из своих узлов
• Ослабленное k -d дерево , k -d дерево, такое, что дискриминанты в каждом узле произвольны

Похожие вариации:

• Quadtree , структура разбиения пространства, которая разделяется в двух измерениях одновременно, так что каждый узел имеет 4 потомка
• Octree , структура, разбивающая пространство на части, которая разделяется в трех измерениях одновременно, так что каждый узел имеет 8 потомков
• Дерево шаров , многомерное разбиение пространства, полезное для поиска ближайшего соседа
• R-дерево и иерархия ограничивающих интервалов , структура для разбиения объектов, а не точек, с перекрывающимися областями
• Дерево точек обзора , вариант k -d дерева, использующий гиперсферы вместо гиперплоскостей для разделения данных.

Проблемы, которые можно решить с помощью k -d деревьев:

• Рекурсивное разбиение , метод построения статистических деревьев решений, которые похожи на деревья k -d.
• Проблема меры Клее , задача вычисления площади объединения прямоугольников, решаемая с помощью k -d деревьев.
• Задача о гильотине — задача нахождения k -мерного дерева, ячейки которого достаточно велики, чтобы вместить заданный набор прямоугольников.

Реализации с открытым исходным кодом

• ALGLIB имеет реализации алгоритмов ближайшего соседа и приближенного ближайшего соседа на C# и C++, основанных на дереве k -d.
• CGAL ( библиотека вычислительных алгоритмов) содержит реализации алгоритмов поиска ближайшего соседа, приблизительного ближайшего соседа, а также поиска по диапазону на основе k -d дерева.
• SciPy , библиотека Python для научных вычислений, содержит реализации алгоритмов поиска ближайшего соседа на основе k -d дерева.
• scikit-learn , библиотека Python для машинного обучения, содержит реализации k -d деревьев для поддержки поиска ближайших соседей и радиусных соседей.

Ссылки

1. "k-dimensional". xlinux.nist.gov . Получено 2023-09-17 .
2. Христов, Христо (29 марта 2023 г.). «Введение в деревья КД». Баелдунг .
3. Бентли, Дж. Л. (1975). «Многомерные двоичные деревья поиска, используемые для ассоциативного поиска». Сообщения ACM . 18 (9): 509–517. doi : 10.1145/361002.361007 . S2CID  13091446.
4. Берг, Марк де; Чеонг, Отфрид; Кревелд, Марк ван; Овермарс, Марк (2008). «Поиск ортогонального диапазона». Вычислительная геометрия . стр. 95–120. дои : 10.1007/978-3-540-77974-2_5. ISBN 978-3-540-77973-5.
5. Blum, M. ; Floyd, RW ; Pratt, VR ; Rivest, RL ; Tarjan, RE (август 1973 г.). "Временные рамки для выбора" (PDF) . Журнал компьютерных и системных наук . 7 (4): 448–461. doi : 10.1016/S0022-0000(73)80033-9 .
6. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л. Введение в алгоритмы . MIT Press и McGraw-Hill. Глава 10.
7. Wald I, Havran V (сентябрь 2006 г.). «О построении быстрых kd-деревьев для трассировки лучей и о том, как это сделать за O(N log N)» (PDF) . Симпозиум IEEE 2006 г. по интерактивной трассировке лучей . стр. 61–69. doi :10.1109/RT.2006.280216. ISBN 1-4244-0693-5. S2CID  1603250.
8. Хавран В., Биттнер Дж. (2002). «Об улучшении деревьев kd для лучевой съемки» (PDF) . В: Труды WSCG : 209–216.
9. Прокопюк, Т; Агарвал, М; Арге, Л; Виттнер, Дж (2003). «Bkd-дерево: динамическое масштабируемое kd-дерево». В Хадзилакосе, Т; Манолопулос, Ю; Роддик, Дж; Теодоридис, Ю. (ред.). Конспекты лекций по информатике . Том. 2750. Берлин: Springer-Verlag. стр. 46–65.
10. Brown R (2015). «Построение сбалансированного дерева kd за время O(kn log n)». Журнал методов компьютерной графики . 4 (1): 50–68.
11. Христов, Христо (29 марта 2023 г.). «Введение в деревья КД». Баелдунг .
12. Чандран, Шарат. Введение в kd-деревья. Университет Мэриленда, кафедра компьютерных наук.
13. Ли, ДТ; Вонг, КК (1977). «Анализ наихудшего случая для поиска регионов и частичных регионов в многомерных бинарных деревьях поиска и сбалансированных квадродеревьях». Acta Informatica . 9 . doi :10.1007/BF00263763. S2CID  36580055.
14. Фрейдман, Дж. Х .; Бентли, Дж. Л .; Финкель, РА (1977). «Алгоритм поиска наилучших совпадений за логарифмическое ожидаемое время». Труды ACM по математическому программному обеспечению . 3 (3): 209. doi :10.1145/355744.355745. OSTI  1443274. S2CID  10811510.
15. Jacob E. Goodman , Joseph O'Rourke и Piotr Indyk , ред. (2004). "Глава 39: Ближайшие соседи в многомерных пространствах". Справочник по дискретной и вычислительной геометрии (2-е изд.). CRC Press.
16. Розенберг, Дж. Б. (1985). «Сравнение географических структур данных: исследование структур данных, поддерживающих запросы регионов». Труды IEEE по автоматизированному проектированию интегральных схем и систем . 4 : 53–67. doi : 10.1109/TCAD.1985.1270098. S2CID  31223074.
17. Houthuys, P. (1987). «Сортировка по ящикам, многомерный метод двоичной сортировки для прямоугольных ящиков, используемый для быстрого поиска в диапазоне». The Visual Computer . 3 (4): 236–249. doi :10.1007/BF01952830. S2CID  3197488.
18. S. Maneewongvatana и DM Mount . Нормально быть худым, если твои друзья толстые. 4-й ежегодный семинар CGC по вычислительной геометрии, 1999.