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

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

КАЗЕННИКОВ АНТОН ОЛЕГОВИЧ

РАЗРАБОТКА МОДЕЛЕЙ И АЛГОРИТМОВ ДЛЯ КОМПЛЕКСА АВТОМАТИЧЕСКОЙ ОБРАБОТКИ И АНАЛИЗА ПОТОКОВ НОВОСТНЫХ СООБЩЕНИЙ НА ОСНОВЕ МЕТОДОВ КОМПЬЮТЕРНОЙ ЛИНГВИСТИКИ

Специальность 05.13.15 Вычислительные машины, комплексы и компьютерные сети

Автореферат

Диссертации на соискание степени кандидата технических наук

5 и:пн ¿014

Москва 2014

005549823

005549823

Диссертация выполнена на кафедре «Информатика и информационные системы» (ИИС) федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Московский государственный технический университет радиотехники, электроники и автоматики» (МГТУ МИРЭА).

Научный руководитель Доктор технических наук, профессор Соловьев Игорь Владимирович, зав. кафедрой ИИС МГТУ МИРЭА

Официальные оппоненты Доктор технических наук, профессор Жуков Дмитрий Олегович, профессор кафедры 721 Института криптографии, связи и информатики федерального государственного казенного образовательного учреждения высшего профессионального образования «Академия Федеральной службы безопасности Российской Федерации» (Академия ФСБ России) Кандидат технических наук, доцент Гуров Валерий Валентинович, доцент кафедры «Компьютерные системы и технологии» Национального исследовательского ядерного университета «МИФИ»

Ведущая организация Федеральное государственное бюджетное учреящение науки Институт проблем передачи информации им. А.А. Харкевнча Российской академии наук (ИППИ РАН)

Защита диссертации состоится 30.06.2014 в 15 часов 00 минут на заседании диссертационного совета Д212.131.05 при Московском государственном техническом университете радиотехники, электроники и автоматики (МГТУ МИРЭА) по адресу: г. Москва, проспект Вернадского, д. 78

Автореферат диссертации разослан «24» мая 2014 г.

С диссертацией можно ознакомиться в библиотеке МГТУ МИРЭА и на сайте vvww.mirea.ru

Отзывы (в двух экземплярах, заверенные печатью учреждения) просим направлять в адрес диссертационного совета Д 212.131.05 при МГТУ МИРЭА.

Ученый секретарь диссертационного совета, к.т.н., доцент

Е.Г. Андрианова

Актуальность темы диссертации.

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

Задача отслеживания развития сюжетов событий во многом схожа с задачей кластеризации текстов. Как и в задаче кластеризации текстов, в современных комплексах и системах кластеризации новостных потоков предполагается, что слова текста независимы друг от друга, а «значимость» каждого слова определяется на основе некоторой семантической метрики «веса» слова. При выполнении этой процедуры используются не сами, слова, а их основы, полученные в результате процедуры стемминга (англ., stemming, выделение основы слова). Из этих основ образуется «мешок слов» (англ., bag of words) над которым выполняются процедуры преобразования и кластеризации. При таком «поверхностном» (shallow, англ.) представлении текстовых данных «поверхностная» кластеризация на основе «мешка слов» не учитывает ни структуру текста, ни присутствующие в тексте именованные сущности (имена персон, названия организаций, географические названия), ни связи между этими сущностями в тексте. Вместе с тем, несомненным достоинством «поверхностных» методов обработки текстов является высокая скорость обработки текстовых сообщений.

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

Альтернативным методом построения компьютерных лингвистических анализаторов является метод на основе размеченных лингвистических «корпусов текстов». При использовании этого метода производится

