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

Пескишева Татьяна Анатольевна

ПАРАЛЛЕЛЬНАЯ СИСТЕМА

ТЕМАТИЧЕСКОЙ ТЕКСТОВОЙ КЛАССИФИКАЦИИ

НА ОСНОВЕ МЕТОДА ОПОРНЫХ ВЕКТОРОВ

05.13.17 – Теоретические основы информатики

АВТОРЕФЕРАТ

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

Москва – 2012

Работа выполнена в ФГБОУ ВПО «Российский государственный гуманитарный университет».

Научные руководители: доктор физико-математических наук, профессор Аншаков Олег Михайлович, кандидат технических наук, доцент Котельников Евгений Вячеславович

Официальные оппоненты: доктор технических наук, профессор Страбыкин Дмитрий Алексеевич (заведующий кафедрой электронных вычислительных машин ФГБОУ ВПО «Вятский государственный университет») кандидат физико-математических наук, Виноградов Дмитрий Вячеславович (старший научный сотрудник Всероссийского института научной и технической информации Российской академии наук (ВИНИТИ РАН))

Ведущая организация: ФГБОУ ВПО «Нижегородский государственный университет им. Н. И. Лобачевского»

Защита диссертации состоится «19» марта 2012 г. в 15.00 часов на заседании диссертационного совета Д 212.198.13 при ФГБОУ ВПО «Российский государственный гуманитарный университет» по адресу: г. Москва, Миусская площадь, д. 6, ауд. 206.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Российский государственный гуманитарный университет».

Автореферат разослан 9 февраля 2012 г.

Ученый секретарь диссертационного совета Д 212.198. канд. техн. наук, ст. науч. сотр. Д. Б. Халяпин

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

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

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

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

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

Разработке и тестированию алгоритмов тематической текстовой классификации, а также связанным с ними моделям представления текстов посвящены труды таких авторов как М. С. Агеев, Г.Г. Белоногов, Б. В. Добров, И. Е. Кураленок, Д. В. Ландэ, Ю. М. Лифшиц, И. С. Некрестьянов, О. В. Пескова, В. И. Шабанов, I. Dagan, S. T. Dumais, M. Halkidi, T. Joachims, T. Kohonen, D. D. Lewis, X. Liu, J. Platt, R. E. Schapire, H. Schutze, F. Sebastiani, Y. Yang, и ряда других.

В настоящее время в мире существуют специализированные системы автоматической классификации текста, такие как TextAnalyst (Микросистемы), диалоговая система классификации и анализа текста ДИСКАНТ (СПб ЭМИ РАН), система классификации текстов информационных сообщений АКТИС (ИПС РАН), NNCS («Бинейро») и др.

Автоматическая классификация текстовой информации также является необходимым этапом работы других систем автоматической обработки текстов, таких как лингвистическая система ПОЛИТЕКСТ (АНО ЦИИ), университетская информационная система РОССИЯ (НИВЦ МГУ им. М. В. Ломоносова и АНО ЦИИ), поисково-аналитическая система Галактика-Zoom (Галактика), комплекс программ Russian Context Optimizer (Гарант-Парк-Интернет), системы Intelligent Miner for Text (IBM), Oracle Text (Oracle), Knowledge Server (Autonomy) и др. В перечисленных системах автоматической обработки текста классификация документов выполняется в отдельных модулях.

Большинство систем и модулей текстовой классификации имеют приемлемую скорость и точность обработки небольших и средних по объему коллекций текстов. Однако значительный рост количества и объема документов, а также увеличение числа рубрик, по которым необходимо классифицировать документы, приводит к падению производительности существующих систем. Под большим объемом данных здесь и далее понимается такой объем, обработка которого требует больше оперативной памяти, чем обычно доступно в современном персональном компьютере. Ещё одна проблема – сложность подбора оптимальных параметров классификатора, поскольку не существует общепринятой и эффективной методики их расчета, только полный перебор. Например, на стандартных текстовых коллекциях, используемых для оценки методов классификации – Reuters-21578, RCV1 (английский язык), коллекции семинара РОМИП (русский язык) – процесс обучения с подбором параметров на одном компьютере может занимать при разных условиях от нескольких часов до нескольких десятков дней.

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

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

