一、组合方法
（1）组合分类器原理：
考虑25个二元分类器，每一个分类误差a=0.35。组合分类器通过多数投票，如果基分类器是独立的，则仅当超过一半的基分类器都预测错误时，组合才会错误，则：
$$ e_{ensemble}=\sum_{i=1}^{25}C_{25}^{i}a^{i}(1-a)^{25-i}=0.06$$
可以看出，其远低于0.35。
（2）组合分类器与基分类器比较：
上图，虚线表示所有基分类器都一样，实线表示所有基分类器都独立。可以看出，当基分类器的错误率大于0.5（仅这个例子吗？）时候，组合分类器的性能不比基分类器的性能好。
组合分类器的性能优于基分类器的条件：
1、基分类器应该是独立的。
2、基分类器应当好于随机猜想。
（3）袋装（bagging）-自助法（bootstrap aggregating）
袋装-自助法（bootstrap）：
训练集是对于原数据集的有放回抽样，如果原始数据集N，可以证明，大小为N的自助样本大约包含原数据63.2%的记录。当N充分大的时候，1-（1-1/N）^(N) 概率逼近 1-e^(-1)=0.632。抽样 b 次，产生 b 个bootstrap样本，则，总准确率为（accs为包含所有样本计算的准确率）：
$$ acc_{boot}=\frac{1}{b}\sum_{i=1}^{b}(0.632\times\varepsilon _{i}+0.368\times acc_{s})$$
袋装算法：
|
|
袋装举例理解：
下面的这个数据集，使用决策树，熵值来分裂，可以得到分裂点为：x<=0.35 或 x<=0.75，但是无论是哪个分类点，准确率都最多为70%。
使用袋装抽样：
使用简单的求和，取符号，可以发现，分类正确率为100%：
袋装评价：
1、通过降低基分类器的方差改善了泛化误差
2、袋装的性能依赖于基分类器的稳定性。如果基分类器是不稳定的，袋装有助于降低训练数据的随机波动导致的误差；如果基分类器是稳定的，则组合分类器的误差主要由基分类器的偏倚引起，则这种情况下，袋装可能会降低分类器的性能。
3、袋装中的数据是均概率被选中，所以对特定数据不敏感，对于噪音，不太受过拟合影响。
（4）提升（Boosting）
提升是一个迭代过程，自适应的改变样本的分布，使得基分类器聚焦在那些很难分类的样本上，提升每次给一个训练样本一个权值，在每一轮结束的时候自动地调整权值。
现在又很多提升算法，算法的差别在于：
（1）每轮提升结束时如何更新训练样本权值
（2）如何组合每个分类器的预测
AdaBoost
在该算法中，基分类器 Ci 的重要性依赖于它的错误率，错误率的定义：
$$ error_{i}=\frac{1}{N}\left[\sum_{j=1}^{N}w_{j}I(C_{i}(x_{j}\neq y_{j}))\right]$$
对于I，为指示变量，错误个数的加权取平均，基分类器的重要度 \alpha 为：
$$ \alpha_{i}=\frac{1}{2}ln\left(\frac{1-error_{i}}{error_{i}}\right)$$
作出重要度 \alpha 关于 error 的图：
发现错误率接近 0 时候，重要度很大，接近 1 时候，重要度负向很大。
Adaboost 的权值更新有以下给出，第 j 次迭代：
Zj 是一个正规因子，用于确保：
$$\sum_{i}w_{i}^{j+1}=1$$
AdaBoost算法：
AdaBoost例子：
1、该组合分类器的训练误差呈指数递减，从而算法很快就会收敛。
2、但是它倾向于那些被误分类的样本，所以提升技术很容易受到过拟合的影响。
二、随机森林（Random Forest）
随机森林的过程图：
已经从理论上证明了，当树的数目足够大的时候，随机森林的泛化误差的上界收敛于下面表达式：
随机森林性质
每棵决策树都使用一个从固定概率分布产生的随机向量。可以使用多种方法将随机向量合并到树中。
不同的随机森立方法：
1、Forest-RI。随机选择 F 个输入特征来对决策树的结点进行分裂，树之后完全增长不进行任何修剪，这有助于减少树的偏倚。之后用多数投票表决来组合预测。为了增加随机性，可以使用自助样本。
2、Forest-RC。d 的数目太小的情况，需要增大特征空间，创建输入特征的线性组合。输入特征用区间[-1,1]的均匀分布产生的系数进行线性组合。
3、对于每个结点，从 F 个最佳划分中随机选择一个，该方法也是比上面两个更花费时间。
4、随机森林的分裂准确率与Adaboost相媲美，但它对噪声更加鲁棒，运行速度也比Adaboost快得多。
随机森林的一些参数选择
通常选取特征数目为：
$$ F=log_{2}^{d}+1$$
d 为输入特征数。
