автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Математическое и программное обеспечение построения списков семантически близких слов на основе рейтинга вики-текстов

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

г

РГБ ОД

КРИЖАНОВСКИЙ

Андрей Анатольевич 2 8 АВГ 2008

МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ПОСТРОЕНИЯ СПИСКОВ СЕМАНТИЧЕСКИ БЛИЗКИХ СЛОВ НА ОСНОВЕ РЕЙТИНГА ВИКИ-ТЕКСТОВ

Специальность 05 13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2008

003445530

Работа выполнена в Учреждении Российской академии наук Санкт-Петербургском институте информатики и автоматизации РАН

Научные руководители: доктор технических наук,

профессор Смирнов Александр Викторович

Официальные оппоненты: доктор технических наук,

профессор Гаврилова Татьяна Альбертовна

доктор технических наук,

профессор Городецкий Владимир Иванович

Ведущая организация

Вычислительный центр им. А. А. Дородницына РАН

Защита состоится « 16 » сентября 2008 г в 12 30 на заседании диссертационного совета Д 002 19901 при Санкт-Петербургском институте информатики и автоматизации РАН по адресу 199178, Санкт-Петербург, В О , 14 линия, 39

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

Автореферат разослан « 29 » июля 2008 г.

Ученый секретарь

диссертационного совета Д.002.199.01

Ронжин Андрей Леонидович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы диссертации

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

Одной из актуальных задач данного направления является поиск похожих объектов, который включает такие (на первый взгляд разные, но общие по способам решения) задачи, как поиск похожих текстовых документов, поиск семантически близких слов, вычисление меры сходства между вершинами графа Анализ работ в области вычислительной лингвистики показал большое разнообразие алгоритмов, предлагающих решение этих задач Hypertext Induced Topic Selection (HITS), PageRank, ArcRank, алгоритм извлечения синонимов из толкового словаря, алгоритм извлечения контекстно связанных слов и др

Поиск семантически близких слов является подзадачей таких актуальных задач информационного поиска, как (1)расширение/переформулировка запросов с помощью тезаурусов (в поисковых системах), (2) распознавание запроса в запросно-ответных системах, (3) определение значения многозначного слова и (4) автоматическое создание тезаурусов

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

Под семантически близкими словами подразумеваются слова с близким значением, встречающиеся в одном контексте Более строго семантически близкие слова определяются в работе через понятия корневого набора (релевантные документы), авторитетных и хаб-документов, вводимые в работах Клейнберга

Современные алгоритмы поиска синонимов (например, алгоритм SimRank, алгоритм Similarity Flooding) не учитывают такую информацию корпусов проблемно-ориентированных документов, как (1) ключевые слова

1 Связь, осуществляемая гиперссылкой, не имеет семантики, те не описывает смысла этой связи Однако категории представляют бинарную (связаны два объекта) семантическую сеть с иерархическими отношениями (родо-видовые и часть - целое)

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

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

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

2 Разработать подход к поиску семантически близких слов (в корпусе текстовых документов с гиперссылками и категориями)

3 Разработать алгоритмы поиска семантически близких слов в корпусе текстовых документов с гиперссылками и категориями

4 Спроектировать и реализовать программный комплекс поиска семантически близких слов, разработать способы численной оценки наборов синонимов

Методы исследования включают методы кластерного анализа, теории графов, элементы теории сложности алгоритмов

Положения, выносимые на защиту:

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

2 Адаптированный HITS алгоритм поиска семантически близких слов в корпусе текстовых документов с гиперссылками и категориями Модификация алгоритма включает (1) новый способ построения корневого набора (релевантных документов), позволяющий отказаться от предварительного поиска документов, а также (2) использование механизма иерархической кластеризации для объединения слов в смысловые группы

3 Клиент-серверная архитектура программного комплекса, предназначенного для решения задачи поиска семантически близких слов с возможностью оценки (с помощью удаленного доступа к тезаурусам и на

основе модификации коэффициента Спирмена) семантической близости построенных списков слов

4 Программный комплекс поиска семантически близких слов в проблемно-ориентированном корпусе текстов с динамической визуализацией результатов поиска

5 Архитектура системы индексирования вики-текстов и ее программная реализация

Научная новизна

1 Новизна предложенного подхода к поиску семантически близких слов в проблемно-ориентированном корпусе заключается в том, что кроме гиперссылок дополнительно учитывается метаинформация документов (ключевые слова, категории)

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

3 Новый способ построения корневого набора документов в адаптированном HITS алгоритме заключается в выборе документов, связанных гиперссылками с исходным документом (заданным пользователем), что позволяет отказаться от шага «предварительный веб-поиск документов»

4 Коэффициент Спирмена модифицирован для численного сравнения списков семантически близких слов, отличие заключается в возможности сравнивать списки разной длины

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

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

7 Эксперименты подтвердили выполнение закона Ципфа для текстов Русской Википедии и Википедии на английском упрощенном языке на основе построенных индексных баз данных

Обоснованность и достоверность научных положений, основных выводов и результатов диссертации обеспечивается за счет тщательного анализа состояния результатов исследований в области вычислительной лингвистики, подтверждается экспериментами на основе трех корпусов текстов Русской Википедии, Английской Википедии и Simple Wikipedia (Википедия на английском упрощенном языке)

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

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

Спроектирован и реализован программный комплекс Russian POS Tagger (RitPOSTaggerf, позволяющий интегрировать среду GATE и модуль морфологической обработки русского языка Lemmatizer (компании Диалинг) Комплекс RuPOSTagger предоставляет доступ к функциям модуля Lemmatizer на основе XML-RPC протокола из системы GATE или из отдельного Java приложения

Реализация результатов работы. Исследования, отраженные в диссертации, были поддержаны грантами РФФИ (проект № 02-01-00284 «Методологические и математические основы построения компьютерных систем быстрой интеграции знаний из распределенных источников» 2002-2004 гг, № 06-07-89242 «Методология и модели интеллектуального управления конфигурациями распределенных информационных систем с динамически изменяющимися структурами», 2006-2008 гг, № 05-01-00151 «Методологические и математические основы построения контекстно-управляемых систем интеллектуальной поддержки принятия решений в открытой информационной среде», 2005-2007 гг), грантами Президиума РАН (проект № 2 44 «Многоагентный подход к построению компьютерной среды для быстрой интеграции знаний из распределенных источников» 2001-2003 гг и проект № 2 35 «Контекстно-управляемая методология построения распределенных систем интеллектуальной поддержки принятия решений в открытой информационной среде» 2003-2008 гг), а также грантом ОИТВС РАН (проект № 1 9 «Разработка теоретических основ и многоагентной технологии управления контекстом в распределенной информационной среде» 2003-2005 гг)

Часть результатов была использована при выполнении контракта «Интеллектуальный доступ к каталогам и документам» на создание системы поддержки клиентов, реализованной для немецкой промышленной компании Фесто, 2003-2004 гг Разработана архитектура программной системы поиска

2 Программная реализация http //synarcher sourceforge net

3 Программная реализация http //rupostagger sourceforge net

семантически близких слов в исследовательском проекте CRDF № RUM2-1554-ST-05 «Онтолого-управляемая интеграция информации из разнородных источников для принятия решений», 2005-2006 гг

Апробация результатов работы: Основные положения и результаты диссертационной работы представлялись на международном семинаре «Автономные интеллектуальные системы агенты и извлечение данных» (Санкт-Петербург 2005), международных конференциях «Диалог» (Бекасово 2006), «Речь и Компьютер» (Санкт-Петербург 2006), «Корпусная лингвистика - 2006» (Санкт-Петербург) и первой конференции в России «Вики-конференции 2007» (Санкт-Петербург 2007)

Публикации: Основные результаты по материалам диссертационной работы опубликованы в 8 печатных работах, в том числе в 2 журналах из списка ВАК

Структура и объем работы: Диссертация объемом 156 страниц (188 с приложениями) содержит введение, четыре главы и заключение, приложения, список литературы (189 наименований), 35 рисунков, 14 таблиц

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована важность и актуальность темы диссертации, сформулированы цели диссертационной работы и решаемые задачи, определена научная новизна работы и указана ее практическая ценность, кратко изложены основные результаты

В первой главе диссертации кратко описаны предыдущие исследования в области теории графов и вычислительной лингвистики, цель которых — поиск похожих интернет-страниц, а также вычисление меры сходства между вершинами графа В настоящее время широкое распространение получил ряд алгоритмов, предлагающих решение этих задач, например, алгоритмы HITS, PageRank, алгоритм распределения рангов ArcRank, алгоритм извлечения синонимов из толкового словаря, метод извлечения контекстно связанных слов и др Такое разнообразие алгоритмов неслучайно

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

семантически близких слов

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

1 Разработка (выбор) алгоритмов Предложена классификация алгоритмов, выполняющих поиск похожих документов и близких по значению слов (1) поиск на основе анализа ссылок, когда ссылки заданы явно гиперссылками (HITS, PageRank, ArcRank, Green, WLVM и др ), и когда ссылки нужно построить (Similarity Flooding, алгоритм извлечения синонимов из толкового словаря), (2) поиск на основе анализа текста (2 1) статистические алгоритмы, а именно ESA, сходство коротких текстов, извлечение контекстно связанных слов на основе частотности словосочетаний и (2 2) автоматическое понимание текстов, и (3) поиск на основе анализа и ссылок, и текста (алгоритмы ученых Bharat и Maguitman) Требованием к алгоритму поиска семантически близких слов является учет дополнительных возможностей, предоставляемых рассматриваемым корпусом документов, а именно (1) наличие категорий, классифицирующих документы по их тематической принадлежности, (2) наличие метаинформации в виде ключевых слов (например, заголовок документа)

2 Оценка результатов работы алгоритма Анализ работ в данной области показал, что необходима разработка оригинальных показателей степени синонимичности полученных списков семантически близких слов Задача выбора текстового ресурса определяет способ оценки результатов поиска Среди множества проблем создания, использования корпусов можно выделить общую проблему отсутствия единого стандарта В диссертации в качестве корпуса вики-текстов предлагается использовать коллективную онлайн энциклопедию Википедия, содержащую 2 4 млн документов

3 Программные ресурсы для обработки текста При выборе программных инструментальных средств разработки и проектирования архитектуры программного комплекса автор придерживался следующих требований открытость исходного кода, кроссплатформенность, модульность архитектуры

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

Во второй главе разработан подход к поиску семантически близких слов (СБС) в корпусе текстов с гиперссылками и категориями на основе указанных выше подзадач поставленной проблемы (рис 1) Входными

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

Рис. 1. Подход к поиску семантически близких слов

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

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

Каждому документу в HITS алгоритме сопоставляются веса а (authority) и

h {hub), которые показывают, соответственно, насколько документ является авторитетным и насколько он является хорошим хаб-документом Формулы алгоритма HITS для итеративного вычисления весов таковы

hj = Е я, , <*J = Е К (1)

I О < U,j)e.E

