Диссертация (1137145), страница 13
Текст из файла (страница 13)
После чего процедура кластеризацииповторяется для оставшихся точек. В экспериментах использоваласьстратегия ассоциирования N ближайших к центрам кластеров и центрывыбирались случайным образом.Алгоритм поиска сканирует множество сконструированных кластеров и,используя неравенство треугольника, проверяет, может ли потенциальныйответ лежать в рассматриваемом кластере. Если кластер может содержатьответ, то каждый объект из кластера сравнивается непосредственно сзапросом.Далеепроверяется,можетлиответсодержатьсявнерассматриваемого кластера. Если не может, то поиск останавливается.В экспериментах использовалась приближенная версия алгоритма,добавив в алгоритм поиска стратегию ранней остановки. Процесс поискаостанавливается после просмотра фиксированного числа кластеров(параметр алгоритма). Множество кластеров рассматривается в порядкевозрастания расстояния от запроса до центров кластеров.853.7.2 ЭкспериментыПроизводились сравнения методов на различных наборах данных,используя три различные функции расстояния:• Евклидово расстояние (L2);• Неметрическая функция расстояния Кульбака Лейблера (KLдивергениция): d ( x, y) = ∑ xi logA.
1951];• Косинусуглаd ( x, y ) = 1 −между∑ xi yixi2∑∑CoPhIRyi2xi[Kullback S., Leibler R.yiвекторамиUnif641000Сокр.выч.метрики(раз)Сокр.выч.метрики(раз)Сокр.выч.метрики(раз)10001001001010,60,70,8Точность0,9100,50,60,70,8Точность0,910,60,70,80,91Точностьmultiprobelshpermutation(incr,sorting)permutation(vptree)listofclustersvptree:triangleinequalitymetrizedsmallworldpermutation(inv.indexneighb.pivots)0,60,70,8Точность0,91Общееускорение(раз)110,50,51010101100Общееускорение(раз)100101100Общееускорение(раз)100010011similarity):.SIFT10000,5(cosine0,50,60,70,80,91Точностьmultiprobelshpermutation(incr,sorting)permutation(vptree)listofclustersvptree:triangleinequalitymetrizedsmallworldpermutation(inv.indexneighb.pivots)0,50,60,70,80,91Точностьmultiprobelshpermutation(incr,sorting)permutation(vptree)listofclustersvptree:triangleinequalitymetrizedsmallworldpermutation(inv.indexneighb.pivots)Рис. 40.
Результаты экспериментов поиска 10-ближайших с функцией расстояния L2.Графики из одного столбца соответствуют одному набору данных. CoPhIR - первыйстолбец, SIFT - второй, Unif64 - третий.863.7.3 Методология оценкиЭксперименты производились на Linux Intel Xeon сервере с частотой3.60 GHz, 32GB оперативной памяти в однопоточном режиме, используябиблиотеку Non-Metric Space Library в качестве инструмента длявалидации [Boytsov L., Naidan B.]. Программная реализация была написанана C++ и скомпилирована при помощи GNU C++ 4.7 (с ключомоптимизации «-Ofast»).Использовалась реализация функций расстояний оптимизированные припомощиSSEдополнительное4.2SIMDинструкций.ВслучаеKL-дивергенцииускорениедостигалосьзасчётпредварительноговычисления логарифмов элементов векторов на этапе построения индекса[BoytsovL.,NaidanB., 2013].
В реализации функции вычислениякосинуса угла между векторами, использовалась инструкция сравнения_mm_cmpinstrm «все-против-всех» . Эта реализация около 2.5 разабыстрее, чем реализация на чистом С++.Для проведения экспериментов случайным образом был разделенкаждый тестовый набор на две части. Меньшая часть содержала только1000 объектов и использовалась в качестве множества запросов.Оставшиеся объекты индексировались.
После индексации тестироваласьпроизводительность методов, производя поиск 10 ближайших элементов(10-NN search). Все методы полностью размещались в оперативнойпамяти. Процедура поиска повторялась пять раз для различных значенийпараметров для того, чтобы получить различные значения точности ииметь некоторое усреднение (значение параметров выбирались вручную).Большинство методов тестировались на всех тестовых наборах данных.Multi-probe LSH и Список кластеров использовались только для Евклидоварасстояния. VP-дерево не использовалась для Wikipedia, связи с высокойразмерностью тестового набора, на котором VP-дерево работала чутьлучше полного перебора.87Результаты сравнения методов для Евклидова расстояния и для KLдивергенции приведены на рисунках 40 и 41 соответственно. График впервой строке показывает во сколько раз тот или иной метод делаетменьше вычислений функции расстояния в сравнении с полным переборомдля различных значений точности.
Во второй строке по вертикалиотложено значение во сколько раз метод быстрее полного перебора (времяработы).Как видно из графиков на рисунках 40 и 41, метод MSW имеетнаилучшее соотношение точности и производительности на всех трёхтестовых наборах данных. Рассмотрим, например, тестовый набор данныхCoPhIR (рисунок 40).
Для значения точности (recall) 0.9 метод MSWвычисляет в 1000 раз меньше расстояний, чем полный перебор. Остальныеметоды для этого значения точности превосходят полный перебор менеечем в сто раз. Подобную производительность метод LSH имеет только длязначения точности 0.4.1000Сокр.выч.метрики(раз)Final2561000Сокр.выч.метрики(раз)Final641000Сркр.выч.метрики(раз)Final16100100100101010110,50,60,70,8Точность0,90,5110000,60,70,8Точность0,90,70,8Точность0,9permutation(incr.sorting)permutation(vptree)vptree:triangleinequalitymetrizedsmallworldpermutation(inv.Indexneighb.pivots)0,8Точность0,910,91110,60,7100,50,60,70,80,9Точность0,50,6Общееускорение(раз)Общееускорение(раз)Общееускорение(раз)10100,510010010011110,510,60,70,8Точноть0,1permutation(incr.sorting)permutation(vptree)vptree:triangleinequalitymetrizedsmallworldpermutation(inv.ind.neighb.pivots)88permutation(incr,sorting)permutation(vptree)vptree:triangleinequalitymetrizedsmallworldpermutation(inv.Indexneighb.pivots)Рис.
41. Результаты экспериментов поиска 10-ближайших с функцией расстояния KLдивергениции. Графики из одного столбца соответсвуют одному набору данных:Обычно, чем меньше раз метод вычисляет функцию расстояния, тембыстрее он работает. Однако для «недорогих» функций расстояний,например, Евклидова расстояния, скорость работы метода зависит ненапрямую от количества вычисленных функций расстояния.
Рассмотримтестовый набор Unif64 на рис. 1 и Final256 на рис. 41: несмотря на то, чтоMSW использовал меньше всего вычислений расстояний во всех случаях,однако дополнительные вычислительные расходы, связанные с обходомграфа, могут быть высокими. Как результат pivot neighborhood index илиmulti-probeLSHиногдапоказываютлучшуюитоговуюпроизводительность.Отметим, что MSW и inv. neighborhood index хорошо работают длярасстояния KL-дивергенции. Для всех трёх наборов данных с функцийрасстояния KL-дивергенции они показывают ускорение более чем в 10 раз,по сравнению с полным перебором, для значения точности 0.9.Результаты сравнения методов на данных Wikipedia представлены нарис. 42(а). Верхний график показывает во сколько раз метод совершаетменьше вычислений расстояний по сравнению с полным перебором дляразличныхзначенийточности.Соответственно,нижнийграфикизображает во сколько раз методы работают быстрее полного перебора дляразных значений точности.
Несмотря на то, что использоваласьулучшенную реализацию функции вычислениякосинуса угла междудвумя векторами с помощью инструкций SIMD, которая 2.5 раза быстрее,чем обычная реализацию на чистом C++, вычисление скалярногопроизведения продолжает оставаться вычислительно затратной операцией.По этой причине сокращение количества вычисленных расстояний,напрямую влияет на общую скорость работы методов.8910001,8E+06Кол-вовычисленийметрикисокр.выч.Метрики(раз)1,6E+06100101,4E+061,2E+061,0E+068,0E+056,0E+054,0E+052,0E+050,0E+000,0E+00 5,0E+05 1,0E+06 1,5E+06 2,0E+06 2,5E+06 3,0E+06 3,5E+0610,50,550,60,650,70,750,80,850,90,951Кол-воэлементоввструктуреТочность10001,8E+06Кол-вовычисленийметрикиОбшееускорение(раз)1,6E+06100101,4E+061,2E+061,0E+068,0E+056,0E+054,0E+052,0E+050,0E+001,0E+0410,50,60,70,8Точностьperm.Vp-treemetrizedsmallwolrd0,911,0E+051,0E+061,0E+07Кол-воэлементоввструктуреperm.Incrsortingperm.Invertedindexperm.vp-treeperm.incr.sort.metrizedsmallworldperm.inv.index(а) Фиксированный набор состоящий из 3 (б) Зависимость скорости поиска от числа200 000 элементов.проиндексированных элементов.Рис.
42. Результаты с набором данных Wikipedia. В качестве расстояния использоваласьфункция косинуса угла между векторами.Как видно из графика, на этом наборе данных MSW работаетзначительно лучше остальных методов. Например, для точности 0.87 MSWпримернов40разбыстрееполногоперебора.Следующийпопроизводительности метод (pivot neighborhood index) достигает такойпроизводительности при значительной меньшей точности 0.6.Для того чтобы понять, как производительность методов зависит отразмера набора данных, производились эксперименты с Википедией.ПроизводилисьзамерыдляподмножествВикипедии,чейразмерварьировался от 12.5 тыс.
до 3.2 миллионов элементов. На каждомтестовом подмножестве для каждого метода запускалась процедура поисканесколько раз с различными параметрами для того, чтобы получитьрезультаты для различных значений точности. Для MSW использовались90параметры,которыедавали0.9,тогдакакдлядругихметодовиспользовались параметры, приводившие к точности 0.8. Результатыэкспериментов приведены на рис. 42(б). Нижний график включает в себярезультаты для всех методов, верхний – только MSW и pivot neighborhoodindex.Как видно из рис.
42(б), все сравниваемые методы, основанные наперестановках, имеют зависимость от количества объектов близкую клинейной. В то время как MSW демонстрирует зависимость близкую клогарифмической(добавитьграфиквдвойномлогарифмическоммасштабе) и при этом имеет большую точность (0.9 против 0.8). Такимобразом, MSW имеет принципиально другую вычислительную сложностьи превосходит в производительности сравниваемые методы тем больше,Сокращениевычислениеметрики(разчем больше набор входных данных.1E+041E+031E+020,20,30,40,50,60,70,80,91ТочностьNN12Rep.t=9NN20Рис. 43. результаты сравнения свойств структуры построеннойалгоритмомConstructionByReparing с алгоритмом соединения с k-ближайшими соседямиMSWConstruction u=12 (NN12) и u=20 (NN20)На рисунке 43 приведеныпостроеннойалгоритмомрезультаты сравнения свойств структурыConstructionByReparingсалгоритмомсоединения с k-ближайшими соседями MSWConstruction.
Параметры былиу ConstructionByReparing t=9, у алгоритма MSWConstruction w = 10; u = 12и 20 соответственно. В входных данных выступали миллион случайных91точек, равномерно распределенных в единичном 30-мерном гиперкубе. Вкачестве функции расстояния использовалась L2 .3.8 Улучшения навигационных свойств графа с помощьюпроцедуры Repair_By_QueryЧтобыпроверитьидеювозможностиулучшениянавигационных(поисковых) свойств графа, используя поток входящих запросов, былпроизведён следующий эксперимент. Алгоритмом ConstructionByReparingс параметром t = 9 была построена структура на множестве из 10 000точек, равномерно распределенных в 30-мерном единичном гиперкубе.После этого были сгенерированы 100 раз 1000 запросов с одинаковымраспределением.
Каждый раз после применения 1000 раз процедурыRepair_By_Query измерялось точность поиска 5-ти ближайших соседей. Вкачестве алгоритма поиска мы использовали алгоритм K-NNSearch.Параметр m брался = 1, 2 и 4 соответственно. Как видно из рисунка 44,точность каждого поиска увеличилась после применения процедурыRepair_By_Query.Также измерялась общая эффективность структуры после применениипроцедурыRepair_By_Query.Измерялосьзначениеповышенияэффективности (во сколько раз меньше алгоритм вычисляет расстояний посравнению с полными перебором), и значения точности поиска послеприменения процедуры Repair_By_Query 100,000 и 1,000,000 раз кструктуре, построенной над множеством из 100,000 30-мерных точек спомощью алгоритма ConstructionByReparing (рисунок 45).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
