'

Национальный исследовательский университет «МЭИ»

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

Неформальная постановка задачи классификации Пусть: ?? – множество классифицируемых объектов ?? – конечное множество классов Предполагается наличие целевой зависимости – отображения ?? ? :??>??, значения которой известны только на документах конечной обучающей выборки ?? ?? = < ?? ?? , ?? ?? > ?? ?? = ?? ? ?? ?? ??=1 ?? Требуется: Построить решающую функцию ?? :??>??, способную классифицировать любой объект ?????. Постановка задачи классификации


Слайд 5

Вероятностная постановка задачи Пусть: ?? – множество классифицируемых объектов, ?? - конечное множество классов, На множестве ?? ??? определена функция плотности распределения: ?? <??,??> = ?? ?? ?? ?? ?? Имеется конечная обучающая выборка ?? ?? = < ?? ?? , ?? ?? > ??=1 ?? , ?? ?? ? ????? ?? Вероятности появления объектов каждого из классов ?? ?? = ??(??) называются вероятностями классов. Плотности распределения ?? ?? ?? = ??(??|??) называются функциями правдоподобия классов. Необходимо: построить эмпирические оценки вероятностей классов ??(??) и функций правдоподобия ?? ?? ?? построить классификатор ?? :??>??, минимизирующий вероятность ошибочной классификации. Постановка задачи классификации


Слайд 6

Описание объектов Ситуация, когда объекты используются для классификации в их первоначальном виде, довольно редка. Чаще всего формируется некоторое признаковое описание объекта. Признак – результат измерения некоторой характеристики объекта. Формально: ??:??> ?? ?? , где ?? ?? - множество допустимых значений признака. Выделяют следующие типы признаков: бинарные ( ?? ?? ={0;1}), номинальные ( ?? ?? - конечное), порядковые ( ?? ?? - конечное упорядоченное множество), количественные ( ?? ?? =?). Постановка задачи классификации


Слайд 7

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


Слайд 8

Метрики качества классификации Точность: ??= ????? [?? ?? =??? ?? ? ?? =??] ????? [?? ?? =??] Полнота: ??= ????? [?? ?? =??? ?? ? ?? =??] ????? [ ?? ? ?? =??] ??-мера: ?? ?? = ( ?? 2 +1)???? ?? 2 ??+?? , ?? 2 ?(0,+?) 2. Оценка качества классификации


Слайд 9

Усреднение метрик Макроусреднение ?? ?????????? = 1 |??| ??=1 |??| ???? ?? ???? ?? + ???? ?? , ?? ?????????? = 1 |??| ??=1 |??| ???? ?? ???? ?? + ???? ?? Микроусреднение ?? ?????????? = ??=1 |??| ???? ?? ??=1 |??| ???? ?? + ???? ?? , ?? ?????????? = ??=1 |??| ???? ?? ??=1 |??| ???? ?? + ???? ?? В данной работе усреднение производится методом макроусреднения, так как этот метод чувствителен к ошибкам классификации на малых классах 2. Оценка качества классификации


Слайд 10

Скользящий контроль Оценкой скользящего контроля по q разбиениям называется величина ?? ?? ?? ??, ?? ?? = 1 ?? ??=1 ?? ?? ?? ?? ?? \ ?? ?? ?? , ?? ?? ?? , где: ?? ?? = ?? 1 ?? ? ?? 2 ?? ?…? ?? ?? ?? – случайное разбиение выборки на ?? непересекающихся подмножеств мощности ??; ?? – метод обучения (отображение, ставящее в соответствие любой обучающей выборке решающую функцию ?? :??>??); ?? – функционал качества. Оценка скользящего контроля является случайной величиной, значение которой зависит от разбиения обучающей выборки. Процедуру скользящего контроля также используют для построения доверительных интервалов, например: ?? ?? ?? ?? ????? , ?? ?? < min 1?????? ?? ?? ?? ?? \ ?? ?? ?? , ?? ?? ?? = 1 ??+1 2. Оценка качества классификации


Слайд 11

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


Слайд 12

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


Слайд 13

Байесовское решающее правило с использованием принципа максимизации апостериорной вероятности ??(??)= arg max ????? ??(??|??) Для вычисления ??(??|??) используют формулу Байеса: ?? ?? ?? = ??(??,??) ??(??) = ?? ?? (??) ?? ?? ????? ?? ?? (??) ?? ?? Для применения решающего правила необходимо получить оценки значений ?? ?? (??) и ?? ?? 3. Обзор методов классификации


Слайд 14