обогащение массивов текстов на естественном языке соответствующей лингвистической информацией, например, морфологической и синтаксической, разметкой именованных сущностей. Разработка таких лингвистических ресурсов менее трудоемка, чем разработка модели языка. При использовании «корпусного метода» автоматические лингвистические анализаторы конструируются с использованием, в том числе, методов машинного обучения. В результате применения машинного обучения происходит обобщение частных примеров, представленных в лингвистическом корпусе текстов, при этом конструируются общие, качественные и во многих случаях эффективные процедуры обработки и анализа текстов. В частности, этот метод успешно применяется для создания синтаксических анализаторов. Проблемой на этом пути является отсутствие априорной информации о возможных синтаксических связях предложения, которая может быть получена с помощью лингвистических правил. Одна из наиболее совершенных среди современных систем синтаксического анализа — лингвистический процессор ЭТАП-3 (Апресян и др., 2001) обладает фильтровым подходом к синтаксическому анализу. Вначале, на основе лингвистических правил конструируются все возможные потенциальные синтаксические связи предложения, затем выполняется процедура фильтрации до тех пор, пока не будет построена корректная с точки зрения совместимости синтаксических связей структура. Основной проблемой при использовании системы ЭТАП-3 является ресурсоёмкая процедура «перебора альтернатив», которая во времени обладает экспоненциальной сложностью.

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

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

лингвистическим методам с высокой скоростью обработки текстов «поверхностными» методами.

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

Для достижения указанной цели в диссертационной работе поставлены и решены следующие задачи:

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

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

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

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

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

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

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

Объектом исследования диссертации является комплекс обработки и анализа потоков новостных сообщений на естественном языке.

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

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

Научная новизна полученных результатов состоит в том, что: 1) разработан гибридный алгоритм синтаксического анализа, сочетающий в себе возможности и характеристики лингвистического процессора ЭТАП-3, так и алгоритма Ковингтона. Разработанный гибридный алгоритм позволяет значительно ускорить (в среднем на 50%) процесс синтаксического анализа при незначительной для задачи кластеризации новостных сообщений потери в его точности.

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

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

4) Разработана математическая модель многоуровнего представления новостного сообщения, дополняющая классическую векторную модель и позволяющая учитывать различные виды информации, присутствующие в документе.

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

6) Разработана математическая модель представления синтаксической структуры новостного сообщения, которая при совместном использовании с разработанным алгоритмом кластеризации, существенно (более чем на 10%) улучшает точность и полноту кластеризации новостных сообщений.

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

Значение полученных соискателем результатов исследования для практики подтверждается тем, что доказана эффективность гибридного синтаксического анализа на реальных потоках новостных сообщений. Произведена оценка качества кластеризации на корпусе размеченных новостных сообщений ведущих информационных агентств - «РИА Новости», «Интерфакс» и новостных сайтов «Лента.Ру», и «NewsRu.COM». Предложенная в работе математическая модель кластеризации потоков новостных сообщений была реализована на языке программирования Java и показала высокую производительность, достаточную для анализа более 20 тыс. новостных сообщений в сутки, что соответствует трафику потоков новостных сообщений ведущих информационных агентств.

Оценка достоверности результатов. Методами компьютерного моделирования и прямыми экспериментами установлено, что при использовании разработанного алгоритма точность кластеризации увеличивается более чем на 5%, а полнота - более чем на 10% по сравнению с базовой моделью. Экспериментально установлено ощутимое улучшение качества кластеризации при использовании разработанного гибридного

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

Научные положения диссертации внедрены в учебный процесс МГТУ МИРЭА в дисциплине «Информационно-поисковые системы». Выводы и рекомендации использованы в действующих поисково-аналитических системах компаний-производителей лингвистических процессоров, что подтверждено актами о внедрении. Получено свидетельство о государственной регистрации программы для ЭВМ № 2014611834 от 11 февраля 2014 г. «Программа для кластеризации потоков новостных сообщений на основе многоуровневой модели представления документа».

Апробация работы. Результаты диссертационной работы доложены, обсуждены и получили положительные отзывы на 5 научных конференциях, конкурсах и семинарах. По материалам диссертационной работы опубликовано 15 печатных работ, в том числе 5 в журналах из перечня ВАК и 1 в журнале, входящем в базу цитирования Scopus.

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

Основное содержание работы

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

