Диссертация (1137145), страница 16
Текст из файла (страница 16)
от того,какаяфункциярасстоянияMetricElementFactory.Имяиспользуется,интерфейсаявляетсясвязанносинтерфейсшаблономпроектирования “Абстрактная Фабрика”, который позволяет создавать ииспользовать объекты, не определяя реализацию их конкретных классов.Интерфейс содержит только два абстрактных метода:public List <MetricElement> getElements()public void setParameterString(String param)Метод getElements возвращает список порожденных объектов.
МетодsetParameterString позволяет передать некоторый набор параметров классупотомку – конкретной реализации фабрики (см. рисунке 57). В качествеконкретных реализаций фабрики служат классыDocumentFactory иEuclidianElementFactory, порождающие элементы классов Document иEuclidianElement. Об этих подробнее – ниже потексту.Рис 57. Диаграмма классов. Применение шаблона проектирования «АбстрактнаяФабрика»1135.3 Работа в n-мерном Евклидовом пространствеКлассEuclidianElementреализациииEuclidianFactoryконкретныхAbstractMetricElementFactoryклассовявляютсяпримерамиAbstractMetricElementсоответственно.Даннаяпараиклассапозволяет работать с элементами n-мерного евклидово пространства.Класс Euclidian содержит массив вещественных чисел private doublex[] и реализацию функции вычисления расстояния d(x, y) =n∑ (x − y )ii2.
Вi=1свою очередь класс EuclidianFactory имеет методы для генерациислучайных точек с равномерным и нормальным распределением. Приравномерном распределении точки генерируются в единичном гипер-кубе[0;1]n ; в случае нормального – в окрестности центра координат с заданнойвеличиной стандартного отклонения.5.4 Работа с частотными векторами текстовС коллекцией документов, точнее с набором векторов частот слов,работают классы расположенные в пакете org.latna.msw.documents. КлассDocument реализует логику работы с вектором частот слов.
Как подклассMetricElement, содержит реализацию функции вычисления расстояния. Вданном случае в качестве расстояния выступает функция косинуса угламежду векторами (вставить формулу). В силу сильной разряженностивекторов частот слов для их хранения используется хэш-таблица, вкоторойвкачествеключейиспользуютсясамисловаилиихидентификаторы; в качестве значений – частоты слов.Класс DocumentFileFactory инкапсулирует логику считывания издиректории и создания объектов типа Document. Путь к директории ипараметрограничивающиймаксимальноеколичествосчитываемыхобъектов передаются через метод setParameterString(String param) в114следующем формате. «dir=(.+); maxDoc=(\\d+)» Ключевое слово«dir», знак равенства, последовательность символов соответствующая путик директории, точка-запятая.
Далее, ключевое слово «maxDoc», знакравенства,целоечисло,соответствующеемаксимальномучислусчитываемых объектов из директории.Файлы частотных векторов слов имеют следующий формат. В каждойстроке содержится две группы символов разделенные пробелом илизнаком табуляции. Первая последовательность- идентификатор слова,вторая – вещественное число в десятичной форме, использующую запятуюв качестве разделителя и лежащее в интервале [0;1].5.5 Класс AbstractMetricStructureВоплощает идею заключённой в эпиграммеприведеннойвначалеглавы. Этот абстрактный класс выражает идею того, что совокупностьалгоритмов добавления и поиска мыслятся в качестве структуры данных.Так в нём задекларированы методы добавления элементов в структуру ипоиска:public abstract void add(MetricElement newElement);public abstract SearchResult knnSearch(MetricElement query,int k, int attempts);Класс AbstractMetricStucture (рисунок 58) является базовым классом длявсех последующих реализаций структур данных для поиска в метрическихпространствах.115Рис.
58. UML диаграмма классов алгоритмов для поиска в метрическом пространстве5.6 Класс MetrizedSmallWorldКласс MetrizedSmallWorld представляет собой совокупность алгоритмадобавленияMSWConstructionиалгоритмапоискаK-NNSearch,предложенных во второй главе. Данный класс выражает идею того, чтосовокупность алгоритмов добавления и поиска мыслятся в качествеструктуры данных.
Так класс MetrizedSmallWorld наследует классAbstractMetricStructure и реализует два основных метода: добавить элементvoidadd(MetricElementnewElement)ипроизвестипоискknnSearch(MetricElement query, int k, int attempts).5.7 Класс SelfAdaptedMetrizedSmallWorldАлгоритм построения структуры СonstuctionByReparing (см. 2.7)инкапсулирован в класс SelfAdaptedMetrizedSmallWorld. В качествеалгоритма поиска k-ближайших используется алгоритм k-nnSearch.Название классаструктурыобусловленноалгоритмомтем, что о способе формированияСonstuctionByReparing116засчётустранениялокальных мининимумов, которые обнаруживаются при добавлении новыхэлементов, можно думать как об адаптации структуры к новым данным.Также как MetrizedSmallWorld этот класс наследуется от классаAbstractMetricStructure,чтодаётвозможностьиспользоватьихединобразно и упрощает тестирование.
Результаты исследования свойствструктуры формируемой алгоритмом СonstuctionByReparing приведены вразделе 3.2.5.8 Библиотека алгоритмов AlgoritmLibОпят же, чтобы избежать дублирования кода и иметь возможностькомбинировать отдельные алгоритмы, получая различные структурыданных, алгоритмы вынесены в качестве статических методов в отдельныйклассAlgorithmLib.ТакклассыMetrizedSmallWorldиSelfAdaptedMetrizedSmallWorld представляющие две разные структурыданных, используют один и тот же алгоритм поиска K-NNSearch, которыйоформлен в качестве статического метода kSearchElementsWithAttempts(MetricElement query, EnterPointProvider provider, int k, intattempts).Среди прочих, класс содержит метод для поиска локальных минимумовgetLocalMin(MetricElement start, MetricElement query),возвращающихблуждательвершинучерезвкоторомзаданноеостанавливаетсячислоgetRandomWalkElement(MetricElementшаговметодслучайный–enterPoint,методintnumberOfSteps), а также многопоточную реализацию алгоритма K-NNSearch – метод kSearchElementsWithAttemptsFuters.5.9 Эксперименты над корпусом текстов Trec-3Чтобы продемонстрировать используются выше описанные классы и какможет выглядеть код, основанный на данной иерархии классов, далееприводится детали эксперимента с коллекцией документов Trec-3.117SearchAttemptsTestTrec3.java – файл в котором содержится код, которыйпроизводит эксперимент.Данный эксперимент (скрипт, сценарий) состоит из 3-х этапов.
Первыйэтап – считывание частотных векторов из коллекции текстов и считываниемножества запросов.MetricElementFactory elementFactory= newDocumentFileFactory();elementFactory.setParameterString("dir="+dataPath+";maxDoc="+dataBaseSize);MetricElementFactory testQueryFactory = newDocumentFileFactory();testQueryFactory.setParameterString("dir="+queryPath+";maxDoc="+querySetSize);После того как элементы были считаны, вызывается конструктор классапредставляющийиспытываемуюструктуруданных(испытываемойсовокупности алгоритмов) и устанавливаются параметры.MetrizedSmallWorld db = new MetrizedSmallWorld();db.setNN(nn);db.setInitAttempts(initAttempts);Далее считанные элементы последовательно добавляются в структуру.for (MetricElement me: elementFactory.getElements()) {db.add(me);}На втором этапе для чтобы иметь возможность оценивать точностьпоиска испытываемой структуры данных, необходимо точно знать, какиеэлементы из индексируемого множества являются k-ближайшими.Для этого задействуется статическая функция из вспомогательногокласса TestLib, которая, в конечном итоге вычисляет расстояние от запросаnewQuery до каждого элемента из множества.118for (MetricElement newQuery: testQueryFactory.getElements()) {testQueries.add(newQuery);rightResultMap.put(newQuery,TestLib.getKCorrectElements(db.getElements(), newQuery, k));}На третьем этапе осуществляется поиск k-ближайших докаждогоэлемента из множества запросов, используя структуру, построенную напервом этапе.
Элементы полученные в результате поиска, сравниваются сэталонными k-ближайшими. Вычисляется значение точности поиска –значение recall. Результаты выводятся в консоль. После чего поискпроизводится с другими параметрами (в данном сценарии, увеличиваетсязначение числа попыток при поиске).Для того чтобы сократить время на процесс вычисления точностипоиска был написан код, который может исполняться независимопараллельновразныхпотокахсоздаваемыхиподдерживаемыхоперационной системой. Поскольку изначально этот код был создан намомент, когда стандарта java 8 ещё не существовал и был доступен только7-йстандарт,параллельноеисполнениевычисленийбылоимплементировано с использованием механизма «фьючерсов» (анл.Future).Данныймеханизмпозволяетосуществлятьотложенныевычисления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
