k -d дерево - k-d tree

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

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

Описание

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

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

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

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

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

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

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

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

function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;

    // Sort point list and choose median as pivot element
    select median by axis from pointList;

    // Create node and construct subtree
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}

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

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

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

Пример реализации

Вышеупомянутый алгоритм, реализованный на языке программирования Python, выглядит следующим образом:

from collections import namedtuple
from operator import itemgetter
from pprint import pformat

class Node(namedtuple("Node", "location left_child right_child")):
    def __repr__(self):
        return pformat(tuple(self))

def kdtree(point_list, depth: int = 0):
    if not point_list:
        return None

    k = len(point_list[0])  # assumes all points have the same dimension
    # Select axis based on depth so that axis cycles through all valid values
    axis = depth % k

    # Sort point list by axis and choose median as pivot element
    point_list.sort(key=itemgetter(axis))
    median = len(point_list) // 2

    # Create node and construct subtrees
    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():
    """Example usage"""
    point_list = [(7, 2), (5, 4), (9, 6), (4, 7), (8, 1), (2, 3)]
    tree = kdtree(point_list)
    print(tree)

if __name__ == "__main__":
    main()

Результат будет:

((7, 2),
 ((5, 4), ((2, 3), None, None), ((4, 7), None, None)),
 ((9, 6), ((8, 1), None, None), None))

Сгенерированное дерево показано ниже.

k -d разложение на дерево для множества точек
(2,3), (5,4), (9,6), (4,7), (8,1), (7,2).

Полученное k -d дерево.

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

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

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

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

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

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

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

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

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

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

Снижение производительности, когда точка запроса находится далеко от точек в дереве k -d

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

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

Сложность

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

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

Также возможно определить k -d дерево с точками, хранящимися исключительно в листьях. Эта форма k -d дерева допускает различные механики разбиения, отличные от стандартного медианного разбиения. Правило разделения средней точки выбирает середину самой длинной оси пространства, в котором производится поиск, независимо от распределения точек. Это гарантирует, что соотношение сторон будет не более 2: 1, но глубина зависит от распределения точек. Вариант, называемый скользящей средней точкой, разделяется только по середине, если есть точки по обе стороны от разделения. В противном случае он разбивается на точку, ближайшую к середине. Maneewongvatana и Mount показывают, что это обеспечивает "достаточно хорошую" производительность на общих наборах данных.

Используя скользящую среднюю точку, можно получить ответ на приблизительный запрос ближайшего соседа . Приблизительный подсчет дальности можно дать с помощью этого метода. ${\ 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 ++ реализаций K -d дерева на основе ближайшего соседа и приблизительных ближайших соседей алгоритмы
• SciPy , библиотека Python для научных вычислений, содержит реализации алгоритмов поиска ближайшего соседа на основе k -d-дерева.
• scikit-learn , библиотека Python для машинного обучения, содержит реализации k -d деревьев для поиска ближайших соседей и соседей по радиусу.

использованная литература