Первая глава посвящена критическому анализу современного состояния работ в области анализа и обработки потоков новостных сообщений. В ней определены основные пробелы в разработках существующих алгоритмов и методов кластеризации потоков новостных сообщений, которые призвана восполнить диссертационная работа. В частности, установлено, что задачу анализа потоков новостных сообщений можно рассматривать как задачу информационного поиска. Такой подход предполагает, что базовым объектом, над которым производятся все операции, является документ - законченный фрагмент текста. В современных системах анализа потока новостных сообщений используется классическое представление документа на основе т.н. «мешка слов» (англ. bag of words). Для оценки веса каждого слова наиболее часто используется метод TF-1DF на основе нормализованной частоты появления слова в документе. Нормализованная частота определяется как отношение числа вхождений слова к общему количеству слов документа.

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

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

Параллельно с областью информационного поиска за последние несколько лет значительные результаты достигнуты в области компьютерной лингвистики. Наиболее существенные результаты получены в области синтаксического анализа. В общем виде синтаксическая структура на основе деревьев зависимостей задается следующим образом. Дано предложение х = ■■■ где — ¿-ое слово в предложении. Дополнительно

вводится фиктивное слово уу0 для обозначения вершины синтаксической структуры предложения. Ь = {71( - множество возможных типов связей,

тогда синтаксическая структура предложения - ориентированный маркированный граф С = (У,А), в котором: V = {0,1, ...,?г} — множество вершин, соответствующих словам предложения, А Е V х х V — множество связей графа.

На Рис. 1 представлен пример синтаксической структуры для предложения «Сначала торговые сети появились в Москве». Из нее следует что слово «появились» является вершиной структуры, от которой зависят остальные слова. Синтаксическая структура отражает ответы на следующие вопросы: «появились что?» - «сети», и «появились где?» - «в Москве», «сети какие?» - «торговые», «появились когда?» - «сначала».

Рис. 1. Пример синтаксической структуры предложения «Сначала торговые сети

появились в Москве»

Классические системы синтаксического анализа построены на основе правил, разработанных экспертами-лингвистами. Одной из наиболее совершенных систем этого типа является лингвистический процессор ЭТАП-3. Основным ограничением этой системы является относительно низкая скорость работы. Экспериментально установлено, что ЭТАП-3 может обрабатывать текст со скоростью около двух предложений в секунду. Такая скорость обработки может оказаться неприемлемой для обработки потока новостей от ведущих информационных агентств.

В Главе 1 диссертации критически проанализированы два наиболее эффективных алгоритма синтаксического анализа на основе машинного обучения. Установлено, что наиболее продуктивным подходом к синтаксическому анализу предложения является подход на основании системы переходов. Синтаксический анализатор на основе такого подхода представляет собой кортеж из четырех элементов 5 = (С, Т, с5,С1): а) конфигурации С, описывающей текущее состояние разбора предложения; б) действий Г, изменяющих текущую конфигурацию; в) функция инициализации начального состояния с£; г) Множество конечных состояний конфигурации С(. На Рис. 2 представлен алгоритм Ковингтона синтаксического анализа на базе системы переходов, который предполагает возможность построения непроективных связей. Это свойство имеет существенное значение, поскольку в более чем 10% предложений русского языка присутствуют непроективные связи.

Рис. 2. Типовой алгоритм синтаксического анализа Ковингтона

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

связи, лучшие результаты показывает алгоритм Ковингтона, корректно построив 87% синтаксических связей. Алгоритм на основе максимальных остовных деревьях построил только 81% корректных связей. В тоже время, лингвистический процессор ЭТАП-3 на том же самом наборе данных корректно построил 92% связей. Такое различие в результатах связано с тем, что алгоритм Ковингтона не делает никаких априорных предположений о допустимых синтаксических связях в рассматриваемом предложении. Кроме того, алгоритм Ковингтона предполагает, что для каждого слова предложения априорно установлены лексические значения и грамматические категории.

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

В заключительном разделе обзорной Главы 1 уточнена постановка задачи диссертационного исследования на основе проведенного аналитического обзора.

Во второй главе разрабатывается гибридный алгоритм синтаксического анализа, сочетающий высокую производительность алгоритма Ковингтона и высокое качество анализа системы ЭТАП-3.

Для практического использования алгоритма Ковингтона необходимо предварительно снять морфологическую омонимию. Для решения этой задачи в диссертации был разработан алгоритм SVMTAG (Support Vector Machine TAGger) для снятия морфологической омонимии на основе методов машинного обучения. Разработанный алгоритм SVMTAG последовательно пословно обрабатывает предложение слева направо, рассматривая каждое слово только один раз. Упрощенная структура алгоритма представлена на Рис. 3.

Снятие омонимии для некоторого слова происходит на основе контекстного анализа. Кроме самого слова рассматриваются несколько соседних слов, стоящих слева и справа от него. Алгоритм рассматривает знаки препинания как полноправные слова предложения. Процедура использует следующие типы доступной информации: а) словоформа, б) часть речи (для знаков препинания используется специальное обозначение «PUNC»), в) морфологические характеристики и их множества, г) способы написания слова (с заглавной буквы, содержит ли данное слово цифры или дефис).

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

