Russian Federation
GRNTI 55.01 Общие вопросы машиностроения
GRNTI 55.13 Технология машиностроения
Rassmotrena problema ocenki effektivno-sti osuschestvleniya bystrogo nechetkogo poiska na osnove matrichnyh algoritmov (AESA, LAESA, PAESA, iAESA, TLAESA) v tekstovyh slovaryah. Privedeny rezul'taty prakticheskogo analiza kolichestva vychislyaemyh rasstoyaniy v moment osuschestvleniya poiska.
metricheskie struktury dannyh, metody poiska, bol'shaya razmernost', effektivnost' algoritmov, priblizhennyy poisk, matricy rasstoyaniy
Данная задача известна как поиск ближайшего соседа. Одним из способов её решения является использование метрических структур данных для хранения и обработки информации, а также применение методов индексации метрических пространств для ускорения доступа к информации. Как правило, они базируются на метрических структурах данных. Все они последовательно делят множество данных на подмножества, близкие к опорным точкам. Существуют различные подходы: матричный подход, сферическое разбиение, гиперплоскостное разбиение [6].
В метрическом пространстве M = (X, d), определённом для множества объектов X, функция расстояния (метрика) d : X × X → R вычисляет расстояния между двумя произвольными объектами из множества X и является мерой сходства объектов. Функция расстояния должна удовлетворять условию тождества (d(x,y)=0 x=y), условию симметрии (d(x,y)= d(y,x)) и условию неравенства треугольника (d(x,z) ≤ d(x,y)+ (d(y,z)) . Также функция расстояния является неотрицательной (∀ x,y ∈ X,d(x,y) ≥0).
Вычисление расстояний между объектами считается дорогостоящей операцией [5]. Информация в метрическом пространстве хранится в виде многомерных объектов, и стоимость вычисления расстояния возрастает с увеличением размерности. Основным критерием, по которому оценивают производительность методов поиска в метрических пространствах, является количество вычислений расстояний при выполнении поискового запроса. Существующие методы индексации метрических пространств разработаны таким образом, чтобы минимизировать количество вычислений расстояний.
В данной статье описываются методы индексации, которые используют матрицу расстояний между всеми или некоторыми объектами, принадлежащими к множеству объектов данных.
Введём некоторые обозначения. Пусть U ⊆ X – множество объектов размера n, среди которых производится поиск объектов, похожих на q со степенью сходства r.
Будем осуществлять два типа поисковых запросов:
• диапазонный запрос: = {u ∈ U ∣ (d(u,q) ≤ r};
• поиск ближайших соседей: kNN = A: ∀ u ∈ A, ν ∈ U ─ A,d(u,q) ≤ d(ν,q), ∣A∣=k.
AESA. Первым предложенным алгоритмом, использующим матрицы расстояний, является AESA (Approximating and Eliminating Search Algorithm) [9]. Этот алгоритм предварительно рассчитывает все n(n-1)/2 расстояний для каждой пары из n объектов множества U и сохраняет их в матрице. На стадии поиска похожих объектов матрица используется для исключения элементов из множества кандидатов в ближайшие соседи.
Для поиска ближайшего соседа AESA на очередном шаге выбирает опорную точку u ∈ U и с её помощью отфильтровывает объекты, которые находятся заведомо далеко от объекта запроса q. Процесс повторяется, пока не будет выполнено сравнение со всеми элементами U либо они не будут заранее отброшены без непосредственного вычисления расстояния от них до q. Для выбора опорной точки на очередном шаге используется минимизирующий критерий
D(u)= , (1)
где P – множество опорных точек, для которых в процессе поиска были вычислены расстояния до объекта q. Расстояния вычисляются во время поиска, а расстояния рассчитаны заранее и помещены в матрицу. Критерий D(u) определяет сумму минимальных границ расстояний между u и q, используя неравенство треугольника.
Ниже представлен алгоритм поиска ближайшего соседа 1NN [4]:
1. Инициализация. Множество P и множество отфильтрованных элементов F изначально пустые: P ← ∅,F ← ∅.
D(u) ← 0, , r ← ∞.
Шаги 2-5 повторяются, пока U не станет равным U ∪ F ,
2. Выбор опорной точки. Очередная опорная точка выбирается согласно условию минимизации критериев 1: D(u).
3. Вычисление расстояния. Между выбранной опорной точкой и объектом запроса вычисляется расстояние . Объект добавляется к множеству P.
4. Обновление кандидата – ближайшего соседа. Если , то становится текущим ближайшим соседом. Затем для каждого объекта в согласно формуле (1) обновляется критерий D(u):
D(u) ← D(u)+ ,
max ( , ).
5. Отсеивание. Элементы u ∈ U , для которых > r, исключаются из кандидатов в ближайшие соседи и добавляются к множеству . Алгоритм возвращается к шагу 2.
AESA является одним из самых быстрых алгоритмов поиска, использующих матрицу расстояний [9]. Однако квадратичная пространственная сложность делает применение AESA непрактичным, если число элементов велико. Например, если множество содержит 10000 объектов, а расстояние между объектами занимает 4 байта, то матрица расстояний занимает 400 MB. Можно сделать вывод, что метод эффективен только для малых объёмов данных (размер которых не превышает нескольких тысяч элементов). Тем не менее если вычисление расстояний обходится дорого, а высокая стоимость предварительной обработки позволительна, производительность поиска является гораздо более высокой по сравнению с другими методами.
LAESA. Метод под названием LAESA (Linear AESA) [8] использует уменьшенную матрицу расстояний с целью снижения пространственной сложности. На стадии предварительной обработки формируется множество B⊆U, состоящее из m элементов – базовых прототипов. В LAESA матрица расстояний содержит расстояния между каждым базовым прототипом и всеми остальными элементами множества U. Пространственная сложность и время предварительной подготовки LAESA оценивается как O(m .
Алгоритм LAESA практически идентичен AESA. Основное отличие - на шаге 2: выбор опорной точки происходит только среди базовых прототипов, т.е. среди элементов множества B. Отсеивание элементов на шаге 5 выполняется, только если они не принадлежат множеству B.
Количество вычислений расстояний во время поиска LAESA, как и в случае AESA, стремится к некоторому среднему значению, растущему с увеличением размерности данных и практически не зависящему от размера множества U.
Рекомендуемый способ выбора базовых прототипов состоит в том, чтобы формировать множество B из элементов, расположенных максимально далеко друг от друга. При этом эксперименты, проведённые авторами LAESA, показывают, что существует оптимальное значение m, определяемое опытным путём, при котором количество вычислений расстояний будет минимальным.
Преимущество LAESA перед AESA заключается в том, что LAESA, производя больше вычислений расстояний по время поиска, потребляет значительно меньше памяти для хранения матрицы расстояний. Время предварительной обработки данных при использовании LAESA также гораздо меньше, чем при использовании AESA.
PAESA. Алгоритм PAESA (the Projection-based AESA – проекция на основе AESA) [5] использует матрицу расстояний, хранящую O (N(N+1)/2) расстояний между объектами, которая является очень практичным решением для больших наборов данных. Основным различием между PAESA и AESA является применение нового ограничения расстояния нижней границы для аппроксимации и исключения. В AESA для каждой точки p, выбранной из набора данных, неравенства и применяются только один раз для обновления связанной нижней границы . В алгоритме PAESA, когда точка поворота будет добавлена в набор таких точек, могут быть вычислены различные нижние границы для .
Таким образом, с выбранными M точками поворота нижние границы или для выбираются как максимум от N(N+1)/2 приближений. Следовательно, нижняя граница, определенная с помощью алгоритма PAESA, как правило, будет гораздо более строгой, чем у AESA, а значит, может быть сохранено больше расчетов расстояний.
Дополнительная нижняя граница от расстояния между двумя объектами определяется тогда, когда известны их расстояния до двух опорных точек.
Если доступно положительное полуопределенное метрическое двухмерное пространство N = (D, d), где o, p, u - неидентичные точки, принадлежащие D, o = p, то для любых q, принадлежащих D, справедливо неравенство .
При использовании метрических пространств общего вида можно расширять их мерность. Принципиально алгоритм не меняется, однако, для вычислений расстояний изменяется подсчет расстояния между точками. Для трехмерного пространства уравнения для границы аналогичные, однако расстояние измеряется в соответствии с формулой вычисления расстояний между точками в трехмерном пространстве:
Исходя из этого размерность не имеет значения, границы будут строиться на основе существующих с добавлением уровня мерности.
iAESA. Метод под названием iAESA (Improved AESA) [4] использует отличный от AESA способ выбора очередной опорной точки на шаге 2. Для этого вводятся следующие понятия:
• Отношение следования y,z ∈ X: y z .
• Перестановка: = , ,…, , где . Иначе говоря, перестановка элемента u – это множество элементов , расположенных в порядке возрастания расстояния до u.
Идея, лежащая в основе iAESA, основывается на следующем утверждении: если два объекта расположены близко, то их перестановки отличаются ненамного. Если, к примеру, объект u расположен близко к q, то будет мало отличаться от .
Для сравнения перестановок используется критерий Спирмана:
F(u)=F( =
где – индекс элемента в перестановке .
Основные отличия iAESA от AESA:
• На шаге 2 выбирается опорная точка, имеющая наименьшее значение F(u): F(u).
• На шаге 3 выбранная опорная точка p вставляется в .
• На шаге 5 опорная точка вставляется в перестановки элементов u, оставшихся после отсеивания. Затем для них обновляются значения F(u).
Временная сложность поиска iAESA в худшем случае оценивается как O( , поскольку требуется O( времени на обновление и F(u).
TLAESA. Tree-LAESA [7] – развитие метода LAESA. Основное отличие TLAESA от LAESA – сублинейная временная сложность поиска. Она достигается за счет использования бинарного дерева T, хранящего все объекты, среди которых производится поиск. Как и в LAESA, используется матрица расстояний M между опорными точками и остальными объектами. Во время выполнения поиска матрица M используется для исключения тех ветвей, объекты в которых находятся заведомо далеко от объекта запроса. Алгоритм состоит из двух стадий.
Стадия предварительной обработки:
• Формируется подмножество опорных точек . Первая опорная точка выбирается случайным образом, а в качестве остальных выбираются точки, находящиеся на максимальном расстоянии друг от друга: , где .
• Формируется бинарное дерево T. Каждый узел соответствует подмножеству . Если t – листовой узел, то содержит один объект. В противном случае , где и – левый и правый потомки t. В каждом узле хранится опорная точка и радиус Для листового узла
Для корневого узла подмножество , а выбирается случайным образом. Для правого потомка каждого узла t опорная точка совпадает с опорной точкой самого узла: В качестве опорной точки левого узла берется объект, находящийся на максимальном расстоянии от опорной точки узла: .
В подмножество правого потомка входят те объекты, которые находятся ближе к . Остальные объекты помещаются в подмножество левого потомка
• Формируется матрица M, в которой хранятся расстояния между каждой опорной точкой и всеми остальными элементами U.
Стадия поиска:
• Формируется D – вектор расстояний от всех опорных точек до объекта запроса: При этом находится наибольшая из нижних границ расстояний от корня дерева до объекта запроса, полученная с помощью опорных точек и неравенства треугольника: . Также определяется ближайшая к объекту запроса опорная точка.
• Производится рекурсивный поиск в дереве. Если t – листовой узел и нижняя граница расстояния между ним и объектом запроса q меньше, чем расстояние до текущего ближайшего соседа , то вычисляется расстояние d(t,q). Если оно меньше , то t объявляется новым ближайшим соседом.
Если t – узел с потомками, то производится рекурсивный поиск в левом и правом поддеревьях. Сравниваются нижние границы расстояний от опорной точки узла до объекта запроса, и первым производится поиск в том поддереве, в котором эта граница меньше.
Оценка эффективности рассмотренных методов
В таблице приведены оценки сложности рассматриваемых в статье алгоритмов.
Пространственная сложность и временная сложность предварительной обработки AESA оценивается как , поскольку AESA хранит матрицу расстояний между всеми парами элементов U. Временная сложность поиска в худшем случае оценивается как . Экспериментально показано, что в среднем количество вычислений расстояний во время поиска является постоянным и практически не зависит от n [1; 2]. С ростом размерности данных количество вычислений расстояний увеличивается. Таким образом, временную сложность поиска AESA можно оценить как O(1).
Пространственная сложность и время предварительной подготовки LAESA оценивается как O(mn). Временная сложность поиска оценивается как m+O(1) [8].
Для iAESA требования к памяти не отличаются от AESA. Временная сложность поиска в худшем случае оценивается как , поскольку требуется O(|P|) времени на обновление и F(u).
Для TLAESA сложность поиска варьируется между O(log n) и O(mn).
Оценки пространственной сложности поиска PAESA и LPAESA совпадают с AESA и LAESA соответственно.
Таблица
Оценка сложности алгоритмов
Алгоритм Пространственная сложность Временная сложность выполнения поискового запроса
AESA
LAESA
iAESA
TLAESA
PAESA
LPAESA
В данной работе была изучена ситуация, когда LAESA быстрее и дешевле, чем AESA. В предыдущих работах было выявлено, что AESA - наилучший алгоритм, потому что он вычисляет меньше расстояний. Тем не менее стоимость функции несхожести очень важна для конечного результата.
Также был предложен метод Reduced Overhead AESA (ROAESA), отличающийся от AESA и LAESA уменьшенным потреблением памяти.
1. Gulakov, V.K. Analiz metodov poiska v metricheskih prostranstvah na osnove sfericheskogo razbieniya mnozhestva ob'ektov / V.K. Gulakov, V.N. Matyushin // Informacionnye tehnologii, radioelektronika, telekommunikacii (IIRT-2014): IV mezhdunar. zaoch. nauch.-tehn. konf. - Tol'yatti, 2014. - S. 98-102.
2. Gulakov, V.K. Ocenka effektivnosti ispol'zovaniya metricheskih derev'ev v priblizhennom poiske na osnove obobschennogo giperploskostnogo razbieniya mnozhestva ob'ektov / V.K. Gulakov, V.N. Matyushin // Vestnik Bryanskogo gosudarstvennogo tehnicheskogo universiteta. - 2013. - № 4. - S. 106-112.
3. Chavez, E. Proximity searching in metric spaces / E. Chávez, G. Navarro, R. Baeza-Yates, J.L. Marroquin // ACM Computing Surveys (CSUR). - 2001. - Vol. 33. - Is. 3. - P. 273-321.
4. Figueroa, K. On the Least Cost for Proximity Searching in Metric Spaces / K. Figueroa, E. Chávez, G. Navarro, R. Paredes // 5th International Workshop, WEA 2006. - Cala Galdana, Menorca, Spain, 2006. - P. 279-290.
5. Matthew, A.S. Aspects of Metric Spaces in Computation / A.S. Matthew. - Waterloo, Ontario, Canada, 2008. - P. 258.
6. Samet, H. Foundations of Multidimensional and Metric Data Structures / H. Samet. - Imprint: Morgan Kaufmann, 2006. - 1024 p.
7. Tokoro, K. Improvements of TLAESA Nearest Neighbor Search Algorithm and Extension to Approximation Search / K. Tokoro, K. Yamaguchi, S. Masuda // In Proc. Twenty-Ninth Australasian Computer Science Conference (ACSC 2006). - Australian Computer Society, Inc. Darlinghurst, Australia, 2006. - P. 77-83.
8. Vidal, E. An algorithm for finding nearest neighbors in (approximately) constant average time / E. Vidal // Pattern Recognition Letters. - 1986. - Vol. 4 (3). - P. 145-157.
9. Vidal, E. A new version of the nearest-neighbor approximating and eliminating search algorithm (AESA) with linear preprocessing-time and memory requirements / E. Vidal, L. Mico, J. Oncina // Pattern Recognition Letters. - 1994. - Vol. 15 (1).
