Авторефераты по всем темам  >>  Авторефераты по разным специальностям Pages:     || Учреждение Российской академии наук

Санкт-Петербургский институт информатики и автоматизации РАН

На правах рукописи

Крижановский Андрей Анатольевич Математическое и программное обеспечение построения списков семантически близких слов на основе рейтинга вики-текстов Специальность: 05.13.11: Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Диссертация на соискание учёной степени кандидата технических наук Научный руководитель д.т.н. проф. А.В. Смирнов Санкт-Петербург 2008 Оглавление ВВЕДЕНИЕ......................................................................................................................................5 ПОЛОЖЕНИЯ, ВЫНОСИМЫЕ НА ЗАЩИТУ...............................................................................................19 1. АНАЛИЗ ПРОБЛЕМЫ АВТОМАТИЧЕСКОЙ ОБРАБОТКИ ТЕКСТА И ПОИСКА СЕМАНТИЧЕСКИ БЛИЗКИХ СЛОВ......................................................................................20 Проблема синонимии.............................................................................................................20 1.1 ОСНОВНЫЕ АЛГОРИТМЫ ПОИСКА ПОХОЖИХ ИНТЕРНЕТ СТРАНИЦ, ПОИСКА СЛОВ БЛИЗКИХ ПО ЗНАЧЕНИЮ, ВЫЧИСЛЕНИЯ МЕРЫ СХОДСТВА ВЕРШИН ГРАФА......................................................................................26 Алгоритмы анализа гиперссылок: HITS, PageRank, ArcRank, WLVM..............................27 Алгоритмы построения и анализа ссылок: Similarity Flooding, алгоритм извлечения синонимов из толкового словаря и другие...........................................................................31 Алгоритмы статистического анализа текста: ESA, поиск контекстно-связанных слов..........................................................................................................................................34 Метрики.................................................................................................................................1.2 СИСТЕМЫ И РЕСУРСЫ ДЛЯ ОБРАБОТКИ ТЕКСТА................................................................................GATE.......................................................................................................................................Проект Диалинг.....................................................................................................................Тезаурусы WordNet, РуТез, Викисловарь.............................................................................Вики-ресурсы..........................................................................................................................Корпус текстов вики-ресурса Википедия...........................................................................Другие системы.....................................................................................................................1.3 СИСТЕМЫ И СПОСОБЫ ГРАФИЧЕСКОГО ПРЕДСТАВЛЕНИЯ ТЕЗАУРУСОВ И РЕЗУЛЬТАТОВ ПОИСКА...............1.4 ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЯ........................................................................................... ВЫВОДЫ ПО ГЛАВЕ 1.......................................................................................................................2. МЕТОДОЛОГИЧЕСКОЕ И МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ПОСТРОЕНИЯ СПИСКОВ СЕМАНТИЧЕСКИ БЛИЗКИХ СЛОВ В КОРПУСЕ ТЕКСТОВЫХ ДОКУМЕНТОВ С ГИПЕРССЫЛКАМИ И КАТЕГОРИЯМИ.................2.1 ПОДХОД К ПОИСКУ СЕМАНТИЧЕСКИ БЛИЗКИХ СЛОВ.........................................................................2.2 HITS АЛГОРИТМ (ФОРМАЛИЗАЦИЯ, АНАЛИЗ, ПОИСК СИНОНИМОВ)....................................................Формализация задачи............................................................................................................Дополнительные замечания..................................................................................................Тематическая связность авторитетных страниц...........................................................Применение способов оценки результатов поиска в Интернет к HITS алгоритму......Поиск синонимов с помощью HITS алгоритма...................................................................2.3 АДАПТИРОВАННЫЙ HITS АЛГОРИТМ, ВКЛЮЧАЮЩИЙ АЛГОРИТМ ИЕРАРХИЧЕСКОЙ КЛАСТЕРИЗАЦИИ......Формализация понятия похожие вершины графа.........................................................Адаптированный HITS алгоритм........................................................................................Кластеризация на основе категорий статей....................................................................Варианты объединения результатов АHITS алгоритма и алгоритма кластеризации.Временная сложность алгоритма......................................................................................Эвристика: фильтрация на основе категорий статей....................................................2.4 ВЫЧИСЛЕНИЕ МЕРЫ СХОДСТВА ВЕРШИН ГРАФА. ОЦЕНКА ВРЕМЕННОЙ СЛОЖНОСТИ. ЭВРИСТИКИ...........Задача поиска похожих вершин графа................................................................................Алгоритм поиска похожих вершин графа..........................................................................Оценка временной сложности.............................................................................................Эвристики..............................................................................................................................2.5 ПОКАЗАТЕЛИ ЧИСЛЕННОЙ ОЦЕНКИ СЕМАНТИЧЕСКОЙ БЛИЗОСТИ СПИСКА СЛОВ.....................................Коэффициент Спирмена.......................................................................................................

