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

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

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

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ И ПРОГРАММНЫХ СРЕДСТВ КЛАССИФИКАЦИИ ТЕКСТОВЫХ ДОКУМЕНТОВ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

з т

Москва 2013

005061636

005061636

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

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

профессор,

Фролов Александр Борисович

Официальные оппоненты: Дзегеленок Игорь Игоревич,

доктор технических наук, профессор, профессор кафедры вычислительных систем и сетей НИУ «МЭИ»

Строгалов Александр Сергеевич, кандидат физико-математических наук, доцент, доцент кафедры математической теории интеллектуальных систем МГУ им. М.В. Ломоносова

Ведущая организация: Федеральное государственное

унитарное предприятие «Научно-исследовательский институт «Квант»

Защита состоится 28 июня 2013 г. в 16 час. 00 мин. на заседании диссертационного совета Д 212.157.01 при НИУ МЭИ по адресу 111250, Москва, ул. Красноказарменная, д. 13, (ауд. М-704).

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «НИУ «МЭИ» Автореферат разослан «%.?» мая 2013 г.

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

диссертационного совета Д 212.157.01, кандидат технических наук, доцент

М. В. Фомина

Общая характеристика работы

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

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

Для решения перечисленных задач требуется применение методов классификации на основе машинного обучения, поскольку состав и содержимое анализируемых документов постоянно изменяется, и одним из путей адаптации к этой динамике является использование таких методов. Целью применения методов машинного обучения для задачи классификации текстовых документов является построение модели классификации на основе обучающего набора и применение построенной модели для предсказания класса или набора классов, релевантных для нового документа. Обучающий набор для рассматриваемой задачи классификации состоит из документов, каждому из которых сопоставлено множество классов, к которым данный документ относится. Разработке и тестированию методов данного вида, а также связанным с ними алгоритмам анализа текстов в настоящее время посвящены труды таких авторов как Агеев М.С., Кураленок И.Б., Joachims Т., Schapire R.E., Schutze Н., Sebastiani F. Стоит отметить, что в современных прикладных задачах обучающие наборы имеют достаточно большой размер (речь идет о сотнях тысяч обучающий примеров), ввиду чего интерес представляет разработка эффективных методов машинного обучения, допускающих параллельную программную реализацию.

На сегодняшний день в задачах текстовой классификации лучше всего зарекомендовали себя следующие методы: метод опорных векторов и методы построения алгоритмических композиций на основе бустинга (улучшения). Анализ российских и зарубежных публикаций показывает, что основные усилия исследователей сконцентрированы на построении классификаторов, обладающих высокими полнотой и точностью. Однако при разработке методов классификации текстовых данных, имеющих высокую размерность (большое число терминов, описывающих документ), особое внимание требуется уделить также вопросам быстродействия (т.е. уменьшению времени, затрачиваемого на отнесение документа к одному из классов). В литературе практически нет работ, посвященных проблемам производительности классификаторов. Фактически, проблемы, связанные с быстродействием классификаторов, ложатся на плечи разработчиков систем машинного обучения. На практике реализаг ция мер, направленных на увеличение точности классификации, обычно приводит к снижению быстродействия. Обеспечение высокого быстродействия имеет особую важность в крупных поисковых системах при решении таких задач, как анализ поисковых запросов, поступающих от пользователей в режиме реального времени, приоритезации URL - Uniform Resource Locator адресов web страниц, число которых достигает нескольких миллиардов, для их загрузки поисковым роботом. Стоит отметить, что подобные системы относятся к классу высоконагруженных, т. е. обладающих либо большим количеством одновременных сессий пользователей, либо большим объемом данных, или совокупностью этих критериев. При решении конкретной задачи быстродействие является ключевым фактором при выборе того или иного метода для таких систем.

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

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

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

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

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

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

2. Обоснование выбора метода векторного представления текстового документа.

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

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

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

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

7. Оценка эффективности предложенных решений на характерной коллекции текстовых документов проведением численных экспериментов.

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

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

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

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

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

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

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

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

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

• Осуществлена программная реализация предложенного метода градиентного бустинга на «невнимательных»деревьях решений с использо-

>

I

ванием различных современных технологий параллельного программирования (SSE - Streaming SIMD Extensions, OpenMP - Open MultiProcessing, MPI - Message Passing Interface, MapReduce).

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