Использование эффективных методов рубрикации в реализации системы текстовой классификации может быть еще одним путем повышения производительности программ автоматической текстовой классификации. По данным зарубежных и российских исследователей (T. Joachims, S. Dumais, J. Platt, F. Sebastiani, Y. Yang, X. Liu, D. Lewis, М. С. Агеев, Б. В. Добров и др.) наилучшие результаты при текстовой классификации показывает метод распознавания образов под названием «машины опорных векторов» (Support Vector Machines, SVM).

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

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

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

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

1. Обзор и анализ существующих модулей и систем текстовой классификации.

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

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

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

5. Экспериментальное исследование характеристик разработанной параллельной системы.

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

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

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

2. Предложен параллельный алгоритм формирования векторной модели текста для иерархической структуры вычислительной системы, основанный на подходе TF-IDF (Term Frequency – Inverse Document Frequency), отличающийся учетом количества ключевых слов документов на этапе балансировки нагрузки между узлами вычислительной системы.

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

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

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

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

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

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

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

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

5. Эффективность параллельных алгоритмов и параллельной системы автоматической классификации доказана экспериментально на общедоступных текстовых коллекциях – Reuters-21578 и RCV1.

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

1. Параллельный алгоритм формирования векторной модели текста на основе подхода TF-IDF.

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

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

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

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

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

Внедрение результатов Теоретические и практические результаты, полученные при выполнении диссертационной работы, использованы в НИР по тематическому плану ВятГГУ на 2011 год «Программная система интеллектуального анализа текстов для социально-гуманитарных исследований», в НИР «Автоматическая классификация текстов»

(ВятГГУ, договор № Н-04-10), в НИР «Разработка математических методов и алгоритмов тематической классификации текстовых документов» (ВятГГУ, НИР № 8/2008). Программная реализация параллельной системы текстовой классификации внедрена в учебный процесс в Вятском государственном университете и в Вятском государственном гуманитарном университете, а также в работу социологической лаборатории Вятского государственного гуманитарного университета.

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

1. Седьмая Международная конференция-семинар «Высокопроизводительные параллельные вычисления на кластерных системах» (г. Нижний Новгород, 2007);

2. Международная научно-практическая конференция «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании 2007» (г. Одесса, 2007);

3. Восьмая Международная конференция-семинар «Высокопроизводительные параллельные вычисления на кластерных системах» (г. Казань, 2008);

4. Международная научная конференция «Параллельные вычислительные технологии (ПАВТ’ 2009)» (г. Нижний Новгород, 2009);

5. X Межрегиональная научно-практическая конференция «Актуальные проблемы гуманитарных и экономических наук» (г. Киров, 2009);

6. Всероссийская конференция с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» (г. Ульяновск, 2009);

7. XII Межрегиональная научно-практическая конференция «Актуальные проблемы гуманитарных и экономических наук» (г. Киров, 2011);

8. Международная научная конференция «Параллельные вычислительные технологии (ПАВТ’ 2011)» (г. Москва, 2011).

Публикации. По результатам исследования опубликовано 12 печатных работ, из них статей и тезисов докладов – 11 (3 опубликованы в изданиях из числа рекомендованных ВАК для опубликования результатов диссертационных исследований), депонированная рукопись – 1. Получено свидетельство об официальной регистрации программы для ЭВМ. Список работ приведен в конце автореферата.

Структура и объем исследования. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка (включающего 147 наименований), списка сокращений и 3 приложений. Основная часть работы изложена на 164 страницах и содержит 27 рисунков и 6 таблиц.

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

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

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

В работе описаны подходы, применяемые для выделения признаков документов.

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

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

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

