Байесовский классификатор
Материал из MachineLearning.
м |
м |
||
Строка 1: | Строка 1: | ||
- | '''Байесовский классификатор''' — широкий класс алгоритмов [[классификация|классификации]], основанный на принципе максимума апостериорной вероятности. Для классифицируемого объекта вычисляются функции правдоподобия каждого из классов | + | '''Байесовский классификатор''' — широкий класс алгоритмов [[классификация|классификации]], основанный на принципе максимума апостериорной вероятности. Для классифицируемого объекта вычисляются функции правдоподобия каждого из классов, по ним вычисляются апостериорные вероятности классов. Объект относится к тому классу, для которого апостериорная вероятность максимальна. |
== Введение == | == Введение == | ||
Байесовский подход к классификации основан на теореме, утверждающей, что если плотности распределения каждого из классов известны, то искомый алгоритм можно выписать в явном аналитическом виде. Более того, этот алгоритм оптимален, то есть обладает минимальной вероятностью ошибок. | Байесовский подход к классификации основан на теореме, утверждающей, что если плотности распределения каждого из классов известны, то искомый алгоритм можно выписать в явном аналитическом виде. Более того, этот алгоритм оптимален, то есть обладает минимальной вероятностью ошибок. | ||
- | На практике плотности распределения классов, как правило, не известны. Их приходится оценивать (восстанавливать) по обучающей выборке. В результате байесовский алгоритм перестаёт быть оптимальным, так как восстановить плотность по выборке можно только с некоторой погрешностью. Чем короче выборка, | + | На практике плотности распределения классов, как правило, не известны. Их приходится [[Восстановление распределения вероятностей|оценивать (восстанавливать)]] по обучающей выборке. В результате байесовский алгоритм перестаёт быть оптимальным, так как восстановить плотность по выборке можно только с некоторой погрешностью. Чем короче выборка, |
тем выше шансы подогнать распределение под конкретные данные и столкнуться с [[переобучение|эффектом переобучения]]. | тем выше шансы подогнать распределение под конкретные данные и столкнуться с [[переобучение|эффектом переобучения]]. | ||
Строка 71: | Строка 71: | ||
долю объектов данного класса в обучающей выборке. | долю объектов данного класса в обучающей выборке. | ||
- | Восстановление плотностей (функций правдоподобия каждого из классов) является | + | [[Восстановление распределения вероятностей|Восстановление плотностей]] (функций правдоподобия каждого из классов) является наиболее трудной задачей. |
Наиболее распространены три подхода: параметрический, непараметрический | Наиболее распространены три подхода: параметрический, непараметрический | ||
и расщепление смеси вероятностных распределений. | и расщепление смеси вероятностных распределений. | ||
Строка 118: | Строка 118: | ||
== Литература == | == Литература == | ||
# ''Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д.'' Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989. | # ''Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д.'' Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989. | ||
+ | # ''Вапник В. Н., Червоненкис А. Я.'' Теория распознавания образов. — М.: Наука, 1974. | ||
# ''Вапник В. Н.'' Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. | # ''Вапник В. Н.'' Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979. | ||
# ''Дуда Р., Харт П.'' Распознавание образов и анализ сцен. — М.: Мир, 1976. | # ''Дуда Р., Харт П.'' Распознавание образов и анализ сцен. — М.: Мир, 1976. |
Версия 16:30, 4 апреля 2008
Байесовский классификатор — широкий класс алгоритмов классификации, основанный на принципе максимума апостериорной вероятности. Для классифицируемого объекта вычисляются функции правдоподобия каждого из классов, по ним вычисляются апостериорные вероятности классов. Объект относится к тому классу, для которого апостериорная вероятность максимальна.
Содержание |
Введение
Байесовский подход к классификации основан на теореме, утверждающей, что если плотности распределения каждого из классов известны, то искомый алгоритм можно выписать в явном аналитическом виде. Более того, этот алгоритм оптимален, то есть обладает минимальной вероятностью ошибок.
На практике плотности распределения классов, как правило, не известны. Их приходится оценивать (восстанавливать) по обучающей выборке. В результате байесовский алгоритм перестаёт быть оптимальным, так как восстановить плотность по выборке можно только с некоторой погрешностью. Чем короче выборка, тем выше шансы подогнать распределение под конкретные данные и столкнуться с эффектом переобучения.
Байесовский подход к классификации является одним из старейших, но до сих пор сохраняет прочные позиции в теории распознавания. Он лежит в основе многих достаточно удачных алгоритмов классификации.
К числу байесовских методов классификации относятся:
- Наивный байесовский классификатор
- Линейный дискриминант Фишера
- Квадратичный дискриминант
- Метод парзеновского окна
- Метод радиальных базисных функций (RBF)
- Логистическая регрессия
Основная формула
Пусть — множество описаний объектов, — множество номеров (или наименований) классов. На множестве пар «объект, класс» определена вероятностная мера . Имеется конечная обучающая выборка независимых наблюдений , полученных согласно вероятностной мере .
Задача классификации заключается в том, чтобы построить алгоритм , способный классифицировать произвольный объект .
В байесовской теории классификации эта задача разделяется на две.
Построение классификатора при известных плотностях классов
Задача 1. Пусть для каждого класса известна априорная вероятность того, что появится объект класса , и плотности распределения каждого из классов, называемые также функциями правдоподобия классов. Требуется построить алгоритм классификации , доставляющий минимальное значение функционалу среднего риска.
Средний риск опредеяется как математическое ожидание ошибки:
где — цена ошибки или штраф за отнесение объекта класса к какому-либо другому классу.
Теорема. Решением этой задачи является алгоритм
Значение интерпретируется как апостериорная вероятность того, что объект принадлежит классу .
Если классы равнозначимы, , то объект просто относится к классу с наибольшим значением плотности распределения в точке .
Восстановление плотностей классов по обучающей выборке
Задача 2. По заданной подвыборке объектов класса построить эмпирические оценки априорных вероятностей и функций правдоподобия .
В качестве оценки априорных вероятностей берут, как правило, долю объектов данного класса в обучающей выборке.
Восстановление плотностей (функций правдоподобия каждого из классов) является наиболее трудной задачей. Наиболее распространены три подхода: параметрический, непараметрический и расщепление смеси вероятностных распределений. Третий подход занимает промежуточное положение между первыми двумя, и в определённом смысле является наиболее общим.
- Параметрическое восстановление плотности при дополнительном предположении, что плотности нормальные (гауссовские), приводит к нормальному дискриминантному анализу и линейному дискриминанту Фишера.
- Непараметрическое восстановление плотности приводит, в частности, к методу парзеновского окна.
- Восстановление смеси плотностей может быть сделано с помощью EM-алгоритма. Дополнительное предположение, что плотности компонент смеси являются радиальными функциями, приводит к методу радиальных базисных функций. Обычно в качестве компонент смеси берут, опять-таки, гауссовские плотности.
Таким образом, формула байесовского классификатора приводит к большому разнообразию байесовских алгоритмов, отличающихся только способом восстановления плотностей.
Наивный байесовский классификатор
Наивный байесовский классификатор (naїve Bayes) основан на той же формуле и дополнительном предположении, что объекты описываются независимыми признаками: . Следовательно, функции правдоподобия классов представимы в виде , где — плотность распределения значений -го признака для класса .
Предположение о независимости существенно упрощает задачу, так как оценить одномерных плотностей гораздо легче, чем одну -мерную плотность. К сожалению, оно крайне редко выполняется на практике, отсюда и название метода.
Наивный байесовский классификатор может быть как параметрическим, так и непараметрическим, в зависимости от того, каким методом восстанавливаются одномерные плотности.
Основные его преимущества — простота реализации и низкие вычислительные затраты при обучении и классификации. В тех редких случаях, когда признаки действительно независимы (или почти независимы), наивный байесовский классификатор (почти) оптимален.
Основной его недостаток — относительно низкое качество классификации в большинстве реальных задач.
Чаще всего он используется либо как примитивный эталон для сравнения различных моделей алгоритмов, либо как элементарный строительный блок в алгоритмических композициях.
Литература
- Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д. Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
- Вапник В. Н., Червоненкис А. Я. Теория распознавания образов. — М.: Наука, 1974.
- Вапник В. Н. Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
- Дуда Р., Харт П. Распознавание образов и анализ сцен. — М.: Мир, 1976.
- Hastie T., Tibshirani R., Friedman J. The Elements of Statistical Learning. — Springer, 2001. ISBN 0-387-95284-5.
Ссылки
- Воронцов К.В. Математические методы обучения по прецедентам. МФТИ (2004), ВМиК МГУ (2007).