Исследование и разработка методов и программных средств классификации текстовых документов тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Гулин, Владимир Владимирович

• Гулин, Владимир Владимирович
• кандидат технических наук
• 2013

Оглавление диссертации кандидат технических наук Гулин, Владимир Владимирович

Содержание

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Приложение

Введение диссертации (часть автореферата) на тему «Исследование и разработка методов и программных средств классификации текстовых документов»

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты данной работы внедрены в проект «[e-mail]», разрабатываемый ООО «Мэйл.Ру»и используются для решения следующих задач:

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

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

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

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

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

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

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

Содержание диссертации

В первой главе вводятся ключевые термины и определения, используемые в работе, формулируется задача классификации текстовых документов. С учетом специфики решаемой задачи описываются основные этапы обработки и анализа текстовой информации. На этапе начальной и содержательной обработки совокупность (коллекция) документов описывается в виде матрицы «документ-термин». При этом отдельный документ представляется вектором (точкой) в М - мерном пространстве терминов. В качестве координат этого вектора выбираются ¿/-гй/ [91] (от

англ. tf — term frequency, idf — inverse document frequency) веса терминов. Для упрощения подобных моделей осуществляют предварительную обработку документов, позволяющую уменьшить количество терминов и как следствие - размерность векторной модели. Рассматриваются достоинства и недостатки лингвистических методов предварительного снижения размерности - стемминга и лемматизации [78]. Предлагается оригинальный алгоритм лемматизации, основанный на алгоритме Ахо-Корасик [27]. В заключение дается формализованная постановка задачи классификации текстовых документов методами машинного обучения с учителем с использованием обоснованного при этом обобщенного показателя полноты и точности - Fi меры.

Во второй главе излагаются и оцениваются по значениям Fi меры методы машинного обучения с учителем, используемые в работе. В первом параграфе дается обзор известных методов машинного обучения. Описываются байесовские методы классификации. Рассматривается вероятностная постановка задачи классификации. Дастся понятие функционала среднего риска. Приводится оптимальное байесовское решающее правило. Описывается наивный байесовский классификатор (Naive Bayes) [51], представляющий собой концептуально простой и эффективный метод классификации текстов. Рассматриваются метрические алгоритмы классификации. Описываются метод ближайшего соседа и его обобщения и приводится алгоритм к взвешенных ближайших соседей (к nearest neighbor - kNN) [21]. Далее рассматриваются линейные алгоритмы классификации [80]. Рассматривается метод стохастического градиента [33], являющийся универсальным алгоритмом обучения линейных классификаторов. Приводится алгоритм логистической регрессии [31]. Анализируется метод опорных векторов (support vector machine) [100], который многие исследователи в настоящее время считают наиболее эффективным методов классификации текстов. Далее рассматриваются ло-

гическис алгоритмы классификации [5]. Приводятся понятие информативности и концепция решающих деревьев [82]. Описываются алгоритмы построения деревьев решений С4.5 [88] и CART (Classification and regression tree) [36].

В завершение обзора известных методов классификации текстовых документов рассматриваются известные методы построения алгоритмических композиций. Поясняется понятие алгоритмической композиции и представляется концепция бустинга (boosting) [93], процедуры последовательного построения композиции алгоритмов машинного обучения, когда каждый последующий алгоритм компенсирует недостатки композиции всех предыдущих алгоритмов. Рассматривается алгоритм AdaBoost (Adaptive Boosting) [46]. Описывается альтернативная концепция построения алгоритмических композиций - бэггинг (bagging) [35]. Название метода произошло от англ. bootstrap aggregating. Данный метод формирует ансамбль классификаторов с использованием случайной выборки с возвратом, примененной к обучающему набору. Также представлен метод случайных подпространств (random subspace method) [57]. Данный метод строит композицию классификаторов при помощи случайной выборки без возвращения, примененной к признаковым описаниям объектов обучающего множества, что является ключевым отличием данного метода от бэггинга.

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

