k -d дерево

k -d дерево
Тип	Многомерный BST
Изобрел	1975 г.
Изобретенный	Джон Луи Бентли
Сложность времени в большой нотации O
Алгоритм Средний Худший случай Космос ${\ Displaystyle О (п)}$ ${\ Displaystyle О (п)}$ Поиск ${\ Displaystyle О (\ журнал п)}$ ${\ Displaystyle О (п)}$ Вставлять ${\ Displaystyle О (\ журнал п)}$ ${\ Displaystyle О (п)}$ Удалить ${\ Displaystyle О (\ журнал п)}$ ${\ Displaystyle О (п)}$

Трехмерное k -d дерево. Первое разделение (красная вертикальная плоскость) разрезает корневую ячейку (белая) на две части, каждая из которых затем разделяется (зелеными горизонтальными плоскостями) на две части. Наконец, четыре ячейки разделяются (четырьмя синими вертикальными плоскостями) на две части. Поскольку разделения больше нет, последние восемь называются листовыми ячейками.

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

Неофициальное описание [ править ]

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

Операции над k -d деревьями [ править ]

Строительство [ править ]

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

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

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

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

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

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

Часто точки «после» медианы включают только те, которые строго больше медианы. Для точек, лежащих на медиане, можно определить функцию «суперключ», которая сравнивает точки во всех измерениях ^{[ non sequitur ]} . В некоторых случаях допустимо, чтобы точки, равные медиане, лежали по одну сторону от медианы, например, путем разделения точек на подмножество «меньше чем» и подмножество «больше или равно».

from  collection  import  namedtuple from  operator  import  itemgetter from  pprint  import  pformatкласс  Node ( namedtuple ( "Node" ,  "location left_child right_child" )):  def  __repr__ ( self ):  return  pformat ( tuple ( self ))def  kdtree ( point_list ,  depth :  int  =  0 ):  если  не  point_list :  return  None k  =  len ( point_list [ 0 ])  # предполагается, что все точки имеют одинаковый размер.  # Выберите ось на основе глубины, чтобы ось проходила через все допустимые значения.  axis  =  depth  %  k # Сортировка списка точек по осям и выбор медианы в качестве сводного элемента  point_list . sort ( key = itemgetter ( axis ))  median  =  len ( point_list )  //  2 # Создать узел и построить поддеревья  return  Node (  location = point_list [ median ],  left_child = kdtree ( point_list [: median ],  depth  +  1 ),  right_child = kdtree ( point_list [ median  +  1  :],  depth  +  1 ),  )def  main ():  "" "Пример использования" ""  point_list  =  [( 7 ,  2 ),  ( 5 ,  4 ),  ( 9 ,  6 ),  ( 4 ,  7 ),  ( 8 ,  1 ),  ( 2 ,  3) )]  tree  =  kdtree ( point_list )  print ( tree )если  __name__  ==  "__main__" :  main ()

((7, 2), ((5, 4), ((2, 3), Нет, Нет), ((4, 7), Нет, Нет)), ((9, 6), ((8, 1), Нет, Нет), Нет))

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

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

Добавление элементов [ править ]

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

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

Удаление элементов [ править ]

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

Другой подход - найти замену удаленной точке. ^[8] Сначала найдите узел R, содержащий точку, которую нужно удалить. Для базового случая, когда R - листовой узел, замена не требуется. В общем случае найдите точку замены, скажем p, из поддерева с корнем R. Замените точку, хранящуюся в R, на p. Затем рекурсивно удалите p.

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

Балансировка [ править ]

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

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

Поиск ближайшего соседа [ править ]

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

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

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

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

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

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

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

Поиск по диапазону [ править ]

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

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

${\ displaystyle t _ {\ text {худший}} = O (k \ cdot n ^ {1 - {\ frac {1} {k}}})}$

Снижение производительности при работе с данными большого размера [ править ]

Поиск ближайшей точки - это в среднем операция O (log n ) в случае случайно распределенных точек, хотя анализ в целом сложен. ^[10]

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

Снижение производительности, когда точка запроса находится далеко от точек в дереве kd [ править ]

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

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

Сложность [ править ]

• Построение статического k -d дерева из n точек имеет следующую сложность наихудшего случая:
  • O ( n log ² n ), если сортировка O ( n log n ), такая как Heapsort или Mergesort , используется для поиска медианы на каждом уровне возникающего дерева;
  • O ( n log n ), если алгоритм медианы медианы O ( n ) ^{[3] [4]} используется для выбора медианы на каждом уровне возникающего дерева;
  • O ( kn log n ), если n точек предварительно отсортированы в каждом из k измерений с использованием сортировки O ( n log n ), такой как Heapsort или Mergesort, перед построением k -d дерева . ^[7]
• Вставка новой точки в сбалансированное 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 дерево может также содержать прямоугольники или гипер прямоугольники . ^{[12] [13]} Таким образом, поиск по диапазону превращается в задачу возврата всех прямоугольников, пересекающих прямоугольник поиска. Дерево строится обычным образом со всеми прямоугольниками на листьях. В ортогональном поиске диапазона , то напротив координат используются при сравнении с медианой. Например, если текущий уровень разделен по x _high , мы проверяем координату x _low прямоугольника поиска. Если медиана меньше _{минимума} xкоордината прямоугольника поиска, тогда ни один прямоугольник в левой ветви не может пересекаться с прямоугольником поиска и поэтому может быть обрезан. В противном случае необходимо пройти обе ветви. См. Также интервальное дерево , которое является одномерным частным случаем.

Очки только в листьях [ править ]

Также возможно определить k -d дерево с точками, хранящимися исключительно в листьях. ^[2] Эта форма k -d дерева допускает различные механики разделения, отличные от стандартного медианного разделения. Правило разделения средней точки ^[14] выбирает середину самой длинной оси пространства, в котором производится поиск, независимо от распределения точек. Это гарантирует, что соотношение сторон будет не более 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 tree , дерево k -d, которое связывает минимальное и максимальное значение с каждым из своих узлов
• Расслабленное k -d дерево , k -d дерево, в котором дискриминанты в каждом узле произвольны

Связанные варианты:

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

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

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

Реализации с открытым исходным кодом [ править ]

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

Ссылки [ править ]