Оценка эффективности использования метрических деревьев в приближённом поиске на основе обобщённого гиперплоскостного разбиения множества объектов

Размещено на http://www.allbest.ru/

оценка эффективности использования метрических деревьев в приближённом поиске на основе обобщённого гиперплоскостного разбиения множества объектов

вычислительная техника и информационные технологии

удк 004.424.4

В.К. Гулаков, В.Н. Матюшин

Рассмотрены три метрические структуры данных, использующие обобщённое гиперплоскостное разбиение, - деревья GH, GNAT и mm-GNAT. Дано их теоретическое описание. Проведено экспериментальное сравнение с целью оценки эффективности при выполнении приближённого поиска. Описан ряд опытов, подтверждающих теоретические свойства описываемых структур данных.

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

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

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

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

В метрических пространствах функция расстояния (метрика) является мерой сходства объектов. Задача диапазонного поиска для объекта запроса с радиусом заключается в том, чтобы найти все объекты , удовлетворяющие условию

,

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

Метрические структуры данных обычно используют либо сферическое, либо гиперплоскостное разбиение пространства данных [4].

Сферическое разбиение

При сферическом разбиении на каждом шаге построения метрического дерева выбирается заданный опорный объект и рассчитывается среднее расстояние от него до всех остальных объектов. Затем все остальные объекты разбиваются на два подмножества: объекты, расположенные внутри сферы с центром в опорном объекте и радиусом , и объекты, расположенные за пределами этой сферы. Далее процесс рекурсивно повторяется для обоих подмножеств. Для построения таким способом нужно знать лишь расстояния между объектами. Недостатком этого метода является неравномерность разбиения пространства данных: во внутренней части сферы находится гораздо больше объектов данных, чем во внешней части. Это приводит к увеличению времени выполнения поисковых запросов. Примером структуры данных, использующей сферическое разбиение, является VP-дерево (Vantage-Point Tree).

Обобщённое гиперплоскостное разбиение

Разбиение обобщёнными гиперплоскостями является более равномерным. Обобщённым такое разбиение называется потому, что если объекты являются точками в n-мерном евклидовом пространстве, то разбиение осуществляется гиперплоскостью размерностью . Обобщённая гиперплоскость (generalized hyperplane, GH) определяется точками и , , и состоит из множества точек , удовлетворяющих условию

Считается, что точка принадлежит стороне плоскости, соответствующей , если [4].

Дерево GH. Первой предложенной метрической структурой данных, использующей гиперплоскостное разбиение, является обобщённое гиперплоскостное дерево (GH-дерево, Generalized Hyperplane Tree). Оно строится следующим образом. На каждом шаге построения случайным образом выбираются две опорные точки: и . Остальные объекты разделяются на подмножества и . Объекты, которые ближе к опорной точке , чем к , помещаются в подмножество (левый потомок текущего узла), остальные помещаются в (правый потомок текущего узла). Затем процесс рекурсивно повторяется для левого и правого потомков. В результате получается бинарное дерево.

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

Преимуществом GH-дерева над метрическими деревьями, основанными на сферическом разбиении, является его симметричность и сбалансированность, достигающаяся за счёт того, что опорные точки выбираются случайным образом. Среди недостатков - наличие максимум двух потомков в каждом узле и необходимость вычислять два расстояния при обходе каждого узла дерева при выполнении поиска (поскольку каждый узел дерева хранит две опорные точки).

Дерево GNAT. GNAT (Geometric Near-neighbor Access Tree) [1] является обобщением GH_дерева. В каждом узле может находиться заданное количество опорных точек. На каждом шаге построения выбирается множество опорных точек таким образом, чтобы они располагались максимально далеко друг от друга. Первая опорная точка выбирается случайным образом. Опорная точка выбирается таким образом, чтобы она была расположена дальше всех от , располагается дальше всех от и т.д.

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

,

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

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

Значение параметра может быть различным для каждого узла. Для корневого узла количество опорных точек равно , а для его потомков это количество выбирается пропорционально количеству объектов, хранящихся в кластерах, принадлежащих этим потомкам.

Достоинство GNAT по сравнению с GH-деревом и деревьями, основанными на сферическом разбиении, заключается в меньшем количестве вычислений расстояний и, как следствие, возросшей производительности поиска. При этом количество вычислений расстояний сокращается с ростом . Если арность дерева GNAT находится между 50 и 100, то производительность поиска превосходит таковую у деревьев, основанных на сферическом разбиении [2]. Главный недостаток GNAT - большое количество вычислений расстояний при построении по сравнению с другими метрическими деревьями. Время построения оценивается как , где N - количество объектов, k - среднее количество опорных точек. Ёмкостная сложность оценивается как [2].

