Шаровое дерево

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

Неофициальное описание [ править ]

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

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

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

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

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

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

Строительство [ править ]

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

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

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

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

Псевдокод [ править ]

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 он может выполнить одну из трех операций, прежде чем, наконец, вернуть обновленную версию приоритетной очереди:

Если расстояние от контрольной точки t до текущего узла B больше, чем самая дальняя точка в , игнорируйте B и возвращайте Q. Q
Если B является конечным узлом, просканируйте каждую точку, перечисленную в B, и соответствующим образом обновите очередь ближайших соседей. Верните обновленную очередь.
Если 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^[2]

Производительность [ править ]

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

Ссылки [ править ]

↑ Перейти обратно: Перейти обратно: ^а ^б ^с Омохундро, Стивен М. (1989) «Пять алгоритмов построения шарового дерева»
↑ Перейти обратно: Перейти обратно: ^а ^б ^с Лю, Т.; Мур А. и Грей А. (2006). «Новые алгоритмы эффективной многомерной непараметрической классификации» (PDF) . Журнал исследований машинного обучения . 7 : 1135–1158.
^ Кумар, Н.; Чжан, Л.; Наяр, С. (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 .
^ Кибрия, А.М.; Франк, Э. (2007). «Эмпирическое сравнение точных алгоритмов ближайшего соседа». Обнаружение знаний в базах данных: PKDD 2007 (PDF) . Конспекты лекций по информатике. Том. 4702. с. 140. дои : 10.1007/978-3-540-74976-9_16 . ISBN 978-3-540-74975-2 .

[r1-1] Перейти обратно: Перейти обратно: ^а ^б ^с Омохундро, Стивен М. (1989) «Пять алгоритмов построения шарового дерева»

[liu-2] Перейти обратно: Перейти обратно: ^а ^б ^с Лю, Т.; Мур А. и Грей А. (2006). «Новые алгоритмы эффективной многомерной непараметрической классификации» (PDF) . Журнал исследований машинного обучения . 7 : 1135–1158.

[kumar-3] Кумар, Н.; Чжан, Л.; Наяр, С. (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 .

[kibriya-4] Кибрия, А.М.; Франк, Э. (2007). «Эмпирическое сравнение точных алгоритмов ближайшего соседа». Обнаружение знаний в базах данных: PKDD 2007 (PDF) . Конспекты лекций по информатике. Том. 4702. с. 140. дои : 10.1007/978-3-540-74976-9_16 . ISBN 978-3-540-74975-2 .

[1]

[2]

[3]

[4]