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

094615448

МОРДВИНОВ АЛЕКСЕЙ ВЯЧЕСЛАВОВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МОДЕЛИ ТЕКСТА ДЛЯ ЕГО КАТЕГОРИЗАЦИИ

Специальность 05.13.01. - "Системный анализ, управление и обработка информации (в науке и промышленности)" по техническим наукам

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

- 2 ДЕК ?010

Нижний Новгород 2010 г.

004615448

Работа выполнена на кафедре "Вычислительные системы и технологии" Нижегородского государственного технического университета им. Р. Е. Алексеева.

Научный руководитель:

доктор технических наук, профессор Ломакина Любовь Сергеевна

Официальные оппоненты:

доктор технических наук, профессор Моругин Станислав Львович

кандидат физ-мат. наук, доцент Ляхов Александр Федорович

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

Всероссийский институт научной и технической информации (ВИНИТИ РАН, г. Москва)

Защита диссертации состоится "о9" декабря 2010 года в £5" часов в аудитории 1258 на заседании диссертационного совета Д.121.165.05 при Нижегородском государственном университете им. Р. Е. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. Р. Е. Алексеева

Автореферат разослан ноября 2010 года.

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

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

А. С. Суркова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность работы.

За последние 10-15 лет задачи управления документами на основании их содержимого (обобщенное название извлечение информации) приобрели особенно важное значение в области информационных систем ввиду постоянно повышающейся доступности документов в цифровой форме и вытекающей отсюда необходимости получать к ним доступ максимально быстрыми и удобными способами. Одной из таких задач является категоризация текстов (синонимы - классификация по категориям, определение тематики) - задача распределения текстов на естественном языке по тематическим категориям из заранее определенного набора. Появление задачи категоризации текстов (КТ) относится к началу 60-х годов прошлого века, но только в 90-х она приобрела свою истинную значимость благодаря возросшему прикладному интересу и доступности более мощных аппаратных средств. КТ сейчас применяется во многих контекстах, начиная от индексирования документов на основе контролируемого словаря, заканчивая фильтрацией документов, автоматической генерацией метаданных, заполнением иерархических каталогов Web ресурсов, атрибуцией текстов неизвестных авторов и вообще в любых приложениях, требующих автоматизированной организации или диспетчеризации документов.

До конца 80-х наиболее популярным подходом к КТ, по крайней мере, в сообществе, занимающемся прикладными исследованиями, была инженерия знаний. Этот подход состоит в ручном задании набора правил на основании знаний экспертов о том, как классифицировать документы по заданным категориям. Среди исследователей в этой области можно выделить В.М. Глушкова, Г.С. Осипова, Д.Э. Попова, Д.А. Поспелова, Т.А. Гаврилову, В.Ф. Хорошевского. В 90-х этот подход стремительно утратил популярность (особенно в исследовательском сообществе) в пользу машинного обучения. В

соответствии с этим подходом производится индуктивное автоматическое построение текстового классификатора с помощью обучения на наборе заранее классифицированных документов. Важную роль в развитии машинного обучения сыграли В. Н. Вапник и А. Я. Червоненкис, активными исследованиями в области KT занимаются С. Apte, F.J. Damerau, N. Fuhr, F. Sebastiani, W.W. Cohen, S.T. Dumais, T. Joachims, S.L. Lam, L.S. Larkey, D.D. Lewis, Y. Yang.

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

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

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

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

- сформулировать требования к разрабатываемой модели текста;

- разработать алгоритм для индексирования текста, то есть для выбора из текста элементов, на основе которых будет построена модель;

- разработать модель текста в виде дерева М-грамм и проанализировать ее свойства;

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

- разработать методику категоризации документов, моделируемых в виде деревьев Ы-грамм;

- разработать тестовую систему, позволяющую получить оценки эффективности методики КТ;

- протестировать разработанную методику КТ с различными алгоритмами классификации данных;

