Разработка моделей и алгоритмов для комплекса автоматической обработки и анализа потоков новостных сообщений на основе методов компьютерной лингвистики тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат наук Казенников, Антон Олегович

• Казенников, Антон Олегович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Казенников, Антон Олегович

Содержание

Глоссарий

Введение

Глава 1. Аналитический обзор современных методов автоматического анализа потоков текстовых сообщений. Постановка задачи

1.1 Современные методы информационного поиска

1.1.1 Метод информационного поиска на основе булевой алгебры

1.1.2 Оценка веса терминов в документе

1.1.3 Оценка схожести документов

1.2 Современные методы анализа потоков новостных сообщений

1.2.1 Современные средства представления и доставки потоков новостных сообщений в сети Интернет

1.2.2 Методы кластеризации потоков новостных сообщений

1.3 Лингвистические методы анализа текста

1.3.1 Методы синтаксического анализа основе экспертных знаний

1.3.2 Представление информации о языке на основе размеченных корпусов текстов

1.4 Методы синтаксического анализа на основе машинного обучения

1.4.1 Синтаксический анализ предложения с использованием алгоритма максимальных остовных деревьев

1.4.2 Метод синтаксического анализа предложения на основе системы переходов

1.5 Постановка задачи диссертационного исследования

Глава 2. Разработка гибридного алгоритма синтаксического анализа

2.1 Алгоритм снятия морфологической омонимии для русского языка

2.2 Модификация алгоритма Ковингтона для задачи анализа потоков новостных сообщений

2.3 Дополнение модифицированного алгоритма Ковингтона априорной информацией, извлеченной из системы ЭТАП-3

2.4 Уточненная математическая модель признаков для синтаксического анализа русского языка

2.5 Краткие выводы

Глава 3. Разработка функциональной структуры комплекса и алгоритмов анализа потоков новостных сообщений

3.1 Математическая модель многоуровнего представления документа

3.2 Алгоритм кластеризации потоков новостных сообщений на модели признаков на

основе обобщенной векторной модели документа

3.3 Базовые уровни представления новостного сообщения

3.4 Дополнительные уровни представления новостного сообщения на основе лингвистического анализа

3.5 Функциональная структура комплекса обработки новостных сообщений

3.5.1 Модуль первичного сбора и предварительной обработки новостей

3.5.2. Модуль индексирования

3.5.3 Модуль синтаксического анализа

3.5.4 Модуль кластеризации новостных сообщений

3.6 Краткие выводы

Глава 4. Экспериментальное исследование качества кластеризации потоков новостных сообщений и основных параметров синтаксического анализа

4.1 Задачи экспериментального исследования

4.2 Оценка качества снятия морфологической омонимии

4.3 Метрики оценки качества синтаксического анализа

4.4 Построение экспериментального корпуса новостных сообщений

4.5 Метрики оценки качества кластеризации новостных сообщений

4.6 Оценка качества кластеризации новостных сообщений

4.7 Оценка влияния различных уровней представления на точность и полноту кластеризации новостных сообщений

4.8 Экспериментальное определение зависимости точности и полноты

кластеризации потоков новостных сообщений от точности синтаксического анализа

4.9 Вклад синтаксических групп в качество кластеризации новостных сообщений

4.10 Оценка влияния метрики расстояния именованных сущностей на качество

кластеризации

4.11 Оценка влияния алгоритма кластеризации на качество кластеризации

4.12 Краткие выводы

Заключение

Библиография

Приложение 1. Исходный код гибридного алгоритма синтаксического анализа

Приложение 2. Исходный код алгоритма кластеризации

Приложение 3. Акты внедрения

Глоссарий

АРХИТЕКТУРА ИНФОРМАЦИОННОЙ СИСТЕМЫ - концепция, определяющая модель, структуру, выполняемые функции и взаимосвязь компонентов информационной системы [1].

БАЗА ЗНАНИЙ - организованная совокупность знаний, представленная в форме, которая допускает автоматическое или автоматизированное использование этих знаний на основе реализации возможностей средств информационных технологий [2].

БИГРАММА — п-грамма, где п=2 (см, Ы-ГРАММА)

ВЕКТОРНАЯ МОДЕЛЬ ДОКУМЕНТА - в информационном поиске представление коллекции документов векторами из одного общего для всей коллекции векторного пространства [3].

ВТОРИЧНЫЕ ИНФОРМАЦИОННЫЕ РЕСУРСЫ - описания (например: уровень образования, тип материала, предмет, аннотация или ключевые слова) и адреса ресурсов, не расположенных на текущем портале, а доступных через Интернет на других порталах, сайтах по гиперссылкам [4] [5].

ГАРМОНИЗАЦИЯ КОНТЕНТА - систематизация и унификация в результате изменения состава, свойств и признаков составляющих контента

[4].

ГИПЕРССЫЛКА - часть гипертекстового документа, ссылающаяся на другой элемент (команда, текст, заголовок, примечание, изображение) в самом документе, на другой объект (файл, каталог, приложение), расположенный на локальном диске или в компьютерной сети, либо на элементы этого объекта [6].

ГРАММАТИКА ЗАВИСИМОСТЕЙ - формальная модель, разработанная в рамках структурного синтаксиса, представляющая строй предложения в виде иерархии компонентов, между которыми установлено отношение зависимости [7].

ГРАММЕМА - грамматическое значение, понимаемое как один из элементов грамматической категории; различные граммемы одной категории исключают друг друга и не могут быть выражены вместе [7]

ДАННЫЕ - качественные или количественные переменные, принадлежащие к набору элементов. Необработанные данные не были подвергнуты обработке или другим манипуляциям. В качестве абстрактного понятия данные лежат на самом нижнем уровне абстракции из которых далее проистекают информация и знания [8].

ИЗВЛЕЧЕНИЕ ИНФОРМАЦИИ - это задача автоматического извлечения (построения) структурированных данных из неструктурированных или слабоструктурированных машиночитаемых документов [9].

ИЗВЛЕЧЕНИЕ ИМЕНОВАННЫХ СУЩНОСТЕЙ — задача автоматического извлечения нормализованных имен собственных из неструктурированного текста. Извлечение персон, названий организаций и др. объектов.

ИМЕНОВАННАЯ СУЩНОСТЬ — объекты текста, обозначаемые с помощью имен собственных: персоны, организации, географические объекты и прочие объекты

ИНДЕКСИРОВАНИЕ - процесс добавления сведений (о сайте) роботом поисковой машины в базу данных, впоследствии использующуюся для (полнотекстового) поиска информации на проиндексированных сайтах.

ИНТЕРНЕТ - всемирная система объединённых компьютерных сетей для хранения и передачи информации. Часто упоминается как Всемирная сеть и Глобальная сеть, а также просто Сеть[2]. Построена на базе стека протоколов TCP/IP.

ИНФОРМАЦИОННО-ПОИСКОВАЯ СИСТЕМА - это система [10], обеспечивающая поиск и отбор необходимых данных в специальной базе с описаниями источников информации (индексе) на основе информационно-поискового языка и соответствующих правил поиска. Главной задачей

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

КЛАССИФИКАЦИЯ - система группировки объектов исследования или наблюдения в соответствии с их общими признаками

КЛАСТЕРИЗАЦИЯ - многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы [11] КЛАСТЕРНЫЙ АНАЛИЗ — см. кластеризация

КОМПЬЮТЕРНАЯ ЛИНГВИСТИКА - научное направление в области математического и компьютерного моделирования интеллектуальных процессов у человека и животных при создании систем искусственного интеллекта, которое ставит своей целью использование математических моделей для описания естественных языков [12].

КОРПУС ТЕКСТОВ - совокупность текстов, собранных в соответствии с определёнными принципами, размеченных по определённому стандарту [13]

КОРПУСНАЯ ЛИНГВИСТИКА - раздел языкознания, занимающийся разработкой, созданием и использованием текстовых (лингвистических) корпусов.

ЛЕКСЕМА - слово как абстрактная единица естественного языка. ЛЕММАТИЗАЦИЯ - процесс приведения словоформы к лемме — её нормальной (словарной) форме [14]

МАШИННОЕ ОБУЧЕНИЕ - обширный подраздел искусственного интеллекта, изучающий методы построения алгоритмов, способных обучаться [13]

МЕТАДАННЫЕ - Информация о содержащейся на веб-странице информации (создателе и т. п.). Пример: Имя автора правки в тексте. Этот

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