Третий параграф посвящен результатам экспериментального сравнения всех представленных в главе методов применительно к задаче классификации текстовой коллекции Reuters-21578 [59]. Для настройки параметров классификаторов в работе использовался метод перекрестной

проверки (cross validation) [69].

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

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

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

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

ности это одна из основных проблем в задачах распознавания образов и машинного обучения. Представлено классическое разделение методов снижения размерности на методы отбора признаков (feature selection) и методы выделения признаков (feature extraction) [56]. В качестве первого метода снижения размерности рассматривается метод главных ком-поиент(разложсние Карунсна-Лоева, РСА - principal component analysis) [67]. Идея метода заключается в поиске в исходном пространстве гиперплоскости заданной размерности с последующим проектированием выборки на данную гиперплоскость. При этом выбирается та гиперплоскость, ошибка проектирования данных на которую является минимальной в смысле суммы квадратов отклонений. Далее в главе описывается метод отбора признаков по принципу максимальной релевантности и минимальной избыточности - mRMR (maximum relevance minimum redundancy) [86]. Как следует из названия, алгоритм призван выбирать подмножество признаков наиболее релевантных классам обучающей выборки, удаляя при этом избыточные признаки, дублирующие информацию о классах. Следующим рассматривается метод главных признаков (principal feature analysis) [41]. Характерной особенностью данного метода является то, что он не требует коллекции документов заранее классифицированной экспертами. Представлена предлагаемая в работе модификация алгоритма главных признаков [13].

В завершение проводится сравнение методов снижения размерности, описанных в главе, для задачи классификации текстов на тестовой коллекции Reuters-21578.

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

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

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

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

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

В главе дано описание архитектуры разработанных программных средств и сформулированы основные свойства разработанного программ-

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

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

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

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

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

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

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

- множество документов (Л^ - количество документов в множестве Б),

С = {сь ... ,Слгс}

- множество категорий (АТ^ - количество категорий),

Ф : В х С {0,1}

(1.1)

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

Методы машинного обучения, используемые для классификации, полагаются на наличие коллекции

9 = {(di, ci)\dieD,cieC,i = l1...,N} (1.2)

заранее классифицированных документов di, для которых известны категории Cij такие, что Ф(di,Cij) = 1, Су G С. Таких категорий для каждого элемента может быть несколько. Принято [20] разбивать коллекцию (1.2) на две части

• обучающую выборку (training-and-validation set) (6ir).

• тестовую выборку (test set) (6iesi).

Задача состоит в построении на основе обучающей выборки ©¿г классификатора - функции Ф', аппроксимирующей функцию Ф. Качество классификатора оценивается суммой «штрафов »на тестовой выборке

(1.3)

di€@tcst

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

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

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

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

2. Выполняется разбиение текста на лексемы [78].

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

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

5. Документ приводится к структурированной форме.

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

Цифровые документы, являющиеся входной информацией для процесса обработки текстовых данных, как правило, представляют собой набор байтов в файле или на веб-сервере. На нервом шаге обработки эта последовательность байтов преобразуется в линейную последовательность символов. Для английского текста, набранного в системе кодирования ASCII, такая задача тривиальна. Однако часто такая задача оказывается куда как сложнее. Последовательность символов может быть закодирована в одной из многих одно- или многобайтовых кодировок (например UNICODE UTF-8 ) или в стандарте, определяемом поставщиком оборудования (например IBM866). В первую очередь необходимо верно определить кодировку. Эту проблему можно интерпретировать как задачу классификации на основе машинного обучения [78], но на практике ее часто решают с помощью эвристических методов, выбора пользователя или имеющихся метаданных о документе. После того как кодировка определена, последовательность байтов преобразуется в последовательность символов. Полученную кодировку следует запомнить, поскольку эта информация дает представление о языке, на котором написан документ.

Возможно, символы нужно декодировать из двоичного представления, например из doc-файла текстового процессора Microsoft Word и/или архивных файлов наподобие zip-файлов. Таким образом, сначала необхо-

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

