WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     ||
|

2. Первый вопрос определяет второй: как для упорядоченной последовательности синонимов, возвращаемой алгоритмом (теоретически неограниченной, например, несколько тысяч), определить: где оборвать эту последовательность, обеспечивая некоторое приемлемое качество Возможный ответ таков. После работы алгоритма у каждой вершины графа определён вес authority, который говорит о степени авторитетности (в нашем случае – синонимичности). Выбрав эмпирически некоторое вещественное d, 0d1, можно отсекать множество синонимов, выбирая только те, у которых authorityd. Либо, вычислив последовательность SER и ER (где например SER соответствует первым i-ым словам результата), i оборвать последовательность на N-том члене при SER d.

N Коэффициент Спирмена Самый простой способ сравнить два набора данных в том, чтобы найти количество общих элементов1.

В [76] метрика Спирмена (Spearman, другое название – Spearman's footrule) используется как для сравнения ранжирования одного и того же набора Интернет страниц разными поисковиками, так и для оценки изменения ранжирования рассматриваемого набора страниц во времени.

Метрика Спирмена2 позволяет сравнить две ранжировки одного и того же набора из N элементов. Каждому элементу назначается ранг от 1 до N 1 Данный способ использовался в экспериментах, см. графу Intersection в таблице 4.8.

2 В статистике коэффициент корреляции Spearman – это непараметрическая мера корреляции, оценивающая насколько хорошо произвольная монотонная функция может описать отношение между двумя переменными в случае, когда неизвестен характер зависимости переменных (линейный или какойлибо др.). См. http://en.wikipedia.org/wiki/Spearman's_rank_correlation_coefficient - 93 (мера основана на перестановках). Метрика Spearman равна сумме модулей расстояний между i-ми элементами набора.

S S F s1, s2= s1i-s2i (2.13) i=Предположим, при поиске синонимов для данного слова и для двух вариантов начальных параметров адаптированного HITS алгоритма I и I 1 (размер корневого набора, число добавляемых страниц и др.) получили два набора слов S и S. Задача заключается в том, чтобы выяснить, какие 1 параметры алгоритма дают лучший результат. Это можно сделать, сравнивая множества слов S и S с эталонным множеством синонимов и близких по 1 значению слов для данного слова (выбранных экспертом или найденных с помощью тезауруса). Для сравнения предлагается использовать метрику Спирмена.

Предлагается расширить метрику Спирмена для сравнения списков разной длины1 следующим способом, отличающимся2 от расширения предложенного в [76]. Дано два списка: (1) A – более короткий, эталонный, составленный экспертом, (2) B – более длинный, составленный автоматически. В конец списка B добавляются отсутствующие в нём элементы А. Далее применяется формула (2.13), где сравниваются положения в списках общих элементов, S – число общих элементов, а также длина более короткого списка.

Далее метрику Спирмена, расширенную таким способом, будем называть коэффициентом Спирмена, так как, вообще говоря, такое расширение не сохраняет свойства метрики (например, может нарушаться свойство симметрии).

Таким образом, с помощью коэффициента Спирмена можно сравнить ранжирование одного и того же набора слов адаптированным HITS алгоритмом при разных параметрах поиска с эталонным списком.

1 В экспериментах необходимо будет сравнивать списки разной длины. Один небольшой по длине список постоянной длины (составлены экспертом), другой список (может быть намного более длинным) строится автоматически программой, его длина может меняться от эксперимента к эксперименту.

2 Разница в том, что в работе [76] сравниваются результаты поисковых серверов, ни один из которых не является эталоном для другого. В экспериментах данной работы один из списков является эталонным.

- 94 Выводы по главе В данной главе были разработаны: (1) подход поиска СБС, (2) формализация понятия похожие вершины, (3) адаптированный алгоритм HITS с использованием алгоритма кластеризации, (4) предложенный автором алгоритм поиска похожих вершин графа и (5) предложенные автором методы численной оценки наборов синонимов (модификация коэффициента Спирмена (Spearman's footrule) и оценка на основе тезаурусов WordNet и Moby).

HITS алгоритм был адаптирован автором к тем дополнительным возможностям, которые предоставляет рассматриваемый корпус документов, относительно обычных Интернет страниц. Это (1) наличие категорий (классифицирующих документы по их тематической принадлежности), (2) наличие метаинформации в виде ключевых слов (в простейшем случае - это заголовок документа).

В адаптированном HITS алгоритме предложено применить алгоритм иерархической кластеризации к базовому набору страниц для получения групп страниц, соответствующих разным тематическим направлениям.

Проведена оценка временной сложности адаптированного HITS алгоритма, см. (2.8). Предложено два варианта объединения результатов работы адаптированного HITS алгоритма и алгоритма кластеризации.

Автором предложены два варианта формализации понятия «похожие вершины» графа. Первый вариант использует понятия авторитетных и хабстраниц и позволяет формализовать задачу поиска похожих страниц в HITS алгоритме. Во втором варианте получена формула сходства двух вершин a и b, основанная на поиске общих вершин среди соседей вершин a и b.

Предложен алгоритм поиска похожих вершин графа. Выполнена оценка временной сложности данного алгоритма. Предложены две эвристики, позволяющие уменьшить временную сложность алгоритма. В первой эвристике предлагается рассматривать не все пары вершин (как кандидаты на «похожие» вершины), а только те, у которых не менее L - 95 соседей совпадают. Во второй эвристике используются результаты работы HITS алгоритма.

Предложены методы численной оценки наборов синонимов, полученных на выходе адаптированного HITS алгоритма. Оценка позволит выбрать входные параметры алгоритма. Для оценки работы алгоритма с английским корпусом текстов предлагается использовать тезаурусы WordNet и Moby.

Метрика Spearman's footrule (коэффициент Спирмена) обычно используется как для сравнения ранжирования одного и того же набора данных. Коэффициент Спирмена модифицирован для численного сравнения списков слов, отличие от оригинального метода заключается в возможности сравнивать списки разной длины. Предлагается с помощью метрики Spearman's footrule сравнить ранжирование одного и того же набора слов, полученных адаптированным HITS алгоритмом при разных параметрах поиска.

- 96 3. Организация программного обеспечения поиска семантически близких слов, автоматической оценки поиска и морфологического анализа слов Предложенный вниманию читателя во второй главе адаптированный HITS алгоритм алгоритм реализован в программе, названной Synarcher1. В рамкам описания архитектуры программы представлены основные классы и методы программы, программный интерфейс доступа к Википедии и особенности реализации модуля визуализации.

В этой главе представлена архитектура и реализация программного модуля системы GATE для удалённого доступа к программе морфологического анализа русского языка (aot.ru) на основе XML-PRC протокола. Данная архитектура представляет способ интеграции приложений написанных на разных языках программирования (например, С++ и Java) посредством XML-RPC протокола. Спроектирована архитектура системы индексирования вики-текстов, включающая GATE и Lemmatizer.

В главе представлена архитектура программной системы оценивания синонимов, позволяющей реализовать метод численной оценки списков семантически близких слов (адаптация метода Spearman's footrule и оценка на основе тезаурусов WordNet и Moby). Данный метод численный оценки описан в подразделе 2.5.

3.1 Архитектура программной системы Synarcher Достоинствами поискового комплекса Synarcher являются (1) визуализация результатов поиска, (2) возможность уточнения запроса в ходе работы пользователя с программой.

В архитектуру программного комплекса Synarcher (рис. 11) включены такие модули, как: модуль kleinberg, предоставляющий доступ к данным Википедии и реализующий алгоритм AHITS, модуль визуализации TGWikiBrowser2. Последовательность взаимодействия частей системы 1 Поскольку задачу программы можно сформулировать так: SYNonym seARCH.

2 Данный пакет представляет собой модификацию программы TouchGraph Wiki Browser (см.

http://www.touchgraph.com). Можно отметить популярность данной программы, например она - 97 указаны на рис. 11 числами (1-7). Входными данными для AHITS алгоритма являются слово, заданное пользователем (1-2), и данные Википедии (2).

Алгоритм строит список СБС, упорядоченных по весу authority (3), а пользователь получает возможность работать с ними благодаря модулю визуализации TGWikiBrowser (4-5). В ходе работы пользователь уточняет список СБС и запускает алгоритм повторно (6-7).

Рис. 11. Архитектура программного комплекса Synarcher Программа написана на языке Java [68], [8], [115]. Для неусыпного контроля работоспособности разных частей программы использовалась методика экстремального программирования – автоматические тесты модулей1 [6], [9], [188].

Программа состоит из двух основных частей. Первая часть отвечает за доступ к базе данных Википедия, содержит реализацию алгоритмов поиска синонимов и вспомогательные функции (пакет kleinberg). Вторая часть представляет пользовательский интерфейс, посредством которого запускаются функции первой части (пакет TGWikiBrowser).

использовалась в прототипе американских учёных [71] для визуального представления отношений RDF.

Недостаток программы в том, что разработчики больше не поддерживают данную программу, а также в том, что программа работает не устойчиво при отображении большого числа вершин и рёбер (например, если вершин больше сотни).

1 На июнь 2007 проект kleinberg программы Synarcher содержал 119 тестов, на июнь 2008 – 241 тест.

- 98 Модуль алгоритмов Основные наборы файлов (package) первого проекта – это rfc2229, wikipedia.clustering, wikipedia.kleinberg, wikipedia.sql, wikipedia.util. Их назначение состоит в следующем:

• rfc2229 – клиент к Dict серверам1, основанный на библиотеке JavaClientForDict (jcfd), разработанной Davor Cengija; расширение данного клиента для удалённого вызова тезаурусов WordNet и Moby;

• wikipedia.clustering – реализация алгоритма кластеризации, описанного в главе 2;

• wikipedia.kleinberg – реализация адаптированного HITS алгоритма и основные структуры данных, используемые в работе этого алгоритма (Article, Category, Node). Также этот пакет содержит вспомогательный класс DumpToGraphViz, позволяющий текущее состояние графа сохранять в специальном формате, который может быть преобразован в форматы PNG, JPEG или SVG программой GraphViz2;

• wikipedia.sql – это программный интерфейс доступа к Википедии.

Пакет позволяет читать данные Википедия, хранимой в базе данных MySQL. Названия классов соответствуют таблицам, с которыми они работают: PageTage, Links, Category. Класс Statistics выдаёт статистическую информацию (число статей, категорий, ссылок) о подключенной Википедии.

• wikipedia.util – пакет содержит вспомогательные классы. Encoding – содержит функции преобразования кодировок, FileWriter – работа с файлами, RandShuffle – обеспечивает случайную перестановку данных в исходном массиве, StringUtil – вспомогательные функции по обработке строковых данных, StringUtilRegular – вспомогательные функции по обработке строковых данных с использованием регулярных выражений [63].

1 Дополнительная информация по Dict серверам и протоколу RFC-2229 на сайте http://www.dict.org 2 См. http://www.graphviz.org - 99 Модуль визуализации: интерфейс и функции Представление в виде графа результатов поиска синонимов и семантически близких слов основывается на программе TouchGraph WikiBrowser V1.021.

Данная программа предназначена для визуализации Wiki страниц.

Программа TouchGraph WikiBrowser была существенно модифицирована для того, чтобы обеспечить следующую функциональность:

• подключение к базе данных Википедия, поскольку клиентсерверная архитектура базы данных MySQL позволяет программе Synarcher обращаться к базе данных Википедия, установленной на удалённом компьютере (рис. 13);

• задание параметров адаптированного HITS алгоритма (рис. 14);

• хранение слов, помеченных пользователем, как синонимы, и параметров поиска на компьютере пользователя. Причём запоминаемые параметры делятся на (1) параметры программы в целом (класс BrowserParameters), например, название базы данных с которой работали, последнее искомое слово и (2) параметры поиска отдельного слова (класс ArticleParameters);

• расширение контекстного меню (рис. 15) для более удобной навигации командами, позволяющими спрятать все вершины (Hide all except node), пометить вершину как синоним (Rate synonym), показать категории (Expand Categories).

Экран программы делится на две части вертикальной полосой, с левой стороны три вкладки2 (англ. tab): Article, Database и Synonyms.

Первая вкладка Article позволяет просмотреть энциклопедическую статью, соответствующую выбранному слову (рис. 12). Адрес статьи (URL) можно увидеть внизу экрана в строке статуса. Представление статьи Википедии в этом мини браузере (то есть во вкладке Article) и, вообще, в Интернет браузере возможен благодаря слаженной работе на стороне сервера таких программ, как: MySQL, Apache, PHP и MediaWiki.

1 См. http://www.touchgraph.com 2 См. http://ru.wikipedia.org/wiki/Вкладка - 100 Вкладка Database позволяет: (1) указать кодировку, (2) указать параметры для подключения к базе данных, (3) проверить подключение и получить статистику по базе данных (рис. 13). В верхней части экрана находится выпадающее меню (поле Wikipedia), позволяющее выбрать одну из баз данных Википедия. На данный момент это английская и русская версии энциклопедии.

Рис. 12. Отображение статей «Браузер» и «Folksonomy» из Русской и Английской Википедии соответственно во вкладке Article Возможность указать кодировку (по умолчанию UTF81) призвана решить возможные проблемы, связанные с хранением текстовых данных на стороне пользователя (например, название последней просмотренной статьи).

Дополнительная информация по настройке кодировки в программе представлена на странице проекта2.

1 «Кодировка переменной длины, предназначенная для отображения всех символов стандарта Unicode, при этом совместимая со стандартом ASCII» (http://en.wikipedia.org/wiki/UTF-8) 2 http://synarcher.sourceforge.net - 101 На рис. 13 показаны параметры подключение к БД Русской Википедии, установленной локально (группа параметров «MySQL database connection parameters»):

Pages:     ||
|



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.