Наилучшие результаты при текстовой классификации показывает метод распознавания образов под названием «машины опорных векторов»2 (Support Vector Machines, SVM). В работе описаны идея, математические основы метода, случаи линейной и нелинейной разделимости, алгоритм подбора параметров для оптимальной работы классификатора.

Среди алгоритмов обучения классификатора на основе SVM выбраны алгоритм последовательной минимальной оптимизации3 (Sequential Minimal Optimization, SMO), предложенный Дж. Платтом, и алгоритм образования фрагментов Chunking4.

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

Salton G. Term-weighting approaches in automatic text retrieval // Information Processing & Management. [s.l.] : Pergamon Press, 1988. 5: Vol. 24. P. 513–523.

Sebastiani F. Machine Learning in Automated Text Categorization. ACM Computing Surveys, Vol. 34. № 1. March 2002. P. 1–47.

Platt J. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines // Microsoft Research. Technical Report MSR-TR-98-14. 1998.

Vapnik V. Estimation of Dependences Based on Empirical Data. Springer-Verlag, 1982.

Изначально метод опорных векторов был разработан для решения задач распознавания с двумя классами. В дальнейшем появились алгоритмы, позволяющие обобщить SVM на многоклассовую классификацию5. В работе исследованы два основных подхода к решению проблемы многоклассовой классификации в SVM. В первом подходе («решение за один шаг» или «все вместе», all-together) задача квадратичной оптимизации усложняется за счет увеличения размерности дополнительных переменных. В другом подходе решение задачи многоклассовой классификации сводится к решению последовательности задач с двумя классами. При этом может быть несколько стратегий генерации такой последовательности: «каждый против всех» («one-against-all»), «каждый против каждого» («one-against-one»), «турнир на выбывание» или «ориентированный ациклический граф SVM» (Directed Acyclic Graph SVM, DAGSVM).

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

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

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

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

Weston J., Watkins C. Multi-class support vector machines. Technical Report CSD-TR-98-04, Department of Computer Science, Royal Holloway, University of London, Egham, TW20 0EX, UK, 1998.

LIBSVM – A Library for Support Vector Machines [Электронный ресурс]. Режим доступа:

http://www.csie.ntu.edu.tw/~cjlin/libsvm/. Дата обращения: 01.10.2011. Загл. с экрана.

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

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

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

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

В работе предложены три стратегии распараллеливания алгоритма Chunking – Предварительное обучение, Турнир и Гонки, в качестве основной выбрана стратегия Турнир.

В этой стратегии распараллеливания проводится турнирный отбор между классификаторами процессоров. На каждом этапе турнира результаты классификации для пары процессоров объединяются. Приведем подробное описание стратегии Турнир (рис. 3).

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

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

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

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

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

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

7) Классификатор оставшегося процессора обучается на сформированном на шаге 5 наборе данных.

8) Обученный классификатор тестируется на всем наборе примеров. Если ошибок нет, процесс обучения заканчивается. Иначе формируется новый обучающий набор из опорных векторов классификатора и ошибочных векторов. Классификатор обучается на полученном наборе.

Приведем приближенную временную оценку. Обозначим: N – число обучающих примеров, NSV – число опорных векторов, Р – количество вычислительных узлов в системе, k = NSV /N – отношение числа опорных векторов к общему числу примеров, S – коэффициент ускорения параллельной стратегии.

На первом этапе турнира участвуют Р процессоров, время обучения пропорционально (N/P)2. Во второй этап выходят P/2 победивших процессоров, каждый с двумя наборами опорных векторов – своим и проигравшего процессора (ошибки не учитываем), время обучения на втором этапе пропорционально (2k·N/P)2. Турнир продолжается, пока не останется один процессор. Таким образом, время обучения для стратегии будет следующим:

Ускорение в лучшем и в худшем случаях зависит от относительного количества опорных векторов k:

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

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

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

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

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