После идентификации последовательности символов текст разделяется на лексемы. Кроме того, иногда из него одновременно удаляются некоторые символы, например знаки пунктуации. Рассмотрим пример:

Ввод: Я пригласил вас, господа, с тем, чтобы сообщить вам пренеприятное известие

Вывод: Я пригласил вас господа с тем чтобы сообщить вам

пренеприятное известие

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

(type/token). JleKceMa(tokcn) - это экземпляр последовательности символов в определенном документе, объединенных в семантическую единицу для обработки. Tnn(typc) - это класс всех лексем, состоящих из одной и той же последовательности символов. Термин (term) - это (возможно, нормализованный) тип, включенный в словарь системы информационного поиска.

Основной вопрос, связанный с разделением текста на лексемы, звучит так: "Как правильно разделить текст на лекссмы?". В нашем примере ответ очевиден: достаточно разделить текст по пробелам и отбросить знаки пунктуации. Это отправная точка, но даже в английском языке здесь содержится много подвохов. Например, что делать с разными формами апострофа, используемого для образования притяжательной формы и сокращений.

Подобные проблемы существенно зависят от языка. Следовательно, язык доку1\1ента должен быть известен заранее. Таким образом, возникает задача определения языка (language identification), которую также принято [79] интерпретировать как задачу классификации на основе машинного обучения [78]. Конкретно для задачи определения языка, применение классификаторов, использующих в качестве признаков короткие последовательности символов, является очень эффективным [79].