Рис. 3 Алгоритм снятия морфологической омонимии SVMTAG

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

scoret(x) = wt * х, (1)

Где х - векторизованное представление контекста, а wt - вектор весов для набора морфологических характеристик t. Векторизация контекста производится следующим образом. Каждая пара характеристика-значение контекста склеивается в единое значение и помещается в таблицу, где каждому уникальному значению ставится в соответствие некоторое число - координата этого признака в пространстве Rn. Если данная пара характеристика-значение присутствует в рассматриваемом контексте, то значение соответствующей координаты вектора контекста устанавливается в 1, в противном случае - 0. Для вычисления оптимального вектора весов wm для каждого класса т используется метод основе машины опорных векторов (SVM):

\т\ I

ъ>

гп=1 ¡=1

при условии: (2)

Wy^i - Wm*i ^ еГ - Si ГО, если у£=т| 1 (1, еслиуг Фтп)' Д Xi - i-тый пример обучения, f; - ошибка классификации ¿-того примера

1

wm wL_ + С

обучения, у; - метка i-того примера, С - коэффициент регуляризации.

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

В разработке гибридного алгоритма синтаксического анализа выполнена модификация алгоритма Ковингтона для использования быстрого параллельного линейного алгоритма обучения SVM при решении задач классификации по нескольким классам. Приводится описание алгоритма преобразования эталонной синтаксической структуры в эталонную последовательность переходов. Дано предложение S = {w1,w2, ...,wn}. Необходимо получить Ts - эталонную последовательность переходов, которая позволяет получить заданную синтаксическую структуру. Дополнительно вводится фиктивное слово-вершина синтаксической структуры w0. Полученная эталонная последовательность действий Ts преобразуется в обучающее множество в виде пар {с, t), где с — промежуточное состояние синтаксического анализа данного предложения, at — эталонное действие, которое позволит получить эталонную синтаксическую структуру. Для применения алгоритма SVM необходимо произвести векторизацию обучающих примеров и формирования выборки X = <x;,yi), где xL вектор примера t, a y-L метка примера i. В случае задачи синтаксического анализа вектор примера формируется на основе разработанной математической модели признаков, учитывающей особенности русского языка и русскоязычных текстов. Метка для обучения формируется на основе эталонного действия £, соответствующего конфигурации, из которой был получен вектор х,-. Для формирования метки существует два подхода. Первый заключается в том, что создается полное перечисление всех возможных действий над этой конфигурацией. Поскольку различных действий четыре, а два из них (Left-Arc и Right-Arc) содержат параметр — тип проводимой связи, то всего типов действий 2 + 2*84 = 170, поскольку в корпусе СинТагРус определено 84 различных синтаксических связи.

