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

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

Крайнов Александр Юрьевич

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

Специальность 05.13.18 —Математическое моделирование, численные методы и

комплексы программ

АВТОРЕФЕРАТ

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

5 мД И13

Ульяновск — 2013

005543035

Работа выполнена на кафедре телекоммуникационных технологий и сетей в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Ульяновский государственный университет»

Научный руководитель: Смагин Алексей Аркадьевич,

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

Официальные оппоненты: Ярушкина Надежда Глебовна,

доктор технических наук, профессор, ФГБОУ ВПО «Ульяновский государственный . технический университет»

Капитанчук Василий Вячеславович,

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

ФГБОУ ВПО «Ульяновское высшее авиационное

училище гражданской авиации (институт)»

Ведущая организация: ФГОБУ ВПО «Поволжский государственный

университет телекоммуникаций и информатики»

Защита диссертации состоится « 27 » декабря 2013 г. в Ю00 часов на заседании диссертационного совета Д 212.278.02 при ФГБОУ ВПО «Ульяновский государственный университет», расположенном по адресу: г. Ульяновск, ул. Набережная р. Свияги, . 106, корп. 1, ауд. 703.

С диссертацией можно ознакомиться в научной библиотеке Ульяновского государственного университета, с авторефератом -— на сайте ВУЗа http://ppo.ulsu.ru и на сайте Высшей аттестационной комиссии при Министерстве образования и науки РФ — http://vak.ed.gov.ru.

Отзывы на автореферат в двух экземплярах, заверенные печатью организации, просим направлять по адресу: 432017, г. Ульяновск, ул. Л. Толстого, д. 42, УлГУ, Отдел послевузовского профессионального образования.

Автореферат разослан «_££_» кОоиор* 2013 года.

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

диссертационного совета Д 212.278.02 кандидат физико-математических наук, доцент

Волков М. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Развитие телекоммуникационных технологий за последние 15 лет привело к возникновению большого числа потоков текстовых сообщений1,2. Всё больший масштаб приобретают социальные медиа-ресурсы3,4 и электронные средства массовой информации. В настоящее время методы и системы сбора и обработки потоков текстовых сообщений из разрозненных источников представляют особый интерес для консультантов и аналитиков, работающих в самых разных сферах: бизнесе, экономике, государственном управлении и т. д.5

Традиционные методы анализа текстов, основанные на глубинной обработке естественного языка (ОЕЯ), ориентированы на взаимодействие с хранилищами документов, изменения в которые вносятся сравнительно редко: национальными корпусами текстов, электронными библиотеки, базами научных статей или архивами вебсайтов. В современных условиях эти методы малоприменимы на практике из-за больших объёмов текстовых коллекций. С другой стороны, большинство методов интеллектуального анализа текстов (ИАТ) и поверхностного ОЕЯ, исследования которых продолжаются с конца 80-х годов, не учитывают динамический характер потоков. Разработка алгоритмов ИАТ, ориентированных на обработку потоков текстовых сообщений, является одним из наиболее перспективных направлений современной информатики.6 .

Современные задачи интеллектуального анализа текстовых потоков (text stream mining) включают:

• классификацию потоков — распределение сообщений по заранее заданным группам (категориям, тематикам, событиям);

• кластеризацию потоков — распределение сообщений по группам, которые должны быть определены в процессе работы алгоритма;

• обнаружение и отслеживание тематик (topic detection and tracking), обнаружение возникающих трендов {emerging trend detection), включая выявление технологических трендов7 — идентификация новых тем, соответствующих новым явлениям, событиям, предметам и т. д.;

1 Ягунова Е. В. Основы теоретической, вычислительной и экспериментальной лингвистики // Автоматическая обработка текстов на естественном языке и компьютерная лингвистика. М.: МИЭМ, 2011. С. 70.

2 Брайчевский С. М., Ландэ Д. В. Современные информационные потоки: актуальная проблематика // Научно-техническая информация. 2005. № 11. С. 21.

1 Англ. social media; включают в себя социальные сети, блоги, микроблоги, форумы, вики-ресурсы, социальные закладки, сайты отзывов и др.

4 Hu X., Liu Н. Text Analytics in Social Media // Mining Text Data / Springer US, 2012. P. 385.

3 Kontostathis A. et al. A Survey of Emerging Trend Detection in Textual Data Mining II Survey of Text Mining I: Clustering, Classification, and Retrieval / Springer, 2003. P. 186.

4 Aggarwal С. C. Mining Text Streams // Mining Text Data / Springer US, 2012. P. 298-317.

7 Хорошевский В. Ф. Выявление новых технологических трендов: проблемы и перспективы И Доклады X111

национальной конференции КИИ-2012. Белгород: Российская ассоциация искусственного интеллекта, 2012. С. 252-258.

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

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

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