В большинстве языков и конкретных предметных областей существуют необычные специфические лексемы, которые следует распознавать, как термины: языки программирования С++ и Сназвания самолетов, например СУ-37. Компьютерные технологии породили новые типы последовательностей символов, которые следует распознавать, как одну лексему, в частности адреса электронной почты ([e-mail]), веб-адреса (URL) (http://go.mail.ru), числовые IP-адреса (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 ставится в соответствие термин ап-tidiscriminatory, то в ходе поиска одного термина обязательно будет находиться и другой.

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

валентности возникают неявно, а не подготавливаются заранее: термины, которые в результате применения этих правил становятся идентичными, относятся к одному и тому же классу эквивалентности. Несмотря на то, что правила удаления символов из лексем писать относительно легко, обратная задача является довольно сложной. Поскольку классы эквивалентности возникают неявно, совершенно неясно, куда следовало бы вставить недостающие символы. Например, трудно понять, как превратить слово antidiscriminatory в anti-discriminatory.

Как правило, в поисковых системах игнорируется регистр букв (case-folding), например все буквы переводятся в нижний регистр. Часто это оказывается удачным решением, позволяющим все слова Automobile, с которых начинаются соответствующие предложения, считать эквивалентными слову automobile. С другой стороны свертывание регистра может привести к совпадению слов, которые следовало бы считать разными. Многие имена собственные являются производными от имен нарицательных и отличаются от них лишь прописной первой буквой. Например, это относится к названиям компаний (General Motors, The Associated Press) и правительственных организаций (the Fed и fed), а также к фамилиям (Bush, Black) [78].

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

1.2.2. Стемминг и лемматизация

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

из них находить документы, содержащие другие слова из этого семейства.

Цель стеммипга и лемматизации - привести словоформы и производные формы слова к общей основной форме. Рассмотрим примеры, am, arc, is —»• be идти, ходить —> ходить В результате может возникнуть следующее преобразование текста.

the boy's cars arc different colours —the boy car be different colour Однако стемминг отличается от лемматизации. Стеммипгом (stemming) обычно называется приближенный эвристический процесс, в ходе которого от слов отбрасываются окончания в расчете на то, что в большинстве случаев это себя оправдывает. Стемминг часто подразумевает удаление производных аффиксов. Лемматизация (lemmatization) - это точный процесс с использованием словаря и морфологического анализа слов, в результате которого удаляются только флективные окончания и возвращается основная, или словарная форма слова, называемая леммой. Например, лексема saw в ходе стемминга может превратиться в букву s, в то время как лемматизация вернет либо слово see, либо слово saw в зависимости от того, является ли лексема глаголом или именем существительным. Важное различие состоит в том, что обычно стемминг считает эквивалентными производные однокоренные слова, а лемматизация склеивает только флективные формы одной леммы. Стемминг и лемматизация часто выполняются с помощью дополнительных программных компонентов, встраиваемых в процесс текстовой обработки.

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

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

Вместо алгоритма стемминга можно использовать лемматизатор (lem-matizer), инструмент из области обработки естественного языка (natural language processing) [68], выполняющий полный морфологический анализ для точного определения леммы каждого слова. Обычно алгоритм лем-матизации представляет собой поиск словоформы по словарю, в котором имеется информация о данной словоформе (морфологические данные) и о том, какое слово является нормальной формой данной словоформы.

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

• Стемминг повышает полноту, но сильно снижает точность поиска. Для того чтобы продемонстрировать недостатки алгоритмов стемминга [87, 76, 83], отмстим, что алгоритм Портера обрезает все слова

operate operating operates operation operative operatives operational до слова oper. Поскольку слово operate во всех своих формах является распространенным глаголом, точность поиска документов, содержащих вышеперечисленные слова, сильно снизится при использовании алгоритма Портера.

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

Таким образом, разрабатывая системы лингвистической нормализации слов, разработчики поисковых систем пытаются достичь следующих целей [10]:

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

• Улучшение точности поиска. Применение статистических алгоритмов поиска предполагает использование частотных характеристик документов. При этом использование вместо частот слов частоты лемм позволяет получить лучший ранк (числовая характеристика, отражающая степень релевантности документа запросу) для релевантных документов и тем самым поместить их выше в результатах поиска;

• Уменьшение размера поискового индекса [78] и ускорение обработки запроса. Так как количество лемм меньше количества слов, то лем-матизация приводит к уменьшению размера индекса и увеличению скорости обработки запроса.

Влияние методов стемминга и лемматизации на качество классификации текстов рассматривается в главе 4.

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

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

По мнению автора, лемматизатор должен состоять из двух компонентов:

• словаря лемм и их словоформ;

• структуры данных хранения словаря и алгоритма поиска но словарю;

Сразу заметим, что создание словарей для лемматизации является задачей прикладной лингвистики, поэтому в данной работе не будет рассматриваться данный вопрос. Далее будем предполагать, что существует размеченный словарь слов 1У = {гУ1,..., ги^}, в котором указано, какие слова являются леммами, а какие их словоформами. Иначе говоря, пусть множество слов разбито на подмножества лексем, соответствующих определенным леммам. При этом омонимы принадлежат одному и тому же подмножеству (например, рысь, рысыо, рыси, рысцой с леммой рысь в одном подмножестве). Тогда эти подмножества суть классы эквивалентности по указанному разбиению (по определению, они не пересекаются). Два слова из словаря эквивалентны, если принадлежат одному и тому же подмножеству, т.е. соответствуют одной и той же лемме.

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

Ясно, что можно было использовать простой переборный поиск по такому словарю. Очевидно, такой алгоритм не является эффективным как с точки зрения быстродействия так и с точки зрения затрат памяти. В данной работе предлагается использовать для хранения словаря префиксное дерево, а для поиска воспользоваться алгоритмом Ахо-Корасик [53]. Используя такой подход, мы сможем узнавать, находится ли слово ии в словаре ]¥, за время 0(|к;|) (|и;| - длина слова). Однако остается нерешенным вопрос, каким образом можно получить все словоформы для данного слова го. Идея заключается в добавлении дополнительных ссылок в конечный автомат Ахо-Корасик.

Пусть по словарю \¥ построено префиксное дерево, к листьям которо-

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