МЕТОД - систематизированная совокупность шагов, действий, которые необходимо предпринять, чтобы решить определённую задачу или достичь определённой цели [15]

МЕТОДИКА - определенная, усвоенная процедура или набор процедур для достижения некоторой специфической цели. Обычно этот термин употребляется с коннотацией, что эти процедуры требуют определенной квалификации, и владение ими отражает некоторый уровень опытности [15] [16].

МЕТОДОЛОГИЯ - учение о структуре, логической организации, методах и средствах деятельности; учение о принципах построения, формах и способах научного познания [15] [17]

МЕТРИКА - функция, определяющая расстояния в метрическом пространстве [3]

МОРФОЛОГИЧЕСКИЙ АНАЛИЗ — процесс определения морфологических признаков словоформы и ее лексемы [14]

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

ПЕРЕСТАНОВОЧНАЯ ФУНКЦИЯ — см. хеш-функция ПЕРТИНЕНТНОСТЬ (англ. pertinence, pertinency) - степень соответствия содержания документов информационной потребности пользователя

ПОЛНОТА — мера оценки для задач классификации, для заданного класса определяется как отношение числа корректно классифицированных

точек к общему числу точек, принадлежащему заданному классу [13]

СИНТАКСИЧЕСКИЙ АНАЛИЗ - процесс сопоставления линейной последовательности лексем (слов, токенов) естественного или формального языка с его формальной грамматикой [3]

СЛОВОФОРМА - слово в узком смысле, то есть обладающая признаками слова цепочка фонем, формально отличающаяся от другой

СНИЖЕНИЕ РАЗМЕРНОСТИ - процесс уменьшения размерности анализируемого множества данных до размера, оптимального с точки зрения решаемой задачи и используемой аналитической модели

СТЕММИНГ — процесс преобразования словоформы к ее основе ТОЧНОСТЬ — мера оценки для задач классификации, для заданного класса определяется как отношение корректно классифицированных точек этого класса к общему числу точек, отнесенных к заданному классу. [13] ТРИГРАММА — n-грамма, где п=3

ХЕШИРОВАНИЕ - преобразование по детерминированному алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины.

ЧАСТЬ РЕЧИ - категория слов языка, определяемая морфологическими и синтаксическими признаками

N-ГРАММА — кортеж из п последовательных элементов. В задаче автоматического анализа текстов обычно используются n-граммы из словоформ [3].

TEXT MINING — собирательное название, используемое для обозначения совокупности методов автоматического анализа текстов для извлечения структурированной информации [9]

TF-IDF - статистическая мера, используемая для оценки важности слова в контексте документа, являющегося частью коллекции документов или корпуса. Вес некоторого слова пропорционален количеству употребления этого слова в документе, и обратно пропорционален частоте употребления слова в других документах коллекции [3].

1188 - семейство ХМЬ-форматов, предназначенных для описания лент новостей, анонсов статей, изменений в блогах и т. п. Информация из различных источников, представленная в формате 1188, может быть собрана, обработана и представлена пользователю в удобном для него виде специальными программами [3]

Введение диссертации (часть автореферата) на тему «Разработка моделей и алгоритмов для комплекса автоматической обработки и анализа потоков новостных сообщений на основе методов компьютерной лингвистики»

Введение

За прошедшие десятилетия произошел взрывной рост количества доступных электронных лент новостей ведущих информационных агентств. В результате возникли серьезные затруднения как для чтения в изобилии поступающих новостных сообщений, так и для их анализа с целью принятия решений на основе полной доступной информации [18-20].

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

Существующие комплексы и системы, предназначенные для решения задач кластеризации новостных сообщений, имеют существенные ограничения. Представление новостного сообщения в таких системах и комплексах основано на «поверхностном» (shallow) представлении и анализе текста [3,13,22]. Это представление предполагает, что слова текста независимы друг от друга, а релевантность, или «важность» каждого слова определяется на основе некоторой семантической [23,24] метрики веса слова. В результате приведения слов к их нормальным формам или выполнения процедуры стемминга (англ., stemming, выделение основы слова) [25], образуется «мешок слов», который представляется в виде пар {термин, частота} над которым выполняются процедуры преобразования и кластеризации. При таком способе представления практически полностью теряется важная лингвистическая информация, которая могла бы существенно улучшить качество кластеризации [26,27]. В частности, не

совершенно не учитывается информация о порядке слов, теряются и синтаксические зависимости, на основе которых можно было бы извлечь информацию об основных объектах новостного сообщения. В результате, кластеризация на основе традиционного представления документа не учитывает ни структуру текста, ни присутствующие в тексте именованные сущности — имена персон, названия организаций, географические названия. Кроме того, метод на основе «мешка слов» не учитывает связи между этими сущностями в тексте [3]. Вместе с тем, несомненным достоинством «поверхностных» методов обработки текстов является их высокая скорость работы [28].

С другой стороны, за последние годы значительно усовершенствовались методы глубокого автоматического лингвистического анализа текстов на естественном языке [29,30,31]. Классический лингвистический подход к анализу текста предполагает существование относительно независимых уровней анализа; в том числе: морфологического, синтаксического и семантического. Кроме того, он предполагает определенную последовательность анализа, в начале -морфологического, затем синтаксического, и наконец, семантического.

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

Другим способом построения лингвистических анализаторов является подход на основе размеченных лингвистических «корпусов текстов». При использовании этого подхода производится обогащение массивов текстов на естественном языке соответствующей лингвистической информацией, например морфологической, синтаксической, разметкой именованных

сущностей. Разработка таких лингвистических ресурсов менее трудоемка, чем разработка модели языка [13].

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

Ряд авторитетных ученых и исследователей, таких как И.Е. Поляков, И.В. Соловьев, В.Я. Цветков, Г.С.Осипов, Д.В. Ландэ, Ю.Д. Апресян, И.А. Мельчук, И.В. Сегалович, И.М. Богуславский, Л.Л. Иомдин, Л.Л. Цинман, Н.И. Ножов, G.Salton, R. Barzilay, J. Nivre, S. Kubler, J. Allan, D. Cutting, J. Beringer своими работами внесли значительный вклад в развитие методов информационного поиска, методов классификации и кластеризации полнотекстовых документов, методов синтаксического анализа и извлечения знаний из текстов. Активно ведут работы в этих направлениях такие организации, как Институт системного анализа РАН, Институт Проблем Передачи Информации РАН, Центр Анализа Интернет Ресурсов, Яндекс, Microsoft, Google, Объединенный Институт Ядерных Исследований, Центр Высокопроизводительных Вычислительных Кластерных Технологий, Научно-Исследовательский Вычислительный Центр МГУ.

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

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

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

Для достижения этой цели диссертационного исследования необходимо решение следующих задач:

1. Разработка гибридного алгоритма синтаксического анализа, который сочетает преимущества метода экспертных знаний существующей системы ЭТАП-3 и методов синтаксического анализа, основанных на машинном обучении.

2. Разработка алгоритма снятия морфологической омонимии, необходимого для эффективной реализации гибридного алгоритма синтаксического анализа

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

4. Разработка математической модели многоуровнего представления новостного сообщения для задачи кластеризации.

5. Разработка алгоритма и программного обеспечения кластеризации потока новостных сообщений, который бы эффективно обрабатывал многоуровневое представление новостного сообщения.

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

7. Внедрение выводов и рекомендаций диссертации в практические разработки и учебный процесс МИРЭА.

Структура диссертации состоит из Введения, четырех глав основного текста, Заключения, Библиографии (135 наименований) и Зх Приложений. Общий объем работы — 155 страниц.

Глава 1. Аналитический обзор современных методов автоматического анализа потоков текстовых сообщений. Постановка задачи

1.1 Современные методы информационного поиска

Обработка потоков новостных сообщений рассматривается как задача информационного поиска и автоматической обработки текстов. Такой подход предполагает, что базовым объектом, над которым производятся все операции, является документ - законченный фрагмент текста. [33] Следовательно, представление документа определяет свойства решения на основе методов информационного поиска. В задаче анализа потока новостных сообщений документом является новостное сообщение.

Первые результаты в области информационного поиска были получены в конце 1940х годов [3]. Основной решаемой задачей был документальный поиск — выявление документов, релевантных пользовательскому запросу [34] . Изначально основным материалом для информационного поиска были библиотечные данные — аннотации книг и статей [35]. Ограниченное быстродействие и ресурсы памяти вычислительных систем того времени не позволяли анализировать большие массивы текстов [36]. В результате типичный документ того времени представлял собой краткое сообщение, например аннотации статей и т.п. По мере развития вычислительной техники значительно расширились возможности систем поиска [37]. Вместе с ростом объема обрабатываемой информации были разработаны более совершенные методы поиска и представления информации. К концу 70х - началу 80х годов сформировались основные модели и методы [38-41], на которых базируются современные информационно-поисковые системы.

