Введение к работе
Актуальность темы
С каждым днем увеличивается объем текстовых данных, хранящихся в электронном виде. Развитие глобальных компьютерных сетей и появление полнотекстовых баз данных (электронных библиотек, баз авторефератов, научных статей) привело к экспоненциальному росту объема текстовой информации. Для организации эффективной работы с этой информацией используются различные системы обработки текстов, предназначенные для решения широкого круга задач, таких как поиск, аннотирование, машинный перевод, извлечение фактов и др.
Важным этапом обработки текстовой информации является тематическая классификация (рубрикация), целью которой является отнесение текстовых документов к одной или нескольким заранее заданным категориям (рубрикам) по определенным признакам. Текстовая классификация применяется в таких областях, как фильтрация спама, сортировка новостей, проверка авторства, составление Интернет-каталогов, автоматическое аннотирование, информационный поиск и др.
В настоящее время существует два базовых подхода к тематической классификации текстов: подход на основе машинного обучения и подход на основе обработки знаний. При использовании подхода на основе машинного обучения классифицирующее правило определяется в результате автоматического анализа выборки заранее отрубрицированных документов. Для составления правила классификации в методах, основанных на знаниях, требуется предварительный анализ рубрик и документов и определение признаков рубрик экспертами вручную. В связи с высокой трудоемкостью использования методов, основанных на знаниях, все большее распространение получают методы машинного обучения.
Решение задачи тематической классификации позволит автоматизировать процесс обработки текстовой информации, сделать его менее трудоемким и более эффективным с точки зрения времени выполнения и точности полученных результатов.
Разработке и тестированию алгоритмов тематической текстовой классификации, а также связанным с ними моделям представления текстов посвящены труды таких авторов как М. С. Агеев, Г.Г. Белоногов, Б. В. Добров, И. Е. Кураленок, Д. В. Лан-дэ, Ю. М. Лифшиц, И. С. Некрестьянов, О. В. Пескова, В. И. Шабанов, I. Dagan, S. Т. Dumais, М. Halkidi, Т. Joachims, Т. Kohonen, D. D. Lewis, X. Liu, J. Piatt, 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, RCVl (английский язык), коллекции семинара РОМИП (русский язык) - процесс обучения с подбором параметров на одном компьютере может занимать при разных условиях от нескольких часов до нескольких десятков дней.
Таким образом, актуальность разработки высокопроизводительной системы автоматической тематической текстовой классификации следует из несоответствия между потребностями задач обработки текстовой информации и производительностью существующих методов текстовой классификации.
Одним из путей решения данной проблемы является использование многопроцессорных вычислительных систем и комплексов. Современные многопроцессорные системы в большинстве случаев имеют иерархическую архитектуру, что позволяет выполнять распараллеливание алгоритмов на нескольких уровнях.
Использование эффективных методов рубрикации в реализации системы текстовой классификации может быть еще одним путем повышения производительности программ автоматической текстовой классификации. По данным зарубежных и российских исследователей (Т. Joachims, S. Dumais, J. Piatt, F. Sebastiani, Y. Yang, X. Liu, D. Lewis, M. С. Агеев, Б. В. Добров и др.) наилучшие результаты при текстовой классификации показывает метод распознавания образов под названием «машины опорных векторов» (Support Vector Machines, SVM).
Объектом исследования являются программные системы автоматической тематической классификации электронных текстовых документов.
Предметом исследования являются методы и средства повышения производительности систем автоматической текстовой классификации.
Целью диссертационной работы является разработка параллельных методов и алгоритмов тематической классификации текстов и построение на их основе параллельной системы автоматической текстовой классификации.
Для достижения этой цели в диссертации решены следующие задачи:
Обзор и анализ существующих модулей и систем текстовой классификации.
Разработка и исследование параллельных методов и алгоритмов текстовой классификации на основе метода опорных векторов.
Разработка структуры и режимов работы параллельной системы тематической классификации текстовой информации.
Разработка программной реализации параллельной системы тематической текстовой классификации.
Экспериментальное исследование характеристик разработанной параллельной системы.
Методы исследования
Для решения задач, поставленных в работе, были использованы основные положения системного анализа, теории информации, теории вероятностей; для проектирования программной системы - методы объектно-ориентированного проектирования и язык UML; для программной реализации алгоритмов и системы - методы структурного, объектно-ориентированного и параллельного программирования.
Научная новизна
В ходе анализа существующих модулей и систем текстовой рубрикации была разработана обобщенная модель системы автоматической текстовой классификации. Отличительной особенностью данной модели является возможность ее применения для разработки системы автоматической классификации, независимо от подходов и методов, используемых на различных этапах работы системы.
Предложен параллельный алгоритм формирования векторной модели текста для иерархической структуры вычислительной системы, основанный на подходе TF-IDF (Term Frequency - Inverse Document Frequency), отличающийся учетом количества ключевых слов документов на этапе балансировки нагрузки между узлами вычислительной системы.
Предложен параллельный алгоритм обучения бинарного классификатора на основе алгоритма образования фрагментов Chunking для метода опорных векторов, отличающийся стратегией распараллеливания.
Предложен параллельный алгоритм обучения многоклассового классификатора для иерархической структуры вычислительной системы, основанный на методе опорных векторов и предложенном параллельном алгоритме обучения бинарного классификатора, отличающийся учетом количества опорных векторов для каждой рубрики на этапе балансировки нагрузки между узлами вычислительной системы.
Предложен параллельный алгоритм настройки параметров классификатора, основанный на методе скользящего контроля по R х Q блокам, отличающийся способами перебора для разных групп параметров.
Предложен параллельный метод текстовой классификации для иерархической структуры вычислительной системы, основанный на разработанных параллельных алгоритмах формирования векторной модели текста, обучения классификатора и настройки параметров классификатора.
Практическая значимость
Разработана структура и предложены режимы работы параллельной системы автоматической текстовой классификации на основе параллельного метода текстовой классификации.
Разработана программная реализация параллельной системы автоматической текстовой классификации для вычислительного кластера с иерархической архитектурой.
Исследована эффективность разработанной параллельной системы автоматической текстовой классификации на различных многопроцессорных иерархических системах.
Разработаны рекомендации по практическому применению системы автоматической текстовой классификации для решения задач обработки текстовых документов.
Эффективность параллельных алгоритмов и параллельной системы автоматической классификации доказана экспериментально на общедоступных текстовых коллекциях - Reuters-21578 и RCV1.
На защиту выносятся:
Параллельный алгоритм формирования векторной модели текста на основе подхода TF-IDF.
Параллельный алгоритм обучения классификатора на основе метода опорных векторов.
Параллельный метод текстовой классификации, основанный на параллельных алгоритмах формирования векторной модели текста, обучения классификатора и алгоритме настройки параметров классификатора.
Структура и режимы работы параллельной системы автоматической текстовой классификации на основе параллельного метода текстовой классификации.
Программная реализация разработанной параллельной системы автоматической текстовой классификации.
Экспериментальная оценка эффективности разработанной параллельной системы на многопроцессорных иерархических системах с использованием общедоступных текстовых коллекций.
Внедрение результатов
Теоретические и практические результаты, полученные при выполнении диссертационной работы, использованы в НИР по тематическому плану ВятГГУ на 2011 год «Программная система интеллектуального анализа текстов для социально-гуманитарных исследований», в НИР «Автоматическая классификация текстов» (ВятГГУ, договор №Н-04-10), в НИР «Разработка математических методов и алгоритмов тематической классификации текстовых документов» (ВятГГУ, НИР № 8/2008). Программная реализация параллельной системы текстовой классификации внедрена в учебный процесс в Вятском государственном университете и в Вятском государственном гуманитарном университете, а также в работу социологической лаборатории Вятского государственного гуманитарного университета.
Апробация работы
Основные результаты исследования докладывались и обсуждались на следующих конференциях:
Седьмая Международная конференция-семинар «Высокопроизводительные параллельные вычисления на кластерных системах» (г. Нижний Новгород, 2007);
Международная научно-практическая конференция «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании 2007» (г. Одесса, 2007);
Восьмая Международная конференция-семинар «Высокопроизводительные параллельные вычисления на кластерных системах» (г. Казань, 2008);
Международная научная конференция «Параллельные вычислительные технологии (ПАВТ' 2009)» (г. Нижний Новгород, 2009);
X Межрегиональная научно-практическая конференция «Актуальные проблемы гуманитарных и экономических наук» (г. Киров, 2009);
Всероссийская конференция с элементами научной школы для молодежи «Проведение научных исследований в области обработки, хранения, передачи и защиты информации» (г. Ульяновск, 2009);
XII Межрегиональная научно-практическая конференция «Актуальные проблемы гуманитарных и экономических наук» (г. Киров, 2011);
Международная научная конференция «Параллельные вычислительные технологии (ПАВТ' 2011)» (г. Москва, 2011).
Публикации. По результатам исследования опубликовано 12 печатных работ, из них статей и тезисов докладов - 11 (3 опубликованы в изданиях из числа рекомендованных ВАК для опубликования результатов диссертационных исследований), депонированная рукопись- 1. Получено свидетельство об официальной регистрации программы для ЭВМ. Список работ приведен в конце автореферата.
Структура и объем исследования. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка (включающего 147 наименований), списка сокращений и 3 приложений. Основная часть работы изложена на 164 страницах и содержит 27 рисунков и 6 таблиц.