Алгоритмом Ахо-Корасик строится конечный автомат Мура, входным алфавитом которого является алгоритм словаря, пополненный символом $, состояния соответствуют вершинам префиксного дерева, функция переходов определяется отношением следования на множестве его вершин, а бинарная функция выхода принимает значение 1 на состояниях, соответствующих листьям дерева, и состояние 0 на остальных вершинах. Каждое состояние сопровождается также служебной ссылкой на предыдущее состояние. По служебным ссылкам можно восстановить слово, соответствующее состоянию с выходом 1. На рис. 1.1 дано представление состояния конечного автомата, соответствующего внутренней вершине префиксного дерева. В представлениях состояний автомата, соответствующих листьям префиксного дерева, ссылки на следующие состояния отсутствуют.

По несколько модифицированному автомату Ахо-Корасик можно построить кольцевые списки слов каждого класса эквивалентности.

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

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

Ссылка на предыдущее состояние

Состояние:

V Ь * с с

Ссылки на > > г \ > г

следующие состояния

Рис. 1.1. Классическое представление состояния конечного автомата в

алгоритме Ахо-Корасик.

Рис. 1.2. Предлагаемое представление состояния конечного автомата, соответствующего листу префиксного дерева, в алгоритме Ахо-Корасик.

А т и —•—«—

о д и —I—I—

Рис. 1.3. Представление классов эквивалентности слов в виде кольцевого

Имея кольцевые списки для каждого класса эквивалентности слов, можно по одной словоформе восстановить весь класс. Чтобы восстановить очередное слово, достаточно, находясь в финальном состоянии конечного автомата (помеченном символом $), двигаться в направлении корня дерева по служебным ссылкам. Пример представления класса эквивалентности кольцевым списком приведен на рис. 1.3, а детальный его разбор представлен в приложении 1.

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

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

Наиболее часто в качестве модели представления документов в системах обработки текстовой информации используется так называемый «мешок слов»(неструктурированная модель «bag of words») [54], которая рассматривает каждый термин в качестве независимой случайной величины вне контекста и связи с другими словами текста.

списка (лемма выделена звездой).

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

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

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

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

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Гулин, Владимир Владимирович

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

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

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

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

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

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

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

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

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

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

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

Заключение

Список литературы диссертационного исследования кандидат технических наук Гулин, Владимир Владимирович, 2013 год

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

[1] Айвазян С.А., Бухштабер В.М., Енюков И. С., Мешалкин Л.Д. Прикладная статистика: Классификация и снижение размерности - М.: Финансы и статистика, 1989

[2] Амосов A.A., Дубинский Ю.А., Копченова Н.В. Вычислительные методы для инженеров. М.: Изд-во МЭИ, 2003

[3] Антонов A.C. Параллельное программирование с использованием технологии MPI. -M.: Изд-во МГУ, 2004.-71 с.

[4] Бредихин Р.Н. Об одном подходе к распознаванию оптических образов текстов // Вестник МЭИ, 2005, № 2, с. 134-141

[5] Вагин В.П., Головина Е.Ю., Загорянская A.A., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах - М.: ФИЗМАТЛИТ, 2004.

[6] Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.

[7] Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. -М.: Наука, 1974

[8] Воеводин В.В., Воеводин Вл.В Параллельные вычисления - СПб.: БХВ-Петербург, 2002

[9] Воронцов К.В. Машинное обучение. Курс лекций (machinelearning.ru)

[10] Губин М.В., Морозов А.Б. Влияние морфологического анализа на качество информационного поиска // Труды RCDL-2006, стр. 224228, 2006

[11] Гулин В. В. Сравнительный анализ методов классификации текстовых документов // Вестник Московского энергетического института, № б, -С.100-108, 2011

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

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

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

[15] Гулин В.В. Объект интеллектуальной собственности свидетельство об офицальной регистрации программы для ЭВМ №2013612095. Библиотека алгоритмов машинного обучения «МЫлЬгагу»- Москва, 2013, 1с.

[16] Деммель Дэю. Вычислительная линейная алгебра. Теория и приложения -М.: Изд-во Мир, 2001