1. анализ современных методов обработки потоков текстовых сообщений для оценки ситуации в предметной области и выявление путей повышения эффективности обработки потоков;

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

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

4. выбор критериев эффективности обработки потока и разработка метода оценки эффективности итерационных алгоритмов обработки текстовых сообщений по выявленным критериям для выбора наиболее эффективного алгоритма;

5. разработка программного комплекса, поддерживающего предложенный алгоритм обработки потока, и экспериментальное исследование эффективности предложенного алгоритма.

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

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

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

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

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

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

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

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

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

Внедрение результатов работы. Система классификации заявок на модификацию программного обеспечения на основе разработанного алгоритма принята к использованию в ФНПЦ ОАО "НПО Марс".

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

Апробация результатов. Апробация основных положений диссертационной работы проведена на XV международной научно-практической конференции "Перспективы развития информационных технологий" (Новосибирск, 2013) и XII международной научной конференции "Актуальные вопросы современной техники и технологии" (Липецк, 2013).

Публикации. По теме диссертационной работы опубликовано 8 работ, 2 из которых — в изданиях из списка ВАК.

Личный вклад автора. Постановка задачи исследования осуществлена совместно с научным руководителем А. А. Смагиным. Основные теоретические и практические исследования проведены автором самостоятельно.

Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы из 112 наименований источников отечественных, зарубежных авторов и электронных ресурсов и трёх приложений. Общий объём диссертации составляет 147 страниц машинописного текста, в том числе 117 страниц основного текста и 30 страниц приложений.

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

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

Глава 1 посвящена анализу современных методов обработки потоков текстовых сообщений и выявление основных недостатков и подходов к их устранению.

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

В § 1.2 проводился сравнительный анализ классического подхода к ОЕЯ, а также методов машинного обучения, связанных с обработкой текстов. Были рассмотрены методы представления связанных и иерархических данных (математические модели) и алгоритмы их обработки. В частности, были исследованы методы классификации текстов и определены оценки эффективности этих методов.

В § 1.3 рассмотрены подходы и алгоритмы обработки потоков данных и текстовых сообщений. Для обработки последовательностей сообщений в информационных системах могут применяться три группы методов:

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

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

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

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

В § 1.5 сформулированы выводы из проведённого исследования существующих моделей, алгоритмов и программных систем для обработки текстов и потоков текстовых сообщений.

Как показал анализ предметной области, повышение эффективности обработки потоков текстовых сообщений большого объёма может быть достигнуто за счёт:

• структурирования информации методами моделирования онтологий8;

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

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

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

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

С Происшествия ) 4 ^

Политика

Праздники

Пожары

Президент

Новый год

'Новогодние4' обращения Президента к ^россиянам*.

Пожары при праздновании Нового года

^ Все сообщения )

Рисунок 1. Пример иерархии тематик информационного потока

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

8 Кузнецов О. П., Суховеров В. С., Шипилина Л. Б. Онтология как систематизация научных знаний: структура, семантика, задачи // Измерение, контроль, информатизация / Москва; Институт проблем управления РАН, 2010. С. 126138.

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

В общем виде модель системы можно представить в виде (рис. 2):

^ = Ч'С^'внеш'^внутр)'

*внеш = 0-0. О)

•^внутр — Ри>

где:

• ^внеш — внешние данные (сообщение в потоке);

• *внутР — внутренние данные (хранящиеся в базе);

• ¥ — алгоритм обработки поступившего сообщения;

• 5 — текст поступившего сообщения;

• t — момент времени, предписанный сообщению;

• Ог — множество актуальных на момент времени t сообщений;

• Сс — множество актуальных на момент времени t тематик;

