【算法】朴素贝叶斯分类

朴素贝叶斯

朴素贝叶斯分类算法是基于两种假设的一种分类算法：

每一个特征同样重要
每一个特征之间相互独立

贝叶斯定理

$P(B|A) = \frac{P(A|B)P(B)}{P(A)}$
证明：
条件概率公式
<center>
$P(A|B) = \frac{P(AB)}{P(B)} ...式(1)$
</center>
同理
<center>
$P(B|A) = \frac{P(AB)}{P(A)} ...式(2)$
</center>
联立可以得到
<center>
$P(B|A) = \frac{P(A|B)P(B)}{P(A)}$
</center>

贝叶斯策略理论

设 $P1(x)$ 表达 $x$ 属于类别一的概率， $P2(x)$ 表达 $x$ 属于类别二的概率：

若 $P1(x) >P2(x)$ ，那么属于类别一
若 $P1(x) <P2(x)$ ，那么属于类别二

但是贝叶斯决策论真正进行比较的是 $P(c_1|x)$ 和 $P(c_2|x)$ ；通过贝叶斯定理我们可以得到计算该条件概率的方法因此

若 $P(c_1|x)>P(c_2|x)$ ，那么属于类别 $c_1$
若 $P(c_1|x)<P(c_2|x)$ ，那么属于类别 $c_2$

贝叶斯分类流程

基于之前的理论我们正式定义一下朴素贝叶斯分类的流程：
设：

$x=\{a_1,a_2,...a_m\}$ 为一个待分类项， $a_i$ 为其特征属性，一共有 $m$ 个
$C=\{y_1,y_2,...,y_n\}$ 表示类别的集合
计算 $P(y_1|x),P(y_2|x),...,P(y_n|x)$
若 $P(y_k|x)=max\{P(y_1|x),P(y_2|x),...,P(y_n|x)\}$ ,则 $x \in y_k$

贝叶斯分类的关键在于求出 $P(y_1|x),P(y_2|x),...,P(y_n|x)$ ，这也是朴树贝叶斯算法的训练过程。
我们分别计算：
<center>
$P(a_1|y_1),P(a_2|y_1),...,P(a_m|y_1)$
$P(a_1|y_2),P(a_2|y_2),...,P(a_m|y_2)$
$...$
$P(a_1|y_n),P(a_2|y_n),...,P(a_m|y_n)$
</center>
基于贝叶斯定理我们可以得到
$P(y_i|x)=\frac{P(x|y_i)P(y_i)}{P(x)}$
分母对于所有类别来说可以看成一个常数，因此我们只需考虑分子，基于先前的假设，所有特征独立可以得到
$P(x|y_i)=P(a_1|y_i)P(a_2|y_i)...P(a_m|y_i)=\Pi_{j=1}^mP(a_j|y_i)$
合并可以得到：
$P(x|y_i)P(y_i)=P(y_i)\Pi_{j=1}^mP(a_j|y_i)$

数据处理

若属性的取值为离散值我们很容易计算，就直接统计出训练样本中各个属性在每个样本中出现的频率就可以计算出 $P(a|y)$ 。如果属性的取值为一个连续值的时候我们就要对其进行处理。
假定其值满足高斯分布:
$p(x_i|y_j)=\frac{1}{\sqrt{2\pi}\sigma_{i,j}}e^{-\frac{(x-\mu_{i,j})^2}{2\sigma_{i,j}^2}}$
这样我们只用计算出训练样本中类别 $y_i$ 中特征 $a_j$ 的均值和标准差，带入上式即可。
在实践中我们常通过取对数的方式来将连乘转化为连加，以避免数值的下溢。
需要注意的是若某个属性值在训练集中没有与某个类同时出现过，则计算出来的概率值为0,则会将其他属性携带的信息给抹去，因此我们需要用到“拉普拉斯修正”，来进行平滑。
设 $N$ 表示训练集 $D$ 中可能的类别数， $N_i$ 表示第 $i$ 个属性可能的取值数
$P(c)=\frac{|D_c|+1}{|D|+N}$
$P(x_i|c) =\frac{|D_{c,x_i}|+1}{|D_c|+N_i}$