WWW.DISSERS.RU

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

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

Pages:     ||
|

– «simplewiki 07 corpus» (зелёный цвет, пунктир) — частота слов в корпусе Simple Wikipedia на 09.09.2007.

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

Рис. 31. Распределение частоты десяти тысяч наиболее употребимых слов в викикорпусах на русском (ruwiki) и английском упрощённом (simplewiki) языках за 2007 и 2008 гг. (слева); проверка выполнения закона Ципфа для данных корпусов (справа) Предложим читателю ещё ряд экспериментов, которые можно выполнить, пользуясь данными индексной БД:

а) взять первую 1000 слов по частоте в корпусе, упорядочить по числу 1 Можно построить аналогичный график, если отсортировать слова не по частоте слов в корпусе, а по числу документов, содержащих слова. В этом случае взаимно поменяется характер кривых «07 corpus» и «ruwiki 07 doc».

- 148 документов, построить график;

б) найти число слов с частотой 1, 2, 3.. 10..1000 слов в корпусе (привести в таблице и построить гистограмму);

в) найти число слов длиной 1 буква, 2, 3.. 30 (таблица и гистограмма);

г) сравнить изменение ранга слов (по популярности, то есть частоте употребления) в корпусе со временем (слово, ранг, повышение/понижение — на сколько), (подсказка: нужно построить две индексных БД для разных по времени дампов википедий); указать часто употребимые слова, ранг которых изменился максимально;

д) найти число различных лексем в документе; среднее и максимальное число по всем документам; то же, но нормированное на число слов в документе; вычислить список первых десяти самых «пёстрых» документов, то есть богатых своим лексиконом, а именно: содержащих максимальное значение отношения числа уникальных лексем к числу слов в документе;

обратная задача: построить упорядоченный список самых «нудных», т.е.

длинных, но бедных лексиконом документов.

4.4 Эксперименты в проекте «Контекстно-зависимый поиск документов в проблемно-ориентированных корпусах» В проекте «Контекстно-зависимый поиск документов в проблемноориентированных корпусах» предлагается решение задача поиска похожих документов на основе онтологий1.

Задача поиска похожих документов решается в два этапа:

индексирование и поиск на основе индекса.

1. Индексирование документов относительно онтологии заключается в (i) определении фрагмента онтологии, соответствующего документу (классы, атрибуты, отношения между ними, см. рис. 34), (ii) вычислении сходства (similarity) между документом и данным фрагментом онтологии. В базе данных 1 По классификации, предложенной в работе [118], приложение, разработаннное в данном проекте, относится к классу «ontology-based search». Определение онтологии см. в [107], [181]. Введение и обзор онтологий также представлены в отечественной монографии [61].

- 149 сохраняется тройка , где A'' – фрагмент онтологии, Doc ID – идентификатор документа, Sim – степень сходства.

Предложено два варианта индексирования: на основе категорий (рис. 32) и полнотекстовое (рис. 33). При полнотекстовом индексировании используется модуль Russian POS Tagger (см., раздел 3.2 на стр. 106).

Рис. 32. Список документов, похожих на документ «Транспорт», полученный с помощью алгоритма поиска на основе категорий 2. Поиск похожих документов на основе индекса заключается в следующей последовательности шагов. По исходному документу выбирают фрагмент онтологии из базы данных индекса. Для данного фрагмента находят похожие фрагменты, сравнивая его с фрагментами, хранящимися в индексе. Упорядоченному (по степени сходства) списку похожих фрагментов соответствует список документов, который возвращают, как упорядоченный список похожих документов (рис. 32). Документы на рис. 32 упорядочены по графе релевантность (relevance).

- 150 Рис. 33. Список документов, похожих на документ «Транспорт», полученный с помощью алгоритма полнотекстового поиска Для решения данных задач автором были спроектированы и реализованы:

(i) алгоритм индексирования на основе категорий Википедии, (ii) алгоритм сравнения графов, (iii) алгоритм выбора минимального связного набора вершин в графе (рис. 35).

- 151 Рис. 34. Фрагмент онтологии, соответствующий документу «Транспорт» Алгоритм сравнения графов и алгоритм выбора минимального связного набора вершин реализованы в виде модулей библиотеки Java Universal Network / Graph Framework (JUNG) [144]. JUNG – это программная библиотека с открытым исходным кодом, обеспечивающая средства для управления, анализа и визуализации таких данных, которые можно представить в виде графа.

Для демонстрации алгоритма сравнения графов автором создано приложение Java WebStart, позволяющее сравнивать графы1. Данное приложение можно также рассматривать как пример интеграции библиотеки JUNG и технологии WebStart2.

Для визуального отображения графов в целях отладки (см., например, рис. 34, 35) использовался формат и программа Pajek, разработанные словенскими учёными [78].

1 Приложение и код программы доступны по адресу: http://whinger.narod.ru/soft/edoc.jung/index.html.

2 См. http://java.sun.com/products/javawebstart, http://mindprod.com/jgloss/javawebstart.html.

- 152 Рис. 35. Из фрагмента онтологии, соответствующего документу «Транспорт», выбран связный граф - 153 Выводы по главе В этой главе (1) описаны эксперименты поиска синонимов в Английской и Русской Википедии с помощью адаптированного HITS алгоритма, (2) дано описание (с точки зрения пользователя) сессии поиска синонимов в программы Synarcher (реализующей адаптированный HITS алгоритм), (3) численно проверена польза предложенных поисковых эвристик, (4) проведены эксперименты по построению индексных баз данных викитекстов, (5) получено подтверждение выполнения закона Ципфа для текстов двух Википедий.

Эксперименты позволяют сделать вывод, что программа Synarcher позволяет находить синонимы и семантически близкие слова в Английской Википедии, отсутствующие в современных тезаурусах WordNet, Moby (например, найден синоним Spationaut для слова Astronaut). Тем не менее некоторые синонимы, представленные в тезаурусах, не были найдены. Таким образом, можно улучшить алгоритм, используя данные тезаурусов.

Эксперименты показывают, что работа AHITS алгоритма медленнее HITS алгоритма в среднем на 52%, а точность поиска AHITS алгоритма выше на 33%.

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

Предложенная модификация коэффициента Спирмена позволила провести эксперименты для оценки чувствительности результатов адаптированного HITS алгоритма к параметрам поиска. Для ряда слов из Русской Википедии (Жаргон, Cамолёт) качество результата поиска1 было достаточно стабильным (значение стандартного отклонения коэффициента Спирмена 2.75 и 4.41 соответственно), что избавляет пользователя от необходимости 1 Под качеством результата поиска понимается число тех слов, которые одновременно есть (1) и в автоматически создаваемом программой списке, (2) и в списке семантически близких слов, составленном экспертом.

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

Описаны данные морфологического анализа Lemmatizer, доступные в модуле Russian POS Tagger. Представлен пример инициализации модуля Russian POS Tagger, указаны параметры для его подключения к XML-RPC серверу LemServer. Показан способ подключения и результаты работы модуля Russian POS Tagger в составе системы GATE.

Описаны эксперименты по построению индексных баз данных Русской Википедии и Википедии на английском упрощённом языке. Данная работа не является первой, применяющей модуль Lemmatizer к текстам Википедии.Тем не менее вкладом работы является: описание достаточно законченной системы индексирования вики-текстов (вероятно, первой общедоступной), а также индексные базы двух википедий, доступные для проведения исследований или включения в поисковые системы.

Проведены эксперименты, подтверждающие выполнение эмпирического закона Ципфа для текстов Русской Википедии и Википедии на английском упрощённом языке.

1 Методика построения индексной базы. 23.10.2006.

http://ru.wikipedia.org/wiki/Википедия:Частотный_словник - 155 Заключение Одной из важных современных задач является задача поиска информации.

Подзадачей является поиск похожих объектов, который кроме поиска похожих текстовых документов включает задачу поиска семантически близких слов, задачу поиска похожих вершин графа и др. С другой стороны большую популярность приобретает новый формат интернет страниц – вики.

Всё это подвигло нас к решению такой теоретически занятной и имеющей большое практическое значение задаче как создание математического и программного обеспечения для поиска семантически близких слова на основе рейтинга вики-текстов.

Анализ методов поиска синонимов и методов поиска похожих интернет страниц показал, что HITS алгоритм наиболее подходит для поиска похожих документов в корпусах текстов специальной структуры (с гиперссылками и категориями). HITS алгоритма, изначально предназначенный для поиска похожих страниц в Интернете, был адаптирован для поиска наиболее похожих документов в корпусе текстов специальной структуры с использованием алгоритма кластеризации. Данный алгоритм был реализован в программном продукте Synarcher с визуализацией результатов поиска и с возможностями интерактивного поиска. Эксперименты показали возможность находить синонимы и семантически близкие слова в Английской Википедии, отсутствующие в современных тезаурусах WordNet, Moby.

В работе предложен итеративный алгоритм поиска похожих вершин графа. Предложены эвристики и проведена оценка временной сложности алгоритма.

Спроектирована архитектура программной системы оценивания степени синонимичности набора слов на основе тезаурусов (WordNet и Moby). Предложены способы оценки семантической близости для списков, строящихся автоматически.