где значение веса hj показывает насколько документ j является хорошим указателем на релевантные документы (/-ый документ рассматривается как хаб-документ) и а, — насколько документ j является авторитетным документом

Предложена формализация понятия «похожие вершины» графа, а также понятий, неформально введенных Клейнбергом (см выше) авторитетные (А) и хаб (Л) документы (здесь вершины) В формулах s обозначает исходную вершину, к— весовой параметр, определяющий приоритет авторитетных либо хаб-документов

Адаптированный HITS алгоритм (AHITS), разработанный автором, учитывает метаинформацию проблемно-ориентированного корпуса документов (1) ключевые слова, (2) категории, классифицирующие документы по их тематической принадлежности и (3) гиперссылки В HITS алгоритме граф содержит взвешенные вершины одного типа Предлагается модификация алгоритма для учета трех типов вершин (авторитетный документ, хаб-документ и новый тип вершин для HITS алгоритма — категория) и трех типов дуг (документ-документ и новые для для HITS документ-категория и категория-категория), определяемых проблемно-ориентированным корпусом текстов

Таким образом, исходными данными для алгоритма являются (рис 1) сеть документов-энциклопедических статей (вершины - документы, дуги -гиперссылки) и дерево категорий (вершины - категории, дуги связывают категории-родителей с категориями-детьми) Причем элемент сети (статья) связан с одним или несколькими элементами дерева (категории) Для каждого документа определены (i) список документов, ссылающихся на данный документ, (и) список документов, на которые ссылается данный документ, (ш) список категорий, определяющих его тематическую принадлежность

Шаги AHITS алгоритма представлены на рис 2 Шаги, предложенные автором, выделены пунктиром Тематическая классификация документов и

A ,\A\-N, X ci^mctx

VGA

HaV,\H\=M, X K^max

vetf

A^V ,кф,1]

к K^max

VGA v6H

A^V ,HzlV ,V aeA 3 heH r+{h)3s,a

Рис. 2. Адаптированный HITS Рис. 3. Иерархическая

алгоритм кластеризация

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

Временная сложность вычисления весов на шаге 4 (рис 2) составляет 0(1 N2), где I - число итераций, N - число документов в базовом наборе Сложность кластеризации (рис 3) определяется как О (С3 + N С'), где С — число категорий, N - число документов в базовом наборе Итак, временная сложность AHITS алгоритма есть 0(С3 + N С2 + IN2), она выросла по

сравнению со сложностью HITS алгоритма 0(IN2), но при этом выросла точность поиска (см далее результаты экспериментов)

Предложены показатели численной оценки построенного упорядоченного списка семантически близких слов, разработанные автором SER (Strong Error Rate) - оценка грубой ошибки, а именно число слов (в процентах от общего числа найденных слов), которые не имеют отношения к исходному слову (определяется либо вручную экспертом либо автоматически - по

наличию / отсутствию в тезаурусе) Обозначим WordsAHITS _ МНОжество слов, найденных с помощью AHITS алгоритма для слова w, Words"WordNe¡ - список синонимов из тезауруса WordNet для слова w, Wordslhhy - список семантически близких слов из Moby, знак «\» - вычитание множеств

100 (2)

\WordsllíTSUWords;yorJNe,VWordslJ

Для численной оценки степени сходства эталонного списка (WordNet, Moby) и автоматически построенного списка СБС адаптирован коэффициент Спирмена Адаптация позволяет сравнивать ранжирование элементов в списках разной длины Итак, для исходного слова даны эталонный список А, построенный экспертом, и список В, построенный автоматически В конец списка В добавляются отсутствующие в нем элементы А. Каждому элементу списка назначается ранг (порядковый номер) от 1 до N Далее применяется формула (3), где сравниваются положения в списках общих элементов, то есть вычисляется сумма модулей расстояний между /-ми элементами набора, S- число общих элементов

i

(3)

1=1

Коэффициент Спирмена позволяет сравнивать с эталонным списком ранжирование одного и того же набора слов AHITS алгоритмом при разных входных параметрах (размер корневого набора, максимальный вес кластера)

В третьей главе представлена архитектура программного комплекса Synarcher, включающего такие модули, как модуль klemberg, предоставляющий доступ к данным Википедии и реализующий алгоритм AHITS, модуль визуализации TGWihBrowser, модуль вычисления степени синонимичности списков слов на основе удаленного доступа к тезаурусам Moby и WordNet Данные Википедии (тексты, ссылки) хранятся в базе данных MySQL, размещенной локально или удаленно Параметры поиска и слова, помеченные пользователем как синонимы, хранятся на компьютере пользователя

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

В главе описаны экраны программы (1) экран Article, позволяющий просмотреть энциклопедическую статью, соответствующую выбранному слову, (2) экран Database, позволяющий подключиться к базе данных н получить статистику по базе данных, (3) экран Synonyms, на котором задаются параметры AHITS алгоритма, выводятся результаты поиска в табличной и текстовой форме, (4) экран с результатами поиска СБС в виде графа (рис 8)

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

Вход_

Язык, Параметры баз данных TF-IDF ограничения

Приложение индексирования Википедии

Управляющее приложение

1 Извлечение текстов из Викиледии

2. Анализ текста (порождение лемм)

3 Сохранение (лемм частот)

Обработчик Википедии

Извлечение страниц вики | [ Преобразование вики в текст"!

Базы данных

Wikipedia DB Lemmatizer DB TF-IDF Index DB

GATE

Tokeneer

Sentence Splitter ]

POS* Tagger

Lemmatizer

TF-IDF Приложение (WikIDF)

Рис. 4. Архитектура системы индексирования вики-текстов

В четвертой главе описаны данные морфологического анализа, доступные в подсистеме Russian POS Tagger Представлены (i) пример инициализации подсистемы, (п) параметры подключения к XML-RPC серверу LemServer и (ш) результаты работы подсистемы в составе системы GATE

С помощью разработанной системы индексирования вики-текстов построены индексные базы Русской Википедии и Ви-кипедии на английском упро-выполнения закона Ципфа для корпусов щенном языке, выполнено Русской Википедии и Simple Wikipedia сравнение основных показателей индексных баз данных (число слов, лексем) Обнаружен более быстрый рост английской за пять месяцев (септ 2007 — февр 2008) скорость роста числа статей была больше на 12% и на 6% быстрее чем в русской пополнялся лексикон Википедии на английском упрощенном языке Эксперименты подтверждают выполнение закона Ципфа4 для текстов Русской Википедии и Википедии на английском упрощенном языке (рис 5)

Далее описаны эксперименты поиска СБС в английской и русской версии Википедии с помощью AHITS алгоритма Описан пример работы в программе Synarcher Эксперименты показали, что разработанный программный комплекс Synarcher позволяет найти синонимы и семантически близкие слова в английской Википедии, отсутствующие в современных тезаурусах WordNet, Moby (например, найден синоним Spanonaut для слова Astronaut) Тем не менее, некоторые синонимы, представленные в тезаурусах и Википедии, не были найдены

На рис 6 представлен пример оценки времени работы и точности поиска СБС для слов и словосочетаний, имеющих энциклопедические статьи в Русской Википедии (Аэродром, Беспилотный летательный аппарат, Движитель, Интернационализация, Истина, Пропеллер, Самолет, Сюжет,

4 Эмпирический закон Ципфа говорит о том, что частота употребления слова в корпусе текстов обратно пропорциональна его рангу в списке упорядоченных по частоте слов этого корпуса

ruwiM 08 Garpui

- --1/x"OÍ19

---i/Xa! 048

X smtie»» 08 eciíu*

-1/X*0 974

- -1/хЧ 174

Рис. 5 Экспериментальная оценка

р,

30 25 -20 -

-♦-Самолёт

т Истина j

а Сюжет ,

Интернационализация < Аэродром j

*] Движитель !

s Пропеллер j

15 — _ / _ ..".Беспилотный ffe-

х -и _ . ------------тательный аппарат

Ю Л * / * * Турбина

2 ■■ * - ЯШ S £ ЩЩ - ..............А

ф ♦ ♦ * ^ ф _

n -А -6 ■< Ч

U 11:1 — | I I 1 -1--1

0 2 4 6 8 10 12 14 16 18 20

Число фильтруемых категорий

Рис. 6. Пример изменения точности5 поиска (Р) AHITS алгоритма в зависимости от числа фильтруемых категорий

Турбина) с помощью AHITS алгоритма в зависимости от числа категорий.