• Рс — множество актуальных на момент времени { пользовательских правил.

Рисунок 2. Структурно-функциональная модель системы обработки Выход К в модели (1) представляется тройкой:

где:

• — множество тематик с из числа существующих С, к которым с большой вероятностью относится сообщение 5, с оценками вероятностей (Ь) принадлежности к ним сообщения, новизны (V) сообщения относительно тематик, новизны (мО тематик; С$л = {(с, Ъ, V, и/)}, с € €,Ь 6 [ОД], и е [ОД], IV 6 [ОД];

• к — новая тематика, к которой относится сообщение 5, с указанием родительской тематики (я) и оценкой новизны (и*); к = (г, и/), гбС^е [ОД];

• 5' — обработанный текст сообщения.

Множества Се, Рс являются результатами следующих процедур поиска:

Dt = A(Blt)l Сс = К(£,а Ре = П(Р, О,

где:

• О — база всех зарегистрированных сообщений;

• С — база всех известных тематик;

• Р — база всех имеющихся пользовательских правил. К алгоритму Ч* предъявляются следующие требования:

• обеспечение точности и полноты классификации;

• обработка сообщений в масштабе реального времени;

• выявление новых тематик;

• определение новизны сообщения.

К алгоритмам А, К, П предъявляется следующее требование:

• точный и быстрый поиск в базе.

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

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

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

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

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

В общем виде предлагаемый алгоритм обработки сообщения можно описать в виде последовательности следующих этапов:

1. Предварительная обработка текста сообщения (перевод текста к виду, пригодному для машинной обработки).

2. Первичная классификация.

3. Точная классификация.

4. Определение новизны тематик.

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

На рисунках 3 и 4 приведена декомпозиция этапов классификации. Для реализации этапа первичной классификации используется структура типа очереди с приоритетом.

Рисунок 3. Алгоритм первичной классификации сообщения

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

• Выбран метод предварительной обработки и представления текста сообщения.

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

• Разработан метод фильтрации тематик и {с, (Г).

• Разработан метод определения степени новизны сообщения У2д.

• Разработан метод определения степени новизны тематики 1УС.

• Выбран метод представления и применения правил предметной области.

• Разработан метод оценки эффективности алгоритмов итерационной классификации потоков.

Рисунок 4. Алгоритм уточнения результатов классификации сообщения

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

В качестве базового метода классификации текстов сообщений в работе был обоснован и выбран наивный байесовский классификатор (НБК)10, основывающийся на решающем правиле вероятностных классификаторов:

cres = argmaxP(c|d) = arg ma^x P (c)P(d \ c)

и двух упрощений:

• предположения о взаимной независимости признаков ("наивная" модель);

• предположения о позиционной независимости (модель "мешка слов");

С учётом упрощений, решающее правило для НБК можно записать в виде:

cres = argmajcP(c) J~J P(f\c). (2)

/6F(d)

' Марчук Ю. Н. Компьютерная лингвистика. ACT, Восток-Запад, .2007. С. 87.

10 Пескова О. В. Алгоритмы классификации полнотекстовых документов // Автоматическая обработка текстов на естественном языке и компьютерная лингвистика. M.: МИЭМ, 2011. С. 175.

Обучение этой модели классификатора состоит в нахождении априорных вероятностей классов Р(с) и условных вероятностей признаков P(f\c~) для всех классов с.

В качестве классификационных признаков для НБК выступают числовые характеристики терминов (слов или групп слов) в тексте сообщения. Метод определения числовых характеристик терминов в НБК зависит от модели представления сообщения d. Существует две основных модели представления документов11:

• как вектора номинальных значений признаков: d = (fv ...fn), ft е F;

• как вектора бинарных Индикаторов, указывающих на наличие признака в документе: d = Qfi е F(d)J).

В первом случае модель НБК называется мультиномиальной12, и оценка условной вероятности появления признака / в классе с равна относительной частоте признака f в сообщениях из класса с:

Fcj + к

где к > 0 — параметр сглаживания, Fcj — количество появлений признака / в обучающих сообщениях из класса с, F ■— множество всех признаков.

Во втором случае модель НБК называется многомерной моделью Бернулли13, и оценка условной вероятности признаков P(f\c) равна доле сообщений из класса с, которые содержат признак /.

Классификатор, описываемый формулой (2), является однозначным (однотем-ными, single-label): для каждого объекта d он определяют только один, наиболее подходящий класс cres из множества доступных. Так как текстовое сообщение может относиться к нескольким классам, необходимо разработать многозначный (многотемный, multi-label) классификатор, который способен определить множество классов Cres = {Cl с2,..., сп}, к которым относится предъявленный объект, причём п > 0.

Для преобразования однозначных классификаторов в многозначные, существует ряд стандартных приёмов14. В случае использования вероятностного классификатора наиболее простым подходом к выбору результирующих классов является использование пороговых методов. В этом случае результирующими классами полагаются те, оценка вероятности P(c\d) которых превышает некоторое пороговое значение 7г:

Cres = {се C\P(c\d) > тг}.

" McCallum A., Nigam К. A comparison of event models for Naive Bayes text classification // AAAI Workshop on Learning for Text Categorization, 1998.

12 Маннинг К. Д., Рагхаван П., Шютце X. Введение в информационный поиск. Вильяме, 2011. С. 267.

13 Маннинг и др., указ. изд., с. 272.

14 Read J. Scalable Multi-label Classification // PhD Thesis / University of Wakaito, 2010. P. 64. URL: http://research-commons.waikato.ac.nz/handle/10289/4645

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

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

Упорядочим значения ряда Rc = P(c\d) по возрастанию и обозначим полученный ряд /?<?: Äg < R[ < ••• < Rf4 (М — количество классов). Определим индекс компоненты вектора, соответствующей максимуму разности между соседними значениями:

U = arg max(i?f+1 — Rf)

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

Для оценки применимости разработанного метода был проведён вычислительный эксперимент, в ходе которого предложенный метод (на основе статического порога) сравнивался с методом бинарного соответствия и методами на основе статического порога. В основе всех трёх методов использовался мультиномиальный НБК, выбор признаков производился на основе стандартного эвристического метода по методу взаимной информации и количеством признаков к = 500. В качестве экспериментальных данных были использованы 2289 новостных сообщений с сайта www.rg.ru, распределённые по 33 тематикам. Критериями эффективности выступали функция потерь Хэмминга (HL), точность (Р), полнота (R), F-мера (F), аккуратность (А) и доля точных соответствий (ЕМ)15. Результаты (табл. 1) эксперимента позволяют заключить, что разработанный метод даёт в целом лучшие результаты.

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

HL Р R F А ЕМ

Бинарное соответствие 0,0429 0,3430 0,4461 0,3593 0,3205 0,2238

Статический порог (л = 0,05) 0,0565 0,5130 0,6383 0,5327 0,4733 0,3242

Динамический порог 0,0346 0,5691 0,5210 0,5303 0,5028 0,4247

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

" Madjarov G. et al. An Extensive Experimental Comparison of Methods for Multi-label Learning // Pattern Recognition. 2012. Vol. 45. № 9. P. 3084-3104.

практике для НБК, может быть представлена следующей последовательностью шагов (см. рис. 5):

1. Начальное множество признаков Р полагаем равным множеству всех терминов из всех сообщений.

2. Удаление из Р стоп-слов по заданному словарю (как правило, в него входят служебные слова: предлоги, союзы, частицы и др.), а также редких терминов, которые могут привести к переобучению.

3. Вычисление меры полезности щ термина t как максимального значения заданной метрики полезности (7(1, с) термина Ь для всех классов с, участвующих в классификации: щ = ша_х и (£, с).

4. В качестве множества признаков Р выбираем к терминов с максимальной мерой щ.

Рисунок 5. Процедура выбора классификационных признаков текста

Метрика полезности и значение k = |F|, приводящие к оптимальному выбору признаков, зависят конкретных задач и определяются на основании эмпирических исследований16.

Из наиболее распространённых метрик полезности для настоящего исследования были выбраны следующие: взаимная информация (MI), знаковая взаимная информация (SMI), параметр хи-квадрат (СШ), коэффициент корреляции (СС), отношение шансов (OR), квадратичное отношение шансов (ORS) и документная частота термина (DF). Метрики MI, СШ, ORS, DF являются двусторонними (оценивающими полезность признака для классификатора в целом), метрики SMI, СС, OR — односторонними (оценивающими полезность признака для отдельного класса).

Для оценки наилучшего метода выбора признаков для разработанного многозначного классификатора был проведён вычислительный эксперимент. В качестве экспериментальных данных были использованы 5 различных наборов данных с числом классов 9—33 и средним числом сообщений в классах 12—300. Фильтрация (шаг 2 из вышеприведённой схемы) не производилась. Результаты для бернуллиевского НБК и набора данных из 33 тематик мощностью 50-90 сообщений каждая (далее — АЗЗ) приведены на рис. 6.

Результаты, в частности, показывают, что для набора данных АЗЗ для |F| < 1000 оптимальными метриками выбора признаков являются MI и SMI при |F| « 178.

16 Zheng Z., Wu X., Srihari R. Feature selection for text categorization on imbalanced data // ACM SIGKDD Explorations Newsletter. 2004. Vol. 6. J& 1. P. 80-89.

0,00 . ________________,_,_______________- ...

1_10_ 100 1000 10000 100000

|-*-CHI ОС-«-Ml ORS ■»• SMI -*-Df Количеств призиаюв

Рисунок 6. Эффективность метрик выбора признаков для эвристической процедуры, бернуллиевской модели НБК и набора данных АЗЗ

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

Для оценки возможности устранения несбалансированности в настоящей работе предложена модификация стандартной процедуры, заключающаяся в том, что на шаге 3 формируются множества Uc = {ut c} наилучших признаков для всех отдельных классов с, а на шаге 4 итоговое множество признаков формируется объединением I наилучших признаков из каждого класса с. (Заметим, что при этом \F\ < IM, где M — количество классов).

Предложенная схема была испытана на тех же наборах данных. Аналогичные результаты для набора АЗЗ показаны на рис. 7.

1 10 100 1000 10000

!•*• CHI -*■ СС MI -»■ ORS SMI PF OR I Количвсяо признано!

Рисунок 7. Эффективность метрик выбора признаков для модифицированной процедуры, бернуллиевской модели НБК и набора данных АЗЗ

Результаты показывают, что количество терминов удалось сократить до 2 для каждого класса (|Р| « 66). Лучшей метрикой стала М1, эффективность классификации возросла с 0,5841 До 0,6406.

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

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

Временным рядом тематики с назовём последовательность Ус = {ус,т}> х = 1,..., Т - 1, где уС;Т — количество сообщений, поступивших за период т с момента начала наблюдений и принадлежащих тематике с. Введём функцию прогнозирования ряда на текущий период времени Т:

Ус,т = 5(УС)

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

Р(С,Т)= Ус-!

Лс'есУс', Т

Анализ экспериментальных данных показал, что характер временных рядов для различных тематик существенно различается (рис. 8).

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

• для рядов, имеющих выраженный периодический характер (рис. 6, а) использовался метод прогнозирования на основе декомпозиции временного ряда;

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

'I 14 | 12

I 4

г

I А Л Г 1М А

и!

л ШМшХшШ

50 0,4

1 40 й 0,3

|| 30 Г

| 20 10,1

I 10 о.о •0,1

0 ____________ ,._____________ 1 ----л- - --------'--а----------------

А) В

30-дек 14-яме 29-янв 13-фее 28-фев 15-мар 30-мар 14-апр 29-апр

Да гя

О 4 8 12 16 20

24 28 32 Сдвиг

30-дек 14-янв 29-яне 13-фее 28-фев 15-мар 30-мар 14-апр 29-апр

Дата

24 28 32 Сдвиг

к) | III М>л1

I пиг ™ ^

30-дек 14-янв 29-янв 13-фев 28-фев 15-мар 30-мар 14-апр 29-апр

Дата

12 16 20

30-дек 14-янв 29-янв 13-фев 28-фев 15-мар 30-мар 14-апр 29-апр

Дата

24 28 32 Сдвиг

30-дек 14-янв 29-янв 13-фев 28-фвв 15-мар 30-мар 14-апр 29-апр

Дата

' 12 16 20 24 28 32 Сдвиг

Рисунок 8. Временные ряды различных тематик и их автокорреляционные функции: а) "Экономика"; б) "Праздники"; в) "Кризис на Кипре"; г) "Челябинский метеорит";

