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

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

(Различия между версиями)
Перейти к: навигация, поиск
м
Текущая версия (18:26, 18 октября 2008) (править) (отменить)
(викификация)
 
(6 промежуточных версий не показаны.)
Строка 1: Строка 1:
-
'''Байесовский классификатор''' — алгоритм классификации, основанный на принципе максимума апостериорной вероятности. Для классифицируемого объекта вычисляются функции правдоподобия каждого из классов; по ним вычисляются апостериорные вероятности классов; и объект относится к тому классу, для которого апостериорная вероятность максимальна.
+
'''Байесовский классификатор''' — широкий класс [[алгоритм]]ов [[классификация|классификации]], основанный на принципе максимума апостериорной вероятности. Для классифицируемого объекта вычисляются функции правдоподобия каждого из классов, по ним вычисляются апостериорные вероятности классов. Объект относится к тому классу, для которого апостериорная вероятность максимальна.
== Введение ==
== Введение ==
Байесовский подход к классификации основан на теореме, утверждающей, что если плотности распределения каждого из классов известны, то искомый алгоритм можно выписать в явном аналитическом виде. Более того, этот алгоритм оптимален, то есть обладает минимальной вероятностью ошибок.
Байесовский подход к классификации основан на теореме, утверждающей, что если плотности распределения каждого из классов известны, то искомый алгоритм можно выписать в явном аналитическом виде. Более того, этот алгоритм оптимален, то есть обладает минимальной вероятностью ошибок.
-
На практике плотности распределения классов, как правило, не известны. Их приходится оценивать (восстанавливать) по обучающей выборке. В результате байесовский алгоритм перестаёт быть оптимальным, так как восстановить плотность по выборке можно только с некоторой погрешностью. Чем короче выборка,
+
На практике плотности распределения классов, как правило, не известны. Их приходится [[Восстановление распределения вероятностей|оценивать (восстанавливать)]] по обучающей выборке. В результате байесовский алгоритм перестаёт быть оптимальным, так как восстановить плотность по выборке можно только с некоторой погрешностью. Чем короче выборка,
тем выше шансы подогнать распределение под конкретные данные и столкнуться с [[переобучение|эффектом переобучения]].
тем выше шансы подогнать распределение под конкретные данные и столкнуться с [[переобучение|эффектом переобучения]].
Байесовский подход к классификации является одним из старейших, но до сих пор сохраняет прочные позиции в теории распознавания. Он лежит в основе многих достаточно удачных алгоритмов классификации.
Байесовский подход к классификации является одним из старейших, но до сих пор сохраняет прочные позиции в теории распознавания. Он лежит в основе многих достаточно удачных алгоритмов классификации.
 +
 +
К числу байесовских методов классификации относятся:
 +
* [[Наивный байесовский классификатор]]
 +
* [[Линейный дискриминант Фишера]]
 +
* [[Квадратичный дискриминант]]
 +
* [[Метод парзеновского окна]]
 +
* [[Метод радиальных базисных функций]] (RBF)
 +
* [[Логистическая регрессия]]
== Основная формула ==
== Основная формула ==
Строка 18: Строка 26:
полученных согласно вероятностной мере&nbsp;<tex>\mathsf P</tex>.
полученных согласно вероятностной мере&nbsp;<tex>\mathsf P</tex>.
-
'''Задача классификации''' заключается в том, чтобы построить алгоритм
+
'''Задача классификации''' заключается в том, чтобы построить [[алгоритм]]
<tex>a:\; X\to Y</tex>,
<tex>a:\; X\to Y</tex>,
способный классифицировать произвольный объект
способный классифицировать произвольный объект
Строка 24: Строка 32:
В байесовской теории классификации эта задача разделяется на две.
В байесовской теории классификации эта задача разделяется на две.
 +
* Построение оптимального классификатора при известных плотностях классов. Эта подзадача имеет простое и окончательное решение.
 +
* Восстановление плотностей классов по обучающей выборке. {{S|В этой}} подзадаче сосредоточена основная сложность байесовского подхода к классификации.
=== Построение классификатора при известных плотностях классов ===
=== Построение классификатора при известных плотностях классов ===
-
'''Задача 1.'''
 
