朴素贝叶斯法
朴素贝叶斯法(naive Bayes) 是基于 贝叶斯定理 与 特征条件独立假设 的分类方法. 朴素贝叶斯学习模型是一种生成模型. 朴素贝叶斯适用于多类分类.
朴素贝叶斯分类器
朴素贝叶斯分类器是基于贝叶斯定理: 已知 $p(x|y)$ 的情况下如何求得 $p(y|x)$, 其基本公式为:
$$ p(x, y) = p(x|y) \cdot p(y) = p(y|x) \cdot p(x) $$
$$ p(y|x) = \frac{p(x|y)*p(y)}{p(x)} $$
设输入空间 $\chi \subseteq R^n$, 样本 $x \in \chi$, 其中$x= \{ a_1, a_2, … , a_m \}$ , $a_i$ 为 $x$ 的一个特征属性. 输出空间为 $\lambda = \{ y_1, y_2, … , y_n \}$ . 对于一个样本 $x$ , 如果有
$$p(y_i|x) = \underset{p(y_i | x)}{\operatorname{argmax}} \{ p(y_1|x), p(y_2|x), …, p(y_i | x), … ,p(y_n|x) \} \tag{1} $$
则样本 $x$ 就可以归为 $y_i$ 类别. 关键问题是如何求得 $p(y_i|x)$. 根据贝叶斯定理可得:
$$p(y_i|x) = \frac{p(x|y_i)p(y_i)}{p(x)} \tag{2}$$
$p(x)$ 对所有的类都是常数, 则求 $p(y_i | x)$ 可以转化为求 $p(x|y_i)$ 和 $p(y_i)$ .
根据我们的假设: 特征条件独立. 所以有:
$$ p(x|y_i) = p(a_1|y_i) \cdot p(a_2|y_i) \cdot … \cdot p(a_m|y_i) = \underset{j=1}{\operatorname{\prod^{m}}}{p(a_j|y_i)} \tag{3} $$
结合公式 $(1)$ , $(2)$ 和 $(3)$, 我们可以得到朴素贝叶斯分类器的表达式:
$$y = \underset{y_i \in \lambda}{\operatorname{argmax}} {p(y_i) \underset{j=1}{\operatorname{\prod^{m}}}{p(a_j|y_i)} }$$
朴素贝叶斯分类器的算法流程如下:
Adaboost
AdaBoost是一种Boosting算法。Boosting算法是一种可将弱学习器提升为强学习器的算法。这中算的思想是：先从初始训练集训练出一个基学习器，再根据基学习器的表现来对训练样本分布进行调整，使得之前基学习器做错的训练样本在后续受到更多的关注，然后基于调整后的样本分布来训练下一个基学习器，如此重复进行.
Boosting和Bagging的区别在于前者的基学习器是串行的, 后一个基学习器依赖于前一个基学习器；而Bagging的基学习器是并行的(具体参见).
Boosting算法有以下几个关键点:
1)如何计算学习误差率 $\varepsilon$
2)如何得到基学习器的权重系数 $\alpha$
3)如何更新样本权重 $D_t$
4)得到所有的基学习器后采用哪种结合策略得到强学习器
Boosting算法要求基学习器对特定的数据分布进行学习, 可以通过”重赋权法”, 在训练的每一轮中, 根据样本分布为训练样本重新赋予一个权重. 一般机器学习算法面对带权重的训练样本时，处理方式往往是权重乘该样本损失形式.
$$\varepsilon = \sum{W_i \cdot L(x_i, y_i)}$$
如果无法接受带权样本的基学习器, 则可以采用”重采样方法”, 对训练集每次进行重采样(AdaBoost以朴素贝叶斯为基学习器的时候就可以采用”重采样”).
对于AdaBoost来说, 其:
学习误差率为 $\varepsilon_t = \underset{i=1}{\operatorname{\sum^{m}}}{W_t(x_i)I(h_t(x_i)) \neq \lambda_t(x_i))}$
基学习的权重系数为 $\alpha_t = \frac{1}{2} ln \frac{1-\varepsilon_t}{\varepsilon_t}$, 可知基学习器 $t$ 的误差越大, 权重系数越小
样本权重的更新为 $ \underset{t+1}{\operatorname{W}}{(\textbf{x})} = W_t(\textbf{x})exp^{(- \alpha_t \lambda_t(\textbf{x}) h_t(\textbf{x}) )}$
采用线性组合的方式得到强学习器
AdaBoost算法流程图(采用线性组合基学习的方式)
实验
数据集
数据集采用 german 和 breast 数据集进行实验(也可以从此处获取).
数据集的规模如下表:
| 数据集规模 | 特征个数 | 离散特征个数 | 连续特征个数 | 类别数 | |
|---|---|---|---|---|---|
| german | 1,000 | 24 | 12 | 12 | 2 |
| breast | 277 | 9 | 9 | 0 | 2 |
实验结果
首先实现Naive Bayes分类器, 然后将Naive Bayes分类器作为AdaBoost的基准分类器. 对german和breast两个数据集都做10折交叉验证, 并给出准确率、mean(准确率的平均值)和standard deviation(准确率的偏差).
实验时对于Adaboost的T取的是100, 重新抽取样本时，抽样本的90%;
| #mean# | german | breast |
|---|---|---|
| Naive Bayes | 0.6216 | 0.6121 |
| AdaBoost | 0.7240 | 0.7425 |
| #standard deviation# | german | breast |
|---|---|---|
| Naive Bayes | 0.1304 | 0.1087 |
| AdaBoost | 0.0413 | 0.0541 |
AdaBoost的偏差小于Naive Bayes，说明AdaBoost学习算法的拟合能力强于Naive Bayes。
代码这次是用Java实现的.
参考文献
[1] 周志华. 机器学习[M]. 北京:清华大学出版社, 2015. 229-235.
[2] Han J,Kamber M,Pei J. Data Mining:conceptions and techniques[J].2001.