д) "Лесные пожары"

Базовыми параметрами антецедентов в правилах, определяемых пользователем, являются:

• результат классификации Cres (множество тематик на выходе классификатора);

• темпоральные отношения между тематиками и сообщениями.

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

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

• оценка новизны сообщения по отношению к тематикам из Cres\

• оценка новизны тематик из Cres.

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

S(d1( d2, F0) = , =====—, =, ^

JZftFotf е Fid,)] ■ Jz/eFo[f е F(d2)]'

где F(x) — функция, возвращающая множество отличительных признаков документа х, [х] — индикатор булевого значения (0, если * ложно, и 1 — если истинно).

Под новизной сообщения в настоящей диссертационной работе понимается набор количественных и качественных параметров, не позволяющих отнести сообщение ни к одной известной тематике. Для количественной оценки новизны введена метрика степени новизны сообщения d по отношению к тематике z, которая формально определяется как:

vdiZ = E(d,c,z); (4)

где с — наиболее вероятный класс из потомков z; E(d, с, z) - максимальная косинусная мера сходства (ф. 3):

F(d, с, z) = тэх^ S(d, g, F(z)) ;

D (с) — функция, возвращающая множество документов класса с; F (с) — функция, возвращающая множество отличительных признаков класса с. Под отличительными признаками F(c) будем понимать подмножество классификационных признаков таких, которые являются общими для отдельной тематики с.

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

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