Пусть для каждого класса <tex>y \in Y</tex> известна
Пусть для каждого класса <tex>y \in Y</tex> известна
''априорная вероятность'' <tex>P_y</tex> того, что появится объект класса <tex>y</tex>,
''априорная вероятность'' <tex>P_y</tex> того, что появится объект класса <tex>y</tex>,
Строка 36: Строка 45:
''Средний риск'' опредеяется как математическое ожидание ошибки:
''Средний риск'' опредеяется как математическое ожидание ошибки:
<center>
<center>
-
<tex>R(a) = \sum_{y\in Y} \sum_{s\in Y} \lambda_{y} P_y \mathsf{P}_{(x,y)}\bigl\{a(x)=s|y\bigr\},
+
<tex>R(a) = \sum_{y\in Y} \sum_{s\in Y} \lambda_{y} P_y \mathsf{P}_{(x,y)}\bigl\{a(x)=s|y\bigr\},</tex>
-
</tex>
+
</center>
</center>
где <tex>\lambda_{y}</tex> — ''цена ошибки'' или
где <tex>\lambda_{y}</tex> — ''цена ошибки'' или
Строка 44: Строка 52:
'''Теорема.''' Решением этой задачи является алгоритм
'''Теорема.''' Решением этой задачи является алгоритм
<center>
<center>
-
<tex>a(x) = \mathrm{arg}\max_{y\in Y} \lambda_{y} P_y p_y(x).
+
<tex>a(x) = \mathrm{arg}\max_{y\in Y} \lambda_{y} P_y p_y(x).</tex>
-
</tex>
+
</center>
</center>
Строка 55: Строка 62:
=== Восстановление плотностей классов по обучающей выборке ===
=== Восстановление плотностей классов по обучающей выборке ===
-
'''Задача 2.'''
 
По заданной подвыборке объектов класса <tex>y</tex>
По заданной подвыборке объектов класса <tex>y</tex>
построить эмпирические оценки априорных вероятностей <tex>P_y</tex>
построить эмпирические оценки априорных вероятностей <tex>P_y</tex>
и функций правдоподобия <tex>p_y(x)</tex>.
и функций правдоподобия <tex>p_y(x)</tex>.
-
В качестве оценки априорных вероятностей берут, как правило,
+
В качестве оценки априорных вероятностей берут, как правило, долю объектов данного класса в обучающей выборке.
-
долю объектов данного класса в обучающей выборке.
+
-
Восстановление плотностей (функций правдоподобия каждого из классов) является самой трудной задачей.
+
[[Восстановление распределения вероятностей|Восстановление плотностей]] (функций правдоподобия каждого из классов) является наиболее трудной задачей.
-
Наиболее распространены три подхода: параметрический, непараметрический
+
Наиболее распространены три подхода: параметрический, непараметрический и разделение смеси вероятностных распределений.
-
и расщепление смеси вероятностных распределений.
+
Третий подход занимает промежуточное положение между первыми двумя, и в определённом смысле является наиболее общим.
-
Третий подход занимает промежуточное положение между первыми двумя,
+
-
и в определённом смысле является наиболее общим.
+
* ''Параметрическое'' восстановление плотности при дополнительном предположении, что [[многомерное нормальное распределение|плотности нормальные (гауссовские)]], приводит к [[нормальный дискриминантный анализ|нормальному дискриминантному анализу]] и [[Линейный дискриминант Фишера|линейному дискриминанту Фишера]].
* ''Параметрическое'' восстановление плотности при дополнительном предположении, что [[многомерное нормальное распределение|плотности нормальные (гауссовские)]], приводит к [[нормальный дискриминантный анализ|нормальному дискриминантному анализу]] и [[Линейный дискриминант Фишера|линейному дискриминанту Фишера]].
* ''Непараметрическое'' восстановление плотности приводит, в частности, к [[метод парзеновского окна|методу парзеновского окна]].
* ''Непараметрическое'' восстановление плотности приводит, в частности, к [[метод парзеновского окна|методу парзеновского окна]].
-
* ''Восстановление смеси плотностей'' может быть сделано с помощью [[EM-алгоритм]]а. Дополнительное предположение, что плотности компонент смеси являются радиальными функциями, приводит к [[Метод радиальных базисных функций|методу радиальных базисных функций]]. Обычно в качестве компонент смеси берут, опять-таки, гауссовские плотности.
+
* ''[[Разделение смеси распределений]]'' может быть сделано с помощью [[EM-алгоритм]]а. Дополнительное предположение, что плотности компонент смеси являются радиальными функциями, приводит к [[Метод радиальных базисных функций|методу радиальных базисных функций]]. Обычно в качестве компонент смеси берут, опять-таки, гауссовские плотности.
Таким образом, формула байесовского классификатора приводит к большому разнообразию байесовских алгоритмов, отличающихся только способом восстановления плотностей.
Таким образом, формула байесовского классификатора приводит к большому разнообразию байесовских алгоритмов, отличающихся только способом восстановления плотностей.
== Наивный байесовский классификатор ==
== Наивный байесовский классификатор ==
-
''Наивный байесовский классификатор'' (naїve Bayes)
+
''[[Наивный байесовский классификатор]]'' (naїve Bayes)
основан на той же формуле и дополнительном предположении, что
основан на той же формуле и дополнительном предположении, что
-
объекты описываются <tex>n</tex> независимыми признаками:
+
объекты описываются независимыми признаками.
-
<tex>x \equiv \bigl( \xi_1=f_1(x),\ldots, \xi_n=f_n(x) \bigr)</tex>.
+
-
Следовательно, функции правдоподобия классов представимы в виде
+
-
<tex>p_y(x) = p_{y1}(\xi_1) \cdot \ldots \cdot p_{yn}(\xi_n)</tex>,
+
-
где
+
-
<tex>p_{yj}(\xi_j)</tex> — плотность распределения значений
+
-
<tex>j</tex>-го признака для класса <tex>y</tex>.
+
-
 
