Шаровое дерево - Ball tree - Wikipedia

Эта статья о варианте двоичного дерева. Для метрического дерева, включающего множественные разбиения, см. М-дерево.

В Информатика, а мяч дерево, Balltree^[1] или же метрическое дерево, это разделение пространства структура данных для организации точек в многомерном пространстве. Дерево шаров получило свое название от того факта, что оно разделяет точки данных на вложенный набор гиперсфер, известных как «шары». Полученная структура данных имеет характеристики, которые делают ее полезной для ряда приложений, в первую очередь поиск ближайшего соседа.

Неформальное описание

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

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

${\displaystyle D^{B}(t)={\begin{cases}\max(|t-B.pivot|-B.radius,D^{B.parent}),&{\text{if }}B\neq Root\\\max(|t-B.pivot|-B.radius,0),&{\text{if }}B=Root\\\end{cases}}}$

Где ${\displaystyle D^{B}(t)}$ это минимально возможное расстояние от любой точки шара B в какой-то момент т.

Деревья-шары относятся к М-дерево, но поддерживает только двоичное разбиение, тогда как в M-дереве каждый уровень разбивается ${\displaystyle m}$ к ${\displaystyle 2m}$ свернуть, что приводит к более мелкой древовидной структуре, поэтому требуется меньше вычислений расстояния, что обычно дает более быстрые запросы. Кроме того, M-деревья лучше хранить на диске, который организован в страницы. M-дерево также сохраняет предварительно вычисленные расстояния от родительского узла для ускорения запросов.

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

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

Доступен ряд алгоритмов построения шарового дерева.^[1] Целью такого алгоритма является создание дерева, которое будет эффективно поддерживать запросы желаемого типа (например, ближайшего соседа) в среднем случае. Конкретные критерии идеального дерева будут зависеть от типа вопроса, на который нужно ответить, и от распределения исходных данных. Однако обычно применимая мера эффективного дерева - это та, которая минимизирует общий объем его внутренних узлов. Учитывая различное распределение наборов реальных данных, это сложная задача, но есть несколько эвристик, которые на практике хорошо разделяют данные. В общем, существует компромисс между стоимостью построения дерева и эффективностью, достигаемой с помощью этой метрики. ^[2]

В этом разделе кратко описывается простейший из этих алгоритмов. Более подробное обсуждение пяти алгоритмов было дано Стивеном Омохундро.^[1]

k-d алгоритм построения

Простейшая такая процедура называется «алгоритм построения k-d» по аналогии с процессом, используемым для построения k-d деревья. Это автономный алгоритм, то есть алгоритм, который работает со всем набором данных сразу. Дерево строится сверху вниз путем рекурсивного разделения точек данных на два набора. Разбиения выбираются по одному измерению с наибольшим разбросом точек, при этом наборы разбиваются по среднему значению всех точек по этому измерению. Нахождение разделения для каждого внутреннего узла требует линейного времени в количестве выборок, содержащихся в этом узле, что дает алгоритм с временная сложность ${\displaystyle O(n\,\log \,n)}$, куда п - количество точек данных.

Псевдокод

функция construct_balltree является    Вход: D, массив точек данных. выход: B, корень построенного шарового дерева. если остается одна точка тогда        создать лист B содержащий единственную точку в D        возвращаться B    еще        позволять c быть измерением наибольшего распространения, пусть п - центральная точка, выбранная с учетом c, пусть L, р - множества точек, лежащих слева и справа от медианы по размерности c        Создайте B с двумя детьми: B.pivot: = п            B.child1: = construct_balltree (L), B.child2: = construct_balltree (R), пусть B.radius - максимальное расстояние от п среди детей возвращаться B    конец, есликонечная функция

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

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

Описание

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

1. Если расстояние от контрольной точки т к текущему узлу B больше, чем самая дальняя точка в Q, игнорировать B и вернуться Q.
2. Если B является листовым узлом, сканировать каждую точку, перечисленную в B и соответствующим образом обновите очередь ближайших соседей. Верните обновленную очередь.
3. Если B является внутренним узлом, вызовите алгоритм рекурсивно на B 's двое детей, ищущих ребенка, чей центр находится ближе к т первый. Возвращать очередь после того, как каждый из этих вызовов обновил ее по очереди.

Выполнение рекурсивного поиска в порядке, описанном в пункте 3 выше, увеличивает вероятность того, что следующий дочерний элемент будет полностью удален во время поиска.

Псевдокод

функция knn_search является    Вход:         t, целевая точка для запроса k, количество ближайших соседей t для поиска Q, очередь с максимальным приоритетом, содержащая не более k точек B, узел или шар в дереве выход:         Q, содержащий k ближайших соседей из B если distance (t, B.pivot) - B.radius ≥ distance (t, Q.first) тогда        возвращаться Q без изменений иначе если B - листовой узел тогда        для каждого точка p в B делать            если расстояние (t, p) <расстояние (t, Q.first) тогда                добавить p к Q если размер (Q)> k тогда                    удалить самого дальнего соседа из Q конец, если            конец, если        повторение    еще        пусть child1 будет дочерним узлом, ближайшим к t, пусть child2 будет дочерним узлом, наиболее удаленным от t knn_search (t, k, Q, child1) knn_search (t, k, Q, child2) конец, есликонечная функция[2]

Спектакль

По сравнению с несколькими другими структурами данных было показано, что шаровые деревья достаточно хорошо справляются с задачей поиска ближайшего соседа, особенно по мере роста их размерности.^[3][4]Однако наилучшая структура данных ближайшего соседа для данного приложения будет зависеть от размерности, количества точек данных и базовой структуры данных.

Рекомендации

1. Омохундро, Стивен М. (1989) «Пять алгоритмов построения Боллтри»
2. Лю, Т .; Мур А. и Грей А. (2006). «Новые алгоритмы эффективной многомерной непараметрической классификации» (PDF). Журнал исследований в области машинного обучения. 7: 1135–1158.
3. Kumar, N .; Zhang, L .; Наяр, С. (2008). «Какой алгоритм хороших ближайших соседей для поиска похожих участков на изображениях?». Компьютерное зрение - ECCV 2008 (PDF). Конспект лекций по информатике. 5303. п. 364. CiteSeerX  10.1.1.360.7582. Дои:10.1007/978-3-540-88688-4_27. ISBN  978-3-540-88685-3.
4. Кибрия, А. М .; Франк, Э. (2007). «Эмпирическое сравнение алгоритмов точного ближайшего соседа». Обнаружение знаний в базах данных: PKDD 2007 (PDF). Конспект лекций по информатике. 4702. п. 140. Дои:10.1007/978-3-540-74976-9_16. ISBN  978-3-540-74975-2.