贝叶斯分类器

贝叶斯决策论

贝叶斯决策论（Bayesian decision theory）是基于概率进行分类决策的基本方法

在所有相关概率均已知的理想情况下，贝叶斯决策论假设：决策问题可以用概率来形式化描述

考虑如下多分类问题，假设有$N$个类别$c1,c_2,…,c_N$
令$\lambda{ij}$表示将一个真实类别为$c_j$的样本分类为$c_i$所产生的损失
那么我们可以基于后验概率$P(c_i|x)$来定义将样本$x$分类为$c_i$产生的期望损失

$$R(c_i|x)=\sum_{j=1}^N\lambda_{ij}P(c_j|x)$$

其中$R(c_i|x)$称为条件风险

我们的目标是寻找一个分类器$h: X\rightarrow Y$以最小化总体风险

$$R(h)=E_x[R(h(x)|x)]$$

显然，若分类器$h$能最小化条件风险$R(h(x)|x)$，则总体风险也将最小化

由此即产生了如下贝叶斯判定准则：为最小化总体风险，只需选择使得条件风险$R(c|x)$最小化的类别标签$c$

$$h^*(x)=\text{argmin}_{c\in Y}R(c|x)$$

此时$h^$称为贝叶斯最优分类器，其对应的最小化的总体风险$R(h^)$称为贝叶斯风险

特别的，若$\lambda_{i,j}$满足如下条件，称分类器为最小错误率贝叶斯，此时条件风险为$R(c|x)=1-P(c|x)$

$$\lambda_{i,j}=\begin{cases}0, &i=j \\ 1, &i\neq j\end{cases}$$

显然条件风险中的后验概率可以通过贝叶斯公式得到

$$P(c|x)=\frac{P(x|c)P(c)}{P(x)}$$

其中$P(c)$称为类先验概率，$P(x|c)$称为类条件概率或似然，$P(x)$称为证据因子

显然$P(x)$是与$c$无关的常量，实际中常常忽略，即有

$$P(c|x) \propto P(x|c)P(c)$$

贝叶斯决策论假设$P(c),P(x|c)$均已知，因此可以很容易的计算条件风险并根据贝叶斯判定准则做出决策

朴素贝叶斯分类

注意上述贝叶斯决策理论的一个重要前提是所有相关概率均已知

然而实际中概率往往未知，且要根据给定数据集$D$计算类条件概率$P(x|c)$并不那么简单
因为多维样本的样本空间大小往往远大于数据集大小，即无法用频率来估计概率

针对这个问题，朴素贝叶斯分类器假设所有属性相互独立，即每个属性独立地对分类结果产生影响

基于该假设，类条件概率$P(x|c)$可表示为

$$P(x|c)=\prod_{i=1}^d P(x_i|c)$$

若$xi$为离散属性，则有$P(x_i|c)=\frac{|D{c,x_i}|}{|D_c|}$，即可以通过频率估计概率

若$xi$为连续属性，可以假定其服从某一概率分布，例如：
假设$P(x_i|c)\sim N(\mu{c,i},\sigma^2{c,i})$，其中$\mu{c,i},\sigma^2_{c,i}$分别为第$c$类样本在第$i$个属性上的均值和方差，则有

$$P(x_i|c)=\frac{1}{\sqrt{2\pi}\sigma_{c,i}}\exp\left(-\frac{(x_i-\mu_{c,i})^2}{2\sigma^2_{c,i}}\right)$$

显然，要计算连续属性$x_i$的类条件概率$P(x_i|c)$必须要获得概率分布的参数

该问题即参数估计问题，其中包括极大似然估计、贝叶斯估计等许多具体方法，此处不展开说明
具体可以看 极大似然估计和贝叶斯估计 和 非参数估计—Parzen窗法与近邻法

拉普拉斯修正

上述朴素贝叶斯中连续乘法的存在可能导致$P(x|c)$趋于零，此外某个$P(x_i|c)$趋于零也会导致该情况

针对这个问题，我们可以使用拉普拉斯修正（Laplacian correction）对估计概率值进行平滑

$$\hat{P}(c)=\frac{|D_c|+1}{|D|+N}\\ \hat{P}(x_i|c)=\frac{|D_{c,x_i}|+1}{|D_c|+N_i}$$

其中$N$为类别数，$N_i$为第$i$个属性（离散属性）可能的取值数

半朴素贝叶斯分类

朴素贝叶斯假设各个属性具有独立性，然而现实中这个条件往往难以满足

半朴素贝叶斯的基本思想是考虑一部分属性间的相互依赖信息
其中独依赖估计（One-Dependent Estimator，ODE）是常用的一种具体策略

独依赖估计假设每个属性仅依赖其他一个属性，即

$$P(x|c)=\prod_{i=1}^dP(x_i|c,pa_i)$$

其中$pa_i$为属性$x_i$依赖的属性，称为$x_i$的父属性

若$pa_i$已知，当$x_i,pa_i$为离散属性时，可以用类似拉普拉斯修正的方法来计算$P(x_i|c,pa_i)$
当$x_i,pa_i$为连续属性时，则可以用参数估计的方法

因此问题的关键在于如何确定每个属性的父属性

SPODE

最简单的父属性选择方法是所有属性都依赖同一个属性，该方法称为SPODE (Super-Parent ODE)

其中被依赖的属性称为超父 (supe-parent) ，supe-parent可通过交叉验证等模型选择方法来确定

树增强朴素贝叶斯TAN

树增强朴素贝叶斯TAN (Tree Augmented naive Bayes) 基于最大生成树获得依赖关系，其步骤如下

1. 计算任意两个属性间的条件互信息

   $$I(x_i,x_j|y)=\sum_{c\in Y} P(x_i,x_j|c)\log \frac{P(x_i,x_j|c)}{P(x_i|c)P(x_j|c)}$$

2. 以属性为节点构建无向完全图，边权为这两个属性的条件互信息

3. 构造该完全图的最大生成树，任意指定一个根将生成树转换为有根树，就确定了各个属性的父属性

平均独依赖估计AODE

平均独依赖估计 (Averaged One-Dependent Estimator) 是一种基于集成学习的独依赖估计，其表达式如下

$$P(x|c)=\sum_{i=1, D_{x_i}\geq m'}^d P(c,x_i)\prod_{j=1}^d P(x_j|c,x_i)$$

其中$D_{x_i}$为第$i$个属性上取值为$x_i$的样本集合，常数$m’$为设定的阈值

通俗的说，AODE的思路是将有足够训练数据支撑的SPODE集成起来作为结果