|£>(с)|

(5)

w(c,z) =

0001

С001

+ \D{c)\

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

С

Начало

Р := период рассмотрения

I начальная дата

Е S + Р

D := сообщения за период [S, Е)

3

Обучение классификатора по сообщениям Р

S := S + Р Е:=Е + Р

D := сообщения за период [S, £)

Ь, оценка качества классификации сообц^ний D

Рисунок 9. Алгоритм оценки итерационных многозначных классификаторов

с частичным обучением

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

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

Для реализации системы были выбраны следующие средства:

• языковая платформа Java;

• интерфейсная среда SWT и платформа Eclipse RCP 4;

• система маршрутизации сообщений Apache Camel;

• нереляционная документная база данных MongoDB;

• машина исполнения правил Drools Expert;

• система обработки потоков событий Drools Fusion;

• библиотека визуализации графов Eclipse Zest;

• библиотека визуализации диаграмм Highcharts.

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

Рисунок 10. Общая архитектура системы обработки потоков сообщений

Экспериментальная оценка производилась на основе 3416 новостных сообщений и 55 тематик. За начальную дату I было взято 1 января 2013 года, период рассмотрения Р равнялся 14 дням. Показано (рис. 11, 12), что предложенный алгоритм обработки потока текстовых сообщений превосходит наиболее близкий по вычислительной сложности алгоритм бинарного соответствия.

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