На следующем этапе вычислительные узлы осуществляют предварительную обработку и морфологический анализ «своих» документов, формируют и отправляют на главный узел локальные словари, в которых присутствуют термины только из «своих» документов. Главный узел объединяет локальные словари в глобальный и рассылает его подчиненным узлам.

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

Параллельный алгоритм обучения многоклассового классификатора для иерархической структуры вычислительной системы Алгоритм основан на алгоритме обучения бинарного классификатора (нижний уровень) и на стратегии многоклассовой классификации «каждый против всех»

(верхний уровень).

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

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

Параллельный алгоритм настройки параметров классификатора основан на методе скользящего контроля по R Q блокам (R Q-fold cross validation). Особенностью данного алгоритма является использование перебора для разных групп параметров: коллекции документов, глобального и локальных словарей, векторной модели, метода опорных векторов. Для каждой группы работает свой способ перебора и балансировки нагрузки между узлами вычислительной системы. Оптимальным считается набор параметров, при котором достигаются максимальные значения характеристик качества обучения.

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

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

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

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

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

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

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

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

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

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

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

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

В диссертации выводится выражение для оценки времени работы предложенного параллельного метода классификации:

где N – общее количество документов в коллекции, Ntrain – количество обучающих документов, M – число вычислительных узлов (без главного узла), Dglobal, – размер глобального словаря, Lav – средний размер документа.

Третья глава содержит описание программной реализаций разработанной системы автоматической текстовой классификации. Структура параллельной системы построена на основе предложенной обобщенной структуры системы текстовой классификации (см. рис. 2) и параллельного метода классификации текстов (см. рис. 4) и представлена на рис. 5.

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

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

Рис. 5. Структура параллельной системы автоматической текстовой классификации Подсистема формирования векторной модели основана на параллельном алгоритме формирования векторной модели текста.

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

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

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

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

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

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

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

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

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

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

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

Программное приложение для многопроцессорной системы с иерархической архитектурой создавалось в среде Microsoft Visual Studio 2010 на языках C# и C++ на основе принципов объектно-ориентированного программирования. Для кластерной архитектуры параллельная реализация алгоритмов обучения проводилась с использованием библиотеки MPI.NET версии 1.0.7 Библиотека MPI.NET представляет собой свободно доступную реализацию интерфейса передачи сообщений MPI для среды Microsoft.NET. Для запуска и выполнения потоков в среде с общей памятью применялась технология OpenMP.

Расчеты проводились на вычислительном кластере Вятского государственного гуманитарного университета, состоящем из 30 вычислительных узлов и одного головного. Каждый узел представляет собой персональный компьютер с процессором Intel Core 2 Duo 2 ГГц и 2 Гб оперативной памяти. Узлы связаны сетью Fast Ethernet.

Кластер функционирует под управлением операционной системы Microsoft Windows HPC Server 2008. Проведено тестирование кластера и проанализированы его характеристики, которые могут влиять на производительность параллельной системы тематической текстовой классификации.

Приведены результаты практической апробации разработанной системы автоматической текстовой рубрикации на коллекции финансовых новостей агентства Reuters (Reuters-21578, Distribution 1.0) и коллекции RCV1.

Project MPI.NET // The Open Systems Lab, Indiana University [Электронный ресурс]. Режим доступа: http://www.osl.iu.edu/research/mpi.net. Дата обращения: 01.10.2011. Загл. с экрана.

Коллекция Reuters-21578 8 создана новостным агентством и предоставлена в свободный доступ для проведения исследований в области автоматической обработки текстов. Коллекция состоит из 21 578 документов – финансовых новостей агентства Reuters, выпущенных в 1987 году. Все документы отрубрицированы экспертами по рубрикатору, состоящему из 135 рубрик. Коллекция была адаптирована для тестирования методов машинного обучения Д. Льюисом.

Обучающий набор документов был выделен в соответствии с общепринятым подходом, названным «ModApte split». При этом исключались документы, не помеченные ни одной рубрикой. Таким образом, обучающий набор в наших экспериментах представлен 7775 документами, каждый из которых относится к одной или нескольким из 115 рубрик.

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