Оценки вероятностей в задаче классификации текстов Для оценки вероятностей классов используется величина ?? ?? ?? = | ?? ?? | |??| , где ?? ?? – число документов, принадлежащих категории ?? ?? , а ?? – общее число документов в выборке. В силу наивного предположения для оценки значений ?? ?? (??) в задаче классификации текстов необходимо оценить только значения ?? ?? ?? ?? , так как: ?? ?? ?? =?? ?? 1 ,…, ?? ?? ,…, ?? ?? ?? ?? =?? ?? 1 ?? ?…??? ?? ?? ?? ?…??? ?? ?? ?? Их значения оцениваются по формуле: ?? ?? ?? ?? = ?? с?? ?? ??? ?? ?? ?? ? , где: ?? с?? ?? - число вхождений слова ?? ?? в документы из обучающего множества, принадлежащие категории ??. 3. Обзор методов классификации


Слайд 15

Переход к суммированию ?? ?? = arg max ????? ?? ?? ?? ?? ?? = arg max ????? (ln ?? ?? + ln ?? ?? ?? )= arg max ????? (ln ?? ?? + ln ??=1 ?? ?? ??( ?? ?? |??) )= arg max ????? (ln ?? ?? + ??=1 ?? ?? ln ??( ?? ?? |??) ) 3. Обзор методов классификации


Слайд 16

Метод k ближайших взвешенных соседей Метрический метод классификации. Предполагается , что близкие в смысле функции расстояния объекты принадлежат к одному классу. Введем пороговую функцию : ?? = 1,?? 0, ?? , где P – некое условие Метод относит классифицируемый объект к тому классу, суммарный вес представителей которого среди ?? ближайших объектов является максимальным: ?? ?? = arg max с??? ??=1 ?? [ ?? ?? ?? =??] ?? ?? , где ?? ?? ?? - категория, к которой принадлежит ?? ?? ?? - ??-й сосед объекта ??. Обычно: ?? ?? = ?? ?? ,??? 0;1 3. Обзор методов классификации


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

Сглаживание вероятностей Вообще говоря, непонятно, как оценивать значение ?? ?? ?? ?? , если слово ?? ?? ни разу не встречалось в документах обучающей выборки. Обычно поступают так. Предполагают существование некоторой априорной вероятности появления какого-либо слова. Рассмотрим, как применяется сглаживание в данной работе: ?? ?? ?? ?? = ?? с?? ?? +?? ??? ?? ?? ?? ? +|??|?? , где: ??>0 – параметр сглаживания, |??| - количество различных слов, встречавшихся в документах обучающей выборки Предполагается, что каждое слово встречается хотя бы раз в каждом из документов выборки. После этого априорная вероятность корректируется в соответствии с содержанием документа. 4. Усовершенствованный метод


Слайд 21

Специфика метода Сделана попытка в явном виде учесть следующую особенность новостных текстов. Обычно новостная статья имеет очень содержательное начало, а вот к концу статьи ее содержательность может снижаться. Предполагается, что, если проводить классификацию, скажем, по первым 150, 100, 50 и т.д. словам, а не по полному тексту, качество классификации ухудшится незначительно. Так, ?? – число слов, по которым проводится классификация, становится еще одним параметром метода, наряду с ?? (параметром сглаживания) 4. Усовершенствованный метод


Слайд 22

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


Слайд 23

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


Слайд 24

Эксперимент 2. Подбор параметра w 5. Вычислительные эксперименты Выводы: Использование при классификации только начальной части текста (к примеру, первых 100 слов) улучшает качество классификации (особенно, при удачном выборе параметра ??) Данный эксперимент показывает, что, проводить ли классификацию по первым 50 словам документа или по всему документу, практически не имеет значения. Было подтверждено предположение о высокой значимости начала новостной статьи Проведение классификации только по началу документа позволяет сократить время работы метода примерно на четверть (на стандартном разбиении Reuters-21578 при ??=50 метод работал 6,53 секунды против 8,5 при полнотекстовой классификации)


Слайд 25

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


Слайд 26

Эксперимент 4. Сравнение метода с SVM(Reuters-21578, 20 Newsgroups) Разработанная модификация метода работает не хуже выбранной реализации SVM Использование только линейного ядра серьезно ухудшает качество работы алгоритма SVM Выбранная реализация SVM может работать быстрее разработанного метода по ряду причин: При оценке времени работы авторского метода учитываются временные затраты на выделение признаков из текстов Используемая реализация SVM написана а языке C, а авторский метод реализован на более «медленном» языке Python Reuters-21578 20Newsgroups


Слайд 27

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


Слайд 28

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


Слайд 29

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


×

HTML:





Ссылка: