k -d дерево

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

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

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

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

Описание

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

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

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

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

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

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

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

не требуется Обратите внимание, что выбирать срединную точку . В случае, когда медианные точки не выбраны, нет никакой гарантии, что дерево будет сбалансированным. Чтобы избежать кодирования сложного $O(n)$ поиска медианы алгоритм или с помощью $O(n\log(n))$ Для сортировки, такой как пирамидальная сортировка или сортировка слиянием, для сортировки всех 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))$ сортируйте, например пирамидальную сортировку или сортировку слиянием, перед построением дерева. Затем он сохраняет порядок этих k предварительных сортировок во время построения дерева и тем самым позволяет избежать поиска медианы на каждом уровне подразделения.

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

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

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

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

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

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

с многомерными

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

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

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

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

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

Сложность

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

Вариации

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

Вместо точек дерево k -d также может содержать прямоугольники или гиперпрямоугольники . Таким образом, поиск диапазона становится проблемой возврата всех прямоугольников, пересекающих прямоугольник поиска. Дерево строится обычным способом со всеми прямоугольниками на листьях. При поиске ортогонального диапазона . при сравнении с медианой используется противоположная координата Например, если текущий уровень разделен по x _high , мы проверяем координату x _low прямоугольника поиска. Если медиана меньше _нижней координаты x прямоугольника поиска, то ни один прямоугольник в левой ветви не может когда-либо пересекаться с прямоугольником поиска и поэтому может быть обрезан. В противном случае придется пересечь обе ветви. См. также дерево интервалов , которое является одномерным особым случаем.

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

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

Используя скользящую среднюю точку, на приблизительный запрос ближайшего соседа в можно получить ответ $O\left({\tfrac {1}{{\epsilon \ }^{d}}}\log n\right)$. Приблизительный подсчет диапазона можно получить в $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 дерева и приближенных алгоритмов ближайшего соседа.
• CGAL, библиотека вычислительных алгоритмов, содержит реализации алгоритмов ближайшего соседа на основе k -d дерева, приблизительного ближайшего соседа, а также алгоритмов поиска диапазона.
• SciPy , библиотека Python для научных вычислений, содержит реализации алгоритмов поиска ближайшего соседа на основе дерева k -d.
• scikit-learn , библиотека Python для машинного обучения, содержит реализации k -d деревьев для поддержки поиска ближайших соседей и соседей по радиусу.