ВЫВОДЫ ПО ГЛАВЕ 2.......................................................................................................................3. ОРГАНИЗАЦИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПОИСКА СЕМАНТИЧЕСКИ БЛИЗКИХ СЛОВ, АВТОМАТИЧЕСКОЙ ОЦЕНКИ ПОИСКА И МОРФОЛОГИЧЕСКОГО АНАЛИЗА СЛОВ..........................................................................3.1 АРХИТЕКТУРА ПРОГРАММНОЙ СИСТЕМЫ SYNARCHER.......................................................................3.2 АРХИТЕКТУРА ПОДСИСТЕМЫ GATE ДЛЯ УДАЛЁННОГО ДОСТУПА (НА ОСНОВЕ XML-RPC ПРОТОКОЛА) К ПРОГРАММЕ МОРФОЛОГИЧЕСКОГО АНАЛИЗА LEMMATIZER.....................................................................3.3 ИНДЕКСИРОВАНИЕ ВИКИ-ТЕКСТОВ: АРХИТЕКТУРА СИСТЕМЫ И СТРУКТУРА ИНДЕКСНОЙ БАЗЫ ДАННЫХ..Архитектура системы построения индексной БД вики-текстов.................................Таблицы и отношения в индексной БД..............................................................................3.4 АРХИТЕКТУРА ПРОГРАММНОЙ СИСТЕМЫ ДЛЯ АВТОМАТИЧЕСКОЙ ОЦЕНКИ СПИСКОВ СЕМАНТИЧЕСКИ БЛИЗКИХ СЛОВ................................................................................................................................ ВЫВОДЫ ПО ГЛАВЕ 3.....................................................................................................................4. ЭКСПЕРИМЕНТЫ И ПРАКТИЧЕСКОЕ ИСПОЛЬЗОВАНИЕ РАЗРАБОТАННЫХ В ДИССЕРТАЦИИ АЛГОРИТМОВ...........................................................................................4.1 ЭКСПЕРИМЕНТАЛЬНАЯ ОЦЕНКА РАБОТЫ АДАПТИРОВАННОГО HITS АЛГОРИТМА................................Оценка тестируемого корпуса текстов..........................................................................Эксперименты с Английской Википедией.........................................................................Эксперименты с Русской Википедией...............................................................................Экспериментальное сравнение адаптированного с исходным HITS алгоритмом.......Сравнение результатов работы AHITS алгоритма с другими на основе 353 пар английских слов....................................................................................................................Пример оценки эвристики с помощью коэффициента Спирмена.................................Применение коэффициента Спирмена для оценки параметров адаптированного HITS алгоритма.............................................................................................................................4.2 СЕССИЯ НОРМАЛИЗАЦИИ СЛОВ НА ОСНОВЕ МОДУЛЯ RUSSIAN POS TAGGER, КАК ОДНОГО ИЗ ЭТАПОВ АВТОМАТИЧЕСКОЙ ОБРАБОТКИ ТЕКСТОВ В СИСТЕМЕ GATE.................................................................4.3 ИНДЕКСИРОВАНИЕ ВИКИ-ТЕКСТА: ИНСТРУМЕНТАРИЙ И ЭКСПЕРИМЕНТЫ...........................................Преобразование вики-текста с помощью регулярных выражений...............................API индексной базы данных вики.......................................................................................Эксперименты по построению индексных баз данных...................................................Проверка выполнения закона Ципфа для вики-текстов..................................................4.4 ЭКСПЕРИМЕНТЫ В ПРОЕКТЕ КОНТЕКСТНО-ЗАВИСИМЫЙ ПОИСК ДОКУМЕНТОВ В ПРОБЛЕМНООРИЕНТИРОВАННЫХ КОРПУСАХ........................................................................................................ ВЫВОДЫ ПО ГЛАВЕ 4..................................................................................................................... ЗАКЛЮЧЕНИЕ.......................................................................................................................... СПИСОК ИСТОЧНИКОВ ЛИТЕРАТУРЫ.......................................................................... ПРИЛОЖЕНИЕ 1. СПИСОК НАИБОЛЕЕ УПОТРЕБИТЕЛЬНЫХ СОКРАЩЕНИЙ......................................................................................................................................................... ПРИЛОЖЕНИЕ 2. АКТЫ ВНЕДРЕНИЯ.............................................................................. ПРИЛОЖЕНИЕ 3. ЭКСПЕРИМЕНТАЛЬНЫЕ ДАННЫЕ ПРОГРАММЫ SYNARCHER................................................................................................................................ ПРИЛОЖЕНИЕ 4. УПОРЯДОЧЕНИЕ СПИСКОВ С ПОМОЩЬЮ РЕСПОНДЕНТОВ......................................................................................................................................................... ПРИЛОЖЕНИЕ 5. ВИКИПЕДИЯ...........................................................................................Отношения в Википедии.....................................................................................................Замечания о категориях и ссылках Википедии.................................................................- 5 Введение Некоторые определения. Для более ясного понимания материала и во избежание недоразумений целесообразно привести следующие определения.