Чёрный список категорий (blacklist) составляется экспертом и сужает пространство поиска. Например, фильтрация по категории XX век позволяет отсечь множество документов с заголовками: 1900, 1901 и т. д. В эксперименте для фильтрации выбираются категории с максимальным числом слов, не являющихся семантически близкими заданному слову. Рис. 7 показывает, что при использовании категорий (для слова Самолёт) время работы вырастает, но точность поиска также увеличивается.

8,5 -7.0 -5,5 -4,0 -2,5 ■ 1,0 --0,5--

Р,%

15,2 - 16

13,6, .

5,2 12,6..---*

□LQddd

-i---Г-i-1-1----1-

0 1 3 6 10 17 1——' " ---Категорий

HITS AHITS

Рис. 7. Изменение времени работы t и точности поиска Р AHITS алгоритма в зависимости от числа фильтруемых категорий для слова Самолёт

5 Точность — отношение числа семантически близких слов, найденных программой, к общему числу найденных слов. Списки СБ С (синонимы, антонимы, гипонимы, гиперонимы, согипонимы, меронимы, холонимы) этих слов представлены в Русском Викисловаре (http://ru.wiktionary.org).

Русской Википедии соответствует граф, содержащий 171 тыс. вершин, 3.4 млн дуг (на ] 1.05.07). При поиске в графе AHITS алгоритм строит базовый набор с числом вершин 200-800, числом дуг 800-12 000 (для слова Самолёт). Указан диапазон вершин и дуг, поскольку изменение фильтруемых категорий меняет число вершин, включаемых в базовый набор. Таким образом, рис. 7 обобщает результаты шести опытов с разными размерами базовых наборов, построенных для слова Самолёт.

Основные отличия HITS и AHITS алгоритмов - не учёт и учёт категорий соответственно. При числе категорий ноль (первый вертикальный ряд на рис. 7) работа AHITS алгоритма (по скорости и точности поиска) соответствует работе HITS алгоритма. Это позволяет сравнить HITS и AHITS алгоритмы. Сравнение для указанных девяти слов показало, что работа AHITS алгоритма медленнее HITS алгоритма в среднем на 52%, а точность поиска AHITS алгоритма выше на 33% (рис. 6).

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

Предложенная модификация коэффициента Спирмена позволила оценить

ПоискД Показать Раскрыть о j