+
Предположение о независимости существенно упрощает задачу,
Предположение о независимости существенно упрощает задачу,
так как оценить <tex>n</tex> одномерных плотностей гораздо легче, чем
так как оценить <tex>n</tex> одномерных плотностей гораздо легче, чем
одну <tex>n</tex>-мерную плотность.
одну <tex>n</tex>-мерную плотность.
-
К сожалению, оно крайне редко выполняется на практике, отсюда и название метода.
+
{{S|К сожалению}}, оно крайне редко выполняется на практике, отсюда и название метода.
-
 
+
Наивный байесовский классификатор может быть как параметрическим, так и непараметрическим,
Наивный байесовский классификатор может быть как параметрическим, так и непараметрическим,
в зависимости от того, каким методом восстанавливаются одномерные плотности.
в зависимости от того, каким методом восстанавливаются одномерные плотности.
-
 
-
Основные его преимущества — простота реализации
 
-
и низкие вычислительные затраты при обучении и классификации.
 
-
В тех редких случаях, когда
 
-
признаки действительно независимы (или почти независимы),
 
-
наивный байесовский классификатор (почти) оптимален.
 
-
 
-
Основной его недостаток —
 
-
относительно низкое качество классификации в большинстве реальных задач.
 
-
 
-
Чаще всего он используется либо как примитивный эталон
 
-
для сравнения различных моделей алгоритмов,
 
-
либо как элементарный строительный блок
 
-
в [[алгоритмическая композиция|алгоритмических композициях]].
 
== Литература ==
== Литература ==
# ''Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д.'' Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
# ''Айвазян С. А., Бухштабер В. М., Енюков И. С., Мешалкин Л. Д.'' Прикладная статистика: классификация и снижение размерности. — М.: Финансы и статистика, 1989.
 +
# ''Вапник В. Н., Червоненкис А. Я.'' Теория распознавания образов. — М.: Наука, 1974.
# ''Вапник В. Н.'' Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
# ''Вапник В. Н.'' Восстановление зависимостей по эмпирическим данным. — М.: Наука, 1979.
# ''Дуда Р., Харт П.'' Распознавание образов и анализ сцен. — М.: Мир, 1976.
# ''Дуда Р., Харт П.'' Распознавание образов и анализ сцен. — М.: Мир, 1976.
Строка 115: Строка 97:
== Ссылки ==
== Ссылки ==
-
* [[:Участник:Vokov|Воронцов К.В.]] [http://www.ccas.ru/voron/teaching.html#ML Математические методы обучения по прецедентам]. МФТИ (2004), ВМиК МГУ (2007).
+
* [[Машинное обучение (курс лекций, К.В.Воронцов)]]
 +
[[Категория:Байесовская теория классификации]]
[[Категория:Машинное обучение]]
[[Категория:Машинное обучение]]
 +
[[Категория:Классификация]]
[[Категория:Энциклопедия анализа данных]]
[[Категория:Энциклопедия анализа данных]]

Текущая версия

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

Содержание

Введение

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

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

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

К числу байесовских методов классификации относятся:

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

Пусть 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.

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

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

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

Пусть для каждого класса 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.

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

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

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

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

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

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

Наивный байесовский классификатор (naїve Bayes) основан на той же формуле и дополнительном предположении, что объекты описываются независимыми признаками. Предположение о независимости существенно упрощает задачу, так как оценить n одномерных плотностей гораздо легче, чем одну n-мерную плотность. К сожалению, оно крайне редко выполняется на практике, отсюда и название метода. Наивный байесовский классификатор может быть как параметрическим, так и непараметрическим, в зависимости от того, каким методом восстанавливаются одномерные плотности.

Литература

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

Ссылки

Источник — «http://machinelearning.ru/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»
Личные инструменты