Тезаурус - это словарь, в котором слова, относящиеся к каким-либо областям знания, расположены по тематическому принципу и показаны семантические отношения (родо-видовые, синонимические и др.) между лексическими единицами.Глоссарий - это собрание глосс (толкований) непонятных слов или выражений с толкованием (толковый глоссарий) или переводом на другой язык (переводной глоссарий).Информационные поисковые системы (ИПС) - системы поиска релевантных3 документов (текст, изображение, аудио, видео файлы и др.) в сети Интернет или на локальном компьютере, где задача формулируется пользователем в виде набора ключевых слов с возможностью их объединения логическими правилами (И, ИЛИ и др.).

Актуальность темы диссертации. Увеличение числа и изменение качества4 электронных документов на локальных компьютерах и в сети Интернет требуют новых алгоритмов для более точного и быстрого поиска.

Выделяют два вида сходства [179]: сходство между объектами (рассматривается в данной работе) и сходство между отношениями (relational similarity, см. [178], [177], [180])5. Является ли сущность свойством объекта или отношением - определяется контекстом [105]. Поиск похожих объектов 1 Определение, функции и примеры тезаурусов см. на стр. 45.

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

3 Релевантность (relevance, relevancy) - соответствие документа запросу [52].

4 Появился новый формат электронных документов - вики, см. стр. 51. Особенности корпуса вики-текстов, позволяющие говорить о качественном изменении вики по сравнению с html страницами, перечислены на стр. 24.

5 Другая задача, получившая название semantic associations, заключается в поиске и ранжировании сложных отношений в данных RDF. Две сущности в RDF графе семантически связаны (semantic associations), если существует связывающий их путь (или несколько путей). В работе [71] представлен поиск в семантической сети [17] интересных пользователю отношений между двумя сущностями и ранжирование отношений, основанное на статистических и семантических (например, учёт типа ссылок) критериях. См. прототип системы: 6 (similarity search) включает такие (на первый взгляд разные, но общие по способам решения) задачи, как поиск похожих текстовых документов, поиск семантически близких слов, поиск похожих вершин графа. Анализ работ в области вычислительной лингвистики показал большое разнообразие алгоритмов, предлагающих решение этих задач (алгоритм HITS [125], алгоритм PageRank [85] (и его модификация Green [145]), алгоритм распределения рангов ArcRank [174], ESA [103], алгоритм извлечения синонимов из толкового словаря [174], метод извлечения контекстно связанных слов [122], [146] и др.). Поиск похожих документов также может являться подэтапом алгоритма поиска документов по запросу [22].

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

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

[44], а также Однако категории представляют однородную (один тип отношений - родо-видовые) бинарную (связаны два объекта) семантическую сеть. Иной подход предлагается в работе [54], где семантические элементы считаются семантически связанными, если они связаны отношением ссылается. Семантическими элементами названы дидактические единицы контента, например лекция, лопределение, теорема, термин.

Pages:     ||    Авторефераты по всем темам  >>  Авторефераты по разным специальностям