Описывается работа комплекса с новостными сообщениями, агрегируемыми в реальном времени с ряда новостных ресурсов (а именно, "Российской газеты" — www.rg.ru, "РИА Новости" — www.ria.ru, "Газета.Ру" — www.gazeta.ru, "Лента.Ру" — www.lenta.ru). Приводится пример работы комплекса с заявками пользователей программных продуктов и услуг (а именно, пожеланиями пользователей с сайта Рефор-мал.Ру). Приводится пример работы комплекса с потоком обращений граждан в открытые сервисы юридических консультаций. Рассматривается методика работы с текстами, создаваемыми в реальном времени пользователями открытых социальных медиа-ресурсов (а именно, Википедии — ru.wikipedia.org).

о.оо

Номер периода времени

Рисунок 11. Оценка эффективности алгоритма бинарного соответствия (В Я) и разработанного алгоритма (ГЯ) по метрике точности с периодом 14 дней

4 5

[-a.br -г-тй] Номер периода времени

Рисунок 12. Оценка эффективности алгоритма бинарного соответствия (ВЛ) и разработанного алгоритма (ТЕ) по метрике полноты с периодом 14 дней

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

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

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

В изданиях из перечня ВАК:

1. Крайнов А. Ю., Смагин А. А. Разработка комплекса анализа ошибок в корпоративных информационных системах // Известия Самарского научного центра Российской академии наук. — Самара, 2013. — Т. 15.—№ 4 (3). — С. 688-692.

2. Крайнов А. Ю. Разработка многозначного наивного байесовского классификатора на основе пороговой оценки // Научно-технический вестник Поволжья. — Казань, 2013. — № 5. — С. 225-228.

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

3. Куприянов А. А., Мельниченко А. С., Крайнов А. Ю. Подход к созданию виртуальной организации проектирования и изготовления программных изделий ИАСУ // Автоматизация процессов управления. — 2009. — № 3. — С. 33-43.

4. Крайнов А. Ю. Об одном варианте применения искусственных нейронных сетей для обработки текстов на естественном языке И Учёные записки Ульяновского государственного университета. — Ульяновск, 2011. — С, 225—230.

5. Захаров В. Г., Крайнов А. Ю., Липатова С. В., Смагин А. А. Построение системы доставки обновлений программных продуктов // Учёные записки Ульяновского государственного университета. — 2012. — № 1 (4). — С. 161—174.

6. Крайнов А. Ю. Применение систем принятия решений в системах сопровождения программной продукции // Учёные записки Ульяновского государственного университета. — Ульяновск, 2012. — № 1 (4). — С. 194-200.

7. Крайнов А. Ю. Построение системы обработки новостного потока информации // Сборник докладов XV международной научно-практической конференции "Перспективы развития информационных технологий". — Новосибирск: ЦРНС, 2013. —С. 12-16.

8. Крайнов А. Ю. Подход к классификации и обнаружению тематик в информационных потоках текстовых сообщений // Сборник докладов ХП международной научной конференции "Актуальные вопросы современной техники и технологии". — Липецк, 2013. — С. 20-23.

Подписано в печать 22.11.2013. Формат 60 х 84/16. Гарнитура Times New Roman. Усл. печ. л. 1,0.

Тираж 120 экз. Заказ № 153 ¡2.^/3

Отпечатано с оригинал-макета в Издательском центре Ульяновского государственного университета 432017, г. Ульяновск, ул. Л. Толстого, 42

УЛЬЯНОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

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

КЛАССИФИКАТОРА

Специальность 05.13.18 — Математическое моделирование, численные методы и комплексы программ

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

04201455451

Крайнов Александр Юрьевич

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

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

Ульяновск

— 2013

Оглавление

Введение...................................................................................................................5

Глава 1. Сравнительный анализ современных подходов и систем обработки потоков текстовых сообщений..........................................................10

1.1. Проблема обработки потоков текстовых сообщений............................10

1.1.1. Современное состояние обработки естественного языка как направления искусственного интеллекта.....................................................10

1.1.2. Области применения алгоритмов обработки потоков

текстовых сообщений.....................................................................................12

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

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

1.2.1. Классический подход к обработке естественного языка..................15

1.2.2. Базовые методы интеллектуального анализа текстов.......................16

1.2.3. Иерархические методы машинного обучения...................................20

1.2.4. Оценка эффективности методов классификации текстов и экспериментальные коллекции документов................................................22

1.2.5. Представление лингвистических данных...........................................24

1.3. Подходы и алгоритмы обработки потоков данных................................26

