Национальный исследовательский университет « МЭИ » Кафедра прикладной математики Выпускная работа студента гр. А Бочарова Ивана на тему : « Исследование и разработка методов классификации новостных текстов » Руководитель работы : д. т. н., проф. Фальк В. Н. Научный консультант : асс. Шаграев А. Г. Москва, 2012 г.

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

План 1. Постановка задачи классификации 2. Метрики качества классификации и способы оценки качества классификации 3. Обзор методов классификации 4. Усовершенствованный метод 5. Вычислительные эксперименты 6. Заключение

План 1. Постановка задачи классификации 2. Метрики качества классификации и способы оценки качества классификации 3. Обзор методов классификации 4. Усовершенствованный метод 5. Вычислительные эксперименты 6. Заключение

Неформальная постановка задачи классификации 1.Постановка задачи классификации

Вероятностная постановка задачи 1.Постановка задачи классификации

Описание объектов 1.Постановка задачи классификации

План 1. Постановка задачи классификации 2. Оценка качества классификации 3. Обзор методов классификации 4. Усовершенствованный метод 5. Вычислительные эксперименты 6. Заключение

Метрики качества классификации 2. Оценка качества классификации

Усреднение метрик 2. Оценка качества классификации

Скользящий контроль 2. Оценка качества классификации

План 1. Постановка задачи классификации 2. Метрики качества классификации и способы оценки качества классификации 3. Обзор методов классификации 4. Усовершенствованный метод 5. Вычислительные эксперименты 6. Заключение

Наивный байесовский классификатор Наивный байесовский классификатор – это один из методов решения задачи в вероятностной постановке. Работа метода основана на теореме Байеса и (« наивном ») предположении о том, что признаки, которыми описывается объект, являются независимыми. Достоинства метода : требуется малое количество данных для обучения высокая скорость работы легкость внесения в метод разного рода изменений 3. Обзор методов классификации

Байесовское решающее правило с использованием принципа максимизации апостериорной вероятности 3. Обзор методов классификации

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

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

Метод k ближайших взвешенных соседей 3. Обзор методов классификации

Машина опорных векторов ( SVM ) Работа метода основана на понятии оптимальной разделяющей гиперплоскости. Задача формулируется следующим образом : можем ли мы найти такую гиперплоскость, чтобы расстояние от нее до ближайшей точки было максимальным ? Если такая гиперплоскость существует, то она нас будет интересовать больше всего, она называется оптимальной разделяющей гиперплоскостью. Достоинства метода : Обучение SVM сводится к задаче квадратичного программирования, допускающей эффективное вычисление единственного решения задачи ; Решение обладает свойством « разреженности » – положение гиперплоскости определяется только небольшой частью выборки ( именно они и называются опорными векторами ); При помощи введения функций ядра этот метод изящно обобщается на случай нелинейных разделяющих поверхностей. 3. Обзор методов классификации

План 1. Постановка задачи классификации 2. Метрики качества классификации и способы оценки качества классификации 3. Обзор методов классификации 4. Усовершенствованный метод 5. Вычислительные эксперименты 6. Заключение

Базовый метод 4. Усовершенствованный метод

Сглаживание вероятностей 4. Усовершенствованный метод

Специфика метода 4. Усовершенствованный метод

План 1. Постановка задачи классификации 2. Метрики качества классификации и способы оценки качества классификации 3. Обзор методов классификации 4. Усовершенствованный метод 5. Вычислительные эксперименты 6. Заключение

5. Вычислительные эксперименты

Эксперимент 2. Подбор параметра w 5. Вычислительные эксперименты

Эксперимент 3. Сравнение метода с kNN (Reuters-21578) Данные по методам kNN и NewsNB получены при помощи 10- кратного скользящего контроля. Разработанная модификация метода работает лучше, чем метод k ближайших взвешенных соседей. 5. Вычислительные эксперименты

Эксперимент 4. Сравнение метода с SVM(Reuters-21578, 20 Newsgroups) МетодТочностьПолнота F- мераВремя работы, с SVM 0,7950,6360,67024,14 0,9150,8960,9087,25 МетодТочностьПолнота F- мераВремя работы, с SVM 0,740,6950,714132,4 0,8160,8100,813148,33 Разработанная модификация метода работает не хуже выбранной реализации SVM Использование только линейного ядра серьезно ухудшает качество работы алгоритма SVM Выбранная реализация SVM может работать быстрее разработанного метода по ряду причин : При оценке времени работы авторского метода учитываются временные затраты на выделение признаков из текстов Используемая реализация SVM написана а языке C, а авторский метод реализован на более « медленном » языке Python Reuters Newsgroups

План 1. Постановка задачи классификации 2. Метрики качества классификации и способы оценки качества классификации 3. Обзор методов классификации 4. Усовершенствованный метод 5. Вычислительные эксперименты 6. Заключение

Заключение Основным результатом работы является разработанная модификация наивного байесовского классификатора. Помимо этого : Изучена одна из возможных формальных постановок задачи классификации – вероятностная постановка. Проведено исследование алгоритмов классификации и методов предварительной обработки текста. Проведено достаточно большое количество вычислительных экспериментов, результаты которых подтверждают качество разработанного метода и позволяют говорить о том, что метод применим на практике. Разработан программный комплекс на ЯП Python, который позволяет проводить предварительную обработку текстов и осуществлять классификацию текстов при помощи модификации наивного байесовского классификатора.

Спасибо за внимание !