[17] Журавлев Ю.И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз. — 1988. - Т. 1. - С. 9-16.

[18] Журавле в Ю. И., Рязанов В. В., Сепъко О. В. «Распознавание». Математические методы. Программная система. Практические применения. — М.: Фазис, 2006.

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

[20] Лифшиц Ю. Курс «Алгоритмы для Интернета», http://yury.name/internet/

[21] Мерков A.B. Распознавание образов: Введение в методы статистического обучения - М.: Едиториал УРСС, 2011.

[22] Тихонов А.Н., Арсении В.Я. Методы решения некорректных задач. - М.: Наука, 1986.

[23] Толчеев В. О. Систематизация, разработка методов и коллективов решающих правил классификации библиографических текстовых документов : диссертация на соискание ученой степени доктора технических наук: 05.13.01 [Место защиты: ГОУВПО «Московский энергетический институт (технический университет)»].- Москва, 2009.355 е.: ил. РГБ ОД, 71 10-5/332

[24] Фролов A.B. Принцип конечной топологии распознавания топологических форм // Известия РАН. Теория и системы управления, 2010, №1, 68-76

[25] Фролов A.B. Классификация и распознавание топологических форм : учебное пособие по курсам «Современные проблемы прикладной математики и информатики»и «Современные компьютерные технологии в науке и образовании»для студентов, обучающихся по специальностям «Прикладная математика»и «Информационные системы и технологии»/ А. Б. Фролов; под ред. В. Б. Кудрявцева; М-во образования и науки Российской Федерации, Федеральное агентство по образованию, Московский энергетический ин-т (технический ун-т) 3 10-7/917, 2010

[26] Чегис А.И., Яблонский С.В. Логические способы контроля работы электрических схем // Тр. математического ин-та им. Стеклова, 1958. Т. 51. с. 270-360.

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

[28] Baeza- Yates R., Navarro G. Integrating Contents and Structure in Text Retrieval // ACM SIGMOD Record, Vol. 25, 1996, No. 1, pp. 67-79.

[29] Bartlett P., Shawe-Taylor J. Generalization performance of support vector machines and other pattern classifiers // Advances in Kernel Methods. - MIT Press, Cambridge, USA, 1999. - Pp. 43-54

[30] Baum L., Petrie T. Statistical Inference for Probabilistic Functions of Finite State Markov Chains // The Annals of Mathematical Statistics 37 (6): 1554-1563, 1966

[31] Bishop C. Pattern Recognition and Machine Learning // Springer, 2006

[32] Bonnans J., Gilbert J., and etc. Numerical optimization: Theoretical and practical aspects // Universitext (Second revised ed. of translation of 1997 French éd.). Berlin: Springer-Verlag. pp. xiv+490, 2006.

[33] Bottou L. Stochastic Learning // Advanced Lectures on Machine Learning, 146-168, Edited by Olivier Bousquet and Ulrike von Luxburg, Lecture Notes in Artificial Intelligence, LNAI 3176, Springer Verlag, Berlin, 2004

[34] Bramer M. Pre-pruning Classification Trees to Reduce Ovcrfitting in Noisy Domains // Intelligent Data Engineering and Automated Learning — IDEAL Lecture Notes in Computer Science Volume 2412, pp 7-12, 2002

[35] Breiman L. Bagging predictors // Machine Learning 24, 123-140, 1996

[36] Breiman L., Friedman J. Classification and regression trees // Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984.

[37] Buttcher C., Clarke G., Cormack G. Information Retrieval: Implementing and Evaluating Search Engines // MIT Press, 2010

[38] Cambazoglu B., Zaragoza H., Chapelle 0. Early exit optimizations for additive machine learned ranking systems // Proceeding WSDM '10 Proceedings of the third ACM international conference on Web search and data mining pp. 411-420, 2010

[39] Cavnar W., Trenkle J. N-Gram-Based text categorization // In Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval, 1994

[40] Chandra R., Menon R., Dagum L., Kohr D., May dan D., McDonald J. Parallel Programming in OpenMP // Morgan Kaufmann, 2000.

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

[42] Cormen TLeiserson C., Rivest R., Stein C. Introduction to Algorithms (3rd cd.) // MIT Press and McGraw-Hill, 2009

[43] Cortes C., Vapnik V. Support-vector // Machine Learning, 1995, Vol. 20, no. 3. - Pp. 273-297.

[44] Croft B., Metzler D. Strohman T. Search Engines: Information retrieval in practice // Addison Wesley, 2010

[45] Dean J., Ghemawat S. Map Reduce: Simplified Processing on Large Clusters // OSDI'04: Sixth Symposium on Operating System Design and Implementation, San Francisco, CA, December, 2004

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

[47] Friedman J. H. Stochastic gradient boosting // Computational Statistics and Data Analysis, 38:367-378, 1999

[48] Friedman J. H. Greedy function approximation: A gradient boosting machine // Annals of Statistics, 29: 1189-1232, 2001

[49] Frolov A., Jako E., Mezey P. Logical models of molecular shapes and their families // Mathematical Chemistry, 2001. No.30(4). Nov. pp.389-409.

[50] Frolov A., Jako E.; Mezey P. Metric properties of factor space of molecular shapes // Mathematical Chemistry, 2001. No.30(4). Nov. pp. 411-428.

[51] George H., Langley J. Estimating Continuous Distributions in Baycsian Classifiers // Proceedings of the Eleventh Conference on Uncertainty in Artificial Intelligence, pp. 338-345, Morgan Kaufmann, San Mateo, 1995

[52] Gerber R., Bik A., Smith K., Tian X. The sofware optimization cookbook (second edition) // Intel Press, 2010

[53] Gusfield D. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology // Cambridge University Press, 1997

[54] Harris, Zellig Distributional Structure // Word 10 (2/3): 146-62, 1954

[55] Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference, and Prediction // Springer Series in Statistics, 2009

[56] Haykin S. Neural networks and learning machines (3rd edition) // Prentice Hall. 2009

[57] Ho, Tin The Random Subspace Method for Constructing Decision Forest // Transactions on Pattern Analysis and Machine Intelligence, 1998

[58] Hofmann T., Cai L. Text Categorization by Boosting Automatically Extracted Concepts // Proceeding SIGIR '03 Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pp. 182-189, 2003

[59] http://www.daviddlcwis.com/resources/testcollcctions/reuters21578/

[60] http://www.comp.lancs.ac.uk/computing/research/stemming/

[61] http://www.cs.waikato.ac.nz/ eibe/stemmers/

[62] http://www.esie.ntu.edu.tw/ cjlin/libsvm/

[63] http://www.rulequest.com/see5-info.html

[64] http://www.tartarus.org/ martin/PorterStemmer/

[65] Intel 64 and IA-32 Architectures Software Developer's Manual. Volume 1: Basic Architecture, 2011

[66] Joachims T. Text Categorization with Suport Vector Machines: Learning with Many Relevant Features // Proceeding ECML '98 Proceedings of the 10th European Conference on Machine Learning, pp. 137-142, 1998

[67] Jolliffe I. Principal Component Analysis // Springer Series in Statistics, 2010

[68] Jurafsky D., Martin J. Speach and language processing (second edition) // Prentice Hall, 2008

[69] Kohavi R. A study of cross-validation and bootstrap for accuracy estimation and model selection // Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence 2 (12): 1137-1143.(Morgan Kaufmann, San Mateo, CA), 1995

[70] Kohavi R., Li C. Oblivious decision trees graphs and top down pruning. //In Proceedings of the 14th international joint conference on Artificial intelligence - Volume 2, pages 1071-1077, San Francisco, CA, USA, 1995. Morgan Kaufmann Publishers Inc.

[71] Kohonen T. Self-organizing maps (Third extended edition) // Springer, 2001

