【机器学习】14. 集成学习 ensemble: bagging, boosting, 随机森林 random forest

1. Ensemble 整体认知

• 一个ensemble结合了多个分类器的预测
• 跟其他分类器组合在一起的分类器称为base classifier（单个分类器），它们是使用训练数据创建的。
• 有多种方法可以对新例子进行预测，例如，多数投票，即加权投票。等
• ensemble往往比base classifier工作得更好

案例：三个base classifier在训练集上面训练：KNN, Logistic Regression, Decision Tree。在预测新样本的时候，每个独立的预测器被结合起来，采取多数投票的结果

总而言之，ensemble 将多个分类器组合，得到更好的预测。

2. 使用Ensemble的原因

举个例子，一个由25个二分类的分类器组成的Ensemble，每个分类器的错误率是0.35，由此会有两个情况。

1. 情况1：所有分类器做了相同的判断，得到同样错误的结果，最终错误率依旧是0.35
2. 情况2： 所有分类器之间是相互独立的，它们的错误没有相关性。那么最终错误率由下面的公式计算得到
   $$e_{ensemble}=\sum _{i=13}^{25}\left(\genfrac{}{}{0ex}{}{25}{i}\right){ϵ}^i(1-ϵ{)}^{25-i}=0.06$$
   注意：
   $$\left(\genfrac{}{}{0ex}{}{25}{i}\right)=\frac{25!}{i!\ast (25-i)!}$$
   从结果来看，错误率大幅度降低。
   

当e > 0.5时，集成比基本分类器差
独立性：当基分类器有轻微的相关性时，集成方法取得了很好的效果。

3. 构建Ensemble 的方法

1. 操作训练数据——根据一些采样分布对原始数据进行重新采样，创建多个训练集，并为每个训练集构建一个分类器（例如Bagging和Boosting）。
2. 操纵特征-使用输入特征的子集（例如随机森林和Random subspace）
3. 操纵标签-(例如Error-correcting output coding: 比如A,B,C三类，变成AB,AC,BC这样)
4. 操纵学习算法（模型参数）

4. Bagging（bootstrap aggregation）

1. 每次采用有放回的抽样从训练集中取出n个样本组成新的训练集
2. 利用新的训练集, 训练得到M个子模型（也有M个boostrap samples）
3. 对于分类问题, 得票最多的分类为最终的类别; 对于回归问题,平均值作为预测值

特点

1. 通常会比单一分类器的效果更好。
2. 特别是对于不稳定分类器

不稳定分类器是指很小的变化在训练集会导致大的变化在最终预测上。比如决策树和神经网络都是不稳定分类器(unstable classifiers)

5. Boosting

主要思想：

1. 让分类器相互比冲
2. 下一个分类器需要使用不一样的样本进行训练。（AdaBoost是不同权重）

AdaBoost

• 使用权重训练集
• 每个训练样本都有关联的权重w(>=0)
• 更高的权重，代表在之前的分类器中，这个样本更难被分类
• 更高权重的样本会有更大的机会被选择在下一个分类器中。

整体算法思路

1. 有N个样本， 标签y属于（+1，1）

2. 初始化所有样本的权重w = 1/N

3. 对于从1到t的分类器

   • 训练一个比较弱的训练器，计算ϵ (误差)
     $${ϵ}_t=\sum _n{w}_t(n)I[y_n\ne h_t(x_n)]$$
     I是indicator function
     $$I[a=b]=1(a=b)or0(a\ne b)$$
   • 计算每个分类器的贡献
     $${\beta }_t=\frac{1}{2}log\frac{1-{ϵ}_t}{{ϵ}_t}$$
   • 更新权重
     $$w_{t+1}(n)=w_t(n)e^{-{\beta }_t{y}_n{h}_t(x_n)}$$

   Yn是（-1，+1） ht(是预测值)，如果预测错误则二者乘积为-1，正确则乘积为1. 所以预测错误会增加权重。

   并且normalize让所有权重和为1

4. 最终的输出是
   $$h[x]=sign[\sum _{t=1}^T{\beta }_t{h}_t(x)]$$
   

6. 比较

1. 相似之处

• 使用投票（用于分类）和平均（用于预测）来合并分类器的输出
• 结合相同类型的分类器，典型的树-例如决策树

2. 差异

• 创建分类器：
  • 装袋-单独
  • 鼓励—迭代—鼓励新的分类器成为专家
• 组合法
• 装袋-所有基础学习者的重量相等
• 提升(AdaBoost) -基于训练集性能的不同给予权重

7. 随机森林

• 性能取决于单个树的准确性和树之间的相关性
• 使用Bagging和随机特征选择来产生多样性，减少树之间的相关性
• 随着特征数量k的增加，强度和相关性都在增加
• 随机森林的表现通常优于单个决策树
• 有抵抗过拟合的能力
• 由于只考虑了特征的一个子集，所以速度很快。