1.3.1. Анализ и прогнозирование временных рядов....................................26

1.3.2. Обработка информационных потоков................................................27

1.3.3. Интеллектуальный анализ последовательностей..............................29

1.4. Средства и системы обработки текстовой информации........................31

1.4.1. Системы обработки естественного языка..........................................31

1.4.2. Системы обработки потоковых данных.............................................34

1.4.3. Функциональная архитектура систем интеллектуального

анализа текстов................................................................................................37

1.5. Выводы........................................................................................................40

Глава 2. Разработка алгоритма классификации текстовых сообщений и обнаружения трендов в потоках текстовых сообщений...................................41

2.1. Математические модели предметной области........................................41

2.1.1. Математическая модель потока текстовых сообщений....................41

2.1.2. Математическая модель системы обработки потока текстовых сообщений........................................................................................................44

2.2. Общая структура алгоритма иерархической обработки текстового сообщения в потоке...........................................................................................47

2.3. Предварительная обработка текста сообщения......................................50

2.4. Этап первичной классификации...............................................................52

2.4.1. Вероятностная классификация текстов..............................................54

2.4.2. Разработка многозначного наивного байесовского классификатора...............................................................................................55

2.4.3. Выбор классификационных признаков сообщений..........................60

2.4.4. Оценка априорных вероятностей тематик.........................................67

2.4.5. Фильтрация нерелевантных тематик..................................................70

2.4.6. Новизна сообщения..............................................................................72

2.5. Этап точной классификации.....................................................................73

2.6. Этап определения новизны тематик........................................................74

2.7. Применение пользовательских правил....................................................75

2.8. Разработка метода оценки алгоритмов оперативной классификации потоков текстовых сообщений.............................................76

2.9. Выводы........................................................................................................78

Глава 3. Создание программного комплекса обработки потоков текстовых сообщений...........................................................................................79

3.1. Определение требований к системе обработки потоков

текстовых сообщений.......................................................................................79

3.1.1. Определение требований к корпоративным системам

принятия решений...........................................................................................79

3.1.2. Определение требований к процессу разработки..............................80

3.1.3. Определение требований к подсистеме визуализации.....................80

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

3.2. Проектирование системы обработки потоков текстовых сообщений.. 82

3.2.1. Разработка архитектуры системы обработки потоков

текстовых сообщений.....................................................................................82

3.2.3. Структура данных предметной области.............................................84

3.3. Программная реализация системы обработки потоков

текстовых сообщений.......................................................................................86

3.3.1. Выбор средств реализации системы обработки потоков текстовых сообщений.....................................................................................86

3.3.2. Описание программных компонентов системы обработки потоков текстовых сообщений......................................................................88

3.3.3. Структура компонентов обработки сообщений................................89

3.3.4. Адаптеры для источников сообщений................................................95

3.4. Описание пользовательского интерфейса системы обработки потоков текстовых сообщений........................................................................96

3.5. Экспериментальная оценка эффективности алгоритма

обработки потоков текстовых сообщений......................................................98

3.6. Выводы......................................................................................................101

Глава 4. Применение системы в практических задачах обработки

потоков.................................................................................................................102

4.1. Обработка потока новостных сообщений.............................................102

4.2. Обработка потока заявок на модификацию программных продуктов 104

4.3. Обработка потока обращений пользователей юридических форумов 106

4.4. Обработка потока статей в социальных медиа-ресурсах.....................107

4.5. Выводы......................................................................................................109

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

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

Приложение А. Эффективность классификации при применении

эвристической процедуры выбора признаков..................................................118

Приложение Б. Эффективность классификации при применении

сбалансированной процедуры выбора признаков............................................123

Приложение В. Временные ряды тематик новостных сообщений.................128

Введение

Проблема обработки информационных потоков была чётко обозначена ещё в 80-е годы XX века. Как отмечено в [1, с. И], "В середине 50-х годов резко возросшие темпы научно-технического прогресса привели к информационному взрыву — скачкообразному увеличению объемов создаваемой и используемой информации, усложнению существовавших и образованию новых информационных потоков, которые захлестнули информационные системы общества. Наиболее ярко информационный взрыв проявился в вида лавинообразного роста потоков публикаций в области технических, естественных и гуманитарных наук. Менее заметным для широкой общественности, но не менее серьезным по своим масштабам и социальным последствиям было резкое увеличение объёма документации, используемой в сфере управления, сопровождавшееся соответствующим ростом количества информационных материалов в области производства и технологии. Общий аффект информационного взрыва усиливался возрастанием информационных потоков в системах массовой информации, возможности которых необычайно расширились в связи с развитием печати, радио, телевидения и сетей связи".