[72] Krishnakumar A. TEXT CATEGORIZATION Building a kNN classifier for the Rcuters-21578 collection, 2006

[73] Kweku-Muata, Osei-Bryson Post-pruning in decision tree induction using multiple performance measures // Computers and Operations Research, 34, pp. 3331-3345, 2007

[74] Lafferty J., McCallum A., Pereira F. Conditional random fields: Probabilistic models for segmenting and labeling sequence data // Proc. 18th International Conf. on Machine Learning. Morgan Kaufmann. pp. 282-289, 2001

[75] LeCun Y., Bottou L., Orr G. B., Muller K. Efficient BackProp // Neural Networks: tricks of the trade. Springer, 1998

[76] Lovins J. Development of a stemming algorithm. Translation and Computational Linguistics 11(1):22-31. 33, 527, 1968

[77] Mackay D. Information theory, inference, and learning algorithms. Cambridge, 2007.

[78] Manning C., Raghavan P., Schutze H. Introduction to information retrieval // Cambridge University Press, 2008

[79] Manning D., Schutze H. Foundations of statistical natural language processing // MIT Press, 1999

[80] Marsland S. Machine Learning: An Algorithmic Perspective // Chapman & Hall/CRC Machine Learning & Pattern Recognition, 2009

[81] Mezey P.G. Shape in Chemistry: An Introduction to Molecular Shape Topology // N.Y.: John k Sons, 1993

[82] Mitchell T. Machine learning // McGraw-Hill, 1997

[83] Paice C. Another stemmer. SIGIR Forum 24(3):56-61. 33, 528, 1990

[84] Parlett B. The Symmetric Eigenvalue Problem // Prentice Hall, Englewood Cliffs, NJ, 1980

[85] Pearson, K. On Lines and Planes of Closest Fit to Systems of Points in Space // Philosophical Magazine 2 (11): 559-572, 1901

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

[87] Porter M. An algorithm for suffix stripping. Program 14(3): 130-137. 33, 529, 1980

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

[89] Quinlan J. R. Induction of Decision Trees, Machine Learning 1 // Kluwcr Academic Publishers, pp. 81-106, 1986

[90] Richardson M., Prakash A., Brill E. Beyond PageRank: machine learning for static ranking // Proceeding WWW '06 Proceedings of the 15th international conference on World Wide Web, pp. 707-715, 2006

[91] Salton G., McGill M. Introduction to modern information retrieval // McGraw-Hill, 1983

[92] Salton G., Wong A., Yang C. A Vector Space Model for Automatic Indexing // Communications of the ACM, vol. 18, nr. 11, pages 613-620, 1975

[93] Schapire R. The Strength of Weak Learnability. Machine Learning (Boston, MA: Kluwer Academic Publishers), pp. 197-227, 1990

[94] Scott S., Matwin S. Feature engineering for text classification // Proceedings of ICML-99, 16th International Conference on Machine Learning, 1999

[95] Sebastiani F. Machine Learning in Automated Text Categorization, // ACM Computing Surveys, Vol. 34, No. 1, March 2002, pp. 1-47

[96] Shawe-Taylor J., Cristianini N. Robust bounds on generalization from the margin distribution: Tech. Rep. NC2-TR-1998-029: Royal Holloway, University of London, 1998.

[97] Shen D. Learning-based Web query understanding // Thesis (Ph.D.)-Hong Kong University of Science and Technology, 2007

[98] Steinhaus H. Sur la division des corps materiels en parties. Bull. Acad. Polon. Sei., CI. Ill vol IV: 801-804, 1956

[99] van Rijsbergen C. J. Information Retrieval (2nd ed.). Butterworth, 1979

[100] Vapnik V. The Nature of Statistical Learning Theory // SpringerVerlag, 1995.

[101] Vapnik V., Chapelle O. Bounds on error expectation for support vector machines // Neural Computation. - 2000. - Vol. 12, no. 9. - Pp. 20132036.