• Осуществлена программная реализация предложенной модификации алгоритма главных признаков с использованием современных технологий параллельного программирования (SSE, OpenMP).

Результаты данной работы внедрены в проект «Поиск@Ма1Ши», разрабатываемый ООО «Мэйл.Ру»и используются для решения следующих задач:

• классификация поисковых запросов;

• классификация страниц коммерческих сайтов по степени релевантности запросу;

• приоритезация URL адресов web-страниц для их загрузки поисковым роботом.

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

Апробация. Основные положения диссертационной работы докладывались на XIX международной научно-технической конференции «Информационные средства и технологии» 2011, XX международной научно-технической конференции «Информационные средства и технологии» 2012, XVIII международной научно-технической конференции студентов и аспирантов «Радио-электноника, электротехника, энергетика» (2012), научном семинаре «Дискретные математические модели» кафедры математического моделирования,

1Коллекдия документов Reuters-21578 - www.daviddlewi3.com/resource8/testcolIections/reuters21678/

научном семинаре кафедры вычислительных машин, систем и сетей (НИУ «МЭИ»).

Публикации. По теме диссертации опубликовано 7 научных работ, в том числе 3 в изданиях из перечня ВАК, выполненных при финансовой поддержке РФФИ, проект №11-01-00792-а. Зарегистрировано 2 объекта интеллектуальной собственности: свидетельства о регистрации программ №2013612095 2 и №2013612097 3.

Объем и структура работы. Диссертация состоит из введения, 5 глав, заключения и 4 приложений. Список использованной литературы содержит 101 наименование. Текст диссертации содержит 172 страницы машинописного текста, включая 32 рисунка.

Содержание работы

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

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

2Гулин В.В. Свидетельство об офицальной регистрации программы дня ЭВМ №2013612095. Библжь тека алгоритмов машинного обучения «MLLibrary»- Москва, 2013,1с.

гГулин В.В. Свидетельство об офицальной регистрации программы для ЭВМ №2013612097. Система лингвистического анализа текстовых документов «MorphAnalyzer»- Москва, 2013,1с.

*Aho A., Corasick М. Efficient string matching: An aid to bibliographic search // Communications of the ACM 18 (6), Pp. 333-340,1975

для каждого класса эквивалентности с общей леммой словаря. Имея кольцевые списки для каждого класса эквивалентности слов, можно по одной словоформе восстановить весь класс (см. рис. 1).

Рис. 1. Представление классов эквивалентности слов в виде кольцевого списка (лемма выделена звездой).

В заключение дается формализованная постановка задачи построения классификатора 1р' текстовых документов методами машинного обучения с учителем с использованием основанного на среднегармоническом для полноты и точности классификации значении обобщенного показателя - Л<1 меры 6

