Модели и методы автоматической классификации текстовых документов

• Автор: Шабанов, Владислав Игоревич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 227 с. : ил.

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

Введение

1. Посгановка задачи

1.1. Формулировки задач классификации и распознавания образов

1.2. Методы оценки эффективности системы классификации текстов.

1. 2.1. Определение меры эффективности классификации.

1.2.2. Возможные виды меры эффективности классификации

1.2.3. Тестовые наборы

1.3. Анализ требований, предъявляемых к обучающим выборкам.

1.4. Жизненный цикл системы автоматической классификации.

2. Обзор методов распознавания образов и классификации

2.1. Основные группы методов распознавания и классификации.
2.1.1. Предъявление обучающего множества
2.1.2. Варианты описаний объектов.
2.1.3. Правила классификации
2.2. Математические модели для одноуровневых рубрикаторов.
2.2.1. Классификаторы, основанные на правиле Байеса3
2.2.2. Сжатие словаря терминов байесовского классификатора
2.2.3. Метод максгшизации энтропии.
2.2.4. Классификация методом поиска Кближайших соседей кИИ
2.2.5. Метод центроид
2.2.6. Нейронные сети.
2.2.7. Ассоциативные сети.
2.3. Математические модели для иерархических рубрикаторов.
2.3.1. Метод вложенных классификаторов.
2.3.2. Метод стягивания параметров классификатора
2.4. Учет гиперссылок
2.5. Сравнение методов классификации.
Содержание продолжение стр.
3. Математическая модель автоматического классификатора текстовых документов
3.1. Математическая модель представления текстового документа
ЗАЛ. Выбор вида терминов.
3.1.2. Выбор методы сопоставления терминов.
3.1.3. Критерии выбора вида терминов и функции нормализации
3.1.4. Алгоритм приближенного выделения словосочетаний.
3.2. Математические модели для оценки значимости терминов
3.2.1. Собственная морфологическая значимость терминов
3.2.2. Контекстная значимость терминов.
3.2.3. Статистическая значимость терминов
3.2.4. Вычисление значимости выделенных из текста дат, денежных
сумм и т. д.
3.3. Математическая модель документов и рубрик, метод классификации
3.3.1. Модель семантического образа рубрики.
3.3.2. Модель классифицируемого документа
3.3.3. Метод классификации, основанный на полнотекстовом поиске
3.4. Математическая модель документов обучающей выборки, метод
обучения
3.4.1. Формирование семантических образов рубрик одного уровня
иерархии
3.4.2. Вычисление пороговых весов терминов и рубрик
3.5. Детальное описание алгоритма обучения классификатора
3.5.1. Структура базы данных системы автоматической
классификации.
3.5.2. Алгоритм обучения классификатора.
3.5.3. Вы числение весов терминов.
Содержание продолжение стр.
3.5.4. Формирование оптимального покрытия.
3.5.5. Формирование семантических образов рубрик
3.6. Структура программного комплекса.
4. Автоматическое выявление ассоциативных связей между словами и словосочетаниями
4.1. Метод построения ассоциативных связей
4.1.1. Виды ассоциаций
4.1.2. Автоматический показ ассоциативных запросов
4.1.3. Алгоритм формирования ассоциативных связей.
4.2. Расширение семантических образов рубрик ассоциативными
терминами.
4.3. Дальнейшее развитие метода.
5. Автоматическое распознавание текстовых метаконструкций
5.1. Структура системы распознавания
5.2. Алгоритм работы системы распознавания
5.2.1. Этапы обработки текста.
5.2.2. Разбиение входного текста на фрагменты.
5.2.3. Операции над распознанными конструкциям и
5.2.4. Параметры, передаваемые процедурам обработки шаблонов
5.3. Алгоритм модификации очереди фрагментов шаблонами
5.4. Язык описания шаблонов.
6. Результаты экспериментов
6.1. Описания тестовых наборов
6.2. Описание тестов и результаты.
6.2.1. Влияние вида выделяемых из документа терминов на
эффективность классификации.
6.2.2. Вклад алгоритма сопоставления, использующего
полнотекстовый поиск
Содержание продолжение стр.
6.2.3. Вклад алгоритма расчета контекстной значимости
6.2.4. Эффективность классификации при увеличении объема обучающей выборки и ручной настройке.
6.2.5. Использование ассоциативных связей для повышения качества классификации
6.2.6. Использование объектов для повышения качества классификации
6.2.7. Скорость обучения и классификации
6.3. Выводы
Заключение
Основные результаты
Направления дальнейшей работы
Литература


