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

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

Шаграев Алексей Галимович

МОДИФИКАЦИЯ, РАЗРАБОТКА И РЕАЛИЗАЦИЯ МЕТОДОВ КЛАССИФИКАЦИИ НОВОСТНЫХ ТЕКСТОВ

Специальность 05.13.17 - Теоретические основы информатики

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

Москва

2014

005550102

Работа выполнена на кафедре Прикладной математики ФГБОУ ВПО Национальный исследовательский университет «МЭИ»

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

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

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

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

Фальк Вадим Николаевич

Гданский Николай Иванович,

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

заведующий кафедрой Информационных сетей и систем РГСУ.

Гулин Владимир Владимирович,

кандидат технических наук, программист, ООО «Мэйл.Ру».

Институт системного анализа Федерального агентства научных организаций Российской Федерации (ФАНО РФ)

Защита состоится 27 июня 2014 года в 1§часов на заседании диссертационного совета Д 212.157.01 при НИУ МЭИ по адресу Москва, Красноказарменная ул., дом 13, ауд. М-704.

С текстом диссертации можно ознакомиться в библиотеке НИУ

МЭИ.

Автореферат разослан мая 2014

года.

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

кандидат технических наук, доцент —М. В. Фомина

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

Актуальность темы. Классификация текстов - одна из важных задач информационного поиска, заключающаяся в отнесении документа к одной или нескольким категориям (классам) из некоторого заранее определенного набора на основании анализа содержания этого документа. Простейшим и исторически первым методом классификации документов является ручная классификация, примеры которой можно видеть в виде рубрик в СМИ, категорий в библиотеках, полученных разделением художественных текстов на жанры, научных текстов по тематикам и т.д. Ручная классификация весьма ограничена в способности быстро обрабатывать большие массивы текстов, характерные для многих приложений автоматических методов классификации текстов. Такие методы широко используются современными интернет-системами: новостные агрегаторы, такие, как сервис Яндекс.Новости или Google News решают задачи тематической рубрикации новостных документов и сюжетов, почтовые сервисы, например, Яндекс .Почта, gmail или Mail.ru, используют алгоритмы обнаружения спама для фильтрации почты, поисковые системы (Яндекс, Google, Mail.ru, Yahoo и другие) решают задачи обеспечения разнообразия поисковой выдачи, и т.д.

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

По этой причине в диссертационной работе рассматриваются, в основном, вопросы, связанные с применением методов машинного обу-

чения к задаче автоматической классификации текстов. Отметим некоторые характерные особенности этой задачи:

1. Тексты являются текстами на естественном языке, не имеют четкой формализации, не структурированы, не являются техническими.

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

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

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

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

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

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

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

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

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

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

6. Разработка метода понижения размерности в задаче классификации текстов.

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

8. Сравнительный анализ всех рассмотренных методов применительно к решению задачи классификации текстов.

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

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

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

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

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

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

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

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

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

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

2. В результате экспериментов на коллекции текстовых документов 11еи1егз-21578 было установлено, что предложенные модификации стандартных линейных методов классификации значительно превосходят стандартные методы по качеству моделей: для показателей качества наивного байесовского метода на 20% по сравнению с оригинальным, а для метода логистической регрессии - на 8%. Также было установлено, что алгоритм, основанный на алгоритмической композиции модельных деревьев, имеет наилучшие показатели качества среди всех рассмотренных в работе методов.

3. Результаты диссертационной работы внедрены в сервис «Яндекс.Новости», разрабатываемый ООО «Яндекс», и используются в задачах рубрикации и кластеризации новостных документов (подтверждено актом об использовании результатов диссертации).

Апробация. Положения диссертационной работы докладывались на XVII ежегодной международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 2011 году, XVIII ежегодной международной конференции «Информационные средства и технологии» в 2010 году, на рабочих совещаниях и выступлениях в компании «Яндекс».

Публикации. По теме диссертации опубликовано четыре научные работы, в том числе две - в изданиях по перечню ВАК.

Объем и структура работы. Диссертация состоит из введения, трех глав и заключения. Список использованной литературы содержит 54 наименования. Текст диссертации содержит 108 страниц машинописного текста, включая 16 рисунков и 7 таблиц.

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

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

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

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

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