{(ж;, ci)\xi £ X, Ci £ С, г = 1,...,N} С domy- обучающая выборка, (1) {(zj, ¿¿¡x'i € X, di е С, i = 1,..., N'} С dornig- тестовая выборка, (2)

.0 Д и —I—-♦—

(1)-(5).

N Nc

(3)

^l,micro max,

(4)

или

Fl,macro -»■ Шах,

,macro

5 van Rijsbergen C. J. Information Retrieval (2nd ed.). Butterworth, 1979

где L— неотрицательная функция потерь, F^micro и Fitmicro - микро и макро-усредненные значения Fi меры, tp— предикат, отражающий объективно существующее отношение принадлежности документов определенным категориям на их множестве domiр.

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

Во втором параграфе представлен предлагаемый в работе алгоритм градиентного бустинга на «невнимательных» деревьях решений (GBOT - gradient boosted oblivious trees) 6.

При этом рассматривается задача бинарной классификации С = {0,1}, X С Пусть Qtr - обучающая выборка. Будем строить алгоритмическую композицию в виде

т

/(*)=«7(/0 + 5>/,(Х)), (6)

<=1

где а— логистическая функция (сигмоид). В качестве метагалгоритма построения алгоритмической композиции возьмем алгоритм градиентнго бустинга (улучшения) 7. Обозначим f(xi) - предсказанное значение для объекта Х{. Определим функцию потерь равной среднему значению энтропии на элементах обучающей выборки

L = jf ЕН* 1о§(/(*0) -(!-«) bg(l - /(*<))] (7)

i=i

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

6Гулин В.В. Исследование метода градиентного бустинга на «невнимательных» деревьях решений в задаче классификации текстовых документов // Вестник МЭИ 2012, №8, с. 124-131.

7Friedman J. Н. Stochastic gradient boosting // Computational Statistics and Data Analysis, 38:367-378,

1999

BKohavi R., Li C. Oblivious decision trees graphs and top down pruning. 11 In Proceedings of the 14th international joint conference on Artificial intelligence - Volume 2, pages 1071-1077, San Francisco, CA, USA,

1995. Morgan Kaufmann Publishers Inc.

предлагается алгоритм обучения «невнимательных» деревьев решений (алгоритм 1).

Алгоритм 1. Алгоритм обучения «невнимательного» дерева решений Параметры:

Вход: обучающая выборка £7tr.; семейство правил В; глубина дерева Я; Выход: условия ßi,l = 1.....Н\ таблица Т : {0,1}я —¥ R\

1. Для всех I = 1,..., Н:

Найти предикат, минимизирующий ошибку:

ß, arg min 7 (/Зі,..., A-i, ß), где/(/?:,...,/?,)= £ Е[хіЄХь](Г(Ь)-с02;

ЬЄ{0,1}' 1=1

Xb = {xi:ßs{xi) = b3,s = l,...,l},X= И Хъ,

ЬЄ{0,1}'

Ц - знак объединения непересекающихся множеств;

2. Для всех Ъ = (i»i,...,ЬН) Є {0,1}н

1 N

Т{ъ ......Ьн) «- ІЗТТ J2ix є

Далее описаны стратегии регуляризации для предложенного метода.

Третий параграф посвящен результатам экспериментального сравнения всех представленных в главе методов применительно к задаче классификации текстовой коллекции Reuters-21578. Они приведены в табл. 1, где NB -наивный байесовский классификатор 9, kNN - метод к ближайших соседей 10, LR - алгоритм логистической регрессии 11, SVM - метод опорных векторов 12, С4.5 - дерево решений, построенное алгоритмом С4.5 13, RandomForest -

9Manning С., Raghavan P., Schutze H. Introduction to Information Retrieval, // Cambridge University Press. 2008

10 Bishop C. Pattern Recognition and Machine Learning // Springer, 2006

nHastie Т., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction // Springer Series in Statistics, 2009

12Platt J. C. Fast TVaining of Support Vector Machines using Sequential Minimal Optimization, // Advances in Kernel Methods / Ed. by B. Scholkopf, С. C. Burges, A. J. Smola. MIT Press, 1999. Pp. 185-208.

"Quinlan J. R. C4.5: Programs for Machine Learning. //Morgan Kaufmann Publishers, 1993

случайный лес деревьев решений u, Adaboost - адаптивный бустинг 1б. Для настройки параметров классификаторов в работе использовался метод перекрестной проверки (cross validation). Лучшие результаты среди известных методов показали алгоритмы SVM, С4.5, RandomForcst и AdaBoost. Этот факт подтверждает результаты других работ. Качество алгоритма GBOT оказалось выше, чем у остальных рассмотренных алгоритмов, на 0.4% по микро-усредненным и на 1% по макроусредненным значениям Fi меры. Этот факт позволяет рекомендовать использование данного алгоритма в промышленных системах текстовой классификации.

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

Алгоритм micro macro

NB 79.0725 61.1379

kNN 94.0444 69.1224

LR 92.2424 51.7786

SVM 98.1119 88.7086

C4.5 97.5886 89.2645

RandomForest 97.9993 90.7176

Adaboost 97.8901 90.6117

GBOT 98.3603 91.8045

В заключительном четвертом параграфе показаны результаты сравнительного анализа алгоритмической сложности и затрат памяти рассмотренных в главе алгоритмов классификации. Также для каждого классификатора измерено среднее время классификации одного документа. Результаты измерений показали, что предлагаемый алгоритм GBOT показал почти на порядок более высокое быстродействие, по сравнению с другими алгоритмическими композициями (Adaboost, RandomForest). Такого эффекта удалось добиться благодаря представлению «невнимательных» деревьев решений в виде решающих таблиц, а также применению современных потоковых процессорных расширений типа SSE при программировании. Детали реализации

uBreiman L. Bagging predictors // Machine Learning 24, 123-140, 1996

15Freund Y., Schapire R. A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting // Journal of Computer and System Science, no. 55. 1997

алгоритма GBOT подробно рассматриваются в пятой главе.

Третья глава посвящена изучению возможности использования некоторых структурных особенностей документов для классификации текстов. Для генерации векторных представлений текстовых документов, учитывающих структурные элементы текста предлагается использовать принцип конечной топологии распознавания топологических форм 16. Он относится к комбинаторно-логическому направлению в распознавании образов 17. На его орнове возможно использование методов теории тестового распознавания сложных структурированных объектов. Приводится описание принципа конечной топологии распознавания топологических форм и предлагается метод представления текстовых документов, на его основе. Далее рассматриваются вопросы его применимости к задаче классификации текстовых документов 18. В разделе доказывается ряд утверждений, позволяющих рассматривать задачу текстовой классификации как задачу распознавания в топологическом пространстве. Предлагается использовать теоретическую основу принципа конечной топологии распознавания топологических форм для порождения различных векторных представлений текстовых документов, учитывающих структуру документов.

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

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

"fMov A., Jako Е., Мсгеу P. Logical models of molecular shapes and their families // Kluwer Scientific Journal Mathematical Chemistry, 2001. No.30(4). Nov. pp.389-409.

"Кудрявцев B.B., Андреев A.E. Теория тестового распознавания. Интеллектуальные системы. 2006. Т. 10. Вып. 1-4. С. 95-166.

18Гулин В.В., Сравнительный анализ методов классификации текстовых документов. - Вестник МЭИ »6 2011. - С. 100-108.

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

Таблица 2. Процентные изменения в качестве классификации для методов (3 и 4), основанных на принципе конечной топологии, относительно базовых аналогов (1 и 2)

Алгоритм FL, mi его macro

3 vs 1 4 va 2 3 vs 1 4 vs 2

NB 0.4141 0.7285 0.1525 0.3064

kNN -0.6492 -2.2536 -1.7555 -7.2013

SVM 0.1393 0.1902 0.0583 0.0519

LR 0.2020 2.5417 0.1236 1.0795

C4.5 0.0063 0.3243 0.0057 0.0724

Adaboost 0.0045 -0.0983 0.1060 0.3779

RandomForest 0.1521 -0.1362 -0.0629 -0.0473

GBOT 0.1271 -0.1128 0.4509 0.0134

В четвертой главе приводится обзор методов снижения размерности признакового описания текстовых документов. Это одна из основных проблем в задачах распознавания образов и машинного обучения. Представлено классическое разделение методов снижения размерности на методы отбора признаков и методы выделения признаков. В главе рассматриваются известные методы снижения размерности: метод главных компонент (разложение Карунена-Лоева, РСА - principal component analysis)19, метод отбора признаков по принципу максимальной релевантности и минимальной избыточности - mRMR (maximum relevance minimum redundancy)20, а также предлагается новый метод основанный на модификации метода главных признаков

19Jolliffe I.T. Principal Component Analysis // Springer Series in Statistics, 2010

20Peng H., Long F., Ding C., Feature selection based on mutual information: criteria of max-dependency, max-relevance, and min-redundency // IEEE Transactions on pattern analysis and machine intelligence, vol. 27, no. 8, 2005

(principal feature analysis) 21, названный модифицированным методом главных признаков - MPFA 22 (алгоритм 2), и отличающийся от оригинального алгоритма шагами 5-6. На шаге 5 в оригинальном алгоритме используется алгоритм кластеризации к-средних 23, на б шаге выбирается признак, наиболее близкий к центру кластера.

Алгоритм 2. Модифицированный метод главных признаков_

Вход: нормированные и центрированные данные X, q - количество при, знаков, которое необходимо выбрать; Выход: sj, S2,..., sq - набор главных признаков;

1. Объявить набор главных признаков пустым множеством 0

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

3. Вычислить собственные векторы А и собственные значения Аі > Аг > ... > Лд/ корреляционной матрицы Е.

4. Выделить подматрицу Aq, составленную из первых q столбцов матрицы А. Обозначим VI, Vj,..., Vn є Rq строки матрицы Aq.

5. Кластеризовать векторы [Vi|, IV2I,..., |V„| є Rq (|V| - вектор, составленный из абсолютных значений координат вектора V) на р > q кластеров используя алгоритм самоорганизующихся карт (self-organizing maps - SOM). В качестве расстояния в алгоритме кластеризации использовать евклидову метрику.

6. Для каждого нейрона самоорганизующейся карты

найти соответствующий вектор Vi, который ближе всего к опорному вектору нейрона.

7. Добавить признак s,- в итоговый набор главных признаков.

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

21Cohen I., Tian Q., Zhou X., Huang T. Feature selection using principal feature analysis // Proceedings of the 15th international conference on Multimedia, pages 301-304, 2007

22Гулин B.B. Методы снижения размерности признакового описания документов в задаче классификации текстов. - Вестник МЭИ, №2, 2013. - С. 115-121.

23Steinkaus Я. Sur la division des corps matériels en parties. Bull. Acad. Polon. Sci., Cl. Ill vol IV: 801—804, 1956

гакизующиеся карты Кохонена 24, вместо метода к-средних. Шаги же 1-4 повторяют аналогичные шаги метода главных компонент.

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

Т&блица 3. Процентные изменения в качестве классификации по макроусредненным и микроусредненным значениям Fi меры

Алгоритм FL.rmcro macro

PCA mRMR MPFA PCA mRMR MPFA

kNN 3.38 2.74 2.43 14.84 11.46 11.11

SVM -0.42 0.28 -0.232 -9.73 1.61 1.03

C4.5 -0.81 0.13 -0.272 -6.13 0.35 -0.12

RF 0.05 0.24 0.26 -3.01 1.14 1.19

AB -0.11 0.29 0.08 -3.58 0.90 0.69

GBOT -0.33 0.09 -0.17 -4.24 0.65 0.38

Из результатов сравнения делается вывод, что лучшим методом снижения размерности оказался метод mRMR. Этот факт легко объяснить тем, что метод mRMR использует информацию о классах обучающей выборки. Алгоритмы, использующие признаковые описания, полученные применением предложенного модифицированного метода главных признаков, показывают более высокое качество классификации, в сравнении с алгоритмами, опирающимися на признаковые описания, полученные методом главных компонент. Кроме того, данный метод позволяет отбирать признаки исходного признакового описания в отличие от метода главных компонент, который позволяет лишь синтезировать новый набор признаков, не поддающихся естественной интерпретации и предполагающих выполнение существенных вычислений. Несмотря на незначительную потерю в качестве классификации относительно метода mRMR, модифицированный метод главных признаков оказывается предпочтительнее метода mRMR в задачах классификации текстов, для которых разметка полной коллекции документов экспертами невозможна или сопряжена со значительными временными и финансовыми затратами (например, задача статического ранжирования URL адресов web страниц).

uKohonen Т. Self-organizing mapa (Third extended edition) // Springer, 2001

Пятая глава посвящена описанию созданных автором программных средств классификации текстовых документов. Работа этих программ основывается на предложенной модели представления текстовых документов и предложенном методе классификации СТЮТ. Для достижения максимального быстродействия для реализации программных средств был выбран язык С++. Глаза содержит описание архитектуры, сценариев функционирования и результаты экспериментального исследования производительности разработанного программного модуля классификации.

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

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

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

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

двух основных компонент:

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

• классификатор - обучает модели классификации текстовых документов для каждого класса.

Модуль типовой ,

предобработки 1

Эксперт

классификации , I

Классификатор

Рисунок 2. Схема модуля классификации текстовых документов

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

Разработанные программные средства внедрены в проект «]IoHCK@Mail.Ru», разрабатываемый ООО «Мэйл.Ру»и используются для решения задач классификации поисковых запросов, классификации страниц коммерческих сайтов по степени релевантности запросу и приоритезации URL адресов web-страниц для их загрузки поисковым роботом.

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

Основные результаты работы

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

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

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

3. Разработан новый метод классификации, являющийся методом градиентного бустинга (gradient boosting) на «невнимательных»деревьях решений, допускающий распараллеливание вычислений на этапе классификации. Даны рекомендации по выбору настраиваемых параметров разработанного метода, получены оценки вычислительной сложности.

4. Проведена программная реализация предложенного метода градиентного бустинга на «невнимательных»деревьях решений на языке С++ с использованием различных современных технологий параллельного программирования (SSE, OpenMP, MPI, MapReduce).

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

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

7. Проведена программная реализация предложенной модификации алгоритма главных признаков на языке С++ с использованием современных технологий параллельного программирования (SSE, OpenMP).

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

9. Разработанное программное обеспечение внедрено в проект

«IIoHCK@Mail.Ru», разрабатываемый ООО «Мэйл.Ру»и используется для решения задач классификации поисковых запросов, классификации страниц коммерческих сайтов по степени релевантности запросу и приори-тезации URL адресов web-страниц для их загрузки поисковым роботом. Реализованный пакет прикладных программ может быть адаптирован к различным предметным областям и требованиям.

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

Список работ, опубликованных по теме диссертации

1. Гулин В.В., Сравнительный анализ методов классификации текстовых документов. - Вестник МЭИ, №6, 2011. - С. 100-108. (Из списка ВАК.)

2. Гулин В.В., Исследование метода градиентного бустинга на «невнимательных» деревьях решений в задаче классификации текстовых документов. - Вестник МЭИ, №6, 2012. - С. 124-131. (Из списка ВАК.)

3. Гулин В.В., Методы снижения размерности признакового описания документов в задаче классификации текстов. — Вестник МЭИ, №2, 2013. -С. 115-121. (Из списка ВАК.)

4. Гулин В.В., Сравнение методов классификации текстовых документов. - Труды XIX международной научно-технической конференции «Информационные средства и технологии». Т.З. - М.: Издательский дом МЭИ, 2011 - С. 207-214.

5. Гулин В.В., Применение метода градиентного бустинга на «невнимательных»деревьях решений в задаче классификации текстовых документов. - Труды XX международной научно-технической конференции «Информационные средства и технологии». Т.1. - М.: Издательский дом МЭИ, 2012 - С. 156-163.

6. Гулин В.В. Сравнение методов классификации текстовых документов, ВИНИТИ, №360-В2012 (ФГБОУ ВПО Национальный исследовательский университет «МЭИ», 2012), 62 с.

7. Гулин В.В., рук. д.т.н проф. A.B. Фролов. Исследование методов классификации текстовых документов. - Труды XVIII международной научно-технической конференции студентов и аспирантов «Радиоэлектноника, электротехника, энергетика»-М.: Издательский дом МЭИ, 2012 - С. 13. ^

Подписано в печать Зак. ЛТир. W0 П.л.

Полиграфический центр МЭИ, Красноказарменная ул.,д.13

i

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

04201353401 и

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

ь/ид^

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

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ И ПРОГРАММНЫХ СРЕДСТВ КЛАССИФИКАЦИИ ТЕКСТОВЫХ ДОКУМЕНТОВ

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

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

Научный руководитель: доктор технических наук, профессор, Фролов Александр Борисович

Москва 2013

Содержание

Введение 4

1. Задача классификации текстовых документов 18

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

1.2. Задачи автоматической обработки текстов ................................19

1.2.1. Вопросы предварительной обработки текстов...........20

1.2.1. Стеммипг и лемматизация............................................25

1.2.3. Алгоритм лемматизации..............................................28

1.2.4. Способы представления текстовой информации ..................32

1.3. Формализация задачи классификации текстов в терминах задачи машинного обучения с учителем................................................35

2. Классификация текстовых документов методами машинного обучения 42

2.1. Классификация текстовых документов известными методами.....42

2.1.1. Применение байесовских методов классификации........42

2.1.2. Применение метрических методов классификации........45

2.1.3. Применение линейных методов классификации..........47

2.1.4. Применение логических методов классификации.........53

2.1.5. Применение алгоритмических композиций ........................61

2.2. Метод градиентного бустинга па «невнимательных»деревьях решений 70

2.3. Сравнительный анализ качества классификации алгоритмов......80

2.4. Анализ алгоритмической сложности и затрат памяти алгоритмов классификации ......................................................................82

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

3.1. О конструировании признаков текста ......................................86

3.2. Применение принципа конечной топологии распознавания топологических форм в задаче классификации текстов..............................88

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

4. Методы снижения размерности признакового описания 99

4.1. Мотивация для снижения размерности ....................................99

4.2. Лингвистический подход к снижению размерности признакового описания ......................................100

4.3. Методы машинного обучения снижения размерности признакового описания....................................105

4.3.1. Метод главных компонент......................105

4.3.2. Критерий отбора признаков по принципу минимальной избыточности и максимальной релевантности..............109

4.3.3. Метод главных признаков......................112

4.4. Сравнительный анализ качества классификации для методов снижения размерности................................117

4.5. Анализ алгоритмической сложности и затрат памяти алгоритмов снижения размерности..............................118

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

5.1. Описание архитектуры системы классификации текстовых документов 122

5.2. Реализация лемматизатора .........................125

5.2.1. Представления словаря в виде сжатого префиксного дерева . . 126

5.3. Реализация алгоритма GBOT........................127

5.3.1. Мета-алгоритм градиентного бустинга...............127

5.3.2. Представление «невнимательных»деревьев решений в виде решающих таблиц............................128

5.3.3. Алгоритм конструирования «невнимательного»дерева решений 130

5.3.4. Эффективное вычисление ансамбля «невнимательных»решающих деревьев.................................131

5.4. Реализация модифицированного метода главных признаков......133

5.4.1. Вычисление корреляционной матрицы...............133

5.4.2. Вычисление собственных значений и собственных векторов . . . 134

5.4.3. Параллельная реализация самоорганизующейся карты.....135

5.5. Новая технология программирования задач машинного обучения . . . 137

Заключение 139

Список литературы 141

Приложение 151

Введение

Стремительное развитие сети Интернет привело к резкому росту количества электронных документов. По оценкам экспертов, в настоящее время около 70% накопленной и используемой обществом цифровой информации находится в неструктурированной (текстовой) форме и лишь 30% составляют другие виды данных. Экспоненциальное с течением времени увеличение количества неструктурированных данных привело по существу к коллапсу традиционной системы получения и распределения текстовой информации, превратили рутинную операцию поиска и анализа необходимых сведений в трудоемкий и малоэффективный процесс, вызывающий информационную перегрузку пользователей. В этой ситуации особую актуальность приобретают работы по созданию систем обработки текстовой информации, так как даже высококвалифицированные эксперты испытывают затруднения по организации поиска документов и распределении полученных текстовых данных по тематикам. Как показывает практика, результаты определения предметной области документа «вручную», т.е. путем экспертного отнесения к имеющейся рубрике, обычно не превышает 80% [23].

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

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

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

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

Основными областями применения классификации текстов в современных поисковых Интернет системах являются:

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

• фильтрация неприемлемых материалов;

• определение языка документа;

• классификация пользовательских запросов;

• ранжирование новостей;

• составление интернет-каталогов;

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

• снятие неоднозначности слов при переводе фраз в автоматических переводчиках.

Для решения перечисленных задач требуется применение методов классификации на основе машинного обучения, поскольку состав и содержимое анализируемых документов постоянно изменяется, и одним из путей адаптации к этой динамике является использование таких методов. Цель методов машинного обучения для задачи классификации текстовых документов заключается в построении модели классификации на основе обучающего набора и применении построенной модели для предсказания класса или набора классов, релевантных для нового документа. Обучающий набор для рассматриваемой задачи классификации состоит из документов, каждому из которых сопоставлено множество классов, к которым данный документ относится. Такой подход обеспечивает качество классификации, сравнимое с качеством классификации, производимой человеком. Разработке и тестированию алгоритмов данного вида, а также связанным с ними алгоритмам представления текстов в настоящее время посвящены труды таких авторов как Агеев М.С., Кураленок И.Е., Joachims Т., Schapire R.E., Schutze Н., Scbastiani F. Стоит отметить, что в современных прикладных задачах обучающие наборы имеют достаточно большой размер (речь идет о сотнях тысяч обучающих примеров), ввиду чего интерес представляет разработка эффективных методов машинного обучения, допускающих параллельную программную реализацию.

На сегодняшний день в задачах текстовой классификации лучше всего зарекомендовали себя метод опорных векторов [100] и методы построения алгоритмических композиций на основе бустинга (улучшения) [93]. Анализ российских и зарубежных публикаций показывает, что основные усилия исследователей [58, 66] сконцентрированы на построении классификаторов, обладающих высокими полнотой и точностью [78]. Однако при разработке методов классификации текстовых данных, имеющих вы-

сокую размерность (большое число терминов, описывающих документ), особое внимание требуется также вопросам быстродействия (т.е. уменьшению времени, затрачиваемого на отнесение документа к одному из классов). В литературе практически нет работ, посвященных проблемам производительности классификаторов [38]. Фактически, проблемы быстродействия классификаторов ложатся на плечи разработчиков систем машинного обучения. На практике реализация мер, направленных на увеличение точности классификации, обычно приводит к снижению быстродействия. Обеспечение высокого быстродействия имеет особую важность в крупных поисковых системах при решении таких задач как анализ поисковых запросов [97], поступающих от пользователей в режиме реального времени, приоритезации URL(Uniform Resource Locator) адресов web страниц [90], число которых достигает нескольких миллиардов, для их загрузки поисковым роботом. Стоит отметить, что подобные системы относятся к классу высоконагруженных, т. е. обладающих либо большим количеством одновременных сессий пользователей, либо большим объемом данных, или совокупностью этих критериев. При решении конкретной задачи быстродействие является ключевым фактором при выборе того или иного метода для таких систем.

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

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

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

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

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

2. Обоснование выбора метода векторного представления текстового документа.

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

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

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

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

7. Оценка эффективности предложенных решений на характерной коллекции текстовых документов проведением численных экспериментов.

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

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

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

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

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

• Исследована применимость принципа конечной топологии распознавания топологических форм [24] к задаче классификации текстов с оценкой эффективности его использования.

• Разработан новый метод классификации, являющийся методом градиентного бустинга (gradient boosting) [47] на «невнимательных» деревьях решений (oblivious decision trees) [70], допускающий распараллеливание вычислений на этапе классификации. Даны рекомендации по выбору настраиваемых параметров разработанного метода, приведены оценки вычислительной сложности и затрат памяти. Предложены стратегии регуляризации.

• Предложена модификация метода главных признаков [41], использующая самоорганизующиеся карты Кохоиена (self-organizing maps) [71] вместо метода k-средних (k-means) [98]. Даны рекомендации ио

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

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

• Осуществлена программная реализация предложенного метода градиентного бустипга на «невнимательных»деревьях решений с использованием различных современных технологий параллельного программирования (SSE (. Streaming SIMD Extensions, потоковое SIMD-расширепие процессора) [65], OpenMP (Open Multi-Processing) [40], MPI (Message Passing Interface) [3], MapReduce [45]).

• В результате исследований на коллекции текстовых документов Reuters-21578 [59] было установлено, что разработанный метод градиентного бустинга на «невнимательных» деревьях решений в среднем на порядок увеличивает быстродействие и, как правило, показывает более высокое качество классификации по сравнению с традиционными методами классификации текстов.

• Осуществлена программная реализация предложенной модификации алгоритма главных признаков с использованием современных технологий параллельного программирования (SSE [65], OpenMP [40]).

Результаты данной работы внедрены в проект «noHCK@Mail.Ru», разрабатываемый ООО «Мэйл.Ру»и используются для решения следующих задач:

• классификация поисковых запросов;

• классификация страниц коммерческих сайтов по степени релевантности запросу;

• приоритезация URL адресов web-страниц для их загрузки поисковым роботом.

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

Апробация. Основные положения диссертационной работы докладывались на XIX международной научно-технической конференции «Информационные средства и технологии» 2011, XX международной научно-технической конференции «Информационные средства и технологии» 2012, XVIII международной научно-технической конференции студентов и аспирантов «Радиоэлектноника, электротехника, энергетика» (2012), научном семинаре «Дискретные математические модели» кафедры математического моделирования, научном семинаре кафедры вычислительных машин, систем и сетей (НИУ «МЭИ »).

Публикации. По теме диссертации опубликовано 9 научных работ, в том числе 3 в изданиях по перечню ВАК. Зарегистрировано 2 объекта интеллектуальной собственности: свидетельства о регистрации программ №2013612095 и №2013612097.

Объем и структура работы. Диссертация состоит из введения, 5 глав, заключения и 4 приложений. Список использованной литературы содержит 101 наименование. Текст диссертации содержит 172 ст