Байесовский классификатор

Материал из MachineLearning.

Перейти к: навигация, поиск

Байесовский классификатор — алгоритм классификации, основанный на принципе максимума апостериорной вероятности. Для классифицируемого объекта вычисляются функции правдоподобия каждого из классов; по ним вычисляются апостериорные вероятности классов; и объект относится к тому классу, для которого апостериорная вероятность максимальна.

Содержание

Введение

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

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

Байесовский подход к классификации является одним из старейших, но до сих пор сохраняет прочные позиции в теории распознавания. Он лежит в основе многих достаточно удачных алгоритмов классификации.

Основная формула

Пусть X — множество описаний объектов, Y — множество номеров (или наименований) классов. На множестве пар «объект, класс» X \times Y определена вероятностная мера \mathsf P. Имеется конечная обучающая выборка независимых наблюдений X^m = \{(x_1,y_1),\ldots,(x_m,y_m)\}, полученных согласно вероятностной мере \mathsf P.

Задача классификации заключается в том, чтобы построить алгоритм a:\; X\to Y, способный классифицировать произвольный объект x \in X.

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

Построение классификатора при известных плотностях классов

Задача 1. Пусть для каждого класса y \in Y известна априорная вероятность P_y того, что появится объект класса y, и плотности распределения p_y(x) каждого из классов, называемые также функциями правдоподобия классов. Требуется построить алгоритм классификации a(x), доставляющий минимальное значение функционалу среднего риска.

Средний риск опредеяется как математическое ожидание ошибки:

R(a) = \sum_{y\in Y} \sum_{s\in Y} \lambda_{y} P_y \mathsf{P}_{(x,y)}\bigl\{a(x)=s|y\bigr\},

где \lambda_{y} — цена ошибки или штраф за отнесение объекта класса y к какому-либо другому классу.

Теорема. Решением этой задачи является алгоритм

a(x) = \mathrm{arg}\max_{y\in Y} \lambda_{y} P_y p_y(x).

Значение P\{y|x\} = P_y p_y(x) интерпретируется как апостериорная вероятность того, что объект x принадлежит классу y.

Если классы равнозначимы, \lambda_{y} P_y = \mathrm{const}(y), то объект x просто относится к классу с наибольшим значением плотности распределения в точке x.

Восстановление плотностей классов по обучающей выборке

Задача 2. По заданной подвыборке объектов класса y построить эмпирические оценки априорных вероятностей P_y и функций правдоподобия p_y(x).

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

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

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

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

Наивный байесовский классификатор (naїve Bayes) основан на той же формуле и дополнительном предположении, что объекты описываются n независимыми признаками: x \equiv \bigl( \xi_1=f_1(x),\ldots, \xi_n=f_n(x) \bigr). Следовательно, функции правдоподобия классов представимы в виде p_y(x) = p_{y1}(\xi_1) \cdot \ldots \cdot p_{yn}(\xi_n), где p_{yj}(\xi_j) — плотность распределения значений j-го признака для класса y.

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

Наивный байесовский классификатор может быть как параметрическим, так и непараметрическим, в зависимости от того, каким методом восстанавливаются одномерные плотности.

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

Основной его недостаток — относительно низкое качество классификации в большинстве реальных задач.

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

Литература

  1. Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
  2. Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
  3. Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1976.
  4. Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.

Ссылки

Источник — «http://recognition.su/wiki/index.php?title=%D0%91%D0%B0%D0%B9%D0%B5%D1%81%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%B8%D1%84%D0%B8%D0%BA%D0%B0%D1%82%D0%BE%D1%80»