朴素贝叶斯

分类

---

主要思想

朴素贝叶斯分类器是一系列以假设特征之间强（朴素）独立下运用贝叶斯定理为基础的简单概率分类器。

产生背景

朴素贝叶斯自20世纪50年代已广泛研究。在20世纪60年代初就以另外一个名称引入到文本信息检索界中。

应用场景

• 文本分类问题
  
  • 垃圾邮件分类

损失函数

01损失，期望风险最小？？

主要推导

对于事件A，B贝叶斯公式

$$p(A|B) = {{P(A)P(B|A)} \over {P(B)}}$$

对于输入$X$和输出$Y$

$$P(Y＝c_k|X = x) = {{P(Y = c_k)P(X = x|Y=c_k)} \over {P(X=x)}}$$

由于X是多维特征（M维），朴素贝叶斯假设特征间相互独立

$$P(X = x|Y = {c_k}) = \prod\limits_{i = 1}^M {P({X^i} = {x^i}|Y = {c_k})}$$

因为$P(X=x)$在计算各个分类时相等，所以不用计算。

朴素贝叶斯最后学习到的是联合概率$P(X,Y)$，所以是生成式模型。

最后朴素贝叶斯求解的问题是

$$y=g(x) = \arg \mathop {\max }\limits_{{c_k}} {\rm{P}}({\rm{Y = }}{{\rm{c}}_k})\prod\limits_{i = 1}^M {P({X^i} = {x^i}|Y = {c_k})}$$

求解算法

通过使用样本结合极大似然估计求解

其中先验概率${\rm{P}}({\rm{Y = }}{{\rm{c}}_k})$的极大似然估计估计如下

$${\rm{P}}({\rm{Y = }}{{\rm{c}}_k}) = {{\sum\limits_{j = 1}^N {I({y_j}{\rm{ = }}{{\rm{c}}_k})} } \over N}$$

设第$i$个特征的取值集合为$\{ a_{i1}^{},a_{i2}^{}...a_{i{S_i}}^{}\}$。

$$P({X^i} = a_{il}^{}|Y = {c_k}) = {{\sum\limits_{j = 1}^N {I(x_j^i = a_{il}^{},{y_j} = {c_k})} } \over {\sum\limits_{j = 1}^N {I({y_j} = {c_k})} }}$$

使用贝叶斯估计可以处理概率为零的情况($\lambda = 1$,拉普拉斯平滑)

伪代码

输入:数据集D(N个样本)
训练过程:
通过数据集D学习求解算法中的两个参数
预测过程:
使用贝叶斯公式计算分类概率，选择有最大概率的分类
输出:分类结果

复杂度分析

训练时间复杂度：计算求解过程中的两个公式

结合第一个公式计算所有类别概率复杂度为O(NK)

结合第二个公式计算为O(KNSM) 每个特征的S不同，但这里为简单起见写为S，且使用相应算法应该可以使复杂度降低。

大数据适配

见Map-Reduce for Machine Learning on Multicore.

评价

• 优点

  • 对小规模的数据表现很好，适合多分类任务，适合增量式训练。
• 缺点
  
  • 属性强独立性假设

算法改进

• 特征不独立，贝叶斯网络？？

相关算法

• BPL字符识别和生成

参考资料

1. wiki

2. 机器学习常见算法个人总结