Другое существенное изменение в алгоритме Ковингтона состоит в использовании априорной информации о возможных синтаксических связях предложения с помощью правил лингвистического процессора ЭТАП-3. Для этого перед проведением синтаксического анализа с помощью модифицированного алгоритма Ковингтона выполняется процедура построения потенциальных синтаксических связей с помощью системы ЭТАП-3. Для использования этой информации в самом алгоритме синтаксического анализа в конфигурацию алгоритма Ковингтона С = {1г,12,р,А), описывающую текущее состояние анализа на момент принятия решения о связи для слов wt и wk, где i < к, = {Wj,j < ¿}, l2 = {Wj,j > к], р — [wj, i > j > к}, вводится дополнительный параметр L — потенциальные синтаксические связи, построенные системой ЭТАП-3. В результате будет получена расширенная

конфигурация С' = (11,12,Р,А, Ь).

гешт с. А

с = т

\ /

с. А = с. А + с

Рис. 4. Модифицированный алгоритм Ковингтона, дополненный априорной информацией о синтаксических связях системы ЭТАП-3

В результате разработан алгоритм, схема которого представлена на Рис. 4, который наряду с использованием априорной лингвистической информации лингвистического процессора ЭТАП-3, использует алгоритм Ковингтона для извлечения синтаксической структуры на основе множества потенциальных синтаксических связей предложения. Однако алгоритм Ковингтона использует только основные характеристики для построения синтаксических связей без учета особенностей анализируемого языка. Для этого в диссертации уточняется модель признаков с помощью дополнительных типов - согласованных пар слов по числу, роду и падежу. Согласование важно выбора корректных синтаксических связей, например в словосочетаниях «осень золотая» и «президент сообщил». В работе предложена математическая модель, содержащая способ кодирования этих признаков в евклидово пространство /?п. В процессе обучения (вычисления вектора весов и^) составляется таблица пар «признак=значение», например «часть речь слова ^[0] — существительное», и каждой такой паре присваивается уникальный индекс, который и является координатой в целевом пространстве Дп. Тогда конфигурация С кодируется в вектор следующим образом. Изначально создается нулевой вектор — вектор, все координаты которого равны 0. Важной положительной особенностью

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

Другая особенность процесса обучения модели, предложенная в работе, состоит в существенном сокращении необходимой памяти для представления таблицы преобразований «признак —> координата». В классическом варианте эта таблица представляется в виде таблицы. Для быстрой работы во время обучения ее необходимо полностью содержать в оперативной памяти компьютера. Если одна запись этой таблицы занимает размер 100 байт, то для ее кодирования 10 млн. признаков необходимо около 1 Гбайта оперативной памяти. Поскольку, в алгоритме БУМ для вычисления вектора весов и^ необходимы не сами вектора данных, а их скалярные произведения, то введем /г(х) - случайную равномерно перемешивающую функцию преобразования Ь(х): Яп -> Ят. Тогда возможна замена (х, у) ~ (Ь(х), /г(у)>. Полученный результат означает, что для отказа от таблицы преобразования признаков необходимо ввести хеш-функцию /(х) —> п, которая преобразовывала признак в диапазон [0 ... п], при этом обладая свойствами равномерности и независимости преобразования. При выборе п приблизительно равному размеру таблицы преобразований возможен полный отказ от использования этой таблицы без существенной потери качества синтаксического анализа.

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

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

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

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

Документ полностью описывается множеством О = [О1,02,..., От}, где т - число уровней представления документа, О1— г-тый уровень представления документа является вектором в пространстве — евклидовом пространстве рассматриваемого уровня:

& = {4,4,...^}, (3)

где Су — вес элементарного термина_/' документа уровня /

Введен также вектор а размерностью т для описания весов уровней документа. Считается, что

£ щ = 1 (4)

О < а; < 1

Определяется функция вычисления расстояния между двумя документами для общей векторной модели. При этом считается, что для каждого уровня / определена своя метрика расстояния (¿¿(х,у). Тогда функция вычисления расстояния между двумя документами будет иметь следующий вид:

т

¿{х (5)

£=1

где — вес очередного уровня представления документа.

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

Требованиям кластеризации во многом удовлетворяет однопроходный алгоритм приближенной онлайновой инкрементальной кластеризации, схема которого приведена на Рис. 5.

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

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

Поскольку новостное сообщение теряет актуальность с течением времени, дополнительно вводятся уровни на основе модифицированной классической модели, в которой весовая модель ТР-ШР вычисляется за фиксированные

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

Рис 5. Базовый алгоритм онлайновой кластеризации

На основе правил извлечения объектов системы, GATE (Cunningam et al., 2003), адаптированных автором для русского языка, извлекаются следующие типы объектов из текста: а) персоны — действующие лица новостного сообщения; б) организации — также действующие лица новостного сообщения; в) географические объекты, упоминаемые в новости. В качестве представления документа на каждом из этих уровней используется совокупность названий выделенных объектов. Для представления синтаксической структуры в обобщенной векторной модели документа вводится понятие синтаксических групп - последовательности синтаксически связанных слов.

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

протоколу ЯББ. Комплекс обработки потоков новостных сообщений состоит из следующих модулей:

Модуль первичного сбора и предварительной обработки новостей, собирающий потоки новостных сообщений в формате ИЗБ из сети Интернет.

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

Модуль синтаксического анализа, основанный на разработанном в диссертации алгоритме гибридного синтаксического анализа

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

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

Для оценки качества разрешения морфологической омонимии в работе используется оценка точности:

Р=\. (7)

где с - количество корректных примеров, t - общее количество примеров.

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

необходимо скорректировать:

где с'- число слов с корректно разрешенной омонимией, г:'- общее число слов в предложении.

Для оценки качества снятия морфологической омонимии в экспериментах использовалось 3 критерия: а) критерий корректности части речи; б) критерий корректности части речи и падежа (в случаях, где он уместен) в) критерий корректности полного набора морфологических характеристик.

В Табл. 1 приведены результаты эксперимента по оценке качества алгоритма снятия морфологической омонимии:

Таблица 1. Результаты качества разрешения морфологической омонимии для различных

категорий слов

Критерий корректности снятия морфологической омонимии Точность, Р Скорректированная точность, Р'

Часть речи (изв. слова) 0,995 0,991

Часть речи + падеж (изв. слова) 0,964 0,959

Полный набор характеристик (изв. слова) 0,959 0,952

Часть речи (неизв. слова) 0,973 0,961

Часть речи + падеж (неизизв. слова) 0,941 0,933

Полный набор характеристик (неизв. слова) 0,913 0,903

Анализ результатов Табл. 1 показывает, что точность предложенного в диссертации алгоритма снятия морфологической омонимии превосходит результаты современных средств решения этой непростой задачи.

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

Первая - оценка доли правильно построенных связей:

Рсв = I' <*>

где п — число правильно построенных синтаксических связей, т - общее число синтаксических связей в контрольной выборке.

Вторая:

% = (Ю)

где п'— число предложений с полностью построенной синтаксической структурой, т' - число предложений в контрольной выборке.

Приведены результаты сравнения качества синтаксического анализа разработанного гибридного алгоритма с другими синтаксическими анализаторами: с лингвистическим процессором ЭТАП-3, базовым алгоритмом Ковингтона (Covington) и алгоритмом на основе максимальных остовных деревьях. Разработанный в диссертации алгоритм в Табл. 2 обозначен как

Hybrid (гибридный).

Таблица 2. Оценка точности алгоритмов синтаксического анализа

Алгоритм синтаксического анализа Среднее время анализа 1 тыс. предложений Точность анализа, доля корректных предложений, Рпп Точность аналнза, доля корректных связей, Рсн

ЭТАП-3 552 сек 0,297 0,923

MST 312 сек 0,201 0,811

Covington 223 сек 0,243 0,873

Hybrid 254 сек 0,261 0,886

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

Для получения достоверных оценок эффективности разработанного алгоритма кластеризации потоков новостных сообщений в НИЦ МГТУ МИРЭА был вручную составлен эталонный корпус новостных сообщений. Для этого было выбрано 500 сообщений каждого из новостных источников "Лента.ру", "NewsRu.COM", "Interfax" и "РИА Новости". Всего было выбрано 2000 новостных сообщений. Сообщения были выбраны за период одной недели. Оценивались следующие параметры качества кластеризации:

