Байесовская классификация
Вероятностная постановка задачи классификации
Пусть $X$ множество объектов, $Y$ конечное множество имён классов, множество $X \times Y$ является вероятностным пространством с плотностью распределения $p(x,y)=P(y)p(x|y)$. Вероятности появления объектов каждого из классов $P_y=P(y)$ называются априорными вероятностями классов. Плотности распределения $p_y(x)=p(x|y)$ называются функциями правдоподобия классов.
Вероятностная постановка задачи классификации разделяется на две независимые подзадачи:
- Имеется простая выборка $X^l=(x_i, y_i)^l_{i=1}$ из неизвестного распределения $p(x,y)=P_yp_y(x)$. Требуется построить эмпирические оценки априорных вероятностей $P'_y$ и функций правдоподобия $p'_y(x)$ для каждого из классов $y \in Y$.
- По известным плотностям распределения $p_y(x)$ и априорным вероятностям $P_y$ всех классов $y \in Y$ построить алгоритм $a(x)$, минимизирующий вероятность ошибочной классификации.
Априорные вероятности классов $P_y$ можно оценить согласно закону больших чисел, тогда частота появления объектов каждого из классов равна $P'_y=\frac{l_y}{l}$ где $l_y=|X^l_y|, y \in Y$ сходится по вероятности к $P_y$ при $l_y \to \infty$. Чем больше длина выборки, тем точнее выборочная оценка $P'_y$.
Оптимальный байесовский классификатор
Рассмотрим произвольный алгоритм $a:X \to Y$. Он разбивает множество $X$ на не пересекающиеся области $A_y=\{x \in X | a(x) = y\}, y \in Y$. Вероятность того,что появится объект класса $y$ и алгоритм $a$ отнесёт его к классу $s$, равна $P_yP(A_s|y)$. Каждой паре $(y,s) \in Y \times Y$ поставим в соответствие величину потери $\lambda_{ys}$ при отнесении объекта класса $y$ к классу $s$.
| Определение: |
| Функционал среднего риска — ожидаемая величина потери при классификации объектов алгоритмом $a$:
|
| Теорема (об оптимальности байесовского классификатора): |
Если известны априорные вероятности $P_y$ и функции правдоподобия $p_y(x)$,
то минимум среднего риска $R(a)$ достигается алгоритмом |
| Доказательство: |
|
Для произвольного $t \in Y$ запишем функционал среднего риска: Применив формулу полной вероятности, $P(A_t \mid y) = 1 −\displaystyle\sum_{ s \in Y \setminus \{t\} }P(A_s \mid y)$, получим: Введём для сокращения записи обозначение $g_s(x) = \displaystyle\sum_{y \in Y}\lambda_{ys}P_yp_y(x)$, тогда $R(a) = const(a) + \displaystyle\sum_{ s \in Y \setminus \{t\} }\int_{A_s}(g_s(x)−g_t(x))dx$. Минимум интегрла достигается, когда $A_s$ совпадает с областью неположительности подынтегрального выражения. С другой стороны, $A_s=\{x \in X \mid a(x) = s\}$. Значит, $a(x) = s$ тогда и только тогда, когда
|
Наивный байесовский классификатор
Допустим, что объекты $x \in X$ описываются $n$ числовыми признаками $f_j:X→R,j= 1,...,n$. Обозначим через $x = (\xi_1,...,\xi_n)$ произвольный элемент пространства объектов $X=R^n$, где $\xi_j=f_j(x)$.
Предположим, что признаки $f_1(x),...,f_n(x)$ являются независимыми случайными величинами. Следовательно, функции правдоподобия классов представимы в виде:
где $p_{yj}(\xi_j)$ плотность распределения значений $j$-го признака для класса $y$. Алгоритмы классификации исходящие из этого предположения, называются наивными байесовскими.
Подставим эмпирические оценки одномерных плотностей в байесовский классификатор. Получим алгоритм:
Основные его преимущества — простота реализации и низкие вычислительные затраты при обучении и классификации. В тех редких случаях, когда признаки почти независимы, наивный байесовский классификатор близок к оптимальному. Достаточно малое количество данных необходимо для обучения, оценки параметров и классификации.
Основной его недостаток — низкое качество классификации в общем случае.
Применение
Из-за своего низкого качества классификации наивный байесовскими классификатор в основном он используется либо как эталон при экспериментальном сравнении алгоритмов, либо как элементарный строительный блок в алгоритмических композициях.
Рассмотрим частое применение байесовского классификатора к задаче классификации документов по их содержимому, а именно к классификации электронных писем на два класса — спам ($S$) и не-спам ($\displaystyle \neg S$), предполагая что вероятность слов в тексте не зависит друг от друга:
Программные спам-фильтры, построенные на принципах наивного байесовского классификатора, делают «наивное» предположение о том, что события, соответствующие наличию того или иного слова в электронном письме или сообщении, являются независимыми по отношению друг к другу. Это упрощение в общем случае является неверным для естественных языков:
Исходя из такого предположения, для решения задачи классификации сообщений лишь на 2 класса: $S$ (спам) и $H = \neg S$ («хэм», то есть не спам) из теоремы Байеса можно вывести следующую формулу оценки вероятности «спамовости» всего сообщения $D$, содержащего слова $W_1, W_2, ... W_N$:
- [так как $W_i$ предполагаются независимыми]
Результат $p$ обычно сравнивают с некоторым порогом (например, $0.5$), чтобы решить, является ли сообщение спамом или нет. Если $p$ ниже, чем порог, сообщение рассматривают как вероятный «ham», иначе его рассматривают как вероятный спам.
- .
Пример кода scikit-learn
Классификатор GaussianNB реализует наивный байесовский классификатор в предположении что изначальное распределение было гауссовым:
from sklearn import datasets
from sklearn.metrics import f1_score, accuracy_score
from sklearn.naive_bayes import GaussianNB
iris = datasets.load_iris()
gnb = GaussianNB()
pred = gnb.fit(iris.data, iris.target).predict(iris.data)
accuracy = accuracy_score(iris.target, pred)
f1 = f1_score(iris.target, pred, average="micro")
print("accruracy:", accuracy, "f1:", f1)
Вывод:
accruracy: 0.96 f1: 0.96