Перечисленные деревья могут работать только с одной мерой подобия. Это значит, что поиск похожих объектов осуществляется с использованием той же функции расстояния, которая применяется при построении дерева. Однако в ряде случаев возникает потребность для одного и того же набора данных выполнять поисковые запросы, используя различные меры подобия. В работе [5] вводится понятие мультимодальности - поддержки различных метрик. Структура данных, обладающая поддержкой мультимодальности, позволяет выполнять поисковые запросы с использованием различных функций расстояния.

Дерево mm-GNAT. Дальнейшим развитием GNAT является mm-GNAT (multi-modality GNAT) [3]. Основным нововведением является поддержка мультимодальности, т.е. возможность использовать при выполнении поисковых запросов метрики, отличные от той, которая применялась при построении дерева. Идея mm-GNAT заключается в том, что дерево mm-GNAT строится с использованием какой-либо заданной метрики, но поисковые запросы по дереву можно осуществлять с применением произвольной метрики.

Авторы доказывают неравенство

, (1)

где - функция расстояния в пространстве ; - d-мерные векторы.

Метрика определяется следующим образом:

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

Для исключения некорректного определения пересечений диапазонов запроса и кластера mm-GNAT при построении вычисляет расширенный диапазон кластеров:

.

Вместо диапазона каждый узел дерева mm-GNAT хранит диапазон , в котором нижняя граница вычисляется с помощью нормы , а верхняя - с помощью нормы . Таким образом, данный диапазон включает в себя диапазоны кластеров, вычисленные с использованием нормы . Это гарантирует, что при выполнении диапазонного поиска кластер не будет ложно классифицирован как расположенный слишком далеко от объекта запроса.

Преимущество mm-GNAT перед GH-деревом и GNAT проявляется тогда, когда желательно при поиске ближайшего соседа использовать различные метрики. При использовании GH-дерева и GNAT необходимо строить дерево для каждой метрики, с помощью которой предполагается осуществлять поиск. В случае mm-GNAT достаточно построить дерево один раз, а затем можно осуществлять поиск с использованием произвольной метрики . Таким образом, значительно сокращается время построения поискового индекса, а также объём памяти, занимаемый индексом. При выполнении диапазонного поиска количество вычислений расстояний является наименьшим, если при построении дерева и выполнении поисковых запросов используется одинаковая метрика.

Экспериментальное сравнение

Была реализована программа для сравнения деревьев GH, GNAT и mm-GNAT. Использовались наборы из 20000 векторов размерностью 4 и 12 со значениями компонентов, сгенерированными случайным образом. В качестве функции расстояния использовались метрики и .

В каждом эксперименте из имеющихся данных брался случайный вектор, который использовался в качестве объекта запроса. Выполнялись диапазонные запросы с постепенно увеличивающимся радиусом. Участвовали деревья GH, GNAT и mm-GNAT с 3 и 30 опорными точками в каждом узле. Деревья mm-GNAT строились с использованием метрик и .

На рис. 1 изображена зависимость количества вычислений расстояний от радиуса запроса при использовании метрики и 4-мерных векторов.

Лучшую производительность показали GNAT и mm-GNAT с числом опорных точек в каждом узле, равным 30. GNAT и mm-GNAT с 3 опорными точками выполняли больше вычислений расстояний. Это обусловлено тем, что чем больше кластеров содержит каждый узел, тем больше их можно исключить из процесса поиска, тем самым уменьшив количество вычислений расстояний. GH-дереву потребовалось в 2-3 раза больше вычислений расстояний, чем GNAT, поскольку фактически дерево GH - аналог GNAT с двумя опорными точками в каждом узле, выбираемыми случайным образом. Поэтому по производительности оно в большинстве случаев будет уступать GNAT. Наименее эффективными оказались деревья mm-GNAT, которые при построении использовали метрику , отличную от метрики , применявшейся при выполнении поисковых запросов.

На рис. 2 изображена зависимость количества вычислений расстояний от радиуса запроса при использовании метрики и 4-мерных векторов. Деревья GNAT и mm-GNAT с 30 опорными точками показали одинаковую производительность. Их аналоги с 3 опорными точками уступили незначительно. Дереву GH по-прежнему потребовалось примерно в 2 раза больше вычислений расстояний. В целом количество вычислений расстояний при использовании метрики меньше, чем при использовании метрики . Это обусловлено тем, что значения всегда меньше значений для одних и тех же объектов, согласно неравенству (1), поэтому больше кластеров помечаются как расположенные слишком далеко и исключаются из процесса поиска.