В настоящее время классическим представлением документа является модель на основе «мешка слов» (bag of words, англ.). Основная гипотеза

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

1.1.1 Метод информационного поиска на основе булевой алгебры

Классическая модель информационного поиска основана на булевой алгебре [3, 43]. Модель предполагает, что документ представляется простым «мешком слов», а запрос — выражение булевой алгебры над отдельными терминами. При выполнении поискового запроса вначале происходит поиск всех документов, содержащих все термины запроса. Затем, каждый документ из целевого множества оценивается на соответствие полному выражению запроса. В результате пользователю возвращаются все документы, которые удовлетворяют заданному выражению булевой алгебры [44].

Кроме средств булевой алгебры в системах такого типа реализуется возможность использования элементарных позиционных параметров, например, предиката положения, который вводит максимальное расстояние терминов запроса в тексте. Например, по запросу «ключ */3 источник» такая система может найти все документы, где «ключ» и «источник» разделены не более чем тремя словами.

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

1.1.2 Оценка веса терминов в документе

После идентификации потенциально интересных документов информационно-поисковые системы производят их ранжирование в

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

В области информационного поиска сформировалось два основных метода ранжирования документов: с использованием векторной модели представления документа и с использованием вероятностной модели представления документа [40].

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

В работе [46] была представлена векторная модель документа, существенно расширяющая модель на основе понятия «мешка слов». В расширенной модели документ представляется вектором в пространстве термов. Пространство конструируется таким образом, чтобы каждый отдельный термин был ассоциирован с отдельной размерностью пространства. При этом, так же как и в модели на основе булевой алгебры предполагается, что термы независимы друг от друга. В результате пространство терминов становится ортогонально [47] и для ранжирования документов достаточно оценить подобие вектора документа и вектора запроса.

Для взвешивания терминов в документе наиболее часто используются следующие подходы.

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

документы различной длины. При этом больший вес будут получать более длинные документы, так как они содержат больше слов.

Второй подход использует скорректированную нормализованную частоту появления слова в документе [48] (TF-IDF). Нормализованная частота определяется как отношение числа вхождений слова к общему количеству слов документа. Для корректировки частоты вводится дополнительный множитель — обратная частота (idf) документов, содержащих слово:

idf, = log2 (-), (1.1)

где N — общее число документов в коллекции, a nt— число документов, в которых содержится терм t. Нормализованный вес wtd термина t в документе d определяется на основе следующей формулы:

Ща = tftd ■ Щф (1-2)

Здесь. tftd — количество вхождений терма t в документе D, idftd — обратная частота документа. При относительной простоте эта характеристика обеспечивает неплохое качество поиска [49]. Недостатком является то, что в данном случае, наоборот, недооцениваются длинные документы, так как в них больше слов и средняя частота слов в тексте ниже. Для устранения этого негативного эффекта применяется дополненная

нормализованная частота, которая вычисляется как 0,5 + 0,5 ^—где

avg(tf) — средняя частота термина в документе [50].

В работе [11] для уравновешивания размеров сравниваемых документов и предотвращает случаи деления на 0 предложено использовать сглаженный вариант для обратной частоты документа:

(N - ть + 0,5\ idf' = 4 nt + 0,5 )• С")

где N — общее число документов в коллекции, щ — число документов,

содержащих терм t.

Третий подход является модификацией подхода на основе частоты

появления слова в документе. Основное отличие этих подходов состоит в дополнительном логарифмировании результирующего веса. Тогда вес входящего в текст документа определяется как 1 + log{tf), где tf - частота термина. Многие статистические характеристики в лингвистике имеют логарифмический характер, что связано с особенностями человеческого восприятия [51]. В результате такой метод взвешивания более устойчив к возможной переоценке документов, где некоторое слово встречается слишком часто. Для компенсации эффекта разной длины документов используют нормализацию, аналогичную применяемой и для частоты. В

этом случае формула выглядит как 1+^g(max(tf)y где тах(Ф —

максимальная частота слова в документе.

1.1.3 Оценка схожести документов

Другой важной решаемой задачей информационного поиска является оценка схожести документов [52-54].

В работах [48] и [55] на основе вышеописанных подходов к оценке веса терминов в документе определяют меру подобия документов двух документов на основе косинусной метрики расстояния:

• f г\ г\ \ St^tdi ' wtd2 ..

sim(D1 D2) = 1 2 , (1.4)

где Ох и й2— сравниваемые документы. Эту меру можно использовать

без нормализации для облегчения вычислений:

г

5нп(Я1(Я2) = ^ (1.5)

¿=1

где /)2 — исходные документы, ? — количество термов для определения подобия.

В работах [55, 56] предлагается использовать оценки релевантности, построенные на основе теории вероятностей, при этом предполагается, что:

каждый документ либо релевантен запросу, либо нет; • релевантность двух документов взаимно независима.

Вероятность релевантности документа й запросу () определяется как /'(Лд = Предполагается, что X Е (ОД) в соответствии бинарным

характером релевантности. Мера подобия может выражаться как отношения вероятностей релевантности к нерелевантности документа:

Р(**<2 = Щ

P(Rq = 0| D)'

По правилу Байеса [13] это соотношение вычисляется как P(Rq = 1\D) P(Rq = 1)P(D\Rq = 1)

(1.6)

(1.7)

P(RQ = 0| D) P(RQ = 0)P(D\RQ = 0)'

P(Rq = l) — вероятность того, что случайно выбранный документ будет релевантен запросу.

Эта величина, так же как и P(Rq — О) является постоянной для заданной коллекции документов. Поэтому эти множители можно не учитывать.

P(D\Rq = l) — вероятность выбора документа из релевантных. Одним из способов оценки этой величины является рассмотрение термов запроса Q = ..., tm} и их распределений в документе и в коллекции.

Для вычисления веса терма можно использовать некоторую функцию частоты, с которой этот терм встречается в документе. В INQUERY [57] использовалась следующая функция определения веса терма:

'N + 0,5Ч

/ Ч^)

^ = " + (1 " Я)/ + 0,5 + КЬ ¿„N + 1 ■ (1Л)

/ — частота терма в коллекции, N — общее число документов в коллекции, К — коэффициент значимости длины документа, Ь — длина документа, а — константа, которая позволяет учитывать терм, даже если он не встречается в документе.

Итоговая вероятность того, что документ релевантен запросу

вычисляется как [58]:

P(D |KQ = l) = ^wt, (1.9)

tEQ

Несмотря на то, что в основной задаче информационного поиска для оценки релевантности рассматривается сопоставление пользовательского запроса и документа в системе, применение векторной модели и особенно взвешивания по TF-IDF в ряде задач используется как самостоятельный метод [59], например, для определения различающей силы терминов в рамках одного документа.

В литературе отмечены попытки [60-63] уйти от индексирования непосредственно термов к более общему представлению, называемому синсетами. Однако в [56, 64] показано, что эти дополнения слабо влияют на качество информационного поиска, а в отдельных случаях могут даже ухудшить его [65].

1.2 Современные методы анализа потоков новостных сообщений

Развитие методов обработки и анализа новостных потоков связано с проведением двух конференций: MUC [66] (Message understanding conference) и DUC [67] (Document underestanding conference) в DARPA в конце 1980x годов. Целью этих конференций была разработка новых эффективных методов анализа потоков сообщений, с помощью которых можно было бы извлекать важную содержательную информацию из текстовых документов. Так, основным вопросом, обсуждаемым на конференции MUC-3 [68] был вопрос извлечения информации о террористических атаках в Латинской Америке из обширной выборки новостных сообщений. Основным результатом этих конференций стала программа разработки методов извлечения информации TIPSTER, на основе которой были созданы промышленные системы текстовой аналитики. В частности была разработана платформа GATE [69] для

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

1.2.1 Современные средства представления и доставки потоков

новостных сообщений в сети Интернет

Основными причинами роста доступных потоков новостных сообщений стало появление и стандартизация средств доставки потоков новостных сообщений. В результате стало возможно получать новостные ленты информационных агентств в машинно-читаемом формате [70].

Наиболее используемыми в настоящее время являются протоколы и АТОМ, стандартизованные в КТС-5023 [71]. Данные протоколы описывают каналы новостных сообщений и имеют следующую структуру.

Канал состоит из следующих элементов:

• Заголовок канала;

• Ссылка на основной источник канала;

• Краткое содержание новостного канала;

• Время последнего обновления канала;

• Список новостных сообщений.

Новостное сообщение состоит из следующих структурных элементов:

• Заголовка новости;

• Краткого содержания новости;

• Гипертекстовой ссылки на полный текст новости;

• Времени создания новостного сообщения;

• Времени последнего обновления новостного сообщения;

• Уникального идентификатора новостного сообщения в пределах данного новостного канала.

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

сообщений из данного новостного канала.

Важной особенностью данного протокола представления потока новостных сообщений является то, что этот протокол основан на pull-технологии. Для получения обновлений необходимо запрашивать из канала новые новостные сообщения. Такой метод одновременно позволяет снизить нагрузку на источники новостных сообщений и в то же время позволяет оперативно получать новостные сообщения для их дальнейшего анализа.

Кроме эффективности использования формата новостных сообщений, важным вопросом является его распространенность. В [22] установлено, что данный формат поддерживается такими ведущими информационным агентствами как: Tompson-Reuters, AFP, Interfax, RIAN, Associated Press и другими. В [26] установлено, что этот протокол поддерживают и ведущие отечественные информационные агентства и новостные сайты: РИА Новости, Интерфакс, Прайм, РБК и др.

1.2.2 Методы кластеризации потоков новостных сообщений

Основным направлением обработки потоков текстовых сообщений, в частности новостей, стал поиск эффективных решений для задач определения и отслеживания развития сюжетов в потоке новостных сообщений (Topic Detection and Tracking) [72-74]. Задачей этих методов является определение сюжета, к которому относится каждое новостное сообщение [75,76].

Условия этих задач предполагают, что, если в реальном мире происходит какое-нибудь важное событие, то вначале появляется новость о том, что событие произошло. Затем, по мере появления подробностей, во входящем потоке новостей появляются уточняющие сообщения. Одной из сложностей задачи отслеживания развития сюжетов является эффект перетекания одного сюжета в другой. Например, при пожаре вначале появится сообщение о самом факте пожара, затем будут появляться

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

Результатом решения этих задач являются кластеры документов, описывающих развитие события.

Задача отслеживания развития сюжетов схожа с задачей кластеризацией текстов. Как и задача кластеризации текстов, в отличие от традиционных задач машинного обучения, задача кластеризации потоков новостных сообщений обладает высокой размерностью данных. Это связано с тем, что большинство методов кластеризации работает с данными, представленными в виде векторов в пространстве Rn [59]. Представление текстовых данных в таком пространстве обычно осуществляется с помощью процедуры сопоставления каждого признака с функцией-индикатором данного слова. Следовательно, общая размерность пространства задачи определяется общим количеством таких признаков. Поскольку в качестве признаков используются слова и их сочетания, то общая размерность пространства может достигать 1-10 млн [80]. При этом вектор признаков каждого отдельного сообщения «крайне разрежен» -лишь небольшое количество координат обладает ненулевыми значениями [81]. Классический подход кластеризации текстовых данных представлен во множестве источников. Наиболее подробно рассмотрены три вида алгоритмов: алгоритм к-средних [82], Scatter-Gather [83], BIRCH [84] и алгоритмы иерархической кластеризации [85]. Однако все эти алгоритмы не лишены существенных недостатков, при выявлении и практическом использовании в задаче анализа новостей [86].

Есть ряд существенных отличий от классической задачи кластеризации данных [87]. Во-первых, основные алгоритмы кластеризации работают на заранее фиксированном множестве данных [88] [89]. Поток новостных сообщений не является фиксированным по определению. Прямое использование этих алгоритмов кластеризации

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

Во-вторых, значительная часть алгоритмов кластеризации предполагает, что заранее известно число кластеров, на которые нужно разбить всю совокупность данных. Это предположение существует в алгоритмах к-теаш, к-тесЫс! и их оптимизированных версиях [82]. В случае задачи обработки новостных потоков неизвестно даже приблизительное число кластеров. Алгоритмы кросс-валидации [90], которые последовательно подбирают число кластеров, неприменимы, поскольку для их работы требуется большое время для подбора оптимального числа кластеров.

В-третьих, оптимизированные версии основных алгоритмов кластеризации ориентированы на низкую размерность данных. Их использование на массивах данных высокой размерности приводит к резкому росту времени обработки [91,92].

В-четвертых, для задачи обработки новостных потоков существуют жесткие временные рамки обработки каждой входящей новости. Задача минимум состоит в том, чтобы алгоритм кластеризации позволял в среднем анализировать до 20 тыс. новостных сообщений в сутки. При таких объемах данных, среднее время анализа одного сообщения не может превышать 4 секунд.

В ряде работ [93-95] для кластеризации предлагается линейный во времени алгоритм приблизительной кластеризации. Первоначально множество кластеров считается пустым. Для каждого нового сообщения выполняются следующие операции:

• Оцениваются расстояния от вектора нового сообщения до центров • всех кластеров.

• Если минимальное расстояние больше некоторого наперед заданного числа, то новое сообщение помещается в отдельный кластер.

• Если нет, то в один (или несколько ближайших).

Список литературы диссертационного исследования кандидат наук Казенников, Антон Олегович, 2014 год

Библиография

1. Информационная система // Глоссарий.ру. URL: http:// www.glossary.ru/cgi-bin/gl_sch2.cgi?RIt%28uwsg.outt:l!xoxyls: (дата обращения: 18.12.2013).

2. База знаний // Википедия. URL: http://ru.wikipedia.org/wiki/ База_знаний (дата обращения: 18.12.2013).

3. Manning С., Raghavan Р., and Schütze Н. , Introduction to Information Retrieval. Cambridge University Press, 2008.

4. Иванников А.Д., Тихонов A.H. Основные положения концепции создания системы образовательных порталов. Москва: Просвещение, 2003. 720 pp.

5. Кудж С.А., Соловьёв И.В., Цветков В .Я. Когнитивные модели и методы. Краткий словарь-справочник. М.: МГТУ МИРЭА, 2014. 88 с.

6. Соловьев И.В., Цветков В.Я., "О содержании и взаимосвязях

категорий «информация», «информационные ресурсы», «знания»," Дистанционное и виртуальное обучение, No. 6, 2011. pp. 11-21.

7. Ножов Н.И. Морфологическая и синтаксическая обработка текста (модели и программы). Диссертация. РГГУ, 2003.

8. Соловьев И.В., "Об информационном объекте и субъекте," Дистанционное и виртуальное обучение, No. 5, 2012. pp. 80-84.

9. Ландэ Д.В. Поиск знаний в Internet. Диалектика, 2005. 272 pp.

10. Соловьёв И.В., Майоров A.A. Проектирование информационных систем. Фундаментальный курс. М.: Академический проект, 2009. 398

pp.

11. Berry M.W. Survey of Text Mining: Clustering, Classification, and Retrieval. Springer, 2003.

12. Компьютерная лингвистика// Wikipedia. URL: http://ru.wikipedia.org/ wiki/Koмпьютepнaя_лингвиcтикa (дата обращения: 18.12.2013).

13. Jurafsky D., Martin M. Statistical Speech and Language Processing. Prentice Hall, 1999.

14. И.А. В. Введение в компьютерную лингвистику. Практические аспекты создания лингвистических процессоров. Москва: ВМиК МГУ, 2006. 44 pp.

15. Большой Энциклопедический Словарь. Санкт-Петербург: Норинт, 1999. 1456 pp.

16. Тихонов А.Н., Иванников А.Д., Цветков В.Я., "Терминологические отношения," Фундаментальные исследования, № 5, 2009. С. 146-148.

17. Монахов С.В., Савиных В.П., Цветков В.Я. Методология анализа и проектирования сложных информационных систем. Москва: Просвещение, 2005. 264 с.

18. Benson Е., Haghighi A., and Barzilay R. Event Discovery in Social Media Feeds // Proceedings of ACL. 2001. pp. 389-398.

19. Поляков А.А., Цветков В.Я. Информационные технологии в управлении. Москва: МГУ, 2007. 138 с.

20. Цветков В.Я. Модели в информационных технологиях. М.: Макс Пресс 2006, 2006. 104 pp.

21. Das A., Datar M., and Garg A. Google News Personalization: Scalable Online Collaborative Filtering // Proceedings of WWW 2007. 2007. pp. 271-280.

22. McKeown K., Barzilay R. Tracking and Summarizing News on a Daily Basis with Columbia's Newsblaster // Proceesings of HLT. 2005. pp. 280285.

23. Tsvetkov V.Y., "Semantic Information Units as L. Florodi's Ideas Development," European Researcher, No. 25,№ 7, 2012. pp. 1036-1041.

24. Цветков В.Я., "Семантика информационных единиц," Успехи современного естествознания, № 10, 2007. С. 103-104.

25. Porter M.F. An algorithm for suffix stripping // Readings in information retrieval. 1997. pp. 313-316.

26. Казенников А.О., "Анализ новостных потоков на основе информационного поиска и компьютерной лингвистики," Информатизация науки и образования, No. 4(16), 2012. pp. 155-164.

27. Luo G., Tang С., and Yu P. Resource-adaptive real-time new event detection // Proceedings of the 2007 ACM SIGMOD Conference. 2007. pp. 497-508.

28. Цветков В.Я., "Некоторые аспекты анализа текста," Современные наукоёмкие технологии, No. 6, 2008. pp. 84-85.

29. Nivre J. Algorithms for Deterministic Incremental Dependency Parsing // Computational Linguistics. 2008. Vol. 34. No. 4. pp. 513-553.

30. Nivre J. Incremental Non-Projective Dependency Parsing // Proceedings of Human Language Technologies: The Annual Conference of the North American Chapter of the Association for Computational Linguistics

(NAACL-HLT). 2007. pp. 396-403.

31. Nivre J., Hall J., and Kubler S. The CoNLL 2007 Shared Task on Dependency Parsing // Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007. 2007. pp. 915-932.

32. Apresyan Y., Boguslavsky I., and Iomdin L. ETAP-3 Linguistic Processor: a Full-Fledged NLP Implementation of the MTT // First International Conference on Meaning - Text Theory (MTT"2003). Москва. 2003. pp. 279-288.

33. Цветков В.Я. Системный анализ при обработке информации. Saarbrucken: LAP LAMBERT Academic Publishing GmbH & Co. KG, 2014. 82 pp.

34. Tsvetkov V.Y., "Information interaction," European Researcher, No. 62, № 11-1, 2013. pp. 2573- 2577.

35. Jahoda G. Electronic searching // In: The State of the Library Art. Graduate School of Library Service, 1961. pp. 139-320.

36. Mitchell F.H., "The Use of the Univ AC FAC-Tronic System in the Library Reference Field," American Documentation, Vol. 4, No. 1, 1953. pp. 16-17.

37. van Rijsbergen C.J. Information Retrieval. 2nd ed. London: Buttworth and Co, 1979.

38. Saltón G and Yang CS, "On the Specification of Term Values in Automatic Indexing," Department ofComputer Science, Cornell University, New-York, TR 73-173, 1973.

39. Saltón G., Wong A., and Yang C.S., "A vector space model for automatic indexing," Communications of the ACM, Vol. 18, No. 11, 1975. pp. 613-

40. Robertson S.E., "The probability ranking principle in IR," Journal of documentation, Vol. 33, No. 4, 1977. pp. 294-304.

41. Robertson S.E., Spärck Jones K., "Relevance weightingof search terms," Journal of the American Society for Information science, Vol. 27, No. 3, 1976. pp. 129-146.

42. Казенников А.О., Трифонов Н.И., and Тюрин А.Г. Исследование методов компьютерной лингвистики для задач повышения эффективности информационного поиска // Информатизация науки и образования. Москва. 2010. Vol. 3(7). pp. 10-20.

43. Казенников А.О., Трифонов Н.И., Панков A.B., "Информационно-поисковая система для исследования методов разрешения лексико-семантической омонимии," Научный вестник МИРЗА, № 2(7), 2009. С. 64-73.

44. Цветков В.Я. Логика в науке и методы доказательств. Saarbrücken: LAP LAMBERT Academic Publishing GmbH & Co. KG, 2012. 84 pp.

45. Казенников А.О., Трифонов Н.И., Панков A.B. Информационно-поисковая система для исследования методов разрешения лексико-семантической омонимии // Материалы III Всероссийской конференции студентов, аспирантов и молодых ученых "Искусственный интеллект: философия, методология, инновации". Москва. 2009. С. 12-15.

46. Salton G., Wong A., and С. Y., "A Vector Space Model for Automatic Indexing," Communications of the ACM, Vol. 18, No. 11, 1975. pp. 613620.

47. Казенников А.О. Разработка экспериментальной информационно-поисковой системы, использующей методы вычислительной лингвистики и машинного обучения // Сборник материалов всероссийского конкурса инновационных проектов аспирантов и студентов по приоритетному направлению: Информационно-телекоммуникационные системы. Москва. 2006. С. 93-94.

48. Salton G., Buckley С., "Term-Weighting Approaches in Automatic Text Retrieval," Journal of Information Process Management, Vol. 24, No. 5, 1988. pp. 513-523.

49. Croft W.B., Metzler D., and Strohman T. Search Engines: Information Retrieval in Practice. Addison-Wesley Publishing, 2009.

50. Губин M.В. Модели и методы представления текстового документа в системах информационного поиска. СПб: Диссертация СПбГУ, 2005.

51. Sidorov G..G.A. Zipf and heaps laws' coefficients dependend on language // In Proceedings of conference on Intelligent Text Processing and Computational Linguistics (CICLING). 2001. pp. 332-335.

52. Tsvetkov V.Y., "Complexity Index," European Journal of Technology and Design, No. 1, № 1, 2013. pp. 64-69.

53. Kudz S.A., Soloviev I.V., and Tsvetkov V.Y., "Spatial Knowledge Ontologies," World Applied Sciences Journal, No. 31(2), 2014. pp. 216221.

54. Tsvetkov V.Y., "Information Interaction as a Mechanism of Semantic Gap Elimination," European Researcher, No. 45,№ 4-1, 2013. pp. 782- 786.

55. van Rijsbergen C.J. Towards information logic // Proceedings of ACM International Conference of Research and Development in Information

Retrieval. 1989. No. 23. pp. 77-86.

56. Robertson J., Spark-Jones K. Simple Proven Approaches to Text Retrieval 1997.

57. Robertson S., Walker S., Jones S., Hancock-Beaulieu M., and M. G. Okapi at TREC-3 // Proceedings of the Third Text REtrieval Conference (TREC 1994). 1994.

58. Robertson S.E., "On Term Selection for Query Expansion," Journal of Documentation, Vol. 46, No. 4, 1990. pp. 359-364.

59. Feldman R., Sanger J. The Text Mining Handbok. Cambridge: Cambridge University Press, 2007.

60. Gonzalo J., Verdejo F., Chungur I., and Cigarran J. Indexing with Wordnet Synsents Can Improve Text Retrieval // Proceedings of the COLING/ACL 1998 Workshop. 1998.

61. Park S.B., Zhang B.T., and Kim Y., "Word Sense Disambiguation by Learning Decision Trees from Unlabeled Data," Applied Intelligence, No. 19, 2003. pp. 27-38.

62. Sanderson M. Word Sense Disambiguation and Information Retrieval // Proceedings of 17th ACM International Conference of Research and Development in Information Retrieval. Dublin. 1994. pp. 49-57.

63. Sanderson M. Word Sense Disambiguation and Information Retrieval. PhD thesis. University of Glasgow, 1997.

64. Krovetz R., Croft B. Lexical Ambiguity and Informational Retrieval // Information Systems. 1992. Vol. 10. No. 2. pp. 115-141.

65. Казенников А.О., Трифонов Н.И. Сравнительный анализ алгоритмов

снятия лексико-семантической омонимии в задачах поиска и индексирования в информационных системах // Сборник трудов VI региональной научно-практической конференции "Профессиональная ориентация и методики преподавания в системе школа-вуз в условиях перехода к единой форме государственной аттестации выпускников образовательных учреждений". Москва. 2007. Vol. II. pp. 33-35.

66. Grishman R., Sundheim В. Message Understanding Conference - 6: A Brief History // Proceedings of the 16th International Conference on Computational Linguistics (COLING),. 1996. pp. 466-471.

67. Dang H. Overview of DUC 2006 // Proceedings of the Document Understanding Conference. 2006. pp. 1-10.

68. Wikipedia // www.wikipedia.org. URL: http://en.wikipedia.org/wiki/ Message_Understanding_Conference (дата обращения: 17.09.2013).

69. Cunningam H. Text Processing with GATE (Version 6). University of Sheffield Department of Computer Science, 2011.

70. Кудж С.А., Цветков В.Я., "Информационные образовательные единицы," Дистанционное и виртуальное обучении, № 1, 2014. С. 2431.

71. Group N.W. Request for Comments: 5023 The Atom Publishing Protocol // The Internet Engineering Task Force (IETF). 2007. URL: http:// tools.ietf.org/html/rfc5023 (дата обращения: 13.02.2014).

72. Shen D., Yang Q., Sun J., and Chen Z. Thread Detection in Dynamic Text Message Systems // Proc. of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 2006. pp. 35-42.

73. Bansal N., Koudas N. Blogscope: a system for online analysis of high volume text streams // Proceedings of the 33rd international conference on Very large data bases. 2007. pp. 1410-1413.

74. Fiscus J. Overview of results (NIST) // In Proceedings of TDT'01 Workshop.

75. Зевайкин A.H., Корнеев B.B. Формирование выпуска новостей на основе автоматического анализа новостных сообщений // Сборник работ научных стипендиатов Яндекс Интернет-Математика 2005. Ярославль. 2005. С. 436-460.

76. Yang Y., Pierce Т., and Carbonell J. A study on retrospective and on-line event detection // Proceedings of the International ACM Conference SIGIR. 1998. pp. 28-36.

77. Allan J. Topic detection and tracking: event-based information organization. Kluwer Academic Press, 2002.

78. Allan J..L.V., Malin D., and Swan R. Detections, bounds, and timelines: Umass and tdt-3 // Proceedings of Topic Detection and Tracking. 2000. pp. 167-174.

79. Gruhl D., Guha R., Kumar R., and Novak J. The predictive power of online chatter // In the proceedings of 11th international conference on Knowledge Discovery and Data Mining. 2005. pp. 78-87.

80. Shutze H., Silverstein C. PRojections for efficient document clustering // Proceedings of SIGIR 1997. 1997. pp. 74-81.

81. Shi Q., Petterson J., Dror G., Langford J., Smola A., and Vishwanathan S.V.N., "Hash kernels for structured data," The Journal of Machine Learning Research , No. 10, 2009. pp. 2615-2637.

82. Hartigan J.A., Wong M.A., "Algorithm AS 136: A k-means clustering algorithm," Journal of the Royal Statistical Society, Vol. Series С (Applied Statistics) 28, No. 1, 1978. pp. 100-108.

83. Cutting D.R., Karger D., Pedersen J.O., and Tukey J.W. Scatter/gather: A cluster-based approach to browsing large document collections // Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval. 1992. pp. 318-329.

84. Zhang Т., Ramakrishnan R., and Livni M. BIRCH: an efficient data clustering method for very large databases // Proceedings of the International ACM Conference on Management of Data (SIGMOD). 1996. pp. 103-114.

85. Defays D., "An efficient algorithm for a complete link method,". The Computer Journal (British Computer Society), No. 20 (4), 1977. pp. 364366.

86. Forman G. Tackling concept dript by temporal inductive transfer // In Proceedings of SIGIR 2006. 2006. pp. 252-259.

87. Joachims T. A statistical learning model of text classification with support vector machines // Proceedings of SIGIR 2001. 2001. pp. 128-136.

88. Zhao Y., Karypis G., "Refining web search engine results using incremental clustering," International Journal of Intelligent Systems, No. 10(2), 2005.

89. Кошкин Д.E., "Автоматическая кластеризация текстов на основе анализа слов," Научный вестник МИРЭА , № 1 (12) , 2012. С. 89-93.

90. Glance N., Hurst М., and Tomokiyo Т. BlogPulse: Automated Trend Discovery for Weblogs // In Proceedings of WWW'2004. 2004.

91. Sahoo N., Callan J., Krishnan R., and Duncan G. Incremental hierarchical clustering of text documents // Proceedings of the ACM International Conference of CIKM. pp. 357-366.

92. Вечур А.В., Суяргулова Е.Б. Модернизация расчета центроидов в алгоритме CMU // Труды РОМИП-2008. Санкт-Петербург: НУ ЦСИ. 2008. pp. 108-119.

93. Beringer J., Hullermeier E. Online Clustering of Parallel Data Streams // Data & Knowledge Engineering. 2006. No. 58. pp. 180-204.

94. Costa G., Mango G., and Ortale R. An incremental clustering scheme for data de-duplication // Data Mining and Knowledge Discovery. Jan 2010. Vol. 20. No. 1. pp. 152-187.

95. Moerchen F., Brinker K., and Neubauer C. Any-Time Clustering of High Frequence News Streams // 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2007. pp. 23-31.

96. Лукашевич H.В., Добров Б.В., and Штернов C.B. Обработка потока новостей на основе больших лингвистических ресурсов // Интернет-математика 2005. Автоматическая обработка веб-данных. 2005. pp. 461-484.

97. Brants Т., Chen F. A system for new event detection // In Proceedings of SIGIR 2003. 2003. pp. 330-337.

98. Zhang Y.J., Liu Z.Q., "Self-Splitting competitive learning: a new on-line clustering paradigm," IEEE Transactions on Neural Networks, No. 13(2), 2002. pp. 369-380.

99. Кондратьев M. Двухуровневая иерархическая кластеризация новостного потока в РОМИП 2006 // Труды РОМИП-2006. Санкт-

Петербург: НУ ЦСИ. 2006. С. 126-138.

100. Indyk P., Motwani R. Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality // Proceedings of 30th Symposium on Theory of Computing. 1998. pp. 604-613.

101. Datar M., ImmorlicaN., Indyk P., and Mirrokni V. Locality-Sensitive hashing scheme based on p-stable distributions // In Proceedings of the 20th Symposium on computational geometry. 2004. pp. 253-262.

102. Broder A.Z., Charikar M., Frieze A.M., and Mitzenmacher M., "Min-wise independent permutations," Journal of Computer and System Sciences, Vol. 60, No. 3, 2000. pp. 630-659.

103. Charikar M. Similarity estimation techniques from rounding algorithms // In Proceedings of STOC'2002. 2002. pp. 380-388.

104. Fisher D., "Knowledge acquisition via incremental conceptual learning," Machine Learning, No. 2(2), 1987. pp. 139-172.

105. Zhang Y.J., Liu Z.K., "Hierarchical clustering algorithms for document datasets," Data Mining and Knowledge Discovery, No. 10(2), 2005. pp. 141-168.

106. Blei D.M., Ng A.Y., and Jordan M.I., "Latent dirichlet allocation," Journal of machine Learning research , No. 3, 2003. pp. 993-1022.

107. Yao L., Mimno D., and McCallum A. Efficient Methods for Topic Model Inference on Streaming Document Collections // Proc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2009. pp. 947-956.

108. Muthukrishnan S. Data streams: Algorithms and applications. Now

Pushlishers Inc., 2005.

109. Levenberg A., Osborne M. Stream-based randomised langue models for SMT // Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing. 2009. pp. 756-764.

110. Мельчук И.А. Опыт теории лингвистических моделелей "Смысл <->Текст". Москва: Школа "Языки русской культуры", 1999. 346 с.

111. Соркирко А.В. Сравнение эффективности двух методик снятия лексической и мор-фологической неоднозначности для русского языка (скрытая модель Маркова и син-'таксический анализатор именных групп) // Сборник работ стипендиатов научных стипендий Яндекса. 2004.

112. Хомский Н. Синтаксические структуры = Syntactic Structures. Москва: Новое в лингвистике, 1962. 412-527 pp.

113. Апресян Ю.Д., Богуславский И.М., Иомдин Б.Л., Иомдин Л.Л. Синтаксически и семантически аннотированный корпус русского языка: современное состояние и перспективы // В кн.: Национальный корпус русского языка 2003-2005. Москва: Индриг, 2005. С. 193-214.

114. Теньер Л. Основы структурного синтаксиса. Москва: Прогресс, 1988. 656 с.

115. McDonald R. Discriminative Learning and Spanning Tree Algorithms. PhD diss. University of Pennsilvania, 2006. 240 pp.

116.

Domingos P., Hulten G. A general method for scaling up machine learning algorithms and its application to clustering // In proceedings of ICML. 2001. pp. 106-113.

117. Freund Y., Schapire R. Experiments with a New Boosting Algorithm // Proceedings of International Conference on Machine Learning. 1996. pp. 148-156.

118. Fan R.E., Chang R.E., Hsieh R.E., Wang X.R., and Lin C.J., "LIBLINEAR: A library for large linear classification," Journal of Machine Learning Research, No. 9, 2008. pp. 1871-1874.

119. Crammer K., Singer Y., "Ultraconservative Algorithms for Multiclass Problems," Journal of Machine Learning Research, No. 3, 2003. pp. 951991.

120. Liere R., Tadepalli P., "Active Learning with Committees," AAAI, 1997. pp. 591-596.

121. McDonald R., Satta G. On the Complexity of Non-Projective Data-Driven Dependency Parsing//In Proceedings oflWPT. 2007. pp. 121-132.

122. Nivre J, "Inductive Dependency Parsing of Natural Language Text," MSI Report 05132, Vaxjo University. (PhD) , 2005.

123. Covington M.A. A fundamental algorithm for dependency parsing // Proceedings of the 39th Annual ACM Southeast Conference. 2001. pp. 95102.

124. Boguslavsky I., Grigorieva S., Grigoriev N., Kreidlin L., and Frid N. Dependency treebank for Russian: Concept, tools, types of information // Proceedings of the 18th International Conference of Computational Linguistics (COLING). 2000. pp. 987-991.

125. Lewis D.D. Machine learning for text categorization: background and characteristics // Proceedings of 21st National Online Meeting. 2000. pp. 221-226.

126. Казенников А.О. Сравнительный анализ статистических алгоритмов синтаксического анализа на основе деревьев зависимостей // Труды международной конференции "Компьютерная лингвистика и интеллектуальные технологии" (Диалог). 2010.

127. Казенников А.О. Исследования алгоритмов построения деревьев зависимостей на основе машинного обучения // Сборник трудов 32ой конференции молодых ученых и специалистов ИППИ РАН "Информационные технологии и системы". Москва. 2009. С. 226-229.

128. Петроченков В.В., Казенников А.О., "Статистический теггер для разметки русскоязычных текстов," Автоматика и телемеханика, No. 10, 2013. pp. 154-165.

129. Cortes С., and Vapnik V.N., "Support-Vector Networks," Machine Learning, No. 20, 1995. pp. 273-297.

130. Казенников А.О., Трифонов Н.И., Куракин Д.В. Гибридный алгоритм синтаксического разбора для системы анализа новостных потоков // Информатизация науки и образования. 2012. № 1(13). С. 90-97.

131. Казенников А.О. Эксперименты по созданию гибридной системы синтаксического анализа на основе системы ЭТАП-3 // Сборник трудов 33 ой конференции молодых ученых и специалистов ИППИ РАН "Информационные технологии и системы". Москва. 2010. С. 306-309.

132. Kudj S.A., Solovjev I.V., and Tsvetkov V.Y., "System Elements Heterogeneity," European Researcher, No. 60 №10, 2013. pp. 23662373.

133. Ляшевская O.H., Астафьева И., Бонч-Осмоловская А., Гарейшина А., and Гришина Ю. Оценка методов автоматического анализа текста:

морфологические парсеры русского языка // Компьютерная лингвистика и интеллектуальные технологии: По материалам ежегодной Международной конференции «Диалог» (Бекасово, 26-30 мая 2010 г.). 2010. pp. 318-327.

134. Mihalcea R., Moldovan D. A Highly Accurate Bootstrapping Algorithm for Word Sense Disambiguation // Jouranl on Artificial Intelligence Tools. 2001. Vol. 10. No. 1 & 2. pp. 5-21.

135. Богуславский И.М., Иомдин JI.JI., Митюшин Л.Г., Сизов В.Г. Длина синтаксических связей в русском аннотированном корпусе // Труды Международной конференции «Корпусная лингвистика - 2008». 2008. С. 75-82.

Приложение 1. Исходный код гибридного алгоритма синтаксического анализа

public class SyntParser { double[] w; List<Action> actions; Action defaultAction;

public SyntTree parse(Annotation sent) {

List<Annotation> words = sent.get("words"); SyntData data = makeData(words); etap3Hypot(data); while(!data.isTreeBuilded()) {

Action nextAction = guessAction(data); next Action.apply(data);

}

}

public Action guessAction(SyntData data) { Action a = defaultAction; double score = Double.NEGATIVEJNFINITY;

for(int i = 0; i < actions.size(); i++) {

SparseVector v = data.vectorize(i); double d = v.dot(w); if(d > score) {

score = d; a = actions.get(i);

}

}

return a;

public class TGTFile {

public static class SentenceBuilder {

StringBuilder text = new StringBuilder(); StringBuilder sep = new StringBuilder(); List<Annotation> anns = new ArrayList<Annotation>(); public SentenceBuilder addWord(String word, Map<String, Object> feats) { Annotation ann = Annotation.newAnnotation(TGT.WORD, text.length(), text.length() + word.length());

text.append(word);

for(Map.Entry<String, Object> f : feats.entrySet()) { ann.setFeature(f.getKey(), f.getValue());

}

anns.add(ann); return this;

public SentenceBuilder addDummy() {

Map<String, Object> feats = new HashMap<String, Object>(); feats.put(TGT.NODETYPE, TGT.NodeType.DUMMY); return addWord("", feats);

public SentenceBuilder addSep(String sep) {

this.sep.append(sep.replaceAll("\n", "")); return this;

}

public SentenceBuilder parseSep() { String sep = this.sep.toString(); sep = sep.replace("\n", ""); sep = sep.replace("\r", ""); sep = sep.replaceAll("\\s+", " "); // skip space before first word in the sentence if(anns.isEmpty()) {

//sep = sep.trimQ; if(!sep.isEmpty()) {

text.append(sep);

}

this. sep. setLength(O); return this;

}

text.append(sep); this. sep. setLength(O); return this;

}

public Document build(Map<String, Object> feats) {

Document d = new Document(text.toString().trim()); for(Map.Entry<String, Object> f : feats.entrySet()) { d.setFeature(f.getKey(), f.getValue());

}

d.addAnnotations(anns); d.sortAnnotations(); return d;

}

}

private static final Interner<List<String» FEATS_INTERNER = Interners.newStrongInterner(); final public File file; protected InputStream s; protected XMLStreamReader reader; //final public TGTInfo info;

public TGTFile(File file) throws IOException, XMLStreamException { this.file = file;

s = new FilelnputStream(file); if(file.getName().endsWith(".gz"))

s = new GZIPInputStream(s); XMLInputFactory inputFactory = XMLInputFactory.newFactory(); inputFactory. setProperty(XMLInputFactory.IS_COALESCING, Boolean.TRUE);

reader = inputFactory.createXMLStreamReader(s);

}

public void close() throws XMLStreamException, IOException { reader.close(); s.close();

}

public Map<String, Object> makeFeats() {

Map<String, Object> feats = new HashMap<String, Object>(); feats.put(TGT.EXTRAFEATS, TGT.EMPTYFEATS); feats.put(TGT.FEATS, TGT.EMPTY FEATS); feats.put(TGT.NODETYPE, TGT.NodeType.NORMAL); return feats;

protected void parseWord(SentenceBuilder sentBuilder) throws XMLStreamException {

TGT.NodeType nodeType = TGT.NodeType.NORMAL;

// <W> attributes parsing

Map<String, Object> f = makeFeats();

for(int i = 0; i != reader.getAttributeCount(); i++) {

String name = reader.getAttributeLocalName(i); String value = reader.getAttributeValue(i); Object val = value; if(name == TGT.ID)

val = Integer.parselnt(value); else if(name == TGT.FEATS)

val = Lists.newArrayList(Splitter.on(' ').split(value)); else if(name == TGT.EXTRAFEATS)

val = Lists.newArrayList(Splitter.on(' ').split(value)); else if(name == TGT.NODETYPE) {

nodeType = TGT.NodeType.getType(value); val = nodeType;

}

else if(name == TGT.HEAD) {

val = value.equals(TGT.ROOT_VALUE)? 0 :

Integer.parselnt(value);

} else {

val = value.internQ;

}

f.put(name, val);

}

String wordform = reader.getElementText();

if(nodeType == TGT.NodeType.DUMMY) sentBuilder.addDummyO;

else {

if(!f.containsKey(TGT.EXTRAFEATS)) {

f.put(TGT.EXTRAFEATS, TGT.EMPTY FEATS);

}

sentBuilder.addWord(wordform, f);

}

}

public Document next() throws XMLStreamException, IOException { SentenceBuilder sentBuilder = new SentenceBuilder(); // <S> attributes parsing

while(reader.hasNext() && ¡(reader.isStartElement() && reader.getLocalName().equals(TGT.SENT))) { reader.next();

}

if(! reader.hasNext()) return null;

Map<String, Object> feats = new HashMap<String, Object>(); feats.put(TGT.FILE, file);

for(int i = 0; i != reader.getAttributeCount(); i++){

String name = reader.getAttributeLocalName(i); String value = reader.getAttributeValue(i); Object val = null;

if(name == TGT.ID) {

val = Integer.parselnt(value);

}

else if(name == TGT.SRCFILE) {

TGT.SentenceSource ss = new TGT.SentenceSource(value); feats.put(TGT.SRC_FILE, ss.filename); feats.put(TGT.SRC_ID, ss.id); val = ss; } else {

val = value.internQ;

}

feats.put(name, val);

}

while(reader.hasNext() && ¡(reader.isEndElement() && reader.getLocalName() == TGT.SENT)) {

if(reader.isCharacters()) {

sentBuilder.addSep(reader.getText());

}

if(reader.isStartElement() && reader.getLocalName() ==

TGT.WORD) {

sentBuilder.parseSep(); parse Word(sentBuilder);

}

reader.next();

}

sentBuilder.parseSep();

return sentBuilder.build(feats);

}

}

public class Features {

private Features() { }

public static class MorphFeatsFeature extends CommonFeatures.Indexed<SequenceStream<Node» { @Override

public String name() { return "feats";

}

@Override

public void eval(Settable res, List<Value> args) {

SequenceStream<Node> seq = getObject(args); int index = getlndex(args);

Node node = seq.current(index); if(node == null) { res.set(null); return;

}

res.set(node.getGold().getFeats());

}

public static class MorphGroupFeatsFeature extends CommonFeatures.Indexed<SequenceStream<Node>> { String name; String group;

public MorphGroupFeatsFeature(String name, String group) { this.name = name; this.group = group;

}

@Override

public String name() {

return name;

@Override

public void eval(Settable res, List<Value> args) {

SequenceStream<Node> seq = getObject(args); int index = getlndex(args);

Node node = seq.current(index); if(node == null) { res.set(null); return;

}

res.set(node.getGold().getFeats().getGroup(group));

}

}

public static class WordFeature extends CommonFeatures.Indexed<SequenceStream<Node» { @Override

public String name() { return "w";

}

@Override

public void eval(Settable res, List<Value> args) {

SequenceStream<Node> seq = getObject(args); int index = getlndex(args);

Node node = seq.current(index); if(node == null) { res.set(null); return;

}

res.set(node.se.getText());

}

}

public static class AffixFeature extends CommonFeatures.Base<SequenceStream<Node» { @Override

public String name() { return "aff";

}

@Override

public void eval(Settable res, List<Value> args) {

SequenceStream<Node> seq = getObject(args); int index = args.get(l).get(Integer.class); int len = args.get(2).get(Integer.class);

Node node = seq.current(index); if(node == null) {

res.set(null); return;

String s = node.se.getText(); len = Math.min(len, s.length());

res.set(len > 0? s.substring(s.length() - len) : s.substring(0, len));

}

}

public static class WordAbsFeature extends CommonFeatures.Indexed<SequenceStream<Node» { @Override

public String name() { return "w-abs";

}

@Override

public void eval(Settable res, List<Value> args) {

SequenceStream<Node> seq = getObject(args); int index = getlndex(args);

if(index < 0) {

index = seq.size() - index;

}

Node node = seq.get(index); if(node == null) { res.set(null); return;

}

res.set(node.se.getTextQ);

}

}

public static class AmbigClass extends Common Features. Indexed<SequenceStream<Node>> { @Override

public String name() { return "a";

}

@Override

public void eval(Settable res, List<Value> args) {

SequenceStream<Node> seq = getObject(args); int index = getlndex(args);

Node node = seq.current(index); if(node == null) { res.set(null); return;

}

StringBuilder sb = new StringBuilderQ;

for(Node.Alt alt : node.alts) { if(sb.length() > 0) { sb.append('_');

}

sb.append(alt.feats.toString('|'));

}

res.set(sb.toString());

}

}

public static class SentPos extends CommonFeatures.Indexed<SequenceStream<Node» {

public static enum SentPosition {

START, MID, END, INVALID;

@Override

public String name() { return "sent-pos";

}

@Override

public void eval(Settable res, List<Value> args) {

SequenceStream<Node> seq = getObject(args); int index = getlndex(args);

int pos = seq.pos() + index; SentPosition p = SentPosition.INVALID;

if(pos == 0) {

p = SentPosition.START; } else if(pos == seq.size() - 1) {

p = SentPosition.END; } else if(pos > 0 && pos < seq.size() - 1) { p = SentPosition.MID;

}

res.set(p);

}

}

public static class Orth extends CommonFeatures.Indexed<SequenceStream<Node>> {

public static enum OrthType {

LOWER, CAP, UPP, MIX

}

@Override

public String name() {

return "sent-pos";

}

@Override

public void eval(Settable res, List<Value> args) {

SequenceStream<Node> seq = getObject(args); int index = getlndex(args); Node node = seq.current(index);

String s = node.se.getText();

}

}

public static List<FeatureFunction> featFunctions() {

List<FeatureFunction> f = new ArrayList<FeatureFunction>();

f.add(new WordFeature()); f.add(new MorphFeatsFeature());

f.add(new MorphGroupFeatsFeature("pos", RussianMorph.POS)); f.add(new MorphGroupFeatsFeature("aspect", RussianMorph.ASPECT)); f.add(new MorphGroupFeatsFeature("voice", RussianMorph.VOICE)); f.add(new MorphGroupFeatsFeature("repr", RussianMorph.REPR)); f.add(new MorphGroupFeatsFeature("mood", RussianMorph.MOOD)); f.add(new MorphGroupFeatsFeature("tense", RussianMorph.TENSE)); f.add(new MorphGroupFeatsFeature("degree", RussianMorph.DEGREE)); f.add(new MorphGroupFeatsFeature("degree-mdf', RussianMorph.DEGREEMDF));

f.add(new MorphGroupFeatsFeature("number", RussianMorph.NUMBER)); f.add(new MorphGroupFeatsFeature("person", RussianMorph.PERSON)); f.add(new MorphGroupFeatsFeature("gender", RussianMorph.GENDER)); f.add(new MorphGroupFeatsFeature("case", RussianMorph.CASE)); f.add(new MorphGroupFeatsFeature("anim", RussianMorph.ANIM)); f.add(new MorphGroupFeatsFeature("inflection", RussianMorph.INFLECTION));

f.add(new AffixFeature()); f.add(new AmbigClass()); f.add(new SentPos()); return f;

}

}

Приложение 2. Исходный код алгоритма кластеризации

public class ClusteringEnvironment implements Closeable {

private static final Logger logger = Logger.getLogger(ClusteringEnvironment.class); boolean useAuxData; TermStats terms; ClusteringSettings settings;

List<Cluster> clusters = new ArrayList<Cluster>(); Map<Cluster, ClusterAuxData> clusterData = new HashMap<Cluster, ClusterAuxData>();

ClusteringFeatureExtraction fe = new ClusteringFeatureExtraction();

ThreadPoolExecutor executor;

public ClusteringEnvironment() throws Exception {

this.executor = ThreadPoolUtils.newBlockingThreadPoolExecutor(4, 4, 10,

TimeUnit. SECONDS, 10); }

public Cluster newCluster(ClusterDoc doc) { Cluster c = new Cluster(0, 0); c.add(doc); clusters.add(c); return c;

}

public List<Cluster> getElibleClusters(ClusterDoc doc) { List<Cluster> clusters = new ArrayList<Cluster>(); long ts = doc.getDate().getTime(); for(Cluster c : this.clusters) {

if(!c.isActive() || c.isExpired(ts))

continue; clusters.add(c);

}

return clusters;

}

public double dist(ClusterDoc doc, Cluster c) { return settings.getMetric().dist(c, doc);

}

public ClusterDoc weight(ClusterDoc d) {

final ClusterDoc dl = new ClusterDoc(d.id, d.url, d.title, d.text, d.title + "\r\n" + d.text, d.date);

dl .fields = d.fields;

int max = d.maxFreqO;

int total = d.totalLength();

dl.v = new SparseVector();

for(ClusterDoc.Entry e : d.entries) {

ClusteringSpace s = settings.spaces.getSpace(e.type); ClusterDoc.Entry el = new ClusterDoc.Entry("nf', e.id, e.tf); int df = terms.getDF(e.type, e.id); if(df < settings.getMinDF())

continue; if(df != 0) {