Коэффициент Спирмена модифицирован для численного сравнения списков слов (отличие от оригинального метода заключается в возможности - 156 сравнивать списки разной длины) и применён в экспериментальной части работы для оценки качества поиска семантически близких слов в энциклопедии Русская Википедия. Спроектирована клиент-серверная архитектура программного комплекса поиска семантически близких слов с возможностью оценки списков слов на основе удалённого доступа к тезаурусам (WordNet, Moby) Предложена и реализована в виде программы интеграция распределённых программных компонент в рамках системы GATE, а именно:

подключен модуль морфологического анализа русского языка (на основе XML-PRC протокола). Плюс данной части работы в том, что это один из шагов по созданию модулей обработки текстов на русском языке в системе GATE. Это по определению (инфраструктуры GATE) приведёт к созданию переносимых, совместимых, обладающих визуальным интерфейсом1 модулей по обработке текстов на естественном языке.

Разработана архитектура системы индексирования вики-текстов, включающая программные модули GATE и Lemmatizer. Реализован программный комплекс индексации текстов Википедии на трёх языках:

русский, английский, немецкий. Выполнено индексирование Русской Википедии и Википедии на английском упрощённом языке, построены индексные базы для них, выполнено сравнение основных показателей баз данных (число слов, лексем). На основе этих баз выполнена проверка, подтверждающая выполнение закона Ципфа для текстов Русской Википедии и Википедии на английском упрощённом языке.

Предложенное решение задачи автоматического поиска синонимов может использоваться в поисковых системах (расширение / переформулировка запроса с помощью тезаурусов), в системах машинного перевода, при составлении словарей синонимов.

1 Визуальный интерфейс GATE позволяет: (1) связывать модули друг с другом, (2) задавать параметры, (3) представлять результаты работы модулей.

- 157 Список источников литературы [1]. Азарова И.В., Митрофанова О.А., Синопальникова А.А. Компьютерный тезаурус русского языка типа WordNet // Компьютерная лингвистика и интеллектуальные технологии. Труды международной конференции «Диалог 2003». Протвино, 2003. – C. 1-6. http://www.dialog-21.ru/materials/id=[2]. Александров В.В. Интеллект и компьютер. СПб.: «Анатолия», 2004. – 285 с. – ISBN 5-314-00080-6. http://www.sial.iias.spb.su/issue.html [3]. Александров В.В., Андреева Н.А., Кулешов С.В. Системное моделирование.

Методы построения информационно-логистических систем / Учеб. пособие.

СПб.: Изд-во Политехн. ун-та, 2006. – 95 с..

http://sial.iias.spb.su/files/semsys.pdf [4]. Александров В.В., Арсентьева А.В., Семенков А.В. Структурный анализ диалога. Препринт № 80. Л.: ЛНИВЦ, 1983. – 50 с..

[5]. Ахо А.В., Хопкрофт Д., Ульман Д.Д. Структуры данных и алгоритмы. : Пер. с англ. М.: Издательский дом "Вильямс", 2003. – 384 с. – ISBN 5-8459-0122-7.

[6]. Бек К. Экстремальное программирование. СПб.: Питер, 2002. – 224 с. – ISBN 5-94723-032-1.

[7]. Берков В.П. Двуязычная лексикография: Учебник. СПб.: Изд-во С.Петербургского ун-та, 1996. – 248 с. – ISBN 5-288-01643-7.

[8]. Блох Дж. Java. Эффективное программирование. М.: Лори, 2002. – 224 с. – ISBN 5-85582-169-2.

[9]. Бобровский С. Технологии Пентагона на службе российских программистов.

Программная инженерия. СПб.: Питер, 2003. – 222 с. – ISBN 5-318-00103-3.

[10]. Браславский П.И. Автоматические операции с запросами к машинам поиска интернета на основе тезауруса: подходы и оценки // Компьютерная лингвистика и интеллектуальные технологии. Труды международной конференции «Диалог 2004». Верхневолжский, 2004. – C. 79-84.

http://www.dialog-21.ru/archive/2004/braslavskij.htm [11]. Браславский П.И., Соколов Е.А. Автоматическое извлечение терминологии с использованием поисковых машин Интернета // Компьютерная лингвистика и интеллектуальные технологии. Труды международной конференции - 158 «Диалог 2007». Бекасово, 2007. – C. 89-94. http://www.dialog-21.ru/dialog2007/ materials/pdf/14.pdf [12]. Брукс Ф. Мифический человеко-месяц или как создаются программные системы: Пер. с англ. СПб.: Символ-Плюс., 1999. – 304 с. – ISBN 5-93286-005-7.

Pages:     ||
|



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

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