- провести эксперимент с целью сравнения эффективности методик КТ, использующих представление текста в виде вектора слов и в виде дерева М-грамм;

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

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

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

1. Предложена модель текста в виде дерева И-грамм, позволяющая

использовать ее в любых приложениях, связанных с решением задачи

5

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

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

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

Практическая ценность работы.

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

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

На защиту выносятся:

1. Модель текста в виде дерева N-грамм.

2. Алгоритмы представления текстовых моделей в виде спектров N-грамм для получения возможности динамической настройки точности (детализации) модели после ее создания.

3. Методика категоризации текстов, построенная на основе использования предложенной модели текста.

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

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

Результаты работы использованы в НИОКР "Использование алгоритмов сжатия данных в задаче определения авторства текста" для программы УМНИК (Участник Молодежного Научно-Инновационного Конкурса) фонда содействия развитию малых форм предприятий в научно-технической сфере, № 08-2-7335.

Апробация работы.

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

- VII международная научно-техническая конференция НТИ 2007 "Информационные технологии" ВИНИТИ РАН, г. Москва, 2007 г.;

- VII международная молодежная научно-техническая конференция "Будущее технической науки" (г. Нижний Новгород, 2007);

- XIV Международная научно-техническая конференция "Информационные системы и технологии - ИСТ" (Н1 ТУ, г. Нижний Новгород, 2008);

- VIII международный симпозиум "Интеллектуальные системы" -INTELS'2008 (г. Нижний Новгород-Москва,МГТУ им. Н.Э. Баумана-НГТУ им.Р.Е. Алексеева 2008);

- Международная открытая научно-практическая конференция "Современные проблемы информатизации" (г. Воронеж, 2008);

- XV Международная научно-техническая конференция "Информационные системы и технологии - ИСТ-2009" (г. Нижний Новгород, 2009);

- XVI Международная научно-техническая конференция "Информационные системы и технологии - ИСТ-2010" (г. Нижний Новгород, 2010);

Публикации.

Основные положения диссертационной работы отражены в 10 работах, опубликованных соискателем лично или в соавторстве в научных изданиях, в том числе в одной статье, представленной в рецензируемом издании из перечня ВАК РФ.

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

Диссертационная работа состоит из введения, четырёх глав, заключения, библиографического списка и приложений. Общий объём работы 153 страницы текста, содержащего 47 рисунков и 8 таблиц. Список литературы содержит 116 наименований.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ Во введении дается общая характеристика работы, обосновывается актуальность исследований, формулируется цель работы, раскрывается научная новизна и практическая значимость полученных результатов. Дается краткий обзор содержания по главам.

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

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

Категоризация текстов (КТ) - задача распределения текстов на естественном языке по тематическим категориям из заранее заданного набора. Развиваясь с 60-х годов XX века, задача КТ стала объектом пристального внимания со стороны исследователей лишь в 90-х годах благодаря прорыву в таких областях как микроэлектроника, сетевые коммуникации, Интернет. Долгое время наиболее популярным подходом к КТ была инженерия знаний, заключающаяся в ручном задании набора правил, в соответствии с которыми документы должны классифицироваться по разным категориям. В настоящее время более перспективным считается машинное обучение, основной идеей которого является построение автоматического классификатора текстов путем его обучения на наборе заранее классифицированных экспертом документов.

КТ - задача присвоения булевого значения каждой паре (dj,c,)eDxC, где D - домен документов, а С = {с,,...,^} - множество

заранее заданных категорий. Значение Т (Tiue), присвоенное (rf;,c,), обозначает решение классифицировать документ d} в категорию с,; тогда как значение F (False) обозначает решение не классифицировать документ dj в категорию с,. Более формально, ставится задача аппроксимировать неизвестную целевую функцию Ф:DxC-+{T,F] (которая описывает как документы должны быть классифицированы) посредством функции 0:DxC-*{T,F}, называемой классификатором, такой что Ф и Ф "совпадают как можно лучше".