Рис. 1. Зависимость количества вычислений расстояний от радиуса запроса при использовании метрики и 4-мерных векторов

Рис. 2. Зависимость количества вычислений расстояний от радиуса запроса при использовании метрики и 4-мерных векторов

На рис. 3 изображена зависимость количества вычислений расстояний от радиуса запроса при использовании метрики и 12-мерных векторов. На этот раз размерность данных выросла до 12, и начало проявляться так называемое «проклятие большой размерности» - падение эффективности методов поиска с ростом количества измерений. Вычисляемые расстояния между объектами начинают стремиться к среднему значению и различаться всё меньше, поэтому всё больше объектов включаются в процесс поиска и не исключаются на шаге проверки диапазонов GNAT. Таким образом, процесс поиска сводится к линейному перебору. Тем не менее GNAT и mm-GNAT с большим количеством точек выполнили диапазонные запросы эффективнее остальных участников сравнения. Как видно, дерево mm-GNAT с метрикой построения, отличающейся от метрики запроса, свело процесс поиска к перебору, причём количество опорных точек не повлияло на количество вычислений расстояний.

Рис. 3. Зависимость количества вычислений расстояний от радиуса запроса при использовании метрики и 12-мерных векторов

На рис. 4 изображена зависимость количества вычислений расстояний от радиуса запроса при использовании метрики и 12-мерных векторов. Негативные эффекты большой размерности при использовании метрики действуют не так сильно, как при использовании метрики . Лучшую производительность показали GNAT и mm-GNAT с большим количеством опорных точек и метрикой построения, совпадающей с метрикой запроса.

Эффективность поисковых запросов с применением mm_GNAT выше, если при выполнении запросов используется та же метрика, что и при построении mm-GNAT. Это связано с тем, что больше кластеров классифицируются как расположенные далеко от объекта запроса и исключаются из процесса поиска. Если же при построении и поиске используются разные метрики, то больше кластеров классифицируются как близко расположенные, что приводит к увеличению количества вычислений расстояний.

дерево метрический гиперплоский разбиение

Рис. 4. Зависимость количества вычислений расстояний от радиуса запроса при использовании метрики и 12-мерных векторов

Метрические структуры данных с обобщённым гиперплоскостным разбиением подходят для индексации больших объёмов редко обновляющихся данных. Эффективность поиска при их использовании падает с увеличением размерности данных, что сводит процесс поиска к линейному перебору. При выполнении диапазонных запросов с применением дерева GNAT требуется в 2-3 раза меньше вычислений расстояний, чем при использовании дерева GH. Эффективность GNAT растёт с увеличением количества опорных точек. Если необходимо выполнять диапазонные запросы с применением различных метрик для одного и того же набора данных, то целесообразно использовать дерево mm-GNAT. Это позволит создать поисковый индекс один раз вместо его построения для каждой метрики. При этом эффективность mm-GNAT оказывается выше, если использовать метрику, с помощью которой осуществлялось построение дерева.

Список литературы

1. Brin, S. Near Neighbor Search in Large Metric Spaces / S. Brin // VLDB '95 Proceedings of the 21th International Conference on Very Large Data Bases. - 1995. - P. 574-584.

2. Chavez, E. Searching in metric spaces / E. Chavez, G. Navarro, R. Baeza-Yates, J. L. Marroquin // ACM Computing Surveys (CSUR) Volume 33 Issue 3, September 2001. - 2001. - P. 273-321.

3. Onishi, K. mm-GNAT: Index Structure for Arbitrary Lp Norm / K. Onishi, M. Kobayakawa, M. Hoshi // IPSJ Transactions on Database 3(3). - 2010. - P. 88-98.

4. Uhlmann, J.K. Satisfying general proximity/similarity queries with metric trees / J.K. Uhlmann // Information Processing Letters 40 (1991). - 1991. - P. 175-179.

5. Yi, B.-K. Fast Time Sequence Indexing for Arbitrary Lp Norms / B.-K. Yi, C. Faloutsos // VLDB '00 Proceedings of the 26th International Conference on Very Large Data Bases. - 2000. - P. 385-394.

Размещено на Allbest.ru