Статья А | База данных D [ Синонимы X j_^

\ Спово W '.Самолёт \

■ i Загрузить L ; | Поиск S, i Соседи N

ссылки □ MaciuTasjjjVj [cronji?)

-: ¡Ts

Параметры Р ;'' Категории С Г Результаты '!

ШЕШС

ES3SES5B

ЕЕЕЩШЙ'

Output

:ategory воздушные.суда

МуСКУЛОЛёТ

Монгольфьер Шарльер Дельтаплан Махолет

Рис. 8. Результаты поиска семантически близких слов для слова Самолёт в виде таблицы (со списком категорий), текста и графа

I Категория Статей! Черный список' j .

¡Истребители i2i 3 С

;АеиаИИ.н it Р IT* —Ii

;55*_с _ш. 1о! j I: 41

1Боздуй;Ны е_шаа ■si. - -i-oasi чп

15 1"_с._ш. 81 □ ¡Г

[Незавершённые.стат... 71 D С

¡rnrvnaocTBo 7i П S=

чувствительность результатов AHITS алгоритма к изменению параметров поиска с помощью экспериментов Для ряда слов из Русской Википедии (например, Самолет) точность поиска было достаточно стабильной (значение стандартного отклонения коэффициента Спирмеиа равно 4 41), что избавляет пользователя от необходимости тщательно подбирать параметры поиска Для более часто употребимого (в данном корпусе текстов) слова Сюжет качество результата оказалось в большей степени зависимым от входных параметров алгоритма (значение стандартного отклонения коэффициента Спирмеиа составило 95 97) На рис 8 представлены результаты поиска семантически близких слов для слова Самолет в виде списка категорий (в левой части экрана в центре), списка статей для выбранной категории («Воздушные суда») и графа

ЗАКЛЮЧЕНИЕ

Диссертационное исследование выполнено в соответствии с положениями пп 9 и 17 областей исследований паспорта специальности 05 13 11 разработанные алгоритмы решают задачи семантического анализа текстовой информации ка основе рейтинга текстов Разработаны математическое и программное обеспечение для автоматизированного построения упорядоченного списка семантически близких слов Результаты таковы

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

2 HITS алгоритм адаптирован к поиску семантически близких слов (в корпусе текстовых документов с гиперссылками и категориями) на основе (1) нового способа построения корневого набора документов и (2) механизма иерархической кластеризации, позволяющего объединять слова в смысловые группы

3 Спроектирована клиент-серверная архитектура программного комплекса поиска семантически близких слов с возможностью оценки списков слов на основе удаленного доступа к тезаурусам (WordNet, Moby) и модифицированного коэффициента Спирмена

4 Разработан программный комплекс поиска семантически близких слов в проблемно-ориентированном корпусе текстов с динамической визуализацией результатов поиска

5 Спроектирована архитектура и реализована система индексирования вики-текстов

ОСНОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИИ ОПУБЛИКОВАНЫ В РАБОТАХ

В рецензируемых журналах из списка ВАК

1 Крижановский, А А Автоматизированный поиск семантически близких слов на примере авиационной терминологии // Автоматизация в промышленности -2008 -Т 4 -С 16-20 (0,47 ал)

2 Крижановский, А А Формирование контекста задачи для интеллектуальной поддержки принятия решений / А В Смирнов, М П Пашкин, Н Г Шилов, Т В Левашова, А А Крижановский // Фундаментальные основы информационных технологий и систем // Труды Института системного анализа РАН - М ИСА РАН, 2004 -Т 9 - С 125-188 (0,56 ал)

В других изданиях

3 Крижановский, А А Оценка результатов поиска семантически близких слов в Википедии // Труды СПИИРАН Вып 5 — СПб Наука, 2007 - С 113-116 (0,24 ал)

4 Крижановский, А А Автоматизированное построение списков семантически близких слов на основе рейтинга текстов в корпусе с гиперссылками и категориями // Компьютерная лингвистика и интеллектуальные технологии Труды международной конференции «Диалог 2006» Бекасово, 2006 - С 297-302 (0,55 а л)

5 Knzhanovsky, A Synonym search in Wikipedia Synarcher / A Krizhanovsky // In 11-th International Conference "Speech and Computer" Russia, St Petersburg, 2006 - pp 474^77 (0,64 а л)

6 Knzhanovsky, A Context-sensitive access to e-document corpus / A Smirnov, T Levashova, M Pashkin, N Shilov, A Knzhanovsky, A Kashevmk, A Komarova // Труды международной конференции «Корпусная лингвистика-2006» — СПб Изд-во С -Петерб ун-та, 2006 -С 360-364 (0,18 ал)

7 Krizhanovsky, A Ontology-based users and requests clustenng in customer service management system / A Smimov, M Pashkm, N Chilov, T Levashova, A Knzhanovsky, A Kashevmk // In Autonomous Intelligent Systems Agents and Data Mining Spnnger-Veilag GmbH, Lecture Notes m Computer Science, 2005, Vol 3505,231-246 (0,98 а л)

8 Knzhanovsky, A Free text user request processing m the system "KSNet" / A Smirnov, M Pashkm, N Chilov, T Levashova, A Knzhanovsky // Proceedings of the 9th International Conference "Speech and Computer" Russia, St Petersburg, 2004 -pp 662-665 (0,36a л)

Отпечатано с готового оригинал-макета, предоставленного автором Подписано в печать 23 07 2008 Формат 60x84 1/16 Бум офсетная Уел печ л 1 Тираж 100 экз Заказ 3366

ООО "Альфа-пресс" Россия, Санкт-Петербург, ВО 3-я линия, д 36

ВВЕДЕНИЕ.

Положения, выносимые на защиту.

1. АНАЛИЗ ПРОБЛЕМЫ АВТОМАТИЧЕСКОЙ ОБРАБОТКИ ТЕКСТА И ПОИСКА СЕМАНТИЧЕСКИ БЛИЗКИХ СЛОВ.

Проблема синонимии.

1.1 Основные алгоритмы поиска похожих интернет страниц, поиска слов близких по значению, вычисления меры сходства вершин графа.

Алгоритмы анализа гиперссылок: HITS, PageRank, ArcRank, WLVM,.

Алгоритмы построения и анализа ссылок: Similarity Flooding, алгоритм извлечения синонимов из толкового словаря и другие.

Алгоритмы статистического анализа текста: ESA, поиск контекстно-связанных слов.

Метрики.

1.2 Системы и ресурсы для обработки текста.

GATE.

Проект Диалинг.

Тезаурусы WordNet, РуТез, Викисловарь.

Вики-ресурсы.

Корпус текстов вики-ресурса Википедия.

Другие системы.

1.3 Системы и способы графического представления тезаурусов и результатов поиска.

1.4 Постановка задачи исследования.

Выводы по главе 1.

2. МЕТОДОЛОГИЧЕСКОЕ И МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДЛЯ ПОСТРОЕНИЯ СПИСКОВ СЕМАНТИЧЕСКИ БЛИЗКИХ СЛОВ В КОРПУСЕ ТЕКСТОВЫХ ДОКУМЕНТОВ С ГИПЕРССЫЛКАМИ И КАТЕГОРИЯМИ.

2.1 Подход к поиску семантически близких слов.

2.2 HITS алгоритм (формализация, анализ, поиск синонимов).

Формализация задачи.

Дополнительные замечания.

Тематическая связность авторитетных страниц.

Применение способов оценки результатов поиска в Интернет к HITS алгоритму.

Поиск синонимов с помощью HITS алгоритма.

2.3 Адаптированный HITS алгоритм, включающий алгоритм иерархической кластеризации.

Формализация понятия «похожие вершины» графа.

Адаптированный HITS алгоритм.

Кластеризация на основе категорий статей.

Варианты объединения результатов AHITS алгоритма и алгоритма кластеризации.

Временная сложность алгоритма.

Эвристика: фильтрация на основе категорий статей.

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 документов (текст, изображение, аудио, видео файлы и др.) в сети Интернет или на локальном компьютере, где задача формулируется пользователем в виде набора ключевых слов с возможностью их объединения логическими правилами (И, ИЛИ и др.).

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

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

1 Определение, функции и примеры тезаурусов см. на стр 45.

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

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

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

5 Другая задача, получившая название semantic associations, заключается в поиске и ранжировании сложных отношений в данных RDF. Две сущности в RDF графе семантически связаны (semantic associations), если существует связывающий их путь (или несколько путей). В работе [71] представлен поиск в семантической сети [17] интересных пользователю отношений между двумя сущностями и ранжирование отношений, основанное на статистических и семантических (например, учёт типа ссылок) критериях. См. прототип системы: httpV/lsdis.cs uga edu/projecte/semdis/index.php'?pnge=3 similarity search) включает такие (на первый взгляд разные, но общие по способам решения) задачи, как поиск похожих текстовых документов, поиск семантически близких слов, поиск похожих вершин графа. Анализ работ в области вычислительной лингвистики показал большое разнообразие алгоритмов, предлагающих решение этих задач (алгоритм HITS [124], алгоритм PageRank [85] (и его модификация Green [144]), алгоритм распределения рангов ArcRank [173], ESA [102], алгоритм извлечения синонимов из толкового словаря [173], метод извлечения контекстно связанных слов [121], [145] и др.). Поиск похожих документов также может являться подэтапом алгоритма поиска документов по запросу [22].

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

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

1 Связь, осуществляемая гиперссылкой, не имеет семантики, то есть не описывает смысла этой связи (см. [44], а также http://ni.wikipedin orti/\viki/CcManTH4ccKnnceTi,'). Однако категории представляют однородную (один тип отношений - родо-видовые) бинарную (связаны два объекта) семантическую сеть. Иной подход предлагается в работе [54], где семантические элементы считаются семантически связанными, если они связаны отношением «ссылается». Семантическими элементами названы дидактические единицы контента, например «лекция», «определение», «теорема», «термин».

2 См. определения авторитетных и хаб-страниц в главе 1 в подразделе «Алгоритм HITS» на стр. 27, см. также подраздел «Поиск синонимов с помощью HITS алгоритма» на стр. 74. Заметим, что слов хаб встречается в отечественной научной литературе, например, «термин-хаб» в работе [11].

3 «Семантическими принято считать системы, в которых в процессе анализа содержания текста делаются попытки учесть не только лингвосемантические, но и логико-семантические отношения между языковыми объектами. Кроме того, контекст, определяющий лингвосемантические отношения и в обычных системах синтаксического анализа не выходящий за пределы предложения, в семантических системах распространяется на уровни дискурса и текста. Наконец, предполагается, что система семантического анализа должна учитывать как сведения о данной предметной области, так и её связи с внешним миром в целом» [30]. лингвосемантические отношения рассматриваются на уровне текста, а также учитываются сведения о данной предметной области.

Современные алгоритмы поиска синонимов (например, алгоритм извлечения синонимов из толкового словаря [173], алгоритм SimRank [118], алгоритм Similarity Flooding [131]) изначально предназначены для вычисления меры сходства между вершинами графов. Поэтому алгоритмы не учитывают такую дополнительную информацию, как тематическая направленность и метаданные текста [142], [93], [112]. Данная работа призвана восполнить этот пробел.

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

1) формулы, вычисления в PageRank требуют экспериментального выбора коэффициента{damping factor)2, а в HITS нет никакого коэффициента, за счёт использования двух типов документов (авторитетные и хаб).

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

Поиск документов, на основе алгоритма. HITS тесно связан с вычислением сходства-вершин в графе. Автором,предложены два способа

1 Это позволяет не решать отдельную сложную задачу классификации — соотнесения документа заданным категориям. См., например, работу [136], в которой описано автоматическое отображение веб-страниц в Yahoo! онтологию с помощью классификатора Байеса, нли статью [105] о поиске похожих документов в библиографическом корпусе на основе алгоритма поиска ближайшего соседа (k-NN). Забегая вперёд, укажем, что задача классификации в вики-текстах решена за счёт наличия категории, указанных авторами текстов.

2 О сложности выбора амортизирующего коэффициента можно судить по работе [73]. вычисления меры сходства вершин графа на основе формализации понятия «похожие вершины» графа. Первый вариант использует понятия авторитетных и хаб-страниц и позволяет формализовать задачу поиска похожих страниц в HITS алгоритме. Во втором варианте получена формула сходства двух вершин а и Ь, основанная на поиске общих вершин среди соседей вершин а и Ъ.

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

При выборе программных инструментальных средств разработки и проектирования архитектуры программы автор придерживался следующих требований: открытость исходного кода (open source), кроссплатформенность (возможность работы на разных платформах: Linux, Windows и др.), модульность архитектуры (возможность использовать предыдущие наработки и интегрировать решения разных подзадач). Важными требованиями были: использование достаточно широко распространённых и хорошо себя зарекомендовавших программных систем для обработки текста на естественном языке и представление результатов работы в виде текста и графики (визуализация). Использование общепринятого стандарта и модульность архитектуры позволяют решить задачу большой сложности (например, машинный перевод), разбив её на ряд подзадач. В.качестве программной среды для обработки текстов на естественном языке была выбрана модульная система GATE [92], [97].

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

Отсутствуют (по крайней мере, неизвестны автору) доступные модули в системе GATE для морфологической обработки русского языка. Возможно, поэтому система GATE редко упоминается в системах обработки текстов на русском' языке. Таким образом, существует насущная необходимость в наличии модуля морфологической обработки русского языка в системе GATE, позволяющая нормализовать слова (лемматизация2), получать морфологические признаки слова (например, род, падеж) и т. д. При этом существует общедоступная программа морфологической обработки русского Lemmatizer (разработанная в проекте Диалинг московскими учёными). Сложность в том, что GATE написан на языке программирования Java, а Lemmatizer написан на С++. Таким образом, решением данной задачи будет разработка архитектуры позволяющей интегрировать эти системы.

К задачам автоматической обработки текста (АОТ) относятся такие задачи, как: машинный перевод, поиск и хранение текста [52], кластеризация

1 «В начале 50-х годов XX века группа американских исследователей под руководством Ч. Осгуда опубликовала сенсационную книгу «Измерение значения». Для языковедов само сочетание этих слов было бессмыслицей: каждому ясно, что значение слова, его смысл невозможно как-то там измерить (курсив наш — A.K.). Но 4. Осгуд действительно открыл для языкознания нечто новое. Он доказал, что в области семантики возможны измерения <.> 4. Осгуд впервые выделил и измерил качественно-признаковый аспект значения слова» [48].

2 Лемматизация - приведение слова к неопределённой (словарной) форме, например, для глаголов - это получение инфинитива (бежал — бежать), для существительных — это 1-ое лицо, ед.ч. (яблоки — яблоко). В работе [67] используется термин лексикографический контроль. «Он заключается в приведении используемых ключевых слов к единой морфологической форме и к единому написанию, в учёте синонимии и многозначности ключевых слов» ([67], стр. 75). текстов1 [43], [70], определение тематически однородных частей текста и приписывание этим частям документа тематических тегов [72], [103], реферирование текстов, и многие др. Автоматический поиск синонимов и семантически близких слов является одной из задач АОТ.

Актуальность работы определяется возможными областями приложений результатов диссертации. Во-первых, это поиск похожих вершин графа в рамках задачи Ontology Matching [131], [163], [189]. Во-вторых, предложенное решение задачи автоматического поиска синонимов и семантически близких слов может использоваться в поисковых системах для расширения запроса (на основе вычисления сходства запроса и документа [86], сходства запросов между собой2 [100], с помощью тезаурусов [10], [94], [162]), для автоматизированного построения онтологии по тексту3, для расширения существующих и создания новых тезаурусов4 [134]. В-третьих, разработанная программа поиска семантически близких слов, вероятно, будет востребована лингвистами-лексикографами при составлении словарей синонимов [7], [56], [160]. В работе [79] перечислены ещё два приложения, требующих решения задачи «similarity search»:

• «collaborative filtering» - определение пользователей, имеющих одинаковый вкус, предпочтения;

• поиск / исключение документов почти-копий (англ. «near duplicate»), которое требуется при индексировании документов.

1 «Кластер-анализ — это способ группировки многомерных объектов, основанный на представлении результатов отдельных наблюдений точками подходящего геометрического пространства с последующим выделением групп как "сгустков" этих точек.» [43]. Кластер в англ. это «сгусток», «гроздь (винограда)», «скопление (звезд)» и т.п. Неформально, кластер — это связный подграф с большим числом внутренних и небольшим числом внешних рёбер [164].

2 В работе [79] указан вариант объединения двух задач: (I) уточнение поискового запроса и (2) определение сходства запросов между собой. Подход заключается в том, чтобы на основе сходства результатов (множеств найденных документов) находить похожие запросы. Тогда поисковая система сможет предложить пользователю альтернативные формулировки запроса.

3 В работе [115] представлена схема извлечения концептов и отношений из текста с помощью эксперта (система T-Rex — The Trainable Relation Extraction framework).

4 Достоинство тезаурусов, построенных с помощью Википедии, как отмечают в работе [134] — это стоимость, постоянное расширение, то есть адекватность современному лексикону, многоязычность (то есть привязка к концепту слов на разных языках).

Ещё одна актуальная область связана с задачей определения значения многозначного слова1. Основа алгоритма представленного в [152], [186] — анализ контекста слова. При этом начальные слова2 в обучающем наборе (в алгоритме, предложенном в [186]) должны точно различать возможные значения. Выбор начальных слов (для заданного слова) можно выполнять с помощью предложенного в диссертации алгоритма поиска семантически близких слов. Другие актуальные направления новых информационных технологий, в которых могут использоваться результаты данной диссертационной работы - это направление запросно-ответных систем (question-answering system) и автоматическое создание проблемно-ориентированных тезаурусов3.

Данная диссертационная работа выполнена в рамках указанного направления исследований.

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

1. Проанализировать методы поиска семантически близких слов, обосновать выбор текстовых ресурсов, алгоритма (с возможной адаптацией) и программных систем для автоматической обработки текстов на естественном языке (ЕЯ).

2. Разработать подход к поиску семантически близких слов (в корпусе текстовых документов с гиперссылками и категориями).

3. Разработать алгоритмы поиска семантически близких слов в корпусе текстовых документов с гиперссылками и категориями.

1 Задача определения значения многозначных слов (Word sense disambiguation или WSD) состоит в приписывании каждому экземпляру слова одного из известных (например из словаря) значений. Эта задача отличается от задачи вывода значения слова (sense induction).

2 Начальные слова (seed words) представляют контекст, то есть входят в словосочетания, содержащие исследуемое многозначное слово. Начальные слова подбираются так, чтобы словосочетание имело однозначный смысл.

3 В работе [122] предложен метод построения таксономии по набору документов (система TaxaMiner).

4. Спроектировать и реализовать программный комплекс поиска семантически близких слов; разработать способы численной" оценки наборов синонимов.

Методы исследования. Для решения поставленных задач в работе используются методы кластерного анализа [43], [70], методы теории графов [19], [28], [29], [38], [45], [46], [49], элементы теории сложности алгоритмов [5], [23], [32], [42], стандарты открытых информационных сред. При разработке программного обеспечения использовалась технология объектно-ориентированного программирования (Java, С++) [13], язык структурированных запросов (SQL) управления данными в реляционных базах данных [26], программная среда для обработки текстов на естественном языке (GATE) [92], [97].

Научная новизна

1. Новизна предложенного подхода к поиску семантически близких слов в проблемно-ориентированном корпусе заключается в том, что кроме гиперссылок дополнительно учитывается метаинформация документов (ключевые слова, категории).

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

3. Новый способ построения корневого набора документов в адаптированном HITS алгоритме заключается в выборе документов, связанных гиперссылками с исходным документом (заданным пользователем), что позволяет отказаться от шага «предварительный веб-поиск документов».

4. Коэффициент Спирмена модифицирован для численного сравнения списков семантически близких слов; отличие заключается в возможности сравнивать списки разной длины.

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

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

7. Эксперименты подтвердили выполнение закона Ципфа для текстов Русской Википедии и Википедии на английском упрощённом языке на основе построенных индексных баз данных.

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

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

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

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

2 Число статей Английской Википедии превысило размер энциклопедии Британника. всей энциклопедии, так и по некоторому подмножеству текстов определённой тематики1.

Разработана архитектура программного модуля RuPOSTagger системы GATE для удалённого доступа к программе морфологического анализа русского языка (использован модуль морфологического анализа русского языка проекта Диалинг). Модуль RuPOSTagger может использоваться как внутри GATE (с другими модулями), так и быть интегрирован в отдельный (standalone) программный продукт. Спроектирована архитектура и реализована система индексирования вики-текстов.

Реализация результатов работы.

Исследования, отражённые в диссертации, были поддержаны грантами РФФИ (проект №02-01-00284 «Методологические и математические основы построения компьютерных систем быстрой интеграции знаний из распределённых источников» 2002-2004 гг.; № 06-07-89242 "Методология и модели интеллектуального управления конфигурациями распределенных информационных систем с динамически изменяющимися структурами", 2006-2008 гг.; № 05-01-00151 "Методологические и математические основы построения контекстно-управляемых систем интеллектуальной поддержки принятия решений в открытой информационной среде", 2005-2007 гг.), грантами Президиума РАН (проект № 2.44 «Многоагентный подход к построению компьютерной среды для быстрой интеграции знаний из -распределённых источников» 2001-2003 гг. и проект №2.35 «Контекстно-' управляемая методология построения распределённых систем, интеллектуальной поддержки принятия решений в открытой информационной среде» 2003-2008 гг.), а также грантом ОИТВС РАН (проект № 1.9 «Разработка теоретических основ и многоагентной технологии управления контекстом в распределённой информационной среде» 2003-2005 гг.).

Разработан программный комплекс Synarcher на языке Java для поиска семантически близких слов в энциклопедии Википедия с динамической

1 Более подробно о фильтрации статей при поиске и чёрном списке категорий см. на стр. 86. визуализацией результатов поиска2. Результаты поиска представлены в виде текста (список семантически близких слов), в виде таблицы (с возможностью упорядочения и редактирования) и в виде графического представления набора вершин и рёбер с возможностью показать/спрятать соседние вершины для текущей вершины. Настройка параметров поиска позволяет (i) указать размер пространства поиска, что определяет время поиска и результат, (и) разрешить поиск статей определённой тематики (то есть сузить область поиска) за счёт выбора категорий статей.

Спроектирована и реализована распределённая клиент-серверная архитектура в программном комплексе Russian POS Tagger2, позволяющая интегрировать среду GATE и модуль морфологической обработки русского языка Lemmatizer (фирма Диалинг). Комплекс RuPOSTagger предоставляет веб-сервис на основе XML-RPC протокола. Веб-сервис обеспечивает вызов функций модуля Lemmatizer из системы GATE или из отдельного Java приложения.

Часть результатов была использована при выполнении контракта «Интеллектуальный доступ к каталогам и документам» на создание системы поддержки клиентов, реализованной для немецкой промышленной компании Фесто, 2003-2004 гг. Разработан и реализован алгоритм кластеризация запросов (на естественном языке) и пользователей на основе использования онтологий в данном проекте [171].

Разработана архитектура программной системы поиска семантически близких слов в исследовательском проекте CRDF № RUM2-1554-ST-05 «Онтолого-управляемая интеграция информации из разнородных источников для принятия решений», 2005-2006 гг.

Апробация результатов работы. Основные положения и результаты диссертационной работы представлялись на международном семинаре «Автономные интеллектуальные системы: агенты и извлечение данных» (Санкт-Петербург 2005), международной конференции «Диалог» (Бекасово 2006), 11оГ| международной конференции «Речь и Компьютер» (Санкт

2 Программа с открытым исходным кодом, доступна по адресу http-Z/synnrclier sourccforgc net

2 Программа с открытым исходным кодом, доступна по адресу http //nipostnggcr.sourccforgc net

Петербург 2006), международной конференции «Корпусная- лингвистика» (Санкт-Петербург 2006) и первой конференции в России «Вики-конференции 2007» (Санкт-Петербург 2007). Часть результатов работы представлена в публикациях [33], [36], [35], [57], [58], [167], [168], [169], [170], [171].

Публикации. Основные результаты по материалам'диссертационной работы опубликованы в 8 печатных работах, в том числе: в 2 журналах из: списка ВАК («Труды Института системного анализа РАН», 2004, «Автоматизация в промышленности», 2008).

Структура? и объём работы. Диссертационная работа; состоит из введения, четырёх глав, заключения; списка литературы и пяти приложений. Работа изложена на 156 страницах и включает 35 рисунков, 14 таблиц, а также список литературы из 189 наименований; приложения на 14 страницах. Общий объём работы составляет 188 страниц.

Выводы по главе 4

В этой главе (1) описаны эксперименты поиска синонимов в Английской и Русской Википедии с помощью адаптированного HITS алгоритма, (2) дано описание (с точки зрения пользователя) сессии поиска синонимов в программы Synarcher (реализующей адаптированный HITS алгоритм),

3) численно проверена польза предложенных поисковых эвристик,

4) проведены эксперименты по построению индексных баз данных вики-текстов, (5) получено подтверждение выполнения закона Ципфа для текстов двух Википедий.

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

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

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

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

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

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

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

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

1 Методика построения индексной http7/ni.wikipedia.org/wiki/BHKnneanfl-4acTOTHbiH словник базы.

23.10.2006.

Закпючение

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

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

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

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

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

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

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

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

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

1. Александров В.В. Интеллект и компьютер. СПб.: «Анатолия», 2004. 285 с.

2. BN 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^.

6. Бек К. Экстремальное программирование. СПб.: Питер, 2002. 224 с. - ISBN5.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. Браславский П.И., Соколов Е.А. Автоматическое извлечение терминологии с использованием поисковых машин Интернета // Компьютерная лингвистика и интеллектуальные технологии. Труды международной конференции

11. Диалог 2007». Бекасово, 2007. С. 89-94. http://www.dialog-21.ru/dialog2007/ materi als/pdf/14 .pdf

12. Брукс Ф. Мифический человеко-месяц или как создаются программные системы: Пер. с англ. СПб.: Символ-Плюс., 1999. 304 с. - ISBN 5-93286-005-7.

13. Вайсфельд М. Объектно-ориентированный подход: Java, .Net, С++. Второе издание / Пер. с англ. М.: КУДИЦ-ОБРАЗ, 2005. 336 с. - ISBN 5-9579-0045-1, 0-672-32611-6.

14. Вахитова Д. Создание корпуса текстов по корпусной лингвистике. 2006. http://matling.spb.ru/files/kurs/VahitovaCorpus.doc

15. Вишняков Р.Ю. Интеллектуальные информационно-поисковые системы. Лингвистический анализ // Перспективные информационные технологии и интеллектуальные системы. — 2006. — Т.4 (28). — С. 37-42. http://pitis.tsure.ru/files28/05.pdf

16. Выготский JI.C. Мышление и речь. Общая психология. Тексты. Раздел 3. Вып. 1. Познавательные процессы: виды и развитие. Часть 2 / Под общей редакцией Петухова В.В. М., 1997. С. 87.

17. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. Санкт-Петербург, Питер, 2000. 384 с. - ISBN 5-272-00071-4.

18. Голуб И.Б. Стилистика русского языка. Учеб. пособие, 2002. http://www.hi-edu.ru/x-books/xbook028/01/

19. Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. М.: Наука. Физматлит, 1999. 544 с. - ISBN 5-02-015238-2.

20. Грин Д., Кнут Д. Математические методы анализа алгоритмов: Пер. с англ. М.: Мир, 1987. 120 е. http://www.proklondike.com/file/CompScience/GrinKnut-MatMetodivanalizealgoritmov.rar

21. Гулин А., Маслов М., Сегалович И. Алгоритм текстового ранжирования Яндекса на РОМИП-2006 // Труды РОМИП'2006, октябрь, 2006 . http://download.yandex.ru/company/03yandex.pdf

22. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи: Пер. с англ. М.: Мир, 1982. 416 е.

23. Даль В.И. Толковый словарь живого, великорусского языка. М., 1955. Т. 1.

24. Дунаев С. Java для Internet в Windows и Linux. М.: ДИАЛОГ-МИФИ, 2004. -496 с.-ISBN 5-86404-188-2.

25. Дюбуа П. MySQL, 3-е изд.: Пер. с англ. М.: Издательский дом "Вильяме", 2007. 1168 с. - ISBN 5-8459-1119-2.

26. Жуков В.П., Сидоренко М.И., Шкляров В.Т. Словарь фразеологических синонимов русского языка: Около 730 синоним. рядов/Под ред. В.П. Жукова. М.: Рус. яз., 1987.-448 с. ISBN 5-17-027498-Х.

27. Зыков А.А. Основы теории графов. М.: Наука. Гл. ред. физ.-мат. лит., 1987. -384 с. ISBN 5-9502-0057-8.

28. Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие. М.: Лаборатория Базовых Знаний, 2003. 288 с. - ISBN 5-93208-093-0.

29. Искусственный интеллект. в 3-х кн. Кн. 2. Модели и методы: Справочник / Под ред. Д. А. Поспелова. М.: Радио и связь, 1990. - 304 с.

30. КожуноваО.С. Применение правдоподобных рассуждений дсм-метода для пополнения- семантического словаря // Компьютерная лингвистика и интеллектуальные технологии. Труды международной конференции «Диалог 2006». Бекасово, 2006. С. 243-247.

31. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. 960 с.5-900916-37-5.

32. Крижановский А. А. Вопросы реализации проблемно-ориентированных агентов интеграции знаний // Труды СПИИРАН / Под ред. Р:М. Юсупова вып. 1, Т.З СПб.: СПИИРАН, 2002. - С. 31-40. http://whingerinarod.ru/paper/index.html

33. Крижановский А А. Автоматизированное построение списков-семантически близких слов на основе рейтинга текстов в корпусе с гиперссылками и категориями // Компьютерная лингвистика и интеллектуальные технологии.

34. Труды международной конференции «Диалог 2006». Бекасово, 2006. — С. 297-302. http://arxiv.org/abs/cs.IR/0606128

35. Крижановский А.А. Оценка результатов поиска семантически близких слов в Википедии: Information Content и адаптированный HITS алгоритм // Вики-конференция 2007. Тезисы докладов. Санкт-Петербург, 2007 . http://arxiv.org/ abs/0710.0169

36. Крижановский А.А. Оценка результатов поиска семантически близких слов в Википедии // Труды СПИИРАН. Вып. 5. — СПб.: Наука, 2007 С. 113-116.

37. Крижановский А.А. Автоматизированный- поиск семантически, близких слов s на примере авиационной терминологии // Автоматизация в промышленности. — 2008. — Т.4 (64). — С. 16-20. http://whinger.narod.ru/paper/aviatermssearchbyAHlTS08.pdf

38. Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978. -215 c.http://nehudlit.ru/l/45/

39. Кулешов С.В. Разработка- автоматизированной системы семантического анализа и построения визуальных динамических глоссариев: Автореф. . дис. канд. техн. наук, СПб., 2005. - 20 с.

40. Леонтьева^ Н.Н. Автоматическое понимание текстов: системы, модели, ресурсы: учеб. пособие для студ. лингв, фак. вузов / Нина Николаевна Леонтьева. М.: Издательский центр "Академия", 2006. 304 с. - ISBN 5-7695-1842-1.

41. Макконнелл Дж. Основы современных алгоритмов. 2-е дополненное издание. М.: Техносфера, 2004: 368 с. - ISBN 5-94836-005-9.

42. Мандель И.Д. Кластерный анализ. М.: Финансы и статистика, 1988.- 176 с. -ISBN 5-279-00050-7.44.: Меликян X. Гйперсемантика. "дальше." Блокнот недовольного программиста. 2004. http://www.melikyan.com/dalshe/articles/hypersemantics.html.

43. Нечепуренко М.И., Попков В.К., Майнагашев С.М. и др. Алгоритмы и программы решения задач на графах и сетях. Новосибирск: Наука. Сиб. отд-ние, 1990.-515 с.-ISBN 5-02-028614-1.

44. Новиков Ф.А. Дискретная математика для программистов. Учебник для вузов. 2-е изд. СПб.: Питер, 2004. 364 с. - ISBN 5-94723-741-5.

45. Ножов И.М. Морфологическая и синтаксическая обработка текста (модели и программы): Дис. . канд. техн. наук. М., 2003. http://www.aot.ru/technology.html

46. Полонников Р.И. Основные концепции общей теории информации. СПб.: Наука, 2006. 203 с. - ISBN 5-02-025082-1.

47. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989.-478 с. ISBN 5-03-001041-6.

48. Репьев А.П. По-ВААЛ-яем дурака, господа! 2007. http://www.repiev.ru/articles/VAAL.htm

49. Сегалович И.В. Как работают поисковые системы, http ://www.dialog-21 .ru/trends/?id= 15539&f=l

50. Семенов Ю.А. Современные поисковые системы. 2006. http://book.itep.ru/4/45/retr4514.htm

51. Семикин В.А. Семантическая модель контента образовательных электронных изданий : Автореф. . канд. техн. наук: 05.13.18. — Тюмень, 2004. — 21 с. http://orel3.rsl.ru/dissert/Semikin.pdf

52. Сичинава Д.В. К задаче создания корпусов русского языка в Интернете, 2001. http://corpora.narod.ru/article.html

53. Словарь синонимов русского языка: В 2 т. / АН СССР, Институт русского языка; Под ред. А. П. Евгеньевой. Л.: Наука, Ленинградское отделение, 1970.

54. Смирнов А.В., Пашкин М.П., Шилов Н.Г., Крижановский А.А. Реализация взаимодействия агентов в системе логистики знаний «Интеграция» // Информатизация и связь. 2003. - № 1-2. - С. 74-78.

55. Сокирко А.В. Семантические словари в автоматической обработке текста (по материалам системы ДИАЛИНГ): Дис. . канд. техн. наук. — М., 2001. http://www.aot.ru

56. Сокирко А.В. Морфологические модули на сайте www.aot.ru // Компьютерная- лингвистика и интеллектуальные технологии. Труды международной конференции «Диалог 2004». «Верхневолжский», 2004. С. 559-564. http://www.aot.ru/docs/sokirko/Dialog2004.htm

57. Торвальдс Л., Даймонд Д. Ради удовольствия. М.: Изд-во ЭКСМО-Пресс, 2002. 288 с. - ISBN 5-04-009285-7.

58. Фридл Дж. Регулярные выражения. Библиотека программиста. СПб.: Питер, 2001. 352 с. - ISBN 5-272-00331-4.

59. Чупановская М. Н. Репрезентация противоположности в семантике производных антонимов (на материале словарей русского языка) : Автореф. канд. филол. наук: 10.02.01. —Новосибирск, 2007. — 21 с. http:// dissovet.nsu.ru/node/67

60. Шемакин Ю.И. Начала компьютерной лингвистики: Учеб. пособие. М.: Иэд-во МГОУ, А/О "Росвузнаука", 1992. 81 е.- ISBN 5-7045-0132-Х. http://sysen.rags.ru

61. Шемакин Ю.И. Семантика самоорганизующихся систем. М.: Академический Проект, 2003. 176 с. - ISBN 5-8291-0168-8. http://sysen.rags.ru

62. Шилдт Г. Java 2, v5.0 (Tiger) . Новые возможности: Пер. с англ. СПб.: БХВ-Петербург, 2005.-208 с. ISBN 5-94157-643-9, 0-07-225854-3.

63. Albert R., Barabasi A.-L. Statistical mechanics of complex networks. Reviews of Modern Physics, 2002. - Vol. 74, No. 47. http://arxiv.org/abs/cond-mat/0106096

64. Aleman-Meza В., Halaschek C., Arpinar I.B., Ramakrishnan C., Sheth A. Ranking complex relationships on the Semantic Web. IEEE Internet Computing, 2005. -Vol. 9, No. 3, pp. 37-44. http://lsdis.cs.uga.edu/libraiy/download/AHARS05-Ranking-IC.pdf

65. Andrews P., Rajman M. Thematic annotation: extracting concepts out of documents. 2004. http://arxiv.org/abs/cs/0412117

66. Avrachenkov K., Litvak N., Son Pham K. Distribution of PageRank mass among principle components of the Web. 2007. http://arxiv.org/abs/0709.2016

67. Bar-Ilan J., Mat-Hassan M., Levene M. Methods for comparing rankings of search engine results. 2005. http://arxiv.org/abs/cs/0505039

68. Batagelj V., Mrvar A. Analysis of large networks with Pajek. In Pajek workshop at XXVI Sunbelt Conference^ ancouver, ВС, Canada, 25-30 April, 2006. http://vlado.fmf.uni-lj.si/pub/networks/Doc/Sunbelt/sunbeltXXVI.pdf

69. Bayardo R., Ma Y., Srikant R. Scaling up all pairs similarity search. In Proc. of the 16thlnt'l Conf. on the World Wide Web, 2007. http://labs.google.com/papers.html

70. Bellomi F., Bonato R. Network analysis for Wikipedia. Wikimania 2005. http://www.fran.it/blog/2005/08/network-analisis-for-wikipedia.html

71. Biber D., Conrad S., Reppen R. Corpus • linguistics: investigating language structure and use (Cambridge approaches to linguistics). Cambridge university press, 2002. - 300 pp. - ISBN 0-521-499577.

72. Blondel V., Senellart P. Automatic extraction of synonyms in a dictionary. In Proceedings of the SIAM Workshop on Text Mining. Arlington (Texas, USA), 2002. http://www.inma.ucl.ac.be/~blondel/publications/areas.html

73. Brin S., Page L. The anatomy of a large-scale hypertextual Web search engine. 1998. http://www-db.stanford.edu/~backrub/google.html

74. Cabezas C., Resnik P. Using WSD techniques for lexical selection in statistical machine translation. Technical report CS-TR-4736/LAMP-TR-124/UMIACS-TR-2005-42, July 2005. ' http://lampsrv01.umiacs.umd.edu/pubs/TechReports/LAMP124/LAMP124.pdf

75. Calderan M. Semantic Similarity Library, Technical Report #DIT-06-036, University of Trento, 2006. http://www.dit.unitn.it/~accord/Publications/Semantic %20Similarity%20Library%20Thesis%20Proposal.pdf

76. Campbell S., Chancelier J.-P., Nikoukhah R. Modeling and Simulation in Scilab/Scicos. Springer, 2006. - 313 pp. - ISBN 978-0-387-27802-5.

77. Cunningham H., MaynardD., BontchevaK., TablanV., UrsuC., DimitrovM., Dowman M., Aswani N., Roberts I. Developing language processing components with GATE (user's guide), Technical report, University of Sheffield, U.K., 2005. http://www. gate, ac. uk

78. DengY. The Metadata Architecture for Data Management in Web-based Choropleth Maps. 2002. http://www.cs.umd.edu/hcil/census/JavaProto/metadata.pdf

79. Ding G., Wang В., Bai S. Robust track: using queiy expansion and rankfusion to improve effectiveness and robustness of ad hoc information retrieval. 2005. http://trec.nist.gov/pubs/trecl4/tl4proceedings.html

80. Dorogovtsev S. N., Goltsev A. V., Mendes J. F. F. Critical phenomena in complex networks. 2007. http://arxiv.org/abs/0705.0010

81. Doshi P., Thomas C. Inexact Matching of Ontology Graphs Using Expectation-Maximization. In Proceedings of AAAI, Special track on AI and the Web, 2006. http://cs.uga.edu/~pdoshi/

82. Efimenko I.V., Khoroshevsky V.F., Klintsov V.P. Ontosminer family: multilingual IE systems. In 9-th International Conference "Speech and Computer" SPECOM'2004. Russia, St. Petersburg, September 20-22, 2004. pp. 716-720

83. Fellbaum C. WordNet: an electronic lexical database. MIT Press, Cambridge, Massachusetts, 1998. - 423 pp. - ISBN 0-262-06197-X.

84. Fortunato S., Boguna M., Flammini A., Menczer F. How to make the top ten: Approximating PageRank from in-degree. 2005. http://arxiv.org/abs/cs/0511016

85. Gayo-Avello D. Building Chinese lexicons from scratch by unsupervised short document self-segmentation. 2004. http://arxiv.org/abs/cs/0411074

86. Gentner D. Structure-mapping: A theoretical framework for analogy. — Cognitive . Science, 1983. — Vol. 7, No. 1, pp. 155-170.http://www.psych.northwestern.edu/psych/people/faculty/gentner/allpubs.htm

87. Geraci E., Pellegrini M: Dynamic, user-defined similarity searching in. semi-structured text retrieval. 2007. http://arxiv.org/abs/0705.4606

88. Gruber T. R. A translation approach to portable ontologies. Knowledge Acquisition, . 1993. - Vol. 5, No; .2, pp. 199-220. http://tomgruber.org/writing/ontolingua-kaj-1993.htm

89. Guy M., Tonkin E. Tidying up taggs?. D-Lib Magazine, 2006. - Vol. 12, No. 1.

90. Hamon Т., Nazarenko A., Poibeau Т., Aubin S;, Deriviere J: A robust linguistic, platform for efficient and domain specific web content analysis. In Proceedings of RIAO, 2007. http://arxiv.org/abs/0706.4375

91. Hearst M., Karadi С. Cat-a-Cone: an interactive interface for specifying searches and viewing retrieval results using a large category hierarchy. In Proc. of ACM SIGIR, 1997. pp. 246-255

92. Hillman D. Using Dublin Core. 2006. http://dublincore.org/documents/usageguide/

93. HollowayT., BozicevicM., BornerK. Analyzing and visualizing the semantic Coverage of Wikipedia and its Authors. 2005. http://arxiv.org/abs/cs/0512085

94. Horstmann C. S., Cornell G. Core Java™ 2 volume I fundamentals, Seventh Edition. - Prentice Hall PTR, 2004. - 784 pp. - ISBN 0-13-148202-5. http ://horstmann. com/corej ava.html

95. Iria J., Ciravegna F. Relation Extraction for Mining the Semantic Web. In Proceedings of the Dagstuhl Seminar on Machine Learning for the Semantic Web. Dagstuhl, Germany, February 13-18, 2005. http://tyne.shef.ac.uk/t-rex

96. Jarmasz M, Szpakowicz S. Roget's Thesaurus and semantic similarity. In Proceedings of Conference on Recent Advances in Natural Language Processing (RANLP 2003). Borovets, Bulgaria, September, 2003. pp. 212-219 http ://www.nzdl. org/ELKB/

97. Jasper R., Uschold M. A framework for understanding and classifying ontology applications. In Twelfth Workshop on Knowledge Acquisition Modeling and Management KAW'99, 1999. http://sem.ucalgaiy.ca/KSI/KAW/KAW99/papers/Uschold2/final-ont-apn-fmk.pdf

98. Jiang J. J., Conrath D. W. Semantic similarity based on corpus statistics and lexical taxonomy. In Proceedings of International Conference Research on Computational Linguistics (ROCLING X). Taiwan, 1997. http://xxx.lanl.gov/abs/cmp-lg/9709008

99. Karov Y., Edelman S. Learning similarity-based word sense disambiguation from sparse data. To appear in the Fourth Workshop on Very Large Corpora, 1996, Copenhagen, http://xxx.lanl.gov/abs/cmp-lg/9605009

100. Karypis G., Han E.-H., Kumar V. Chameleon: a hierarchical clustering algorithm using dynamic modeling. IEEE Computer: Special Issue on Data Analysis and

101. Mining, 1999. Vol. 32, No. 8. http://www-users.cs.umn.edu/~kaiypis/publications/Papers/PDF/chameleon.pdf

102. Kleinberg J. Authoritative sources in a hyperlinked environment. — Journal of the ACM, 1999. Vol. 5, No. 46, pp. 604-632. http://www.cs.cornell.edu/home/kleinber

103. Krizhanovsky A. Synonym search in Wikipedia: Synarcher. In 11-th International Conference "Speech and Computer" SPECOM'2006.' Russia, St. Petersburg, June 25-29, 2006. pp. 474-477 http://arxiv.org/abs/cs/0606097

104. Kroski E. The Hive Mind: Folksonomies and User-Based Tagging. 2006. http://infotangle.blogsome.eom/2005/12/07/the-hive-mind-folksonomies-and-user-based-tagging

105. Lin D. An information-theoretic definition of similarity. In Proceedings of International Conference on Machine Learning, Madison, Wisconsin, July, 1998. http ://www. cs. ualberta. ca/~lindek/papers.htm

106. Maguitman A. G., Menczer F., Roinestad H., Vespignani A. Algorithmic Detection of Semantic Similarity. 2005. http://www2005.org/cdrom/contents.htm'

107. Mahadevan P., Krioukov D., Fall K., Vahdat A. A basis for systematic analysis of network topologies. 2006. http://arxiv.org/abs/cs/0605007

108. Manning C. D., Schutze H. Foundations of Statistical Natural Language Processing. The MIT Press, 1999. - 620 pp. - ISBN 0262133601. http ://nlp. Stanford, edu/ fsnlp/

109. Melnik S., Garcia-Molina H., Rahm E. Similarity flooding: a Versatile graph matching algorithm and its application to schema matching. In 18th ICDE. San Jose CA, 2002. http://research.microsoft.com/~melnik/publications.html

110. Meyer C.F. English corpus linguistics: An introduction. — Cambridge: Cambridge University Press, 2004. 168 pp. - ISBN 0-521-00490-X.

111. Milne D. Computing Semantic Relatedness using Wikipedia Link Structure. // New Zealand Computer Science Research Student Conference (NZCSRSC'2007). Hamilton, New Zealand. http://www.cs.waikato.ac.nz/~dnk2/publications/nzcsrsc07.pdf

112. Mizzaro S., Robertson S. HITS hits TREC exploring IR evaluation results with network analysis. In SIGIR 2007. ACM, 2007. - pp. 479-486 http://www.soi.city.ac.uk/~ser/papers/MizzaroRobertsonSIGIR07.pdf

113. Muller C., Meuthrath В., Baumgrass A. Analyzing wiki-based networks to improve knowledge processes in organizations. Journal of Universal Computer

114. Science, 2008. Vol. 14, No. 4, pp. 526-545. http://www.jucs.org/jucs144/analyzingwikibasednetworks

115. Newman M. E. J. The structure and function of complex networks. 2003. http://arxiv.org/abs/cond-mat/0303516

116. North Carolina ECHO (Exploring Cultural Heritage Online: Guidelines for Digitization). Ed.: К. M. Wisser, 2006. http://www.ncecho.org/Guide/metadata.htm

117. O'Madadhain J., Fisher D., Smyth P., White S., Boey Y.-B. Analysis and visualization of network data using JUNG (preprint). — Journal of Statistical Software, pp. 1-35. 2007. http://jung.sourceforge.net/doc/JUNGJournal.pdf

118. Pantel P., Lin D. Word-for-word glossing with contextually similar words. In Proceedings of ANLP-NAACL 2000. Seattle, Washington, May, 2000. pp. 75-85 http://www.cs.ualberta.ca/~lindek/papers.htm

119. Pedersen T. Computational approaches to measuring the similarity of short contexts: a review of applications and methods. — South Asian Language Review (to appear), 2008. Vol. 1, No. 1. http://arxiv.org/abs/0806.3787

120. Pedersen Т., Pakhomov S., Patwardhan S., Chute C. Measures of semantic similarity and relatedness in the biomedical domain. Journal of Biomedical Informatics, 2007. - Vol. 40, No. 3, pp. 288-299. http://www.d.umn.edu/~tpederse/ Pubs/jbi2007.pdf

121. Ponzetto S., Strube M. Exploiting semantic role labeling, WordNet and Wikipedia for coreference resolution. In Proceedings of the Human Language

122. Technology Conference of the North American Chapter or the Associaton for Computational Linguistics (HLT-NAACL 06). New York City, N.Y., June 4-9, 2006. pp. 192-199 http://www.emlresearch.de/english/research/nlp/publications.php

123. Resnik P. Disambiguating noun groupings with respect to WordNet senses. In Proceedings of the 3rd Workshop on Very Large Corpora. MIT, June, 1995. http:// xxx.lanl.gov/abs/cmp-lg/9511006

124. Resnik P., Yarowsky D. Distinguishing systems and distinguishing senses: new evaluation methods for word sense disambiguation. — Natural Language Engineering, 2000. Vol. 5, No. 2, pp. 113-133. http://www.cs.jhu.edu/~yarowsky/pubs.html

125. Robertson S. Understanding inverse document frequency: on theoretical arguments for IDF. Journal of Documentation, 2004. - Vol. 60, No. , pp. 503-520. http://www.soi.city.ac.uk/~ser/idfpapers/RobertsonidfJDoc.pdf

126. Robertson S., Zaragoza H. On rank-based effectiveness measures and optimization. Information Retrieval, 2007. - Vol. 10, No. , pp. 321-339. http://www.soi.city.ac.uk/~ser/papers/newoptimisationfinal.pdf

127. Rosenzweig R. Can history be open source? Wikipedia and the future of the past. The Journal of American History, 2006. - Vol. 93, No. 1, pp. 17-46. http://chnm.gmu.edU/resources/essays/d/42

128. Ruiz-Casado M., Alfonseca E., Castells P. Automatic assignment of Wikipedia encyclopedic entries to WordNet synsets. 2005. http://arantxa.ii.uam.es/~castells/publications/awic05.pdf

129. Sahami M., Heilman Т. D. A web-based kernel function for measuring the similarity of short text snippets. In Proceedings of the 15th International World Wide Web Conference (WWW), 2006. http://robotics.stanford.edu/users/sahami/papers-dir/www2006.pdf

130. Schmitz C., Hotho A., Jaschke R., Stumme G. Mining association rules in folksonomies. In Proc. IFCS 2006 Conference. Ljubljana, July, 2006. pp.261.270 http://www.kde.cs.unikassel.de/hotho/pub/2006/schmitz2006assoifcs.pdf

131. Schone P. Toward knowledge-free induction of machine-readable dictionaries. Ph.D., University of Colorado at Boulder, 2001. http://hometown.aol.com/boisebound/family/publications/DPFV.pdf.gz

132. Serrano M.A., Maguitman A., Boguna M., Fortunato S., Vespignani A. Decoding the structure of the WWW: facts versus sampling biases. 2006. http://arxiv.org/abs/ cs/0511035

133. Shi Z., Gu В., Popowich F., Sarkar A. Synonym-based expansion and boosting-based re-ranking: a two-phase approach for genomic information retrieval. Simon Fraser University, 2005. http://trec.nist.gov/pubs/trecl4/tl4proceedings.html

134. Shvaiko P., Euzenat J. A Survey of schema-based matching approaches. Journal on Data Semantics, 2005. http://www.ontologymatching.org

135. Sima J., Schaeffer S.E. On the NP-completeness of some graph cluster measures. 2005. http://arxiv.org/abs/cs/0506100

136. SmirnovA., PashkinM., ChilovN., LevashovaT., Krizhanovsky A. High-level business intelligence service in networked organizations. In Abstracts of eBusiness Research Forum eBRF 2003. Tampere, Finland, 2003. — pp. 37-39

137. SmirnovA., PashkinM., ChilovN., LevashovaT., Krizhanovsky A. Free text user request processing in the system "KSNet". In Proceedings of the 9th International Conference "Speech and Computer". St.Petersburg, Russia, 2004. — pp. 662-665

138. Survey of text mining: clustering, classification, and retrieval, M. Berry (Ed.). -Springer-Verlag, New York, 2003. 244 pp. - ISBN 0-387-955631.

139. Teich E., Fankhauser P. WordNet for lexical cohesion analysis. In Proceedings of the Second Global WordNet Conference. Brno, Czech Republic, January 20-23, 2004. pp. 326-331 http://www.fi.muni.cz/gwc2004/proc/77.pdf

140. Thom J. A., Pehcevski J., Vercoustre A.-M. Use of Wikipedia categories in entity ranking. In 12th Australasian Document Computing Symposium (ADCS'07'), 2007. http://arxiv.org/abs/0711.2917

141. Turney P.D. Mining the Web for synonyms: PMI-IR versus LSA on TOEFL. In Proceedings of the Twelfth European Conference on Machine Learning (ECML-2001). Freiburg, Germany, 2001. pp. 491-502 http://arxiv.org/abs/cs.LG/ 0212033

142. Turney P.D. Similarity of semantic relations. Computational Linguistics, 2006. -Vol. 32, No. 3, pp. 379-416. http://arxiv.org/abs/cs/0608100

143. Uschold M., Gruninger M. Ontologies: principles, methods, and applications. -Knowledge Engineering Review, 1996. Vol. 11, No. 2, pp. 93-155. http://citeseer.ist.psu.edu/uschold96ontologie.html

144. Vercoustre A.-M., Thom J. A-., Pehcevski J. Entity ranking in Wikipedia. In Proceedings of the 23rd Annual ACM Symposium on Applied Computing (SAC08), 2008. http://arxiv.org/abs/0711.3128

145. Voss J. Collaborative thesaurus tagging the wikipedia way. Collaborative Web Tagging Workshop. 2006. http://arxiv.org/abs/cs/0604036

146. Widdows D. and Dorow B. A graph model for unsupervised lexical acquisition. In 19th International Conference on Computational Linguistics.Taipei, 2002. — pp. 1093-1099 http://infomap.stanford.edu/graphs/

147. Wu Z., Palmer M. Verb semantics and lexical selection. In Proc. of ACL-94, 1994.-pp. 133-138 http://acl.ldc.upenn.edU/P/P94/P94-1019.pdf

148. Yarowsky D. Unsupervised word sense disambiguation rivaling supervised methods. In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics. Cambridge, MA, 1995. pp. 189-196 http ://www.cs .j hu.edu/~y arowsky/pubs .html

149. Zaidman A., Rompaey В., Demeyer S., Deursen A. On how developers test open source software systems. 2007. http://arxiv.org/abs/0705.3616

150. Zhdanova A., Shvaiko P. Community-driven ontology matching. In Proceedings of ESWC'06, LNCS 4011, 2006. pp. 34-49 http://dit.unitn.it/~knowdive/index.php?idx=pubs