uzluga.ru
добавить свой файл
1



Цели и задачи

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

Задачи:
  • Исследование постановок задачи классификации, методов решения, способов оценки качества классификации

  • Усовершенствование одного из классических методов

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



План

  • Постановка задачи классификации

  • Метрики качества классификации и способы оценки качества классификации

  • Обзор методов классификации

  • Усовершенствованный метод

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

  • Заключение



План

  • Постановка задачи классификации

  • Метрики качества классификации и способы оценки качества классификации

  • Обзор методов классификации

  • Усовершенствованный метод

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

  • Заключение



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

Пусть:
  • – множество классифицируемых объектов

  • – конечное множество классов

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

Требуется:

Построить решающую функцию , способную классифицировать любой объект

Вероятностная постановка задачи

Пусть:

– множество классифицируемых объектов, - конечное множество классов,

На множестве определена функция плотности распределения:

Имеется конечная обучающая выборка

,

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

Необходимо:
  • построить эмпирические оценки вероятностей классов и функций правдоподобия

  • построить классификатор , минимизирующий вероятность ошибочной классификации.



Описание объектов

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

Признак – результат измерения некоторой характеристики объекта.

Формально: , где - множество допустимых значений признака.

Выделяют следующие типы признаков:
  • бинарные (),

  • номинальные ( - конечное),

  • порядковые ( - конечное упорядоченное множество),

  • количественные ().



План

  • Постановка задачи классификации

  • Оценка качества классификации

  • Обзор методов классификации

  • Усовершенствованный метод

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

  • Заключение



Метрики качества классификации

  • Точность:

  • Полнота:

  • -мера:



Усреднение метрик

  • Макроусреднение

  • Микроусреднение

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

Скользящий контроль

Оценкой скользящего контроля по q разбиениям называется величина

где:
  • – случайное разбиение выборки на непересекающихся подмножеств мощности ;

  • – метод обучения (отображение, ставящее в соответствие любой обучающей выборке решающую функцию );

  • – функционал качества.

Оценка скользящего контроля является случайной величиной, значение которой зависит от разбиения обучающей выборки.

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

План

  • Постановка задачи классификации

  • Метрики качества классификации и способы оценки качества классификации

  • Обзор методов классификации

  • Усовершенствованный метод

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

  • Заключение



Наивный байесовский классификатор

Наивный байесовский классификатор – это один из методов решения задачи в вероятностной постановке.

Работа метода основана на теореме Байеса и («наивном») предположении о том, что признаки, которыми описывается объект, являются независимыми.

Достоинства метода:
  • требуется малое количество данных для обучения

  • высокая скорость работы

  • легкость внесения в метод разного рода изменений



Байесовское решающее правило с использованием принципа максимизации апостериорной вероятности

Для вычисления используют формулу Байеса:

Для применения решающего правила необходимо получить оценки значений и

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

Для оценки вероятностей классов используется величина

, где

– число документов, принадлежащих категории , а – общее число документов в выборке.

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

Их значения оцениваются по формуле:

, где:

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

Переход к суммированию



Метод k ближайших взвешенных соседей

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

Введем пороговую функцию :

, где P – некое условие

Метод относит классифицируемый объект к тому классу, суммарный вес представителей которого среди ближайших объектов является максимальным:

,

где - категория, к которой принадлежит - -й сосед объекта .

Обычно:

Машина опорных векторов (SVM)

Работа метода основана на понятии оптимальной разделяющей гиперплоскости.

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

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

Достоинства метода:
  • Обучение SVM сводится к задаче квадратичного программирования, допускающей эффективное вычисление единственного решения задачи;

  • Решение обладает свойством «разреженности» – положение гиперплоскости определяется только небольшой частью выборки (именно они и называются опорными векторами);

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



План

  • Постановка задачи классификации

  • Метрики качества классификации и способы оценки качества классификации

  • Обзор методов классификации

  • Усовершенствованный метод

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

  • Заключение



Базовый метод

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

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

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

Сглаживание вероятностей

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

Обычно поступают так. Предполагают существование некоторой априорной вероятности появления какого-либо слова. Рассмотрим, как применяется сглаживание в данной работе:

где:

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

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

Специфика метода

Сделана попытка в явном виде учесть следующую особенность новостных текстов. Обычно новостная статья имеет очень содержательное начало, а вот к концу статьи ее содержательность может снижаться.

Предполагается, что, если проводить классификацию, скажем, по первым 150, 100, 50 и т.д. словам, а не по полному тексту, качество классификации ухудшится незначительно.

Так, – число слов, по которым проводится классификация, становится еще одним параметром метода, наряду с (параметром сглаживания)

План

  • Постановка задачи классификации

  • Метрики качества классификации и способы оценки качества классификации

  • Обзор методов классификации

  • Усовершенствованный метод

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

  • Заключение



Эксперимент 1. Подбор параметра . Влияние предобработки.

  • Предварительная обработка (стемминг, удаление стоп-слов) положительно влияют на качество классификации

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



Эксперимент 2. Подбор параметра w



Эксперимент 3. Сравнение метода с kNN (Reuters-21578)



Эксперимент 4. Сравнение метода с SVM(Reuters-21578, 20 Newsgroups)



План

  • Постановка задачи классификации

  • Метрики качества классификации и способы оценки качества классификации

  • Обзор методов классификации

  • Усовершенствованный метод

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

  • Заключение



Заключение

Основным результатом работы является разработанная модификация наивного байесовского классификатора.

Помимо этого:
  • Изучена одна из возможных формальных постановок задачи классификации – вероятностная постановка.

  • Проведено исследование алгоритмов классификации и методов предварительной обработки текста.

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

  • Разработан программный комплекс на ЯП Python, который позволяет проводить предварительную обработку текстов и осуществлять классификацию текстов при помощи модификации наивного байесовского классификатора.