Со времён выхода этой книги положение дел в области обработки потоков текстовых сообщений несколько изменилось. С одной стороны, во второй половине 90-х годов были созданы и стали развиваться эффективные системы информационного поиска глобального масштаба, так называемые поисковые машины (search engines). С другой стороны, за последние 15 лет дальнейшее развитие телекоммуникационных технологий привело к возникновению большого числа новых источников потоков текстовых сообщений. Всё больший масштаб приобретают социальные медиа-ресурсы (социальные сети, блоги, микроблоги, вики и др. [2]) и электронные средства массовой информации. В настоящее время методы и системы сбора и обработки потоков текстовых сообщений из разрозненных источников представляют особый интерес для аналитиков, работающих в самых разных сферах: бизнесе, экономике, государственном управлении и т. д. [3, с. 186]

Традиционные методы анализа текстов, основанные на глубинной обработке естественного языка (ОЕЯ), ориентированы на взаимодействие с хранилищами документов, изменения в которые вносятся сравнительно редко: национальными корпусами текстов, электронными библиотеки, базами научных статей или архивами веб-сайтов. В современных условиях эти методы малоприменимы на практике из-за больших объёмов текстовых коллекций. С другой стороны, большинство методов интеллектуального анализа текстов (ИАТ, text mining) и поверхностной ОЕЯ, исследования которых продолжаются с конца 80-х годов, не учитывают динамический характер потоков. Разработка алгоритмов ИАТ, ориентированных на обработку потоков текстовых сообщений, является одним из наиболее перспективных направлений современной информатики.

Современные задачи интеллектуального анализа текстовых Потоков (text stream mining) включают:

• классификацию потоков — распределение сообщений по заранее заданным группам (категориям, тематикам, событиям);

• кластеризацию потоков — распределение сообщений по группам, которые должны быть определены в процессе работы алгоритма;

• обнаружение и отслеживание тематик (topic detection and tracking), обнаружение возникающих трендов (emerging trend detection), включая выявление технологических трендов — идентификация новых тем, соответствующих новым явлениям, событиям, предметам и т. д.;

• анализ эволюции потоков (evolution analysis) — исследование динамики отдельных тем, а также их взаимодействий с течением времени.

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

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

и компьютерные модели этих потоков и методы обработки входящих в них сообщений.

Цели и задачи исследования.

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

1. анализ современных методов обработки потоков текстовых сообщений для оценки ситуации в предметной области и выявление путей повышения эффективности обработки потоков;

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

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

4. выбор критериев эффективности обработки потока и разработка метода оценки эффективности итерационных алгоритмов обработки текстовых сообщений по выявленным критериям для выбора наиболее эффективного алгоритма;

5. разработка программного комплекса, поддерживающего предложенный алгоритм обработки потока, и экспериментальное исследование эффективности предложенного алгоритма.

Методы исследования.

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

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

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

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

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

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

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

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

Практическая и теоретическая значимость исследований.

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

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

Апробация основных положений диссертационной работы проведена на XV международной научно-практической конференции "Перспективы развития информационных технологий" (Новосибирск, 2013) и XII международной научной конференции "Актуальные вопросы современной техники и технологии" (Липецк, 2013).

Личный вклад автора. Постановка задачи исследования осуществлена совместно с научным руководителем А. А. Смагиным. Основные теоретические и практические исследования проведены автором самостоятельно.

Структура и объём работы.

Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы из 112 наименований источников отечественных, зарубежных авторов и электронных ресурсов и одного приложения. Общий объём диссертации составляет 147 страниц машинописного текста, в том числе 117 страниц основного текста и 30 страниц приложений.

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

1.1. Проблема обработки потоков текстовых сообщений

1.1.1. Современное состояние обработки естественного языка как направления искусственного интеллекта

Анализ и понимание текстов на естественном языке занимали важную нишу в исследованиях по искусственному интеллекту с момента возникновения этой науки. В течение многих десятилетий работы в этом направлении были сосредоточены в областях, называемых "вычислительной лингвистикой" и "обработкой естественного языка". Целью вычислительной лингвистики (BJI, computational linguistics, CL) является "построение логико-лингвистических моделей и соответствующих им алгоритмов и программ" [4, введение]. В отличие от BJI, где большое значение имеет теоретическая лингвистическая корректность и адекватность предложенных моделей, обработка естественного языка (ОЕЯ, natural language processing, NLP) сосредоточена "на моделировании всего того, что изучает лингвистика в целом" [4].

Первоначально обе этих области, преимущественно, стремились построить точные языковые модели, основанные на формальном синтаксическом и семантическом анализе; этот подход получил название "глубинная ОЕЯ", deep NLP, DNLP [5] (иногда применяется термин "символическая ОЕЯ" — symbolic NLP). Потребность в точных моделях была обусловлена тем, чт