1. 随机森林
1.1 定义
RF是一个用随机方式建立的，包含多个决策树的集成分类器，其输出类别由各个树投票而定(回归树取平均)。
1.2 生成过程
假设样本总数为n，特征数为a。
1. 从原始样本中采用有放回抽样(bagging)的方法选取n个抽样。
2. 对n个样本选取a个特征中的随机k个，用于建立决策树的方法，获得最佳分割点。
3. 重复m次，获得m棵决策树。
4. 对输入样例进行预测时，每个子树都产生一个结果，采用多数投票机制输出。
1.3 优点
1. 实现简单，训练速度快，泛化能力强，可并行实现。（因为训练时树与树之间是相互独立的）。
2. 相比单一决策树，能学习到特征之间的相互影响，且不易过拟合。
3. 能处理高维数据，并且不用做特征选择，因为特征子集是随机选取的。
4. 对于不平衡的数据集，可以平衡误差。
5. 相比SVM，不是很怕特征缺失(待选特征也是随机选取的)。
6. 训练完后可以给出哪些特征比较重要。
1.4 缺点
1. 在噪音过大的分类和回归问题，还是容易过拟合。
2. 相比单一决策树，它的随机性让我们难以对模型进行解释。
2. 梯度提升树GBDT
2.1 定义
是以决策树(回归树)为基学习器的迭代算法。一般boosting算法都是一个迭代过程，每一次的训练都是为了改进上一次的结果。
核心：每一棵树学习的是之前所有树结论和的残差。
2.2 优点
1. 适用面广，离散|连续的数据都可以处理；
2. 几乎可用于所有回归问题(线性|非线形)；
3. 亦可用于二分类(设置阈值)；
4. 在相对较少的调参时间下，预测的准确度较高。
2.3 缺点
1. 由于弱分类器的串行依赖，难以并行训练数据。
2.4 GBDT与RF的区别
bagging与boosting都来源于Booststrap思想(有放回抽样)。
| ????????????????????? RF | ????????????????????? GBDT | ||
| 1 | 基于思想 | bagging | boosting |
| 2 | 采样方式 | 有放回的均匀取样 | 根据错误率取样(分类精度比较高) |
| 3 | 训练集选择 | 随机的，各训练集之间相互独立 | 其选择与前一轮结果有关 |
| 4 | 训练方式 | 弱分类器可并行 | 串行 |
| 5 | 组成 | 回归树|分类树 | 回归树(分类树的结果无法累加) |
| 6 | 输出结果 | 多数投票 | 将所有结果累加或加权累加 |
| 7 | 异常值 | 不敏感 | 非常敏感 |
| 8 | 提高性能方法 | 减少模型方差 | 减少模型偏差 |
| 9 | 对训练集一视同仁 | 由基于权值的弱分类器集成 | |
| 10 |
3. XGBoost
3.1 定义
XGB是大规模、分布式的通用梯度提升(GBDT)库，它在GB框架下实现了GBDT和一些广义线性ML算法。
3.2 特点
1. 还支持线性分类器
GBDT以回归树作为基学习器；
XGB还支持线性分类器，此时XGB相当于带有L1和L2正则化的LR(分类)或线性回归。
2. 对损失函数进行二阶泰勒展开
GBDT优化时只用到一阶导数信息；而XGB优化时同时用到一阶、二阶导数信息。
XGB还支持自定义的代价函数，但次代价函数需要一阶、二阶可导。
3. XGB在代价函数中加入了正则项，用于控制模型复杂度
正则项中包含了树的叶子结点个数、每个叶子结点上输出的score的L2模的平方和。
从平衡方差、偏差角度来看，降低了方差，使学习出来的模型更加简单，防止过拟合。
这是XGB优于GBDT的一个特性。
4. XGB的权重衰减(eta shrinkage)????? <=>
XGB在进行完一次迭代后，会将叶子结点的权重*该系数，主要是为了削弱每棵树的影响，让后面的树有更大的学习空间(给后面的树提供空间优化模型)。
一般把eta设置越小，迭代次数越多。
5. XGB支持列抽样
借鉴了RF的做法，支持列抽样，不仅能降低过拟合，还能减少计算。
对缺失值处理(对特征有缺失的样本，可自动学习出它的分裂方向)。
列抽样防止过拟合的效果比行抽样还好，也有利于后面的并行化处理算法。
这也是XGB优于GBDT的一个特性。
6. 支持并行
不是树粒度的并行，（XGB也是一次迭代完才进行下一次迭代的，第t次迭代的代价函数里面包含了前面t-1次迭代的预测值），而是特征粒度上的。
DT学习最耗时的一个步骤就是对特征值进行排序(确定最佳分割点)，xgb在训练前预先对数据进行了排序，并保存为block结构，之后的迭代中重复使用之，大大减少了计算量。
在进行结点的分裂时，需要计算每个特征的增益，最终选择增益最大的那个特征去做分裂，这样，各个特征增益的计算就可以多线程进行。
7. 内置交叉验证
接着已有模型学习，高灵活性、高速缓存压缩感知算法。
8. 切分点查找算法
1. 贪心算法获取最优切分点；
2. 近似算法；
3. 分布式加权直方图算法。