При решении задачи категоризации подразумевается, что:

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

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

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

Рис.1 - Фазы построения системы КТ

В результате анализа текущей ситуации в области КТ была

сформулирована задача диссертационной работы: необходимо разработать

модель текста для использования как минимум в задаче КТ, которая

обеспечивала бы более высокую эффективность категоризации по сравнению

10

с моделью вектора слов, была бы индифферентна по отношению к используемому в системе классификатору, а также позволила бы:

- Учитывать композиционную семантику документа;

- Устранить необходимость применения морфологического анализа перед индексированием документа;

- Обеспечить большую устойчивость к ошибкам и опечаткам в тексте;

- Более гибко реализовать этап снижения размерности пространства элементов;

- Динамически корректировать представление документа уже после создания модели в зависимости от требований прикладной задачи.

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

С точки зрения системного подхода текст обладает всеми признаками стационарной системы: с одной стороны это целостный объект, в то же время мы можем выделить наименьшие элементы текста, взаимодействие которых по определенным правилам порождает текст как систему. Кроме того, текст обладает четкой иерархической структурой, где каждый элемент более низкого уровня входит в состав какого-либо элемента более высокого уровня иерархии как показано на рис. 2:

с - Уровень слов

Б - Уровень букв

Л - Уровень предложений

Рис. 2 - Структура текстовой системы

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

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

Пусть задана последовательность Я = {з,,^,...,^,} из 1| элементов. И-граммой будем называть любую подпоследовательность последовательности Я из N подряд идущих элементов: 5" М-граммы чаще всего используются в контексте создания вероятностных моделей для предсказания появления очередного элемента подобной последовательности. Мы будем использовать термин "Ы-грамма" только лишь для обозначения общего вида составных элементов модели, которые, в соответствии с этим определением и ограничениями, указанными выше, могут быть как отдельными буквами, так и последовательностями букв произвольной длины. Разбиение строки символов на М-граммы проиллюстрировано на рис. 3 для слова "ТЕКСТ".

Рис. 3 - Все возможные Ы-граммы для строки "ТЕКСТ' Учитывая требования к модели текста, обозначенные в постановке задачи, было принято решение, что в процессе отбора Ы-грамм:

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

- не должно устанавливаться ограничений на длину N - метод отбора И-грамм, составляющих модель, из исходного текста должен выбирать только статистически значимые для него Ы-граммы, причем конкретная интерпретация понятия "статистической значимости" задается методом отбора Ы-грамм;

Исходя из поставленных задач было решено использовать следующий способ выбора Ы-грамм из текста: алгоритм последовательно считывает символы из входного потока по одному и накапливает их в буфере /. Когда какой-либо символ считывается и присоединяется к I, строка I ищется в списке уже отобранных Ы-грамм. Пока строка I находится в словаре, процесс продолжается. На определенном шаге добавление нового символа л: приводит к тому, что поиск оказывается неудачным: строка I находится в словаре, а строка 1х уже нет. В этом случае алгоритм сохраняет строку 1х в списке и инициализирует строку I символом л:. Дальше процесс

продолжается пока не будет обработан весь текст. Работа описанного алгоритма проиллюстрирована на рис. 4.