1) Средняя точность кластеризации, определяемая как:

Р = (И)

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

=Щ (12)

где и* - число новостей, корректно отнесенных к кластеру к, Пд-эталонное число новостей в кластере к.

С целью проверки эффективности разработанной в диссертации математической модели многоровнего представления документа для задачи кластеризации потоков новостных сообщений были проведены эксперименты на основе сравнения трех моделей признаков для кластеризации. Модель №1 -базовая модель признаков на основе поверхностных признаков документа. Модель №2 - Расширенная модель признаков на основе базовой, дополненная признаками персон, организаций и географических локаций. В модели №3 -дополнительно присутствуют признаки синтаксических групп. Результаты экспериментов представлены в Табл. 3.

Как следует из таблицы, использование расширения модели признаков синтаксическими характеристиками значительно (количество ошибок уменьшается более, чем в 2 раза) улучшает качество кластеризации, как в оценках точности, так и полноты, по сравнению с моделью №1.

Таблица 3. Влияние признаков синтаксической структуры на эффективность

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

Модель признаков Точность, Рф Полнота, Rep Скорость, сообщений/сек

Модель №1 0,809 0,743 4

Модель №2 0,835 0,791 1

Модель №3 0,841 0,809 0,26

Кроме того, производительность модели №3 достаточна для обработки потока новостных сообщений от ведущих информационных агентств, поскольку время обработки одного входящего сообщение равно 4 секундам, что соответствует более 22 ты с. сообщений в сутки.

Экспериментально оценен вклад гибридного алгоритма синтаксического анализа для алгоритма кластеризации новостных сообщений относительно использования биграмм (пар соседних слов в предложении) в качестве синтаксических групп. Такая оценка необходима, поскольку в литературе отмечено, что более 50% синтаксических связей имеют длину равной 1, следовательно, биграммы слов в значительном числе случаев соответствуют синтаксическим группам. Результаты экспериментов представлены в Табл. 4.

Таблица 4. Оценка влияния синтаксических признаков на качество кластеризации потока новостных сообщений

Способ построения пар словоформ Точность, Рф Полнота, Rep

Биграммы 0,837 0,796

Синтаксические группы 0,841 0,809

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

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

Основные результаты работы, выносимые на защиту:

1. Разработан алгоритм снятия морфологической омонимии на основе методов машинного обучения. Алгоритм обладает точностью (precision) 96% и позволяет эффективно выбирать корректный морфологический разбор заданного слова.

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

3. Уточнена существующая математическая модель признаков для синтаксического анализа русского языка. Уточненная модель учитывает не только части речи рассматриваемой словоформы, но и такие важные дополнительные морфологические характеристики как падеж, представление глагола и согласование по числу, роду и падежу между зависимыми узлами синтаксической структуры. Уточненная модель позволяет улучшить точность синтаксического анализа на 5-7%.

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

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

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

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

8. Осуществлено внедрение результатов диссертации в части алгоритмов и программ в практические разработки Центра новых информационных технологий МГТУ МИРЭА. Произведено внедрение части разработанных в диссертации алгоритмов в действующие поисково-аналитические системы компаний-разработчиков лингвистических процессоров, что подтверждено актами внедрения. Получено свидетельство о государственной регистрации программы для ЭВМ № 2014611834 от 11 февраля 2014 г. «Программа для кластеризации потоков новостных сообщений на основе многоуровневой модели представления документа». Научные положения диссертации в части алгоритмов и моделей включены в учебный процесс Факультета информационных технологий по дисциплине «Информационно-поисковые системы».

Список публикаций по теме диссертации

Публикации в .журналах перечня ВАК:

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

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

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

4. Петроченков В. В., Казенников А. О. Статистический теггер для морфологической разметки русскоязычных текстов. Автоматика и Телемеханика. М., 2013 № 10. С. 154-165.