Эксперименты, проведенные на коллекции Reuters-21578 (рис. 6 и 7) показали работоспособность и эффективность разработанной системы автоматической текстовой классификации при той же точности вычисления, которая была получена в последовательном приложении, использующем тот же метод обучения классификатора. Предложенная структура и алгоритм обучения параллельной системы автоматической текстовой классификации позволяют существенно сократить время обработки больших тестовых коллекций. Так для коллекций размером порядка 105 документов при использовании вычислительного кластера, состоящего из 20–30 обычных персональных компьютеров, время обработки сокращается с десятков часов до десятков минут.

Рис. 6. Зависимость ускорения от количества узлов для коллекции Reuters- RCV1 (Reuters Corpus Volume 1 Version 2)9 – это коллекция отсортированных вручную новостей агентства Reuters за период с августа 1996 по август 1997 года.

Коллекция содержит иерархические категории (один документ может относится к разным категориям, например к экономике и к нефти одновременно). Каждая категоресурс]. Режим доступа:

Reuters-21578, Distribution 1.0 [Электронный http://www.daviddlewis.com/resources/testcollections/reuters21578. Дата обращения: 01.10.2011.

Загл. с экрана.

Lewis D. D., Yang Y., Rose T., Li F. RCV1: A New Benchmark Collection for Text Categorization Research // Journal of Machine Learning Research, 5:361-397, (http://www.jmlr.org/papers/volume5/lewis04a/lewis04a.pdf).

рия имеет свой код, и эти коды приписываются новостям (всего около восьмидесяти категорий). Например, во главе иерархии стоят четыре категории: CCAT (Corporate/Industrial), ECAT (Economics), GCAT (Government/Social), и MCAT (Markets).

Коллекция состоит из 804 414 документов, которые делятся на 23 149 обучающих и 781 265 тестовых.

Рис. 7. Зависимость эффективности от количества узлов для коллекции Reuters- Коллекция RCV1 также отличается сильной неравномерностью распределения количества обучающих документов по рубрикам.

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

Рис. 8. Зависимость ускорения от количества узлов для коллекции RCV Рис. 9. Зависимость эффективности от количества узлов для коллекции RCV Снижение эффективности на коллекции RCV1 оказывается меньше, чем на коллекции Reuters-21578. Связано это с немного меньшей неравномерностью распределения документов по рубрикам в коллекции RCV1.

На основе системы протестированы три подхода к распределению нагрузки на узлы вычислительной системы и предложены рекомендации не только по работе с параллельным приложением, но и по выбору подхода к балансировке нагрузки. Применение предложенных алгоритма распределения документов и алгоритма распределения рубрик увеличивает ускорение в среднем на 80%, причем 9/10 этого увеличения приходится на алгоритм распределения рубрик, поскольку он используется гораздо чаще во время обучения, чем алгоритм распределения документов.

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

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

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

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

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

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

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

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

7. Экспериментально подтверждена эффективность разработанной параллельной системы для автоматической текстовой классификации на различных многопроцессорных иерархических системах с использованием общедоступных текстовых коллекций – Reuters-21578 и RCV1.

Статьи, опубликованные в журналах из списка ВАК 1. Пескишева, Т. А. Параллельная реализация алгоритма обучения системы текстовой классификации [Текст] / Т. А. Пескишева, Е. В. Котельников // Вестник УГАТУ. Серия управление, вычислительная техника и информатика. – 2011. – № (45). – С. 130–136.

2. Пескишева, Т. А. Параллельный алгоритм обучения текстового классификатора для многопроцессорной системы с иерархической архитектурой [Текст] / Т. А. Пескишева, Е. В. Котельников, О. А. Пестов // Вопросы современной науки и практики. Университет им. В. И. Вернадского. – 2011. – № 3 (34). – С. 103–110.

3. Пескишева, Т. А. Параллельная система автоматической текстовой классификации [Текст] / Е. В. Котельников, Т. А. Пескишева // Программные продукты и системы. – 2012. – № 1 (97) (в печати).

4. Стародубова (Пескишева), Т. А. Параллельный алгоритм обучения машин опорных векторов [Текст] / Р. А. Веснин, Т. А. Стародубова (Пескишева) // Высокопроизводительные параллельные вычисления на кластерных системах: материалы седьмой Междунар. конф.-семинара. – Н. Новгород: Изд-во Нижегородского госуниверситета, 2007. – С. 79–85.

5. Стародубова (Пескишева), Т. А. Распараллеливание алгоритма обучения опорных векторов с использованием метода декомпозиции по данным [Текст] / Р. А. Веснин, Т. А. Стародубова (Пескишева) // Сборник научных трудов по материалам международной научно-практической конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании 2007». Т. 5. – Одесса: Черноморье, 2007. – Т. 5. – С. 92–96.

6. Стародубова (Пескишева), Т. А. Параллельные алгоритмы многоклассовой классификации на основе метода опорных векторов [Текст] / Е. В. Котельников, Т. А. Стародубова (Пескишева) // Высокопроизводительные параллельные вычисления на кластерных системах: материалы Восьмой междунар. конф.-семинара. – Казань: КГТУ, 2008. – C.228–233.

7. Стародубова (Пескишева), Т. А. Распараллеливание методов обучения в задачах многоклассовой классификации [Текст] / Е. В. Котельников, Т. А. Стародубова (Пескишева) // Вестник ВятГГУ. Информатика. Математика. Язык. Вып. 5. – Киров:

ВятГГУ, 2008. – С. 63-66.

8. Стародубова (Пескишева), Т. А. Вариант параллельной реализации процесса обучения машин опорных векторов на основе алгоритма Chunking [Текст] / Е. В. Котельников, Т. А. Стародубова (Пескишева), А. В. Котельникова // Параллельные вычислительные технологии (ПАВТ’ 2009): труды междунар. науч. конф. (Нижний Новгород, 30 марта – 3 апреля 2009 г.). – Челябинск: Изд-во ЮУрГУ, 2009. – С. 549–555.

9. Пескишева, Т. А. Системы и модули текстовой рубрикации [Текст] / Т. А. Пескишева // Всероссийская конференция с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации», 1–5 декабря 2009 г. Россия, Ульяновск: сб. науч. тр.: в 4 т. – Т. 2. – Ульяновск: Изд-во УлГТУ, 2009. – С. 238–242.

10. Пескишева, Т. А. Современные системы и модули автоматической рубрикации текстовых документов [Текст] / Пескишева Т. А.: Вятский государственный гуманитарный университет. – Киров, 2010. – 37 с.: – Библиогр. 30 назв. – Рус. – Деп. в ВИНИТИ 01.07.2010, № 410 – В 2010.

11. Пескишева, Т. А. Планирование вычислительной нагрузки в многопроцессорной системе с иерархической архитектурой (на примере системы текстовой классификации) [Текст] / Е. В. Котельников, Т. А. Пескишева // Актуальные проблемы гуманитарных и экономических наук: сб. материалов XII межрегион. науч.-практ.

конф. – Киров: Изд-во Кировского филиала МГЭИ, 2011. – С. 250–252.

12. Пескишева, Т. А. Параллельная реализация алгоритма обучения системы текстовой классификации [Текст] / Т. А. Пескишева, Е. В. Котельников // Параллельные вычислительные технологии (ПАВТ’ 2011): тр. междунар. науч. конф. (Москва, 28 марта – 1 апреля 2011 г.). – Челябинск: Изд. ЮУрГУ, 2011. – С. 597–605.

13. Котельников, Е. В., Пескишева, Т. А. Свидетельство о государственной регистрации программы для ЭВМ «Система параллельной многоклассовой классификации на основе метода опорных векторов» № 2010613404.

Вятского государственного гуманитарного университета, 610002, г. Киров, ул. Красноармейская, 26, т. (8332)