...з1г_а(1_еа51тапЯеаз11у_1еа5е5_5еа_5юк_5еа15...

Ы-граммы

Обработка гт

Поиск

1

Поиск

!="_' [—1="_е" !—1=- еа" Ь

1Г "" '"

Поиск

и ■

__>

Добавление новой Ы-граммы

1

| 1='а"~!

Рис. 4 - Пример работы алгоритма выбора И-грамм из текста Так как полученный список Ы-грамм не информативен, то на его основе создается модель текста в виде леса деревьев или одного дерева с фиктивным корнем (см. рис. 5). Пусть имеется алфавит ={а,,а2,...,а.} из и символов, тогда модель текста будет содержать максимум п деревьев, каждое из которых также может содержать максимум п под-деревьев и т.д. Узлами и листьями деревьев являются символы входного алфавита. Если говорить о представлении модели в виде одного дерева с фиктивным корнем, то максимальное количество узлов т -го уровня равно «".

Подобное представление модели отражает процесс отбора Ы-грамм алгоритмом, кроме того позволяет дополнительно не хранить статистическую информацию об элементах модели. Вес конкретной 14-граммы = {х,,^,...^,}, содержащейся в дереве, Р(Б) = т+1, где т -

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

0

Рис. 5 - Пример дерева И-грамм Для того, чтобы сократить размерность модели и настроить ее для конкретной задачи (это может быть не обязательно задача КТ, а, теоретически, любая задача из области извлечения информации) или конкретного классификатора, применяется представление модели в виде спектра Ы-грамм определенной фиксированной длины N. Значение N может варьироваться от 1 до Ьюа - максимальной длины входящей в модель Ы-граммы. Например, спектр с детализацией для дерева,

изображенного на рис. 5, будет выглядеть, как показано на рис. 6:

9"

8

.6

4

3

2

о

' а _ .. б ^ ь в......г

Рис. 6 - Спектр с уровнем детализации Z = 1

Спектр с уровнем детализации Z = 2 для того же дерева показан на рис. 7:

.0 -'аН: ¿¿бе,«;.' бл ве ;;вУ.„¿.го■■ ;

Рис. 7 - Спектр с уровнем детализации Z = 2 В третьей главе объясняется необходимость следования принципам модульного дизайна при разработке системы КТ; рассматривается моделирование текста в виде дерева И-грамм с точки зрения модульного дизайна; описываются экспериментальная методики по созданию системы КТ.

Одним из основных требований к описываемой в данной работе модели текста была возможность ее использования в различных системах автоматизированной обработки документов. Соответственно, изначально совокупность алгоритмов для создания модели текста разрабатывалась как отдельный встраиваемый в систему модуль, реализующий функции индексирования текстов. Таким образом, представленная модель текста в виде дерева Ы-грамм позволяет реализовать модуль индексирования документов в виде функционально законченной единицы, использование которой в системе КТ не накладывает никаких ограничений на структуру и состав других модулей. Модуль индексирования имеет один вход, на который поступает текст документа, и один выход, на котором выдается представление текста в виде И-граммной модели, как показано на рис. 8; для

16

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

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

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

- с помощью алгоритма извлечения Ы-грамм из текста для каждого обучающего документа (1) е Тг строим модель т} в виде дерева И-грамм;

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

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

документ в формате ASCII

модуль

индексирования

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

дерева Ы-грамм

и>, —- , где - количество раз, которое

' с,) ,

подстрока встречается в спектрах категории с,; \Тг\ - количество документов во всех категориях; 2#(*4,су) - количество раз, которое

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

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

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

- в общем случае имеем поэтому нормируем вектора,

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

еР,&&у, 6.У,, еР, ¿Б, '

- обучаем классификатор на множестве векторов V = {К,К,};

- система классификации текстов по категориям С = {с, } настроена и готова к работе.

Процесс создания системы КТ по предложенной методике показан на рис. 9.

Рис. 9 - Процесс создания системы КТ с использованием деревьев И-грамм

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

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

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

Рис. 10 - Основные блоки тестовой программной системы

Часть системы, выполняющая функции моделирования документов и формирования бинарных векторов, подающихся на вход классификатору, была реализована в соответствии с методикой, описанной в главе 3. Центральным элементом этой части системы является модуль обработки текста документа и создания на его основе N-граммной древовидной модели документа, описанной в главе 2. Отдельные части данного модуля реализованы с использованием трех различных языков программирования: С, Java и Perl, что обусловлено приспособленностью каждого языка для решения своего круга задач.

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

File Reader

Classifier Learner

Interactive Table

EZ3

