Диссертация (1137145), страница 10
Текст из файла (страница 10)
24. Построение структурыминимумовс помощью процедуры устранения локальныхАлгоритм InsertByRepairing можно рассматривать качестве одного извозможных способов построения некоторой аппроксимации множествасоседей области Вороного добавляемого элемента.Для построения структуры обладающими свойствами навигационноготесного мира с помощью процедуры устранения локальных минимумов,опять же используется идея инкрементального добавления элементов вслучайном порядке (см.
алгоритм на рисунке 24). Ниже на рисунке 25приведён пример графа построенного алгоритмом СonstuctionByReparingдля точек Евклидовой поскости.Рис 25 Пример структуры построенной алгоритмом СonstuctionByReparing намножестве точек Евклидого пространства. Числа рядом с окружностями соответствуютпорядку добавления элементов в структуру.602.8 Процедура улучшения поисковых свойств сети за счётиспользования информации о запросахКак было отмечено ранее, обнаружить локальный минимум можно налюбом этапе существования структуры, как на этапе добавления элементовв структуру, так и на этапе исполнения запросов.
Пользуясь даннымобстоятельствомпоисковыхпредлагаютсясвойствструктурыследующаянаэтапепроцедураисполненияулучшениязапросовRepairByQuery (см. рисунок 26). Процедура RepairByQuery аналогичнапроцедуреInsertByRepairing с тем исключением, что локальныеминимумы ищутся относительно запроса – некоторого элемента q измножества всевозможных объектов D .RepairByQuery( q ∈ D , G(V, E) , τ ∈ Ν )01 L, P ← Get_Local_Minimums( q , G , τ )02 x ← arg min(d ( y, q))y∈L030405for each z ∈ L \ x doP' ← { y ∈ P : d ( y, q) < d ( z, q)}x' ← arg min(d ( z, y))y∈P'E ← E ∪ ( x' , z ) ∪ ( z , x' )0607 end forРис. 26. Процедура устранения локальных минимумов на этапе исполненияпоисковых запросов.2.9 ВыводыВ главе были предложены алгоритмы построения структуры в видеграфа над конечным множеством используя функцию расстояниязаданную внешним образом.
Был предложен алгоритм приближенногопоиска k-ближайших соседей на графе, а также алгоритм улучшенияпоисковых свойств структуры на за счёт дополнительной информации озапросах. Важно, что все предложенные в главе алгоритмы не используютвекторное представление данных, опираются только на вычислениезначения функции расстояния и используют только локальное знание оструктуре сети.61Глава3.ИсследованиесвойствпредложенныхалгоритмовЧтобыиметьвозможностьпроанализироватьсвойстваструктур,получаемых в результате работы алгоритмов предложенных в главе 2, онибыли реализованы на языках программирования Java и С++.
ИсходныйкодреализациинаязыкеJavaдоступен[https://github.com/aponom84/MetrizedSmallWorld].С++поадресуреализациядоступна в качестве части библиотеки методов для поиска ближайшегососеда Non-Metric Space Library [Boytsov L., Naidan B., 2013].В главе исследуются такие свойства структуры, как средняя длинакратчайшего пути между всеми парами вершин, диаметр графа,коэффициент кластеризации, средняя длинна пути пройденная жаднымалгоритмом, устойчивость к выпадению произвольных вершин, точностьпоиска k-ближайших, количество вычислений функции расстоянияалгоритмом поиска.
Устанавливалась взаимосвязь этих характеристик ипараметров алгоритмов. Эксперименты производились на различныхвходных данных. Использовались синтетические данные и реальныенаборы данных.Цели эмпирического исследования не включали в себя проведениесравнения производительности с алгоритмами приведенными в первыхдвух главах, поскольку они решают задачи разного класса. Более тогобольшинства алгоритмов первых двух глав известна теоретическая оценкавычислительной сложности алгоритма поиска.
Алгоритмы из первогораздела первой главы имеют сложность поиска класса (log ) .Алгоритмы из второго раздела первой главы опираются на модельКлайнберга и имеют сложность поиска из класса ((log )! ), где –размерность векторного пространства. Поэтому предложенные алгоритмысравнивалась с популярными методами для поиска ближайшего соседа.62Материалы главы в полной мере изложены в следующих публикациях:[Alexander Ponomarenko, Nikita Avrelin et.al., 2014], [Пономаренко А.
А.,Аврелин Н. С. и др., 2015]3.1 Наборы данныхВ экспериментах использовались следующие наборы данных.1) CoPhIR (L2): коллекция 208-мерных векторов извлечённых изизображений в формате MPEG7 [Bolettieri P. и др., 2009]. Векторасоставлены из пяти различных свойств MPEG7.2) SIFT (L2): часть коллекции данных TexMex [Jegou H., и др., 2011].Содержит 1 миллион 128-мерных векторов. Каждый векторсоответствует дескрипторам извлеченных из изображений методом«Scale Invariant Feature Transformation» (SIFT) [Lowe D.
G., 2004]3) Википедия (cosine similarity): коллекция состоящая из 3.2 миллионоввекторов в разряженном формате. Каждый вектор хранит частотувстречаемости каждого слова в конкретной странице Wikipedia.Вектора были построены при помощи библиотеки gensim [ŘehůřekR., SojkaP., 2010]. Вектора в этом наборе данных имеютсверхвысокую размерность – более 100 тысяч компонентов. Однако,вектора разряженные. В среднем, каждый вектор имеет только около150 ненулевых компонент.4) Unif64(L2):синтетическийнабор64-мерныхвекторовсгенерированных случайно с равномерным распределением вединичном гиперкубе.5) Final16, Final64 и Final256 (KL-дивергенция): набор из 500 тысячгистограмм заголовков полученных с помощью латентногоразмещения Дирихле (LDA) [Blei D.
M., и др, 2003]. Числовойсуффикс названия коллекции соответствует размерности, котораяравна количеству LDA-заголовков (топиков). Данные коллекциибыли созданы Кейтоном [Cayton L., 2008]633.2 Исследование навигационных свойств: распределениедлины кратчайшего пути и распределение длины путисовершаемой жадным алгоритмом.Одной из важнейших характеристик графа (сети), c точки зрения поиска,является возможность жадным алгоритмом («Greedy Walk»; такжеупотребляется термин «greedy roting») находить вершину, ближайшую кзаданному объекту относительно функции расстояния : × ⟶ ! .Про граф обладающий данным свойством в литературе принято говорить,что он обладает навигационным свойством [Clauset A., Moore C., 2003],[Chaintreau A., и др.
2008], [Fraigniaud P., 2007], [Kleinberg J. 2000], [BogunaM. и др. 2009], [Liben-Nowell D., и др, 2005], [Sandberg O., 2006].ЭффективностьалгоритмаGreedyWalkзависитотколичествапройденных вершин, другими словами от длинны совершённого пути,иначе от количества совершенных шагов – «хопов». Если среднее число«хопов» пропорционально (log ()! ), где n – число вершин, > 0, топринято говорить о навигационных свойствах тесного мира.
В особенностиэто характеристика существенно влияет на время работы алгоритма вслучае, когда вершины расположены на различных физических узлах иполучение списка соседей у соседней вершины (совершение «шага»)сопряжено с передачей данных по сети и требует относительно большоговремени.На рисунках 27-33 приведены графики распределения длинны путисовершаемым жадным алгоритмом до момента остановки в точкелокального минимума (ряд «GW»). Так же на графиках приведенаинформация о процентном соотношении количества успешных поисковимеющих определенную длину (ряд «SUCCEED»).Распределениеследующегостроилосьэксперимента.поданнымполученнымСтроилисьграфыврезультатеалгоритмомMSWConstruction с параметрами u=2;3;4;10; В качестве входного64множества использовались 100 тыс.
точек изd-мерного Евклидогопространства, сгенерированные случайно с равномерным распределениемв единичном гипер-кубе.генерировалось100Далее с равномерным распределениемслучайныхточек(множество ),которыеиспользовались в качестве запросов. Затем от 100 произвольных вершины,выбираемые равновероятно среди всех вершин графа, запускался алгоритмGreedyWalkпоиска каждой точки из множества запросов . Такимобразом всего производилось 10,000 поисков. После чего экспериментповторялся 20 раз, значения усреднялись.Для каждого произведенного поиска собиралась информация о длинепути, а так же информация о том, был ли поиск успешным, то есть был лив результате поиска обнаружен глобальный минимум.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
