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

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

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

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

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

${\ displaystyle D ^ {B} (t) = {\ begin {cases} \ max (| tB.pivot | -B.radius, D ^ {B.parent}), & {\ text {if}} B \ neq Корень \\\ max (| tB.pivot | -B.radius, 0), & {\ text {if}} B = Корень \\\ end {cases}}}$

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

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

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

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

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

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

алгоритм построения kd

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

Псевдокод

function construct_balltree is
    input: D, an array of data points.
    output: B, the root of a constructed ball tree.

    if a single point remains then
        create a leaf B containing the single point in D
        return B
    else
        let c be the dimension of greatest spread
        let p be the central point selected considering c
        let L, R be the sets of points lying to the left and right of the median along dimension c
        create B with two children: 
            B.pivot := p
            B.child1 := construct_balltree(L),
            B.child2 := construct_balltree(R),
            let B.radius be maximum distance from p among children
        return B
    end if
end function

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

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

Описание

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

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

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

Псевдокод

function knn_search is
    input: 
        t, the target point for the query
        k, the number of nearest neighbors of t to search for
        Q, max-first priority queue containing at most k points
        B, a node, or ball, in the tree
    output: 
        Q, containing the k nearest neighbors from within B

    if distance(t, B.pivot) - B.radius ≥ distance(t, Q.first) then
        return Q unchanged
    else if B is a leaf node then
        for each point p in B do
            if distance(t, p) < distance(t, Q.first) then
                add p to Q
                if size(Q) > k then
                    remove the furthest neighbor from Q
                end if
            end if
        repeat
    else
        let child1 be the child node closest to t
        let child2 be the child node furthest from t
        knn_search(t, k, Q, child1)
        knn_search(t, k, Q, child2)
    end if
    return Q
end function

Представление

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

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