基于树的集成学习算法

决策树

决策树是一个用于监督学习的非参数模型 ,即参数的个数不固定.
决策树的参数: 每次分裂的特征及阈值.
分裂的原则: 分裂后两个分支的样本越纯净越好.
令节点的样本集合为 ,选择特征,分裂阈值为,即候选分裂,将样本分裂为成左右两个分支和

• 对于回归问题, 集合 的不纯净性为集合中样本的y值的差异,常用L2损失,其中为集合中样本的y的均值,即表示分裂后划分为同一分支的y值越接近越纯净
• 对于分类问题,集合 的不纯净性跟集合中样本种类数及每类样本的比例相关,分裂后种类越单一就越纯净,常用不纯净度量有(,即集合中每类样本的比例 )
  • 错分率 :
  • 熵:
  • Gini系数:

树模型的优点:

1. 容易解释
2. 不要求对特征做预处理
3. 能处理离散值和连续值混合的输入
4. 对特征的单调变换不敏感(只与数据的排序有关)
5. 能自动进行特征选择
6. 可处理缺失数据
7. 可扩展到大数据规模

树模型的缺点:

1. 正确率不高：建树过程过于贪心

– 可作为Boosting的弱学习器（深度不太深）

1. 模型不稳定（方差大）：输入数据小的变化会带 来树结构的变化

– Bagging：随机森林可降低

1. 当特征数目相对样本数目太多时，容易过拟合

随机森林(RandomForest)

对给定有N个样本的数据集进行Bootstrap采样(有放回的重采样)，得到 ， 在 上训练模型的时候，在节点上所有的样本特征中随机采用一部分样本特征.
将上面的过程重复B次,得到B个弱学习器,如果是分类预测，则 B 个弱学习器投票最多的类别作为最终结果；若是回归预测，则使用B个弱学习器的算术平均作为最终模型的输出结果即.
RF的优点：

1. 弱分类器之间没有关联，训练可以高度并行化，大样本训练速度有优势。
2. 由于采用了随机采样，训练出的模型的方差小，泛化能力强。

RF的缺点：

1. 降低了可解释性
2. 取值划分比较多的特征容易对RF的决策产生更大的影响，从而影响拟合的模型的效果。

   AdaBoost

   没有先验知识的情况下，初始的分布为等概分布，即训练集如果 有N个样本，每个样本的分布概率为1/N
   每次循环后提高误分样本的分布概率，误分样本在训练集中所占 权重增大，使得下一次循环的弱学习器能够集中力量对这些误分 样本进行判断
   准确率越高的弱学习机权重越高
   AdaBoostM1算法 伪代码:
   训练集上样本的初始分布：
   对 m= 1 : M
   对训练样本采用权重计算弱分类器
   计算该弱分类器在分布上的误差:
   计算该弱分类器的权重:
   更新训练样本的分布 其中是个归一化常数
   最后的强分类器为:

对进行迭代展开

即样本i在下轮的弱学习器m+1的权重为,样本i在本轮学习器m的权重 乘以 样本i在前m个弱学习器上指数损失 与 所有样本在前m个弱学习器上指数损失之和 的比值
第m个弱学习器的指数损失为 ,求能让损失最小的权重

两边同时乘以
又因为 所以 错误率小的弱分类器的权重更大
Adaboost的主要优点有：

1. Adaboost作为分类器时，分类精度很高
2. 在Adaboost的框架下，可以使用各种回归分类模型来构建弱学习器，非常灵活。
3. 作为简单的二元分类器时，构造简单，结果可理解。
4. 不容易发生过拟合

Adaboost的主要缺点有：

1. 对异常样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。

前向逐步递增

前向逐步递增 这个角度来看待AdaBoost
目标函数:
前项逐步递增:
初始化:

指数损失对离群点比较敏感，而且也不是任何二值变量y 的概率密度取log后的表示。 所以可以将损失函数取负log似然损失，得到 logitBoost. 对回归问题，损失函数可取L2损失，用弱学习器来预测残差,得到L2boosting

其中
通常对系数增加一个小的收缩因子(或称为学习率)， 测试性能更好
其中,较小的收缩因子通常意味着更多弱分学习器

Gradient Boosting

目标:, 其中为参数
在第m步,
梯度为:
更新: ,其中,
其中为步长
上述算法只在N个数据点优化F ,将其修改为用一个能最小化下式的弱学习器来近似负梯度，即
即
损失函数取L2,得到L2Boosting,同样适用于Logistic损失 、Huber损失等等

总结

Bagging和Boosting的区别：
样本选择：

• Bagging：训练集是在原始集中有放回选取的，从原始集中选出的各轮训练集之间是独立的。
• Boosting：每一轮的训练集不变，只是训练集中每个样例在分类器中的权重发生变化。而权值是根据上一轮的分类结果进行调整。

样例权重：

• Bagging：使用均匀取样，每个样例的权重相等
• Boosting：根据错误率不断调整样例的权值，错误率越大则权重越大。

预测函数：

• Bagging：所有预测函数的权重相等。
• Boosting：每个弱分类器都有相应的权重，对于分类误差小的分类器会有更大的权重。

并行计算：

• Bagging：各个预测函数可以并行生成
• Boosting：各个预测函数只能顺序生成，因为后一个模型参数需要前一轮模型的结果。

参考链接:https://murphypei.github.io/blog/2019/03/bootstrap-bagging-boost