dec vvEW

где С - множество документов, относящихся к рассматриваемому классу, s(d) — логарифм вероятности верной классификации документа d, f(w) - вес слова iv в модели, ц - параметр регуляризации.

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

(2 = £ log(l + ехр(—a(d) ■ y(d))) + Л £ [

Здесь D — множество всех документов, D' - множество тестовых документов, a(d) - значение предсказания для документа d, y(d) - значение целевой функции на документе d, Л - вес трансдуктивной составляющей функционала.

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

• константное предсказание, равное среднему значению ответа на обучающей выборке (constant);

• предсказание наилучшей одномерной линейной регрессионной модели (simple linear regression, sir);

• предсказание наилучшей одномерной линейной регрессионной модели (best simple linear regression, bslr);

• предсказание линейной регрессионной модели, построенной после десяти итераций метода градиентного бустинга (gradient boosted linear regression, gblr);

• предсказание линейной регрессионной модели, построенной после десяти итераций метода последовательного решения одномерных задач линейной регрессии (positional linear regression, plr).

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

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

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

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

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

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

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

Эксперименты демонстрируют, что предложенные модификации линейных методов классификации, наивного байесовского классификатора и логистической регрессии значительно превосходят по качеству получаемых моделей оригинальные версии этих методов применительно к задаче классификации текстов. График на рис. 1 демонстрирует показатели качества для рассмотренных линейных методов классификации: наивного байесовского (N6), наивного байесовского метода с модифицированным функционалом потерь и регуляризацией (1№В), стандартной логистической регрессии (1Л), логистической регрессии, использующей при построении модификацию метода стохастического градиентного бу-стинга (бЬЯ), а также логистической регрессии с модифицированным функционалом потерь (вЬЬК).

Реи1ег5-21578, Р1-мера

I_I_|__|__I_I

ОД 0,2 0,3 0,4 0,5 0, 6 0,7 0, 8 0,9 1

№ ¡N8 1Д 51.1?

■ Р1 0,48391 0,58551 0,82778 0,85572 0,89253

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

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

Таблица 1

machine cpu cpu_act cpu small kin8nm

IV|-1' i 8 МШШР Щз&Ш л, ОД81000

М5Р 60,191030 2,718290 3,177530 0,159970

deviation. 50-,7-68а?6% ж Ш 1 щш - sir 51,980808 2 1110931 2,596932 4 ¡¡¡¡В ^BSB^^B^BBBBBBBBSS 3,107491 ¡¡иЛ 6590,0 - { 0,160036

¡■■J,. ~ gi'&S&A i^r^j 2,478590 ЮШнврМ 35025314 • 0,146§?2 | -

gblr 48,224856 2,460375 3,019703 0,143096

¡jjjp , I 46^64099 2,3824ii5 2.9.4990 J 0.131108 * Г -F .. ~

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

fix) = 0.1л:2 + х

на отрезке [—10,10].

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

тод позволяет достигнуть значения коэффициента детерминации Д2 = 0,78783. Соответствующее приближение изображено на рис. 2.

Рис. 2. Приближение по методу наименьших квадратов.

Построим теперь для этой функции приближения в виде модельных деревьев высоты один. Рассмотрим два варианта построения модельных деревьев: методом, основанным на минимизации стандартного отклонения ответов (deviation) и методом, основанным на ошибке одномерной линейной регрессии (sir). На рис. 3 изображены оценки ошибок этих методов в зависимости от выбора точки разбиения.

Видно, что минимумы достигаются в различных точках: для метода deviation - в точке 4.3, для метода sir - в точке 0.

На рис. 4 и 5 представлены приближения функции /, построенные при осуществлении соответствующих разбиений.

Рис. 3. Оценки качества разбиения. Разбиение по методу deviation позволяет получить приближение с коэффициентом детерминации R2 - 0,95957. Разбиение по методу sir позволяет получить приближение с коэффициентом детерминации R2 = 0,98674.

Рис. 4. Приближение, полученное при разбиении методом deviation.

Рис. 5. Приближение, полученное при разбиении методом sir.

Приведенный пример иллюстрирует справедливость следующих утверждений:

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

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

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

получаемых моделей классические методы классификации. Сравнение качественных показателей различных методов классификации приведено на рис. 6.

Р1-мера

0,5000 0,5500 0,6000 0,6500 0,7000 0,7500 0,8000 0,8500 0,9000 0,9500 1,0000

|П5 Вз1апсе 0|аЬеГе5 НеаГС 1опо5рИеге \Л/ауе^гт 5опаг

«икШ 0,9533 0,6090 0,6650 0,7490 0,8405 0,7373 0,8635

я РЕРТгее 0,9400 0,5380 0,7185 0,7590 0,8845 0,7690 0,7530

яМ8 0,9600 0,5417 0,7080 0,7635 0,9045 0,7513 0,7110

в ИР 0,9533 0,5860 0,6965 0,7780 0,9225 0,8137 0,8080

ш 0,9397 0,6097 0,7355 0,8305 0,8680 0,8593 0,7685

и 5ВМТ 0,9741 0,7358 0,7472 0,8346 0,9252 0,8685 0,8684

Рис. 6. Показатели качества различных методов классификации.

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

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

Яеи1ег5-21578/ Р1-мера

О ОД 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

ЫВ ПЧВ 1Д 5ЬШ бвмт

я Р1 0,48391 0,58551 0,82778 0,85572 0,89253 0,91602

Рис. 7. Качество классификации для различных методов на коллекции Кеи1еге-21578.

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

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

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

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

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

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

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

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

5. Разработан и реализован метод понижения размерности признакового пространства задачи классификации текстов на основе матричного разложения.

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

Лично автором получены все основные теоретические результаты

и осуществлены все программные реализации.

РАБОТЫ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК РФ:

1. Шаграев А. Г., Бочаров И. А. Фальк В. Н. Трансдуктивное обучение логистической регрессии в задаче классификации текстов. // Программные продукты и системы, №2, 2014.

2. Шаграев А. Г., Фальк В. Н. Линейные классификаторы в задаче классификации текстов // Вестник МЭИ, №4, 2013.

Другие статьи и материалы конференций:

3. Шаграев А. Г., Фальк В. Н. Сети и сетевые языки. // Доклады международной конференции «Информационные средства и технологии». (МФИ-2010). - Т.З. - 2010.

4. Шаграев А. Г., Фальк В. Н. Статистически обоснованный метод обрезания регрессионных деревьев. // Радиоэлектроника, электротехника и энергетика: Семнадцатая Междунар. науч-техн. конф. студентов и аспирантов: Тез. докл. В 3-х т. - Т. 1. - 2011.

Подписано в печать ч'^М ■ (у 0Р-1 Зак. ->$0 Тир. ЮО П.л. ¡А^ Полиграфический центр МЭИ Красноказарменная ул.,д.13

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

УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «МЭИ»

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

УДК 004.852

Шаграев Алексей Галимович

МОДИФИКАЦИЯ, РАЗРАБОТКА И РЕАЛИЗАЦИЯ МЕТОДОВ КЛАССИФИКАЦИИ НОВОСТНЫХ

ТЕКСТОВ

Специальность 05.13.17 - Теоретические основы информатики Диссертация на соискание ученой степени кандидата технических наук

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

Москва

2014

Содержание

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

1. Задача текстовой классификации как задача обучения по прецедентам.............................................................................................12

1.1 Оценка качества методов классификации...................................15

1.1.1 Метрики точности и полноты................................................16

1.1.2 Метрика Accuracy..................................................................17

1.1.3 Метрика AUC.........................................................................19

1.1.4 Комбинированные метрики...................................................20

1.2 Методы решения задачи текстовой классификации....................23

1.2.1 Наивный байесовский метод..................................................23

1.2.2 Метод ближайших соседей....................................................24

1.2.3 Оценка качества.....................................................................25

2. Задача классификации текстов..........................................................27

2.1 Линейные методы классификации...............................................27

2.1.1 Наивный байесовский метод и его модификации..................27

2.1.2 Логистическая регрессия.......................................................32

2.2 Модельные деревья решений.......................................................35

2.2.1 Одномерная линейная регрессия...........................................41

2.2.2 Инкрементальное обновление...............................................47

2.2.3 Многомерная линейная регрессия.........................................48

2.3 Алгоритмические композиции....................................................54

2.3.1 Алгоритмические композиции в задаче регрессии................57

2.3.2 Алгоритмические композиции в задаче бинарной классификации...................................................................................58

2.4 Матричное разложение как метод выделения признаков............59

2.5 Выводы........................................................................................62

3. Экспериментальное исследование рассмотренных методов.............65

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

3.1.1 Метод скользящего контроля................................................66

3.1.2 Стратификация.......................................................................68

3.2 Исследуемые наборы данных......................................................69

3.2.1 Коллекция ЯеШегБ-21578.......................................................69

3.2.2 Коллекция иС1.......................................................................70

3.3 Результаты численных экспериментов........................................72

3.3.1 Линейные методы классификации.........................................72

3.3.2 Линейные методы восстановления регрессии.......................75

3.3.3 Модельные деревья решений в задаче восстановления регрессии...........................................................................................77

3.3.4 Алгоритмические композиции на основе модельных деревьев в задачах классификации...................................................................84

3.4 Выводы........................................................................................92

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

4. Список сокращений и условных обозначений...................................94

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

5. Приложение. Тексты программ для решения задач линейной регрессии...............................................................................................102

ВВЕДЕНИЕ

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

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

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

• фильтрация спама;

• контекстная реклама;

• автоматическое реферирование наборов текстов;

• категоризация (рубрикация) в агрегирующих системах;

• обеспечение разнообразия поисковой выдачи и другие.

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

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

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

1. Тексты являются текстами на естественном языке, не имеют четкой формализации, не структурированы, не являются техническими.

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

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

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

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

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

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

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

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

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

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

6. Разработка метода понижения размерности в задаче классификации текстов.

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

8. Сравнительный анализ рассмотренных методов применительно к задаче классификации текстов.

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

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

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

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

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

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

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

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

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

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

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

1. Осуществлена программная реализация всех предложенных методов.

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

3. В результате экспериментов на коллекции текстовых документов 11еШ:ег8-21578 [24] было установлено, что предложенные модификации стандартных линейных методов классификации значительно превосходят по качеству моделей стандартные методы. Так, удалось добиться улучшения показателей качества наивного байесовского метода на 20% по сравнению с оригинальным методом, а для метода логистической регрессии-на 8%. Также было установлено, что алгоритм, основанный на алгоритмической композиции

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

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

Апробация. Положения диссертационной работы докладывались на XVII ежегодной международной научно-технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 2011 году, XVIII ежегодной международной конференции «Информационные средства и технологии» в 2010 году, на рабочих совещаниях и выступлениях в компании «Яндекс».

Публикации. По теме диссертации опубликовано четыре научные работы, в том числе две - в изданиях по перечню ВАК.

Объем и структура работы. Диссертация состоит из введения, трех глав и заключения. Список использованной литературы содержит 54 наименования. Текст диссертации содержит 108 страниц машинописного текста, включая 16 рисунков и 7 таблиц.

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

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

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

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

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

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

Эксперименты подтверждают значительный рост качества предложенных автором линейных методов классификации по сравнению со стандартными методами.

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

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

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

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

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

1. ЗАДАЧА ТЕКСТОВОЙ КЛАССИФИКАЦИИ КАК ЗАДАЧА ОБУЧЕНИЯ ПО ПРЕЦЕДЕНТАМ

Неформально задача обучения по прецедентам [45] может быть сформулирована следующим образом. Имеется множество объектов и множество возможных ответов. Существует некоторая зависимость между объектами и ответами - целевая функция, но она неизвестна. Известно только конечное множество прецедентов - пар, состоящих из объектов и соответствующих им ответов. Это множество будем называть выборкой. На основе множества прецедентов необходимо восстановить неизвестную зависимость, то есть, построить алгоритм, способный для всякого объекта предсказать соответствующий ему ответ. Этот алгоритм будет называться решающей функцией. Значения решающей функции будем называть предсказаниями. Способ построения решающей функции по множеству прецедентов называется методом обучения, а процесс построения решающей функции будем называть процессом обучения. Выборку, используемую в процессе обучения, будем называть обучающей выборкой.

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

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

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

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

Более формально, будем считать, что имеется множество объектов X, множество ответов У и существует неизвестная целева