Диссертация (1137145), страница 12
Текст из файла (страница 12)
Степеннуюзависимость можно видеть на нижнем рисунке 36 у структурыпостроенной алгоритмом MSWConstrcution с параметрами u=12 w=10 надмножеством из 100 тысяч случайных точек распределенных равномерно вединичном гиперкубе размерностью 30. Распределение степеней вершин уструктуры построенной алгоритмом ConstructionByReparing, в отличии отструктуры построенной алгоритма MSWContruction, имеет более сложнуюзависимость, определить которую в рамках данной работы не удалось.760E+001E+002E+024E+026E+028E+021E+031E+03MSWConstructionu=12w=10Додлявершин1E-01InsertbyRepairt=91E-021E-031E-041E-051E-06Степеньвершины1E+001E+001E+011E+021E+031E+04MSWConstructionu=12w=10Додлявершин1E-01ConstructionByReparingt=91E-021E-031E-041E-051E-06СтепеньвершиныРис.
36. Распределение степеней вершин. В структуре построенной над множеством из100 тысяч случайных точек распределенных равномерно в единичном гиперкуберазмерностью 30. Нижний график построен в двойном логарифимечком масштабе. Наверхнем графике логарифмический масштаб имеет только ось ординат.3.5 Коэффициент кластеризацииСуществуюнесколькоразличныхопределенийкоэффициентакластеризации. В данном исследовании использовалось определениеданное в работе [T.
Opsahl, 2003].Интереснуюзакономерностьповедениясреднегокоэффициентакластеризации можно видеть на рис. 37. Оно интересно тем, что внекоторых случаях, коэффициент кластеризации остаётся постоянным сростом числа элементов в структуре. Кроме того из графика можно видеть,что коэффициент кластеризации для77фиксированной размерностипространстваизменяетсявопределённомдиапазоне,которыйсоответствует данной размерности.0,7Среднийкоэффициенткластеризации0,60,50,40,30,20,10100010000100000Количествоэлементов1000000dim=1;u=2dim=1;u=4dim=1;u=6dim=2;u=2;dim=2;u=3dim=2;u=4;dim=3;u=2;dim=3;u=3;dim=3;u=4dim=3;u=5dim=3;u=6dim=6;u=10dim=10;u=10dim=10;u=20dim=10;u=14dim=10;u=8dim=30;u=20dim=4;u=2dim=4;u=3dim=4;u=4dim=4;u=5dim=4;u=6dim=4;u=7dim=4;u=8dim=4;u=9dim=1;u=3dim=1;u=5dim=6;u=2Рис.
37. Зависимость коэффициента кластеризации от числа элементов в структуре3.6 Вычислительная сложность и точность алгоритма поискаВ данном эксперименте учитывалось количество просмотренныхэлементов, как во время удачных поисков, так и в случае неудачных. Длякаждого набора параметров (dim, u) эксперименты производились на 20,независимо собранных структурах. Значения усреднялись.
Ось ординатсоответствует квадратному корню от среднего числа просмотренныхэлементов. Как можно видеть на рисунке 38, точки на графиках ложатся вблизи примой линии, из чего можно сделать предположение о зависимости~log ()! , где константа растёт пропорционально значению параметра«u».7810501000100001000001000000Количествоэлементовdim=4;u=2dim=4;u=3dim=4;u=4dim=4;u=5dim=4;u=6dim=4;u=7dim=4;u=8dim=4;u=925201510501000100001000001000000Количествоэлементовdim=10;u=7dim=10;u=8dim=10;u=10dim=10;u=14Квадратныйкореньчислапросмотренныхэлементов151816141210Квадратныйкореньчислапросмотренныхэлементов20КвадратныйкореньчислапросмотренныхэлементовКвадратныйкореньчислапросмотренныхэлементов25dim=10;u=20864201000100001000001000000Количествоэлементовdim=6;u=2dim=6;u=3dim=6;u=4dim=6;u=5dim=6;u=10dim=6;u=73025201510501000100001000001000000Количествоэлементовdim=1;u=6dim=4;u=8dim=10;u=20dim=20;u=7dim=3;u=6dim=6;u=10dim=15;u=10dim=30;u=20Рис. 38.
Зависимость среднего числа элементов, до которых было вычисленорасстояние жадным алгоритмом.790,90,80,70,60,50,40,30,20,101000100001000001000000ДоляуспешныхпоисковжаднымалгоритмомДоляуспешныхпоисковжаднымалгоритмом110,90,80,70,60,50,40,30,20,1Количествоэлементовdim=4;u=2dim=4;u=3dim=4;u=4dim=4;u=5dim=4;u=6dim=4;u=7dim=4;u=8dim=4;u=9ДоляуспешныхпоисковдажднымалгоритмомДоляуспешныхпоисковжаднымалгоритмом0,90,80,70,60,50,40,30,20,1100001000001000000100000100000010,90,80,70,60,50,40,30,20,101000100001000001000000Количествоэлементоввструктуре,nКоличествоэлементовdim=10;u=7dim=10;u=8dim=10;u=1010000Количествоэлементовdim=6;u=2dim=6;u=3dim=6;u=4dim=6;u=5dim=6;u=7dim=6;u=1010100001000dim=1;u=6dim=4;u=8dim=10;u=20dim=20;u=7dim=10;u=14dim=10;u=20dim=3;u=6dim=6;u=10dim=15;u=10dim=30;u=20Рис.
39. Зависимость доли успешных поисков от числа элементов в структуре.Точность поиска жадным алгоритмом имеет тенденцию снижаться сростом числа элементов в структуре (см. рисунок 39). Это легкообъясняется тем, что длина «жадного» пути растёт, в тоже время накаждом шагу есть некоторая не нулевая вероятность остановиться влокальном минимуме.80Тем не менее, при достаточно больших значениях u, с ростом n,точность поиска остаётся равной единице (правый нижний график нарисунке 39, кривая dim=1; u=6).3.7 MSW – как структура данных для поиска ближайшегососеда. Сравнительный анализ с другими структурамиданных для поиска ближайшего соседа.Одним из общепринятых способов оценки точности поиска являетсяrecall.
Значение recall вычисляется как| {x : x ∈ knn(q, X )} |, где knn(q, X ) kмножество истинно ближайших объектов к запросу q во множестве X .На сегодняшний день было предложено множество структур данных,как для точного, так и для приближенного поиска k-ближайших. Хорошийобзор методов для точного поиска приведён в [Chávez E., и др., 2001] иметодов для поиска в неметрическом пространстве [Skopal T., Bustos B.,2011]. Однако для многих методов отсутствуют теоретические оценки.Поэтому,основнымспособомвыявлениянаиболееэффективнойструктуры данных, остаётся запуск методов на общих наборах данных сиспользованием одинакового оборудования.
Во время экспериментовизмеряется время работы, количество обращений к функции близости dна этапах предобработки (индексирования) и исполнения запросов.Ранее сообществом поддерживалась библиотека методов для точногопоиска ближайшего соседа "metric space library" [Figueroa K., Navarro G.,Chávez E., 2007]. Однако с пониманием неэффективности точных методовна практике, мотивация поддерживать данную библиотеку исчезла. Тем неменее, недавно была создана открытая библиотека “Non-Metric SpaceLibrary” [Boytsov L., Naidan B., 2013], включающая методы дляприближенного поиска, различные функции близости, включая неметрики[Kullback S., Leibler R.
A., 1951][ Jung, J., и др., 2011], и наборы данных.81Далееприводятсярезультатысравненияметодов,используяэтубиблиотеку.3.7.1 Сравниваемые методы3.7.1.1 VP-деревоVP-дерево (Vantage Point Tree)– метод основанный на иерархическомразбиении пространства, который на этапе поиска использует неравенствотреугольника для исключения областей заведомо не содержащих запрос[Uhlmann J. K., 1991], [Yianilos P. N., 1991]. Оригинальная версия этогометода поддерживала только точный поиск. Тем не менее, ослаблениенеравенства треугольника, допуская «растяжение» [Chávez E., Navarro G.,2003],позволяетиспользоватьданнуюструктуруданныхдляприближенного поиска, как в метрическом, так и в неметрическихпространствах [Boytsov L., Naidan B., 2013].Оптимальноезначениеэкспериментально.коэффициентарастяженияопределялосьСначала строилась структура из небольшого числаслучайно выбранных объектов; производился поиск 10 ближайшихэлементов, используя различные значения коэффициента растяжения;замерялась производительность и точность поиска.
Далее, выбиралосьзначение коэффициента, при котором достигалась наибольшая скоростьдля заданного значения точности.3.7.1.2 Методы основанные на перестановках (Permutation Methods)Идея методов основанных на перестановках, заключается в том, чтоблизкие к друг другу объекты метрического пространства будут "видеть"фиксированноемножествоP = { pi ∈ D}im=1 , называемых опорнымиобъектами (pivots) в одном и том же порядке.
Эта последовательностьрассматривается в качестве перестановки, которую можно представить ввиде целочисленного вектора. Так каждый объект x ∈ X представляетсяперестановкойΠxэлементовмножества82P .ПерестановкаΠxсоответствующая объектуx,определяется порядком следования опорныхточек в порядке возрастания расстояния σ (x, pi ) . Первая позиция вперестановке, соответствует номеру самого близкой опорного объекта кобъектуx , последняя - номеру самого удалённого.Данный подход позволяет сократить размерность и помогает перейти квекторному представлению данных, в случае когда объекты метрическогопространства изначально не имеют координатного представления.На этапе исполнения запроса сначала вычисляется расстояние междузапросом q и опорными точками P , строится перестановка Π q .
Далее,проиндексированныеобъекты,сортируютсявпорядкепохожестиперестановок относительно перестановки Π q . В свою очередь, похожестьперестановок можно определять различными способами. Это приводит кразличным вариациям методов основанных на перестановках.
Один изпервых основанных на перестановках методов был предложен независимоЧавесом и соавторами [Gonzalez E. C., и др., 2008], а так же Амато иСавино [Amato G., Savino P., 2008].В базовой версии опорными точками является множество случайновыбранных объектов из множества X . Перестановки хранятся в видемассива и вычисляются для каждого объекта из X . На этапе поискавычисляется похожесть (обычно используется евклидово расстояние)между перестановкой Π q и каждой перестановкой Π i . Формируетсясписок объектов кандидатов, сортируемый относительно близости ихперестановок к перестановке Π q .
Выбирается подмножество объектов снаименьшим значением расстояния. До каждого объекта из подмножествавычисляетсярасстояние,непосредственно,используя изначальную меру близостиσдообъекта-запроса q ,. Среди них выбираются kближайших к q и возвращаются в качестве результата.83Существует несколько путей улучшить базовую версию.
Первый –уменьшить число перестановок близких к Π q [Gonzalez E. C., и др., 2008].Второй, - проиндексировать перестановки, вместо того, чтобы искатьнаиболее близкую перестановку последовательно. Для этого можноиспользовать дерево префиксов [Esuli A., 2012], обратный индекс [AmatoG., Savino P., 2008], либо метод для поиска в метрических пространствах,например VP-дерево [Figueroa K., Frediksson K., 2009].Недавно, было предложено индексировать окрестность опорныхобъектов, т.е. для каждого объекта x ∈ X формировать множество Pxнаиболее близких опорных точек, такое что | Px |<< m и | Px ∩ P |= 0 [TellezE.S., 2013] Идея в том, что близкие объектыxи y имеют не пустоепересечения окрестностей | Px ∩ Py |≠ 0 .Предварительные эксперименты показали, что в зависимости от набораданных,наиболееперестановках,эффективнымиявляютсяследующиеметодамиметоды:основаннымибазоваянаверсияиспользующая частичную сортировку (incremental sorting), приближеннаяверсия использующая VP-дерево в качестве индекса перестановок"permutation (VP-tree)", и вариация индексирующая окрестность опорныхвекторов (pivot neighborhood index).3.7.1.3 Хэширование сохраняющиее близость (LSH)Хэширование сохраняющее близость (англ.
Locality Sensitive Hashing,сокр. LSH) – класс методов использующих хэш-функции принимающих сбольшой одно и тоже значение для близких объектов и разное дляудаленных. На сегодняшний день было предложено множество классовтаких функций для различных видов мер близости и распределенийданных [Dong W., и др., 2008], [Indyk P., Motwani R. 1998]. Метод широкоизвестен за счёт наличия вероятностных оценок и простоте реализации.Однако LSH имеет трудности обработки данных с различной плотностью84распределения.
Кроме того LSH нельзя использовать для произвольныхметрических пространств. Он применим только для определенныхсемейств функций расстояний, для которых известны эффективные LSHфункции. Тем не менее это очень сильный метод в случае Lp пространств.В экспериментах использовалась версия multiprobe LSH [Dong W., и др.,2008], которая была реализована в рамках библиотеки LSHKIT [Dong W.,и др., 2008].3.7.1.4 Список кластеров (List of Clusters)Список кластеров (List of Clusters) – метод для точного поискаближайшего соседа в метрическом пространстве, который основывается нагруппировании объектов в кластеры [Chávez E., Navarro G., 2005].Кластеры строятся последовательно, начиная со случайно выбранногоцентра кластера. Далее, точки находящиеся от центра кластера нарасстоянии не далее чем R или N ближайших точек, ассоциируют ссоответствующим кластером.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
