Диссертация (1137145), страница 9
Текст из файла (страница 9)
Выходом является то, что для работы вероятностногопоиска не обязательно строить весь граф Делоне [Beaumont O., и др., 2007].Как будет показано далее, вероятность найти глобальный минимумэкспоненциально стремится к единице с ростом среднего числа ребер ваппроксимированном графе Делоне.2.4 Серия поисковПредположим, что уже имеется некоторая аппроксимация графа Делоне,но нас не устраивает точность, получаемая алгоритмом жадного поиска.Для того чтобы «обойти» ложно локальные минимумы, предлагаетсяиспользовать серию из m поисков, инициированных от случайных вершини выдавать в качестве результата элемент, ближайший к запросу измножестванайденных.АлгоритмжадногопоискаGreedyWalkдетерминирован для каждой точки входа ! ∈ , он заканчивается либоуспехом – нахождением истинного ближайшего, либо ошибкой –нахождением элемента, который не является ближайшим соседом для q.Фактически поиск ближайшего к одному и тому же элементу можетзаканчиваться, как нахождением глобального минимума, так и локального,в зависимости от того, с какой точки был инициализирован поиск.Поскольку точка входа выбирается случайно, то появляется вероятностьp нахождения глобального минимума относительно конкретного элементаq (а не всех элементов).
Причем эта вероятность всегда отлична от нуля,т.к. всегда есть вариант, что точка входа является глобальным минимумоми алгоритм жадного поиска возвратит в качестве результата именно её.Если вероятность найти глобальный минимум одним поиском равна p,то вероятность найти тот же самый элемент при m поисках, грубопредполагая независимость этих поисков, будет 1 − (1 − p)m , т.е.
вероятностьошибки падает экспоненциально с ростом количества поисков (данноесвойство, в том числе и независимость серии поисков более детально52исследуются в главе 3). Таким образом, увеличивая параметр количествапроизводимых независимых поисков , можно улучшать точностьпоиска,.
При значении = , где n количество элементов в структуре,алгоритм сводится к полному перебору.Рис 17. Блок-схема алгоритма поиска k-ближайших соседей в графе (, ). (АлгоритмK-NNSearch)2.5 Алгоритм поиска k-ближайших соседей K-NNSearchБлок-схема алгоритма поиска k-ближайших соседей приведена нарисунке 17.
В алгоритме поддерживается три множества53,и. Вупорядоченном множество результатоваккумулируются известныеближайшие вершины к запросу; в множестве «кандидатов»хранятсявершины до которых было вычислено расстояние σ . Множествопосещённых вершин(visitedSet) – хранит вершины, чьи окрестностииспользовалось для расширения множества. На очередной итерациивычисляется расстояние до всех элементов из окрестности вершины c.Далееизмножествакандидатовалгоритмвыбираетэлементближайшую к запросу q и помещает его в переменную c, после чегоитерация повторяется.элемент cКритерием остановки служит условие того, чтонаходится на расстояние от запроса, не дальше, чем k-йближайший элемент к q из множества .
Такой более «слабый» критерийостановки позволяет алгоритму выходить из локальных минимумов ипомогает сформировать множество результатовk элементов.состоящее минимум изТак же в алгоритме используется повторные поиски отслучайных вершин для увеличения точности (параметр m).Ниже нарисунке 18 приводится также описание алгоритма в виде псевдокода.K-NNSearch(object q, integer: m, k)1 TreeSet [object] tempRes, candidates, visitedSet, result2 for (i ← 0; i < m; i++) do:3put random entry point in candidates4tempRes ← null5repeat:6get element c closest from candidates to q7remove q from candidates8//check stop condition:9if c is further than k-th element from visitedSet10than break repeat11//update list of candidates:12for every element e from friends of c do:13if e is not in visitedSet then14put e to visitedSet, candidates, tempRes1516end repeat17//aggregate the results:18add objects from tempRes to result19 end for20 return best k elements from resultРис.
18. Псевдокод алгоритма поиска k-ближайших K-NNSearch54Рис. 19. Блок-схема алгоритм построения структуры (графа) MSWConstruction2.6 Алгоритм добавленияБлок-схемаалгоритмапостроенияструктурыMSWConstructionприведена на рисунке 19. Алгоритм принимает на вход четыре аргумента:функцию расстояния , конечное множество объектовX, над которымнеобходимо построить структуру и два параметра - целые положительныечисла w и u. На каждой итерации алгоритм выбирает из множестваXпроизвольный элемент c .
Далее для элемента c алгоритм формирует55окрестность N (c) из uближайших элементов к элементу c , среди тех,которые есть на данный момент времени в структуре.Для этогоиспользуется алгоритм K-NNSearch, в который передаются параметры k=uи m=w. После чего в граф G добавляются рёбра соединяющие элемент c иэлементы из множества N (c) . Алгоритм работает до тех пор, пока всеэлементы из множестваXне будут добавленных в структуру.Внешне алгоритм предельно прост, однако он позволяет строитьхорошую аппроксимацию графа Делоне и в тоже время получатьмножество рёбер с таким распределением длин, которое обеспечиваетсуществование коротких путей в графе использующихсяалгоритмомпоиска. Ниже на рисунке 20 также приводится описание алгоритма в видепсевдокода.MSWConstruction(object []: X, integer: w, integer: u)1 ← случайная перестановка элементов множества X2 for (i ← 0; i < n; i++) do3new_object ← X[(i)];3SET[object]: neighbors ← k-NNSearch (new_object, w, u);4for (i ← 0; i < u; i++) do5neighbors[i].connect(new_object);6new_object.connect(neighbors [i]);Рис.
20. Псевдокод алгоритма добавления всех элементов сНа рисунке 21 изображен пример графа построенного для элементовпространства ! . Элементы обозначены кругами. Числа рядом с нимисоответствуют порядку добавления. Сплошными линиями изображенырёбра графа (, ). Пунктирные линии соответствуют границам областейразбиения Вороного. До полного графа Делоне не хватает ребра междуэлементами0и10,1и9.СтруктураполученаалгоритмомMSWConstruction с параметрами u=3 и w=1. Элемент с номер 0 будетлокальным минимумом для запросов, попавших в заштрихованнуюобласть “A”, соответственно 10 для “B”, 9 для D и 1 для области “С”.Штрихованными линиями изображены пути двух поисковых алгоритмовпри поиске запроса из области “B”.
Алгоритм поиска GreedyWalk,стартующий из вершины 7, останавливается на элементе 10, являющийся56локальным минимумом, но не глобальным. GreedyWalk, стартующий извершины 5, останавливается в глобальном минимуме 0.Рис. 21. Структура полученная алгоритмом MSWConstruction. В качестве метрическогопространства выступает Евклидово пространство. Номера элементов соответствуютпорядку их добавления в структуру.2.7Алгоритмдобавленияоснованныйлокальных минимумов57наустраненииGetLocalMinimums( q ∈ D , G(V, E) , τ ∈ Ν )01 L ← {} ; τ '← 002 while τ ' < τ do03vstart ← Random( V )//put to vstart random vertex from V04v, P ← GreedyWalk( q , G , vstart )05if v ∉ L then τ '← 0 ; L ← L ∪ v08else τ ' ← τ '+109 end while11 return L , PРис.
22. Алгоритм нахождения локальных минимумов.Алгоритм возвращаетмножество локальных минимумов L, и множество элементов P до которых быловычислено расстояние в ходе работы алгоритмаКак было отмечено ранее, существование локальных минимумов в сети,является главной проблемой для корректной работы алгоритмов поискаближайшего соседа основанных на идее градиентного спуска. С этойпроблемой можно бороться различными способами.
Один возможныхвариантов – пытаться устранять их явным образом, в момент ихобнаружения. Обнаружить локальные минимумы можно на любом этапесуществования структуры.Критерий того, что некоторый элементa ∈ VGявляется локальнымминимум в графе G относительно некоторого произвольного элементаb ∈ D - это факт того, что в N G (a) а1 в нет элемента, который был ближе кb , чем a .
Обнаружить локальный минимум можно на любом этапесуществования структуры, то есть как на этапе добавления элементов вструктуру, так и на этапе исполнения запросов.На рисунке 22 представлен псевдокод алгоритма для нахождениялокальных минимумов. Этот алгоритм так же опирается на идею сериизапусков алгоритма GreedyWalk от произвольной вершины графа G(V , E) .1N G ( p) = {x ∈ VG : ( p, x) ∈ EG } , где VG множество вершин графа G, EG множество рёбер58InsertByRepairing( x ∈ X , G(V, E) , τ ∈ Ν )01 V ← V ∪ x ; P ← {}02 L, P ← Get_Local_Minimums( x , G , τ )03 P ← P ∪ x04 for each z ∈ L do05P ' ← {y ∈ P : d(y, x) < d(z, x)}x' ← argmin(d(z, y))06y∈P'0708E ← E ∪ (x ', z)∪ (z, x ')end forРис. 23. Псевдокод алгоритма добавления нового элемента, использующий идеюустранения локальных минимумов.Для того чтобы устранить локальный минимум a относительноэлемента b достаточно добавить ребро, соединяющее локальный минимумс элементов расстояние до которого от b меньше, чем до элемента a .Добавляемый элемент в структуру можно так же рассматривать вкачестве локального минимума, поскольку изолированная вершинаполностью удовлетворяет вышеназванному критерию.
Это обстоятельстводелает возможным определить процедуру добавления (вставки) вструктуру нового элемента, как процедуру устранения локальногоминимума (см. Рисунок 23).АлгоритмInsertByRepairingпринимаетнавходтриаргумента:добавляемый элемент x ∈ X , текущий граф G(V, E) , и натуральное число –параметр τ ∈ Ν . Сначала алгоритм получает список локальных минимумовв структуре относительно элемента x . Затем каждый локальный минимумz ∈ L устраняется следующим образом. Среди множества элементовпросмотренных в процессе поиска локальных минимумов, отбираютсяэлементы, которые могут быть использованы для устранения локальногоминимума z т.е.
те элементы расстояние от которых до добавляемогоэлемента x меньше, чем от локального минимума z (строка 05).Локальныйминимум z устраняется,локального минимума, к элементупутёмдобавленияребраотx' , расстояние до которого минимально59среди всех известных алгоритму элементов из множества P' , позволяющихустранить локальный минимум z .СonstuctionByReparing( X ⊂ D , τ ∈ Ν )01 G ← ({}, {})02 while X ≠ {} dox ← Random( X ); X ← X \ x03G ← InsertByRepairing( x , G , τ )0405 end whileРис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
