Содержание к диссертации
Введение
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% составляют другие виды данных. В этой ситуации особую актуальность приобретают работы по решению различных задач для удобной работы с неструктурированной информацией.
Классификация текстов, т.е. сортировка текстовых документов по заранее определенным категориям, является одним из способов структурирования данных. Основными областями применения классификации текстов в современных поисковых Интернет системах являются задачи: фильтрация спама, фильтрация неприемлемых материалов, ранжирование новостей, проверка авторства, составление интернет-каталогов, контекстная реклама.
Для решения перечисленных задач требуется применение методов классификации на основе машинного обучения, поскольку состав и содержимое анализируемых документов постоянно изменяется, и одним из путей адаптации к этой динамике является использование таких методов. Целью применения методов машинного обучения для задачи классификации текстовых документов является построение модели классификации на основе обучающего набора и применение построенной модели для предсказания класса или набора классов, релевантных для нового документа. Обучающий набор для рассматриваемой задачи классификации состоит из документов, каждому из которых сопоставлено множество классов, к которым данный документ относится. Разработке и тестированию методов данного вида, а также связанным с ними алгоритмам анализа текстов в настоящее время посвящены труды таких авторов как Агеев М.С., Кураленок И.Е., Joachims T., Schapire R.E., Schutze H., Sebastiani F. Стоит отметить, что в современных прикладных задачах обучающие наборы имеют достаточно большой размер (речь идет о сотнях тысяч обучающий примеров), ввиду чего интерес представляет разработка эффективных методов машинного обучения, допускающих параллельную программную реализацию.
На сегодняшний день в задачах текстовой классификации лучше всего зарекомендовали себя следующие методы: метод опорных векторов и методы построения алгоритмических композиций на основе бустинга (улучшения). Анализ российских и зарубежных публикаций показывает, что основные усилия исследователей сконцентрированы на построении классификаторов, обладающих высокими полнотой и точностью. Однако при разработке методов классификации текстовых данных, имеющих высокую размерность (большое число терминов, описывающих документ), особое внимание требуется уделить также вопросам быстродействия (т.е. уменьшению времени, затрачиваемого на отнесение документа к одному из классов). В литературе практически нет работ, посвященных проблемам производительности классификаторов. Фактически, проблемы, связанные с быстродействием классификаторов, ложатся на плечи разработчиков систем машинного обучения. На практике реализация мер, направленных на увеличение точности классификации, обычно приводит к снижению быстродействия. Обеспечение высокого быстродействия имеет особую важность в крупных поисковых системах при решении таких задач, как анализ поисковых запросов, поступающих от пользователей в режиме реального времени, приоритезации URL - Uniform Resource Locator адресов web страниц, число которых достигает нескольких миллиардов, для их загрузки поисковым роботом. Стоит отметить, что подобные системы относятся к классу высоконагруженных, т. е. обладающих либо большим количеством одновременных сессий пользователей, либо большим объемом данных, или совокупностью этих критериев. При решении конкретной задачи быстродействие является ключевым фактором при выборе того или иного метода для таких систем.
Таким образом, на сегодняшний день для современных поисковых Интернет систем является актуальным проведение исследований методов и алгоритмов классификации текстовых документов на основе машинного обучения, обеспечивающих высокое быстродействие при сохранении или повышении качества (полноты и точности) классификации, и разработка программных средств реализующих такие методы и алгоритмы.
Цель диссертационной работы. Целью диссертации является повышение быстродействия и качества классификации текстовой информации поисковых Интернет систем на основе современных технологий программирования задач машинного обучения.
Под современными технологиями программирования задач машинного обучения в данной работе будем понимать применение современного аппарата методов машинного обучения с использованием технологий параллельного программирования, актуальных на сегодняшний день.
Для достижения указанной цели в диссертации решаются следующие задачи:
-
Разработка и программная реализация средства лингвистического анализа текстовых документов - лемматизатора.
-
Обоснование выбора метода векторного представления текстового документа.
-
Определение возможности использования некоторых структурных особенностей документов в задаче текстовой классификации и оценка эффективности использования подобной информации.
-
Комплексный сравнительный анализ известных методов машинного обучения применительно к задаче текстовой классификации.
-
Разработка метода машинного обучения, обладающего более высоким качеством и быстродействием, обусловленным возможностью эффективного распараллеливания вычислений на этапе классификации, по сравнению с известными методами.
-
Комплексный сравнительный анализ традиционных методов снижения размерности признаковых описаний документов применительно к задаче классификации текстов и обоснование метода, обеспечивающего более высокое быстродействие.
-
Оценка эффективности предложенных решений на характерной коллекции текстовых документов проведением численных экспериментов.
-
Разработка программных средств обработки и анализа массивов текстовой информации, удовлетворяющих требованиям современных высоко- нагруженных поисковых Интернет систем, на основе предложенных в работе процедур и известных методов.
Методы исследования. Полученные в диссертации результаты основываются на применении методов статистического и лингвистического анализа текстов, теории вероятностей, теории информации, математической статистики, линейной алгебры, теории алгоритмов, теории параллельного программирования, численных методов.
Научная новизна. Основные результаты работы являются новыми и заключаются в следующем:
-
Разработан и реализован лингвистический модуль (морфологический анализатор), позволяющий проводить лемматизацию текстов на русском и английском языках. С помощью разработанной методики, обоснован выбор используемых в работе процедур предварительной обработки текстовых документов.
-
Исследована применимость принципа конечной топологии распознавания топологических форм к задаче классификации текстов с оценкой эффективности его использования.
-
Разработан новый метод классификации, являющийся методом градиентного бустинга на «невнимательных» деревьях решений, допускающий распараллеливание вычислений на этапе классификации. Даны рекомендации по выбору настраиваемых параметров разработанного метода, приведены оценки вычислительной сложности и затрат памяти. Предложены стратегии регуляризации.
-
Предложена модификация метода главных признаков, использующая самоорганизующиеся карты Кохонена вместо метода k-средних. Даны рекомендации по выбору размера самоорганизующейся карты. Представлены оценки вычислительной сложности и затрат памяти.
Практическая ценность.
-
Осуществлена программная реализация предложенного метода градиентного бустинга на «невнимательных»деревьях решений с использованием различных современных технологий параллельного программирования (SSE - Streaming SIMD Extensions, OpenMP - Open MultiProcessing, MPI - Message Passing Interface, MapReduce).
-
В результате исследований на коллекции текстовых документов Reuters-21578 было установлено, что разработанный метод градиентного бустинга на «невнимательных» деревьях решений в среднем на порядок увеличивает быстродействие и, как правило, показывает более высокое качество классификации по сравнению с традиционными методами классификации текстов.
-
Осуществлена программная реализация предложенной модификации алгоритма главных признаков с использованием современных технологий параллельного программирования (SSE, OpenMP).
Результаты данной работы внедрены в проект «Поиск@Маіі^и», разрабатываемый ООО «Мэйл.Ру»и используются для решения следующих задач:
-
классификация поисковых запросов;
-
классификация страниц коммерческих сайтов по степени релевантности запросу;
-
приоритезация URL адресов web-страниц для их загрузки поисковым роботом.
Разработанное программное обеспечение может быть адаптировано к различным предметным областям и требованиям.
Апробация. Основные положения диссертационной работы докладывались на XIX международной научно-технической конференции «Информационные средства и технологии» 2011, XX международной научно-технической конференции «Информационные средства и технологии» 2012, XVIII международной научно-технической конференции студентов и аспирантов «Радио- электноника, электротехника, энергетика» (2012), научном семинаре «Дискретные математические модели» кафедры математического моделирования,
научном семинаре кафедры вычислительных машин, систем и сетей (НИУ «МЭИ»),
Публикации. По теме диссертации опубликовано 7 научных работ, в том числе 3 в изданиях из перечня ВАК, выполненных при финансовой поддержке РФФИ, проект №11-01-00792-a. Зарегистрировано 2 объекта интеллектуальной собственности: свидетельства о регистрации программ №2013612095 и №2013612097 .
Объем и структура работы. Диссертация состоит из введения, 5 глав, заключения и 4 приложений. Список использованной литературы содержит 101 наименование. Текст диссертации содержит 172 страницы машинописного текста, включая 32 рисунка.
Вопросы предварительной обработки текстов
Цифровые документы, являющиеся входной информацией для процесса обработки текстовых данных, как правило, представляют собой набор байтов в файле или на веб-сервере. На первом шаге обработки эта последовательность байтов преобразуется в линейную последовательность символов. Для английского текста, набранного в системе кодирования ASCII, такая задача тривиальна. Однако часто такая задача оказывается куда как сложнее. Последовательность символов может быть закодирована в одной из многих одно- или многобайтовых кодировок (например UNICODE UTF-8 ) или в стандарте, определяемом поставщиком оборудования (например IBM866). В первую очередь необходимо верно определить кодировку. Эту проблему можно интерпретировать как задачу классификации на основе машинного обучения [78], но на практике ее часто решают с помощью эвристических методов, выбора пользователя или имеющихся метаданных о документе. После того как кодировка определена, последовательность байтов преобразуется в последовательность символов. Полученную кодировку следует запомнить, поскольку эта информация даст представление о языке, на котором написан документ.
Возможно, символы нужно декодировать из двоичного представления, например из doc-файла текстового процессора Microsoft Word и/или архивных файлов наподобие zip-файлов. Таким образом, сначала нсобходимо определить формат документа, а затем выбрать соответствующий алгоритм декодирования. Также может понадобиться отделить текстовую часть документа от другого материала, содержащего служебную информацию о документе или информацию другого типа (изображение или видео). Это часто практикуется при обработке XML-файлов, если требуется проигнорировать разметку, а также почти всегда при обработке postscript- и PDF-файлов.
После идентификации последовательности символов текст разделяется на лексемы. Кроме того, иногда из него одновременно удаляются некоторые символы, например знаки пунктуации. Рассмотрим пример:
Ввод: Я пригласил вас, господа, с тем, чтобы сообщить вам пренеприятное известие
Вывод: Я пригласил вас господа с тем чтобы сообщить вам пренеприятное известие Эти лексемы иногда ошибочно называются терминами или словами, однако следует четко отличать класс лексем и экземпляр лексемы (type/token). Лексема(іоксп) - это экземпляр последовательности символов в определенном документе, объединенных в семантическую единицу для обработки. Tnn(type) - это класс всех лексем, состоящих из одной и той же последовательности символов. Термин (term) - это (возможно, нормализованный) тип, включенный в словарь системы информационного поиска.
Основной вопрос, связанный с разделением текста на лексемы, звучит так: "Как правильно разделить текст на лексемы?". В нашем примере ответ очевиден: достаточно разделить текст по пробелам и отбросить знаки пунктуации. Это отправная точка, но даже в английском языке здесь содержится много подвохов. Например, что делать с разными формами апострофа, используемого для образования притяжательной формы и сокращений.
Задача классификации текстовых документов Подобные проблемы существенно зависят от языка. Следовательно, язык документа должен быть известен заранее. Таким образом, возникает задача определения языка (language identification), которую также принято [79] интерпретировать как задачу классификации на основе машинного обучения [78]. Конкретно для задачи определения языка, применение классификаторов, использующих в качестве признаков короткие последовательности символов, является очень эффективным [79].
В большинстве языков и конкретных предметных областей существуют необычные специфические лексемы, которые следует распознавать, как термины: языки программирования C++ и С#, названия самолетов, например СУ-37. Компьютерные технологии породили новые типы последовательностей символов, которые следует распознавать, как одну лексему, в частности адреса электронной почты (support@mail.ru), веб-адреса (URL) (http://go.mail.ru), числовые ІР-адрсса (142.32.48.231) и т.д.
В английском языке расстановка дефисов (hyphenation) используется для разных целей: для разделения гласных букв в словах (co-education), для объединения существительных в названиях (Hewlett-Packard), а также для группирования слов (the hold-him-back-and-drag-him-away maneuver) [78]. Легко видеть, что первый пример нужно рассматривать как одну лексему (на самом деле, это слово чаще записывается как coeducation), последний следует разделить на несколько слов, а второй пример остается неясным. Следовательно, автоматическая обработка дефиса может оказаться сложной: можно либо рассматривать се как задачу классификации, либо применять некие эвристические правила.
В принципе, разделение текста по пробелам приводит к разрыву слов, которые следовало бы рассматривать как целые лексемы. Это часто происходит с названиями (San Francisco, Los Angeles), а также с фразами, заимствованными из иностранных языков (au fait), сложными словами,
Задача классификации текстовых документов которые могут записываться как с пробелами, так и слитно (например, white space whitespace). К словам с внутренними пробелами, которые следовало бы рассматривать как отдельную лексему, относятся телефонные номера (800-234-2333) и даты (Маг 8, 2013). Разделение лексем по пробелам может привести к неверным результатам. Например, при поиске York University будут также возвращаться документы, содержащие словосочетание New York University. Проблемы, связанные с дефисом и неразделяющими пробелами, могут оказаться взаимосвязанными. Например, реклама авиационных перелетов часто содержит слова San Francisco-Los Angeles. Совершенно очевидно, что в этом случае разделение по пробелам приведет к неправильным результатам.
Для решения этой проблемы можно было бы на этапе предварительной лингвистической обработки провести сегментацию на слова (word segmentation). Методы сегментации па слова весьма разнообразны: от использования большого лексикона (выполняется поиск самой длинной последовательности, представленной в лексиконе, дополнительно используются эвристики для незнакомых слов) до использования методов машинного обучения, таких как скрытые марковские модели (ЫММ - hidden markov models) [30] или условные случайные поля (CRF - Conditional Random Fields) [74], обученные на основе слов, выделенных вручную. Из-за неоднозначности сегментации последовательности символов вес эти методы иногда порождают ошибки и поэтому не могут гарантировать непротиворечивое и однозначное разбиение на лексемы. Альтернативный метод основан на отказе от обработки слов и переходе к обработке коротких последовательностей символов независимо от того, пересекают ли эти подпоследовательности границы слов.
Иногда некоторые очень распространенные слова, не представляющие никакой информационной ценности, вообще исключаются из лексикона. Они называются стоп-словами (stop-words). Как правило, для создания
Задача классификации текстовых документов списков стоп-слов термины упорядочиваются по числу повторений термина в коллекции, а затем наиболее часто встречающиеся термины, отфильтрованные вручную с учетом их семантической связи с предметной областью обрабатываемых документов, включаются в список стоп-слов (stop-list), элементы которого при индексировании отбрасываются. В большинстве случаев игнорирование стоп-слов при обработке текста не вызывает проблем: использование предлогов the и by в качестве признаков какой-либо тематики вряд ли можно назвать очень полезным. Однако в случае, когда в качестве признака используется целая фраза, это не так (например President of the United States). В современных же поисковых Интернет системах стоп-слова вообще рассматриваются наряду с обычными словами.
Допустим, что документ уже разделен на лексемы и необходимо определить, содержится ли среди лексем документа нужный признак, характеризующий конкретную тематику. Очень часто может оказаться так, что конкретный признак не совпадает с определенной лексемой, однако они считаются эквивалентными. Например, если проводится поиск слова USA, хотелось бы также найти аббревиатуру U.S.A.
Нормализация лексем (token normalization) - это процесс приведения лексем к канонической форме, чтобы устранить несущественные различия между последовательностями символов. Самый распространенный способ нормализации заключается в неявном создании классов эквивалентности (equivalence classes), которые обычно называются по имени одного из их членов. Например, если в тексте документов лексемам anti-discriminatory и antidiscriminatory ставится в соответствие термин апidiscriminatory, то в ходе поиска одного термина обязательно будет находиться и другой.
Применение алгоритмических композиций
В ситуациях, когда ни один из алгоритмов не обеспечивает желаемого качества классификации, имеет смысл строить алгоритмические композиции, в которых решающее правило определяется как некоторая функция от результатов классификации отдельных алгоритмов.
Понятие композиции алгоритмов. Наиболее общее определение алгоритмической композиции дается в алгебраическом подходе Ю.И. Журавлева [17]. Наряду с множествами X и С вводится вспомогательное множество R, называемое пространством оценок. Рассматриваются алгоритмы, имеющие вид суперпозиции f{x) = Z(b(x)), где функция b : X — R называется алгоритмическим оператором, функция Z : R — С - решающим правилом.
В этих обозначениях алгоритмическая композиция ft(х) = Z(bt(x)), t = 1,..., Т, определяется как суперпозиция алгоритмических операторов
Алгоритмы bt называют базовыми алгоритмами. Суперпозиции вида F(b\,..., Ьт) являются отображениями из X в R, то есть, опять-таки, алгоритмическими операторами, что позволяет строить иерархические композиции, определяемые рекурсивно.
Взвешенное голосование. Корректирующая операция F может иметь параметры, настраиваемые по обучающей выборке, наряду с параметрами базовых алгоритмов. Например, в линейной комбинации настраиваются веса at базовых алгоритмов:
Естественно предполагать, что вес щ тем больше, чем выше качество
Классификация текстовых документов методами машинного обучения базового алгоритма bt. Данная корректирующая операция называется взвешенным голосованием (weighted voting).
Бустинг в задачах классификации [93] . Рассмотрим задачу классификации на два класса, С = {—1, +1}- Допустим, что решающее правило фиксировано, Z(b) = sign(b), базовые алгоритмы возвращают ответы -1, 0, -(-1. Ответ bt(x) = 0 означает, что базовый алгоритм bt отказывается от классификации объекта х, и ответ bt(x) не учитывается в композиции. Искомая алгоритмическая композиция имеет вид:
Определим функционал качества композиции как число ошибок, допускаемых ею на обучающей выборке:
Для упрощения задачи минимизации функционала QT сделаем два предположения: во-первых, при добавлении в композицию очередного слагаемого atbt(x) будем оптимизировать только базовый алгоритм bt и коэффициент при нем at, а все предыдущие слагаемые a\bi{x),.... a,t-.\bt-i{x) будем считать фиксированными; во-вторых, пороговую функцию потерь в функционале Qt заменим непрерывно дифференцируемой оценкой сверху. Эти предположения называются предположениями бустинга (улучшения) в задачах классификации.
Алгоритм Adaboost (adaptive boosting - адаптивный бустинг). При использовании экспоненциальной замены [Q6(XJ) 0] е-0 "2" эти два предположения приводят к широко известному алгоритму AdaBoost [46] (алгоритм 2.3).
Классификация текстовых документов методами машинного обучения Алгоритм 2.3. AdaBoost - построение линейной комбинации классификаторов
Определим два функционала качества алгоритма классификации Ь на обучающей выборке Qtr с нормированным вектором весов W = (wi,... , Щ/v): суммарный вес ошибочных (negative) классификаций N(b; W) и суммарный вес правильных (positive) классификаций P(b; W):
Микроусреднснные и макроусредненные значения меры F\ (1.18) и (1.16) будут вычисляется по значениям предиката Алгоритм AdaBooat прост в реализации и обладает хорошей обобщающей способностью. Эта обобщающая способность оказывается выше, чем у базовых алгоритмов и часто может улучшаться по мере увеличения числа базовых алгоритмов. Кроме того, алгоритм AdaBoost обладает возможностью идентифицировать объекты-выбросы в обучающих данных. Время построения композиции алгоритмом AdaBoost определяется временем обучения базовых алгоритмов, т.е. сам алгоритм не дает никаких накладных расходов.
Однако у алгоритма AdaBoost есть и недостатки. AdaBoost склонен к переобучению при наличии зашумленных данных. Экспоненциальная функция потерь слишком сильно увеличивает веса объектов-выбросов, на которых ошибаются многие базовые алгоритмы, что введет к настройке алгоритма на шум. Сам алгоритм для достижения хорошей обобщающей способности требует достаточно больших обучающих выборок.
Классификация текстовых документов методами машинного обучения Жадный алгоритм добавления базовых алгоритмов приводит к образованию их неоптимального набора. В целом, бустинг может приводить к построению громоздких композиций, состоящих из сотен алгоритмов. Результаты классификации такой композиции пс могут быть интерпретированы содержательным образом. Как следствие, требуется большой объем памяти для хранения базовых алгоритмов и существенное время на классификацию.
Для коллекции Reuters-21578 получены оценки обобщающей способности алгоритма AdaBoost по макроусредненным и микроусредненным значениям F\ меры, представленным в таблице 2.6 (результаты получены при помощи авторской программы [15]).
Бэггинг и метод случайных подпространств. Кроме бустинга существует и другая стратегия построения алгоритмических компози Классификации текстовых документов методами машинного обучения цнй, когда базовые алгоритмы настраиваются независимо друг от друга на случайно выбранных подмножествах обучающей выборки, либо на различных случайных подмножествах признаков - случайных подпространствах.
Метод независимой настройки базовых алгоритмов на независимых друг от друга случайно выбранных подмножествах обучающей выборки называется методов бэггинга (bagging, bootstrap aggregation). Он был предложен Л. Брсймсном в 1996 году [35]. Из исходной обучающей выборки длины N формируются различные обучающие подвыборки той же длины N с помощью случайного выбора с возвращениями. При этом некоторые объекты попадают в подвыборку по нескольку раз, некоторые - ни разу. Базовые алгоритмы, обученные но подвыборкам, объединяются в композицию с помощью простого голосования.
Эффективность бэггинга объясняется двумя обстоятельствами. Во-первых, благодаря различности базовых алгоритмов, их ошибки взаимно компенсируются при голосовании. Во-вторых, объекты-выбросы могут не попадать в некоторые обучающие подвыборки. Тогда алгоритм, построенный по подвыборке, может оказаться даже точнее алгоритма, построенного по полной выборке.
Бэггинг особенно эффективен на малых выборках, когда исключение даже небольшой доли обучающих объектов приводит к построению существенно различных базовых алгоритмов. В случае сверхбольших избыточных выборок приходится строить подвыборки меньшей длины Щ С N, при этом возникает задача подбора оптимального значения N0.
В методе случайных подпространств (random subspace method, RSM) базовые алгоритмы строятся на различных подмножествах признакового описания, которые также выбираются случайным образом [57]. Такой метод более предпочтителен в задачах с большим числом признаков
Классификация текстовых документов методами машинного обучения и относительно небольшим размером обучающих данных, а также при наличии неинформативных признаков. В таких ситуациях алгоритмы, построенные по части признакового описания, могут обладать лучшей обобщающей способностью, чем алгоритмы, построенные но всем признакам.
Полученные базовые алгоритмы объединяются в композицию с помощью простого или взвешенного голосования. В случае взвешенного голосования для настройки коэффициентов at применяются стандартные линейные методы.
Обобщение бэггинга и RSM приводит к Алгоритму 2.4. Пусть объекты описываются набором признаков Т = {F\,..., FM} И метод обучения /х(Ф, U) строит алгоритмический оператор по обучающей подвы-борко U С Qtrj используя только часть признакового описания ФС7. Выборка объектов на шаге 2 может производиться как с возвращениями, так и без возвращений; вообще говоря, это еще один (бинарный) параметр алгоритма. Числа N — \\U\\ N и М = Ф] М являются параметрами метода. Алгоритм 2.4 соответствует бэггингу при Ф = J- и методу случайных подпространств при U = fitr.
На этапах 5-6 отсеиваются неудачные базовые алгоритмы. Базовый алгоритм bt признается неудачным, если его качество на обучающей выборке хуже заданного порога Єї, либо качество на контрольной выборке &tr\U хуже е2. Такая ситуация может сложится, когда в обучающих данных случайно оказалось слишком много зашумленных объектов-выбросов, или среди признаков оказалось слишком много пеинформатив-ных.
Лингвистический подход к снижению размерности признакового описания
Как было описано в первой главе, существует два лингвистических подхода к снижению размерности признаковых описаний документов - стсм-минг и лемматнзация.
Для коллекции Rcuters-21578, к признаковым описаниям которой был применен метод стемминга, получены оценки обобщающей способности алгоритмов ближайшего соседа (kNN), опорных векторов (SVM), дерева решений С4.5, случайного леса деревьев решений (RandomForcst), AdaBoost, а также предложенного во второй главе алгоритма GBOT по макроусреднепным и микроусредненным значениям F\ меры, представленным в таблице 4.1 (полная таблица по 10 наиболее крупным классам
Методы снижения размерности признакового описания документов коллекции Reuters-21578 представлена в приложении 3).
Для коллекции Reuters-21578, к признаковым описаниям которой был применен метод лемматизации, получены оценки обобщающей способности алгоритмов ближайшего соседа (kNN), опорных векторов (SVM), дерева решений С4.5, случайного леса деревьев решений (RandomForest), AdaBoost, а также предложенного во второй главе алгоритма GBOT по макроусредненной и микроусредненной F\ мере, представленные в таблице 4.2 (полная таблица по 10 наиболее крупным классам коллекции Reuters-21578 представлена в приложении 3).
Методы снижения размерности признакового описания документов
Из таблиц 4.1 и 4.2 видно, в среднем, более высокое качество классификации показывают алгоритмы, использующие признаковые описания, полученные после лемматизации текстовых документов коллекции.
Рассмотрим теперь изменение качества классификации при применении стемминга и лемматизации относительно ненормализованных признаковых описаний (т.е. признаковых описаний, к которым не применялся ни один метод снижения размерности). Результаты сравнения представлены на рисунках 4.1 - 4.4.
Методы снижения размерности признакового описания документов
Как видно из рисунков 4.1 - 4.4, рост качества классификации для алгоритмов, использовавших признаковые описания, полученные посредством лемматизации текстовых документов коллекции, оказался больше, чем для алгоритмов, использующих при обработке текстов метод стсм-минга. В частности, для метода ближайших соседей рост составил более 3% по макроусредненным значениям F\ меры, в то время как аналогичный рост для метода стемминга составил менее 3%. Для метода опор-пых векторов снижение качества классификации составило порядка 0.5 % по макроусредненным значениям Fi меры. Аналогичный показатель для метода стемминга составил более 1 %. Таким образом, использование лемматизации в качестве метода нормализации слов текста в среднем приводит к более высокому качеству классификации. Далее будем всегда применять лемматизацию для нормализации лексем.
Эффективное вычисление ансамбля «невнимательных»решающих деревьев
Для эффективного вычисления ансамбля «исвнимательных»решающих деревьев необходимо преобразовать его к табличному виду. Будем хранить следующие значения:
Листья «невнимательных»деревьев, в виде одного непрерывного массива данных leafPredictors.
Индексы признаков - разделителей, в виде одного непрерывного массива данных splitFeaturcsIndexes.
Условия признаков - разделителей, в виде одного непрерывного массива данных splitFeaturesValues.
Тогда алгоритм вычисления ансамбля «нсвнимательных»решающих деревьев примет вид, представленный в алгоритме 5.2.
Создание и исследование программного обеспечения задач классификации текстов
Алгоритм 5.2. Эффективный алгоритм вычисления ансамбля «невнимательных» деревьев решений
Важно заметить, что в программной реализации шаги 3-5 могут быть эффективно распараллелены с помощью технологии параллельного программирования SSE.
Модифицированный метод главных признаков был представлен в четвертой главе, в данном параграфе будут рассмотрены вопросы его практической реализации.
Реализация модифицированного метода главных признаков подразумевает выполнение следующих ключевых шагов:
вычисление корреляционной матрицы:
нахождение собственных векторов и собственных значений корреляционной матрицы;
построение самоорганизующейся карты Кохонена;
Рассмотрим подробно каждый из них.
Для вычисления корреляционной матрицы необходимо предварительно нормировать и центрировать данные X:
Операция нормирования и центрирования выполняется независимо для каждого столбца матрицы X, поэтому может быть эффективно распараллелена с помощью технологии параллельного программирования ОрепМР.
Создание и исследование программного обеспечения задач классификации текстов
По нормированным и центрированным данным X корреляционная матрица может быть вычислена по следующей формуле
Другими словами, чтобы рассчитать корреляционную матрицу , необходимо перемножить две матрицы Хт и X. Существует множество способов распараллеливания операции матричного умножения [8]. В программной реализации могут быть применены технологии параллельного программирования, такие как MPI, ОрепМР и SSE.
Проблема нахождения собственных векторов и собственных значений довольно часто встречается в прикладных задачах [2], поэтому достаточно хорошо изучена. Для ее решения разработаны и исследованы специальные численные методы [16]. Нахождение собственных векторов и собственных значений для корреляционной матрицы относится к так называемой симметричной проблеме собственных значений. В данной работе для поиска собственных векторов и собственных значений был использован метод QR-итерации со стратегией сдвигов Уилкинсоиа [16], являющийся одним из наиболее эффективных в симметричном случае. Показано [84], что данный метод сходится глобально, по меньшей мере, с линейной скоростью. Для большинства матриц данный метод сходится с кубической скоростью.
Создание и исследование программного обеспечения задач классификации текстов 135
Алгоритм построения самоорганизующейся карты представлен в алгоритме 5.3 [71]. Как видно из описания алгоритма, на шаге 4 происходит поиск нейрона, в который попадает пример х. Для этого необходимо вычислить расстояния от вектора х до всех нейронов карты. Очевидно, расстояния могут быть вычислены независимо друг от друга и, следовательно, шаг 4 алгоритма 5.3. может быть распараллелен. Таким образом, могут быть применены технологии параллельного программирования ОрепМР и SSE.
Также стоит отмстить, что могут быть распараллелены шаги 5-6 обновления значений опорных векторов самоорганизующейся карты при помощи технологии параллельного программирования ОрепМР.
