贝叶斯分类器

贝叶斯决策论

贝叶斯决策论（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} λ_{i j} P (c_{j} | x)

其中 $R (c_{i} | x)$ 称为条件风险

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

R (h) = E_{x} [R (h (x) | x)]

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

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

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

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

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

λ_{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 π} σ_{c, i}} \exp (- \frac{(x_{i} - μ_{c, i})^{2}}{2 σ_{c, i}^{2}})

显然，要计算连续属性 $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}^{d} P (x_{i} | c, p a_{i})

其中 $p a_{i}$ 为属性 $x_{i}$ 依赖的属性，称为 $x_{i}$ 的父属性

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

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

SPODE

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

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

树增强朴素贝叶斯TAN

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

计算任意两个属性间的条件互信息
$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)}$
以属性为节点构建无向完全图，边权为这两个属性的条件互信息
构造该完全图的最大生成树，任意指定一个根将生成树转换为有根树，就确定了各个属性的父属性

平均独依赖估计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集成起来作为结果