F7!?!

Node *

Node7

Рис. 11 - Статистический программный пакет KNIME

Для тестирования совместно с представленной в данной работе моделью текста использовались следующие типы классификаторов, описание которых можно найти в главе 1: SVM - классификатор, использующий машины опорных векторов (SVM - Support Vector Machines); PNN -классификатор на основе вероятностной нейронной сети (PNN - Probabilistic Neural Network); MLP - классификатор на основе многослойной нейронной сети (MLP - Multilayer Perceptron); FR - правила принятия решений (FR -Fuzzy Rules); DT - деревья принятия решений (DT - Decision Trees); NB -Наивный Байесовский классификатор (NB — Naive Bayes).

Для проведения эксперимента использовался корпус Cl = {d,,...,d66} из 66 текстов, тематически относящихся к 5 категориям множества С = (с, ,...,с5} = {"Экономика", "Художественная литература", "Философия", "Психология", "Программирование"}. Исходный корпус текстов П = {d,,...,d66} был разделен на обучающую Тг = {</,,...,dm} и тестовую Те = {</,,..;dm} выборки объемом 30 и 36 документов соответственно. Документы из тестовой выборки Те = {¿,,...,</|Г(Г|} не участвовали в обучении классификатора для обеспечения достоверности результатов эксперимента.

Для оценки эффективности классификаторов использовался как процент верно классифицированных документов, так и более специфические метрики: точность (я) и полнота (р). По отношению к категории с, точность я, определяется как условная вероятность ) = Т\<ЬЦх,с,) = Т). Аналогично, полнота р, относительно категории с, определяется как Р(Ф(ёг,с1) = Т | Ф(</Х,с() = Т).

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

Классификатор Молелг, текста

Вектоо слот Деоево Ы-гге 1ММ

я Р % '■■■ я Р %

БУМ 0.89 0.90 89 1.00 1.00 100

РШ 0.59 0.74 69 1.00 1.00 , 100

МЬР 0.93 0.84 89 1.00 1.00 100

ЕЯ • 0.60 0.43 42 0.97 0.95 94

БТ 0.90 0.80 83 0.96 0.92 94

ИВ 0.25 0.23 25 0.92 0.84 86

Таблица 1 - Сравнение оценок эффективности классификаторов для двух моделей текстов

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

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

Приложение содержит акт о внедрении разработанной системы в производственный процесс компании "МЕРА", а также свидетельство о государственной регистрации программы для ЭВМ "Система моделирования текстов".

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

7. Результаты диссертационной работы внедрены в производственный процесс компании "МЕРА".

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ Публикации в изданиях, рекомендованных ВАК

1. Мордвинов, A.B. Системный подход в моделировании текста / A.B. Мордвинов // Математическое Моделирование. Оптимальное управление: Вестник Нижегородского университета им. Н.И. Лобачевского. - 2010. -№2. С. 185-190.

Публикации в других изданиях

2. Мордвинов, A.B. Использование алгоритмов сжатия в задаче атрибуции / A.B. Мордвинов, Л.С. Ломакина// Мат. VII Междунар. молодеж. науч.-техн. конф. "Будущее технической науки". Н. Новгород, 2007 г. - Н. Новгород: НГТУ, 2007. - С. 79.

3. Мордвинов, A.B. Исследование текстовой системы в контексте задачи атрибуции / A.B. Мордвинов, JI.C. Ломакина // Мат. 7-й Междунар. конф. "НТИ-2007". Информационное общество. Интеллектуальная обработка информаци. Информационные технологии. Москва, 24-26 окт. 2007 г. -М.: ВИНИТИ РАН, 2007. - С. 215-217.

4. Мордвинов, A.B. Анализ, моделирование и атрибуция текстовой системы / A.B. Мордвинов, JI.C. Ломакина // Мат. Междунар. науч.-техн. конф. "Информационные системы и технологии (ИСТ 2008)". Н. Новгород, 2008 г. - Н. Новгород: НГТУ, 2008. - С. 254.

5. Мордвинов, A.B. Эффективное моделирование текста в задаче атрибуции. / A.B. Мордвинов // Тр. Междунар. сими. "Интеллектуальные системы 2008 INTELS'08". Н. Новгород, 30 июня - 4 июля 2008 г. - М.: МГТУ им. Баумана - Н. Новгород: НГТУ им. P.E. Алексеева, 2008. - С. 249-252.

6. Мордвинов, A.B. Модель текста в задаче атрибуции / A.B. Мордвинов // Современные проблемы информатизации в экономике и обеспечении безопасности: Сб. трудов. Вып. 13. - Воронеж: Научная книга, 2008. - С. 73-74.

7. Мордвинов, A.B. Текст как система. / А. В. Мордвинов // Мат. Междунар. науч-техн. конф. "Информационные системы и технологии (ИСТ 2009)". Н. Новгород, 2009 г. - Н. Новгород: НГТУ, 2009. - С. 314.

8. Мордвинов, A.B. Атрибуция текстов: сравнение текстовых систем. / А. В. Мордвинов // Мат. Междунар. науч-техн. конф. "Информационные системы и технологии (ИСТ 2010)". Н. Новгород, 2010 г. - Н. Новгород: НГТУ, 2010.-С. 241.

9. Мордвинов, A.B. Методика автоматической категоризации текстов / A.B. Мордвинов // Труды НГТУ. Системы обработки информации и управления. - Н. Новгород: НГТУ. - 2010. - №4(83). - С. 75-81.

Ю.Мордвинов, A.B. Система моделирования текстов / A.B. Мордвинов, Л.С. Ломакина // Свидетельство об официальной регистрации программ для ЭВМ № 2010615295. Зарегистрировано в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ от 18.08.10.

Подписано в печать 02.11.10. Формат 60 х 84 '/16. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 674.

Нижегородский государственный технический университет им. Р. Е. Алексеева. Типография НГТУ. 603950, Нижний Новгород, ул. Минина, 24.

61 11-5/1386

</(1 На правах рукописи

МОРДВИНОВ АЛЕКСЕЙ ВЯЧЕСЛАВОВИЧ

РАЗРАБОТКА И ИССЛЕДОВАНИЕ МОДЕЛИ ТЕКСТА ДЛЯ ЕГО

КАТЕГОРИЗАЦИИ

Специальность 05.13.01. - "Системный анализ, управление и обработка информации (в науке и промышленности)" по техническим наукам

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

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

Нижний Новгород 2010 г.

Содержание

Введение........................................................................................................................4

Глава 1. Обзор предметной области и постановка задачи.....................................11

1.1 Категоризация текстов: определение, виды, ограничения............................................13

1.2 Прикладное использование категоризации текстов......................................................16

1.2.1 Автоматическое индексирование для систем извлечения информации............... 17

1.2.2 Организация и управление документами................................................................18

1.2.3 Фильтрация текста.....................................................................................................18

1.2.4 Определение значений многозначных слов на основе контекста.........................20

1.2.5 Иерархическая категоризация страниц в Интернете..............................................21

1.3 Решение задачи категоризации текстов на основе машинного обучения...................22

1.3.1 Инженерия знаний и машинное обучение...............................................................22

1.3.2 Машинное обучение: базовые понятия, задачи, алгоритмы..................................25

1.3.3 Применение техник машинного обучения в задаче категоризации текстов........30

1.4 Использование механизмов из области извлечения информации в жизненном цикле системы по категоризации текстов........................................................................................32

1.4.1 Индексирование документа......................................................................................32

1.4.2 Снижение размерности пространства элементов...................................................38

1.4.3 Индуктивное построение текстовых классификаторов..........................................45

1.4.4 Оценка классификаторов...........................................................................................57

1.5 Анализ этапов и методов построения системы категоризации документов.

Постановка задачи...................................................................................................................60

Выводы к главе 1.....................................................................................................................65

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

2.1 И-граммы как элементы модели......................................................................................66

2.2 Алгоритм выбора ТчГ-грамм из текста..............................................................................71

2.2.1 Распределение отобранных Ы-грамм по частоте в зависимости от значения N..72

2.2.2 Зависимость количества отобранных алгоритмом К-грамм от длины документа ...............................................................................................................................................74

2.2.3 Динамика занесения Ы-граммы в словарь...............................................................77

2.2.4 Оценка сложности алгоритма отбора 1Ч-грамм.......................................................82

2.3 Древовидная модель текста. Спектры модели...............................................................84

2.3.1 Оценка сложности алгоритма построения спектра М-грамм.................................87

Выводы к главе 2.....................................................................................................................89

Глава 3. Использование разработанной модели в модульной системе категоризации текстов...............................................................................................90

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

3.2 Моделирование текста в виде дерева М-грамм с точки зрения модульного дизайна 93 3.2.1 Экспериментальная методика категоризации текстов...........................................95

Выводы к главе 3...................................................................................................................105

Глава 4. Программная реализация и оценка эффективности тестовой системы категоризации текстов, использующей И-граммную модель текста.................106

4.1 Описание тестовой программной системы...................................................................106

4.2 Описание условий проведенного эксперимента и его особенностей........................109

4.3 Анализ результатов экспериментов по оценке эффективности системы категоризации текстов с использованием древовидной М-граммной модели................115

4.4 Сравнение эффективности систем категоризации текстов, использующих

представление текста в виде дерева №грамм и вектора слов..........................................132

Выводы к главе 4...................................................................................................................

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

Литература................................................................................................................ ^

Приложение 1...........................................................................................................^

Приложение 2........................................................................................................... ^

Приложение 3...........................................................................................................

Введение

Актуальность работы

За последние 10-15 лет задачи управления документами на основании их содержимого (обобщенное название извлечение информации) приобрели особенно важное значение в области информационных систем ввиду постоянно повышающейся доступности документов в цифровой форме и вытекающей отсюда необходимости получать к ним доступ максимально быстрыми и удобными способами. Одной из таких задач является категоризация текста (синонимы - классификация по категориям, определение тематики) - задача распределения текстов на естественном языке по тематическим категориям из заранее определенного набора. Появление задачи категоризации текстов (КТ) относится к началу 60-х годов прошлого века, но только в 90-х она приобрела свою истинную значимость благодаря возросшему прикладному интересу и доступности более мощных аппаратных средств. КТ сейчас применяется во многих контекстах, начиная от индексирования документов на основе контролируемого словаря, заканчивая фильтрацией документов, автоматической генерацией метаданных, заполнением иерархических каталогов Web ресурсов, атрибуцией текстов неизвестных авторов и вообще в любых приложениях, требующих автоматизированной организации или диспетчеризации документов.

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

4

помощью обучения на наборе заранее классифицированных документов. Важную роль в развитии машинного обучения сыграли В. Н. Вапник и А. Я. Червоненкис, активными исследованиями в области KT занимаются Apte С., Damerau F.J., Fuhr. N., Sebastiani F., Cohen W.W., Dumais S.T., Joachims T., Lam S.L., Larkey L.S., Lewis D.D., Yang Y.

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

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

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

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

5

как при использовании этих моделей решаются задачи индексирования документа и уменьшения размерности модели;

- сформулировать требования к разрабатываемой модели текста;

- разработать алгоритм для индексирования текста, то есть для выбора из текста элементов, на основе которых будет построена модель;

- разработать модель текста в виде дерева И-грамм и проанализировать ее свойства;

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

- разработать методику категоризации документов, моделируемых в виде деревьев 14-грамм;

- разработать тестовую систему, позволяющую получить оценки эффективности методики КТ;

- протестировать разработанную методику КТ с различными алгоритмами классификации данных;

- провести эксперимент с целью сравнения эффективности методик КТ, использующих представление текста в виде вектора слов и в виде дерева 14-грамм;

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

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

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

повысить эффективность автоматизированных систем категоризации текстов.

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

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

Практическая ценность работы

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

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

На защиту выносятся:

1. Модель текста в виде дерева М-грамм.

2. Алгоритмы представления текстовых моделей в виде спектров Ы-грамм для получения возможности динамической настройки точности (детализации) модели после ее создания.

3. Методика категоризации текстов, построенная на основе использования предложенной модели текста.

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

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

Результаты работы использованы в НИОКР "Использование алгоритмов сжатия данных в задаче определения авторства текста" для программы УМНИК (Участник Молодежного Научно-инновационного Конкурса) фонда содействия развитию малых форм предприятий в научно-технической сфере, № 08-2-7335. Апробация работы

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

- VII международная научно-техническая конференция НТИ 2007 "Информационные технологии" ВИНИТИ РАН, г. Москва, 2007 г.;

- XIV Международная научно-техническая конференция "Информационные системы и технологии - ИСТ" (г. Нижний Новгород, 2008);

- VIII международный симпозиум "Интеллектуальные системы" -INTELS'2008 (г. Нижний Новгород-Москва,МГТУ им. Н.Э. Баумана-НГТУ им.Р.Е. Алексеева 2008);

- Международная открытая научно-практическая конференция "Современные проблемы информатизации" (г. Воронеж, 2008);

- VII международная молодежная научно-техническая конференция "Будущее технической науки" (г. Нижний Новгород, 2008);

- XV Международная научно-техническая конференция "Информационные системы и технологии - ИСТ-2009" (г. Нижний Новгород, 2009);

- XVI Международная научно-техническая конференция "Информационные системы и технологии - ИСТ-2010" (г. Нижний Новгород, 2010);

Публикации

Основные положения диссертационной работы отражены в 10 работах, опубликованных соискателем лично или в соавторстве в научных изданиях, в том числе в одной статье, представленной в рецензируемом издании из перечня ВАК РФ. Структура и объём работы

Диссертационная работа состоит из введения, четырёх глав, заключения, библиографического списка и приложений. Общий объём работы 153 страницы текста, содержащего 47 рисунков и 8 таблиц. Список литературы содержит 116 наименований.

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

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

9

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

Во второй главе рассматриваются Ы-граммы в качестве элементов текста, подлежащих индексированию; описывается и анализируется алгоритм отбора 14-грамм из текста и его свойства; рассматривается модель текста в виде дерева Ы-грамм и ее представление с помощью спектров ]ЧГ-грамм.

В третьей главе объясняется необходимость следования принципам модульного дизайна при разработке системы КТ; рассматривается моделирование текста в виде дерева ТчГ-грамм с точки зрения модульного дизайна; описываются экспериментальная методики по созданию системы КТ.

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

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

Приложение содержит акт о внедрении разработанной системы в производственный процесс компании "МЕРА", а также свидетельство о государственной регистрации программы для ЭВМ "Система моделирования текстов".

Глава 1. Обзор предметной области и постановка задачи

За последние 10-15 лет задачи управления документами на основании их содержимого, называемые также задачами извлечения информации, приобрели особенно важное значение в области информационных систем ввиду постоянно повышающейся доступности документов в цифровой форме и вытекающей отсюда необходимости получать к ним доступ максимально быстрыми и удобными способами. Одной из таких задач является категоризация текста - задача распределения текстов на естественном языке по тематическим категориям из заранее определенного набора. Появление задачи категоризации текстов относится к началу 60-х годов прошлого века, но только в 90-х она приобрела свою истинную значимость благодаря возросшему прикладному интересу и доступности более мощных аппаратных средств, категоризация текстов (КТ) сейчас применяется во многих контекстах от индексирования документов на основе к