5. Казенников А. О., Трифонов Н. И. Алгоритм автоматического извлечения информации из сообщений новостного потока. Информатизация образования и науки. М., 2014. № 1 (21). С. 111-119.

В журналах, сборниках статей и научных трудов:

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

7. Казенников А. О., Трифонов Н. И. Сравнительный анализ алгоритмов снятия лексико-семантической омонимии в задачах поиска и индексирования в информационных системах. Сб. трудов VI Регион, научно-практической, конф. «Профессиональная ориентация и методики преподавания в системе школа-вуз в условиях перехода к единой форме государственной аттестации выпускников общеобразовательных учреждений». МИРЭА, Том II, Москва 2007. С. 33-35.

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

9. Казенников А. О. Исследование алгоритмов построения деревьев зависимостей на основе машинного обучения. Сборник трудов 32-ой Конференции молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы (ИТиС'09)», Бекасово (14-18 декабря). М., 2009. ISBN 978-5-901158-11-1. С. 226-229.

10.Казенников А. О. Трифонов Н. И., Панков А. В. Информационно-

поисковая система для исследования методов разрешения лексико-семантической омонимии. Материалы III Всероссийская конференция студентов, аспирантов и молодых ученых: «Искусственный интеллект: философия, методология, инновации», МИРЭА, С. 12-15.

11.Казенников А. О. Сравнительный анализ статистических алгоритмов синтаксического анализа на основе деревьев зависимостей. Труды Международной конференции «Компьютерная лингвистика и интеллектуальные технологии» (Диалог 2010). 2010. Вып. 9 (16). С. 157162.

12.Казенников А. О. Эксперименты по созданию гибридной системы синтаксического анализа на основе системы ЭТАП-3 Сборник трудов 33-ой Конференции молодых ученых и специалистов ИППИ РАН «Информационные технологии и системы (ИТиС'Ю)», Геленджик (20-24 сентября). М.: ИППИ, 2010. С. 306-309.

13.Казенников А. О., Куракин Д. В. Сравнительный анализ алгоритмов синтаксического разбора в рамках задачи анализа новостных потоков. Труды XVIII Всероссийской научно-методической конференции Телематика-2011. СПб, 2011, С. 235-236.

14.Казенников А. О., Трифонов Н. И. Информационно-поисковая система обработки потоков новостных сообщений с гибридным алгоритмом синтаксического разбора. Современные информационные технологии. Сборник научных трудов. В 3-х ч. М:ФГУП НИИ "Восход". 2012. С. 5561.

15.Казенников А. О., Трифонов Н. И. Гибридный алгоритм синтаксического разбора для анализа новостных потоков. Современные информационные технологии и ИТ-образование / Сборник трудов VII Международной практической конференции. Под ред. проф. В.А. Сухотина -М.ИНТУИТ.РУ, 2012 1050с. ISBN 958-5-9556-0140-3 С. 564-575.

Подписано в печать: 12.05.2014 Объем: 1,0 п. л. Тираж: 100 экз. Заказ № 370 Отпечатано в типографии «Реглет» 119526, г. Москва, пр-т Вернадского, д. 39 (495) 363-78-90; www.reglet.ru

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ»

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

04201455461

КАЗЕННИКОВ АНТОН ОЛЕГОВИЧ

РАЗРАБОТКА МОДЕЛЕЙ И АЛГОРИТМОВ ДЛЯ КОМПЛЕКСА АВТОМАТИЧЕСКОЙ ОБРАБОТКИ И АНАЛИЗА ПОТОКОВ НОВОСТНЫХ СООБЩЕНИЙ НА ОСНОВЕ МЕТОДОВ КОМПЬЮТЕРНОЙ ЛИНГВИСТИКИ

Специальность 05.13.15 - «Вычислительные машины, комплексы и компьютерные сети». Область исследования №3

ДИССЕРТАЦИЯ На соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор Соловьев И. В.

Москва 2014

Содержание

Глоссарий.........................................................................................................................4

Введение........................................................................................................................10

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение..................................................................................................................108

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

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

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

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

Глоссарий

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

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