Меню

Главная
Случайная статья
Настройки
Участник:KindDragon33/k-мерное дерево
Материал из https://ru.wikipedia.org

Если статья не подходит под формат Википедии, то её можно перенести в другой вики-проект.

Обратите внимание, что временная статья не должна содержаться в категориях, предназначенных для основного пространства имён. Используйте конструкцию [[:Категория:Название категории]] вместо [[Категория:Название категории]] для указания, в какие категории эта статья должна включаться.

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

Содержание

Неофициальное описание

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

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

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

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


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

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

Учитывая список n точек, следующий алгоритм построит сбалансированной k-d дерева, содержащего эти моменты. 
функция kdtree (список пунктов pointList, глубина int )
{
    Если pointList является пустым
        возвращение ноль;
    остальное
    {
        / / Выберите ось, основанные на глубину тем этой оси циклический перебор всех действительных значений
        var int оси: = глубина mod k;
        
        / / Сортировать список точек и выбрать медиана как основной элемент
         выберите  средний по оси от pointList;
        
        / / Создать узел и построить поддеревьев
        var tree_node узел;
node.Location: = средний;
node.leftChild: = kdtree (пунктов в pointList до медианы, глубина + 1);
node.rightChild: = kdtree (пунктов в pointList после медиана, глубина + 1);
        возвращает узел;
    }
}


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

Этот алгоритм реализации языка программирования Python является следующим: 
class Node: passdef kdtree(point_list, depth=0):    if not point_list:        return    # Select axis based on depth so that axis cycles through all valid values    k = len(point_list[0]) # assumes all points have the same dimension    axis = depth % k    # Sort point list and choose median as pivot element    point_list.sort(key=lambda point: point[axis])    median = len(point_list) // 2 # choose median    # Create node and construct subtrees    node = Node()    node.location = point_list[median]    node.left_child = kdtree(point_list[:median], depth + 1)    node.right_child = kdtree(point_list[median + 1:], depth + 1)    return node


Пример использования будет: 
point_list = [(2,3), (5,4), (9,6), (4,7), (8,1) (7,2)]
дерево = kdtree(point_list)


Справа показано дерево создается.

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

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

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

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

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

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

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

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

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

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

Существует несколько вариантов сбалансированных k-d деревьев. Они включают разделенных k-d дерево, псевдо k-d дерево, k-d B-дерева, hB дерево и ФКД дерево. Многие из этих вариантов, адаптивной k-d деревоs.

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

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

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


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


Поиск ближайшей точки является операцией O (log N) по случайно распределенным точкам. Анализируя поиск по двоичным деревьям установлено, что в худшем случаее время поиска для 
k-мерного KD дерева содержащего N узлов вычесляется следующим уравнением.[3]


В пространстве с очень большим количеством измерений, из за измерений алгоритму необходимо посетить намного больше ветвей чем при меньшем количестве измерений пространства. В 
частности, когда количество точек лишь немного больше чем количество


измерений, алгоритм лишь немногим лучше, чем линейный поиск по всем точкам.

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

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

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

Данные большого количества измерений

k-d деревья не пригодны для эффективного поиска ближайшего соседа в пространствах большого количества измерений. Как правило, если размерность k, количество точек данных, N, должна быть N >> 2k. В противном случае при использовании k-d деревья с данными большого количества измерений  большиство из точек в дереве будут обработаны и эффективно ничуть не лучше, чем полный перебор,[4] и вместо будет использоватся приблизительный поиск ближайккго соседа.

Сложность
  • Создание статического k-d дерева из n точек занимает O(n log 2 n) время если O(n log n) Сортировка используется для вычисления медианы на каждом уровне. Сложность является O(n log n), если алгоритм линейного медианного поиска таких, как описанный в Cormen и др.[5].
  • Вставка новой точки в сбалансированной k-d дерева займет O (log n) времени.
  • Удаление точки из сбалансированного k-d дерева займет O (log n) времени.
  • Запрос параллельного оси диапазона в сбалансированном k-d дереве займет O (n1-1/k +m) времени, где m — это количество зарегистрированных точек и k количество измерение в k-d дереве.


Вариации

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

Вместо точек, k-d деревья моут также содержать прямоугольники или гиперпрямоугольники.[6] [7] Таким образом диапазон поиска становится проблемой возвращения всех прямоугольников, пересекающиеся искомый прямоугольник. Дерево строится обычным способом с прямоугольниками на листьях. Ортогональные поиск диапазона противоположные координаты используется при сравнении с медианой. Например, если текущий уровень делится вдоль xhigh, мы проверяем xlow координату искомого прямоугольника. Если медиана меньше xlow координаты поиска прямоугольник, то не прямоугольник в левой ветке может никогда не пересекаются с искомым прямоугольником и может быть исключен. В противном случае следует просматривать обе ветви. Смотрите также интервал дерева, который является одномерным особым случаем.

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

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

См.также
  • неявное k-d дерево
  • мин/макс k-d дерево
  • QuadTree
  • Октодерево
  • R-дерево
  • Ограничивающий интервал иерархия
  • Поиск ближайшего соседа
  • Клее мера проблемы


Ссылки
  1. J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509-517, 1975.
  2. Chandran, Sharat. Introduction to kd-trees. University of Maryland Department of Computer Science.
  3. Lee, D. T.; Wong, C. K. (1977). Worst-case analysis for region and partial region searches in multidimensional binary search trees and balanced quad trees. Acta Informatica. 9 (1): 23–29. doi:10.1007/BF00263763.
  4. Jacob E. Goodman, Joseph O'Rourke and Piotr Indyk (Ed.). Chapter 39 : Nearest neighbours in high-dimensional spaces // Handbook of Discrete and Computational Geometry. — 2nd. — CRC Press, 2004.
  5. Шаблон:Introduction to Algorithms Chapter 10.
  6. Rosenberg J. Geographical Data Structures Compared: A Study of Data Structures Supporting Region Queries. IEEE Transaction on CAD Integrated Circuits Systems 4(1):53-67
  7. Houthuys P. Box Sort, a multidimensional binary sorting method for rectangular boxes, used for quick range searching. The Visual Computer, 1987, 3:236-249
  8. de Berg, Mark et al. Computational Geometry: Algorithms and Applications, 3rd Edition, pages 99-101. Springer, 2008.
  9. S. Maneewongvatana and D. M. Mount. It's okay to be skinny, if your friends are fat. 4th Annual CGC Workshop on Computational Geometry, 1999.


Внешние ссылки
Downgrade Counter