Существуют системы для автоматической оценки эффективности программ классификации, которые в пакетном режиме выполняют обработку одного и того же набора тестовых документов несколькими различными методами, сравнивают результаты с экспертными оценками и вычисляют показатели эффективности. При этом один и тот же метод классификации может быть протестирован многократно с разными значениями настроечных параметров. Одна из таких систем описана в . В работах , приведены результаты экспериментов, в которых сравниваются современные методы классификации на одних и тех же наборах документов. Перед исследователями систем обработки текстов стоит задача сравнения различных методов, выбора среди них лучшего для данных условий и его тонкой настройки. Говоря математическим языком, выполняется поиск оптимального решения задачи. Для того, чтобы вести такой поиск, нужна численная мера того, насколько эффективно работает система. Принцип 1 ii i ii, Если ответы системы упорядочены по убыванию вероятности полезности для пользователя, причем эти вероятности оценены настолько точно, насколько это возможно с использованием данных, доступных системе, то эффективность такой системы максимальна по сравнению со всеми другими, располагающими этой же информацией. Понятно, что использовать его в чистом виде на практике не получается. Более того, не все используемые на практике меры эффективности согласуются с этим принципом. Пусть мы имеем некоторую меру эффективности , где результаты работы классифицирующей системы, экспертные оценки, с которыми мы эти результаты будем сравнивать , . Так как разные эксперты могут классифицировать документы по разному, причем среди всех документов, которые эксперты отнесли к рубрике, есть те, которые бесспорно ей соответствуют и те, которые соответствуют не вполне например, лишь часть документа посвящена данной тематике, можно представить в виде множества случайных величин , вероятность соответствия документа i рубрике каждая из которых имеет некоторое
распределение 7. А вот результаты работы классифицирующей системы наоборот, определяются исключительно алгоритмом, обучающими выборками, текстами документов и настроечными параметрами, и поэтому случайными величинами не являются1. Таким образом, перед нами стоят следующие задачи выбор меры эффективности и нахождение эффективных способов ее вычисления для заданных 7. Затем, имея меру эффективности, мы можем выбрать оптимальный метод классификации или настроить параметры имеющегося метода так, чтобы значение меры было максимальным. В общем виде решать такую задачу очень сложно, поэтому рассмотрим частный случай бинарный классификатор. В этом случае принимают значения 1 документ соответствует рубрике с вероятностью и значение 2 0 документ не соответствует рубрике с вероятностью 1 . Предположим также, что величины 2 независимы. Б представляет собой множество , где 1, если система классификации решила, что документ с, соответствует рубрике Г,, И 5,7 0 в противном случае. МММ 0. Вычисление меры эффективности по формуле 1. Этот принцип можно применять на практике для того, чтобы выбрать мы можем в каждой рубрике упорядочить документы по убыванию вероятности соответствия затем вычислить , для п1 различных экспертных оценок. Предположим, что набор из п документов и системы из т рубрик был одновременно подан на вход программе классификации и эксперту. Тогда для каждой пары г,, возможно одно из четырех состояний, перечисленных в ячейках таблицы 1. Величины а, Ь, с и обозначают количество пар в соответствующем состоянии . Наиболее часто при оценке эффективности используются следующие характеристики точность у, полнота м и частота ошибок д

а Ь а
1. Из этих формул следует, что для классификатора, который относит каждый подаваемый ему на вход документ ко всем рубрикам, полнота будет равна 1. Поэтому напрямую использовать какуюлибо одну из указанных выше величин нельзя. Существует очень большое количество функций от этих величин. Свойства некоторых из них рассмотрены в , . Чаще всего для оценки эффективности используется следующая мера , ,
где р параметр, задающий приоритет точности над полнотой или наоборот. М 1. А 1. II м 1 V 1 1.