本文为本人另两篇博客机器学习/计算机视觉(cv)实习面试资料整理（附字节、阿里、腾讯、美团面经）、机器学习知识点整理以及集成树知识点概括下的子内容，有需要的朋友按需自取~
另：本文只是知识点的整理概括，更为详细的可以参考我每个部分给出的链接~
目录
- 概述
- 原理
- 预排序算法的优缺点
- 缺失值的处理
- 离散值的处理
- 重要参数
- 树停止生长条件
- 剪枝
- 并行化
- 防止过拟合
- 正则项
- 用于特征选择时，如何评价特征重要性
- 选择最佳分裂点
- XGBoost和GBDT的不同点
详细介绍参考深入理解XGBoost、XGBoost 重要参数(调参使用)和[校招-基础算法]GBDT/XGBoost常见问题
概述
- XGBoost是基于GBDT的一种算法或者说工程实现；
- GBDT是一种基于boosting集成思想的加法模型，训练时采用前向分布算法进行贪婪的学习，每次迭代都学习一棵CART树来拟合之前 t-1 棵树的预测结果与训练样本真实值的残差；
- XGBoost的基本思想和GBDT相同，但是做了一些优化，如默认的缺失值处理，加入了二阶导数信息、正则项、列抽样，并且可以并行计算等
原理
- 首先，对所有特征都按照特征的数值进行预排序；
- 其次，在遍历分割点的时候用O(#data)的代价找到一个特征上的最好分割点；
- 最后，找到一个特征的分割点后，将数据分裂成左右子节点；
预排序算法的优缺点
- 优点：能精确地找到分割点；
- 缺点：
1）首先，空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（例如排序后的索引，为了后续快速的计算分割点），这里需要消耗训练数据两倍的内存；
2）其次，时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大；
3）最后，对 cache 优化不友好。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对 cache 进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的 cache miss；
缺失值的处理
- 在xgboost里，在每个结点上都会将对应变量是缺失值的数据往左右分支各导流一次，然后计算两种导流方案对Objective的影响，最后认为对Objective降低更明显的方向（左或者右）就是缺失数据应该流向的方向，在预测时在这个结点上将同样变量有缺失值的数据都导向训练出来的方向；
- 例如，某个结点上的判断条件是 A>0 ，有些数据是A<=0，有些是A>0，有些数据的A是缺失值。那么算法首先忽略带缺失值的数据，像正常情况下一样将前两种数据分别计算并导流到左子树与右子树，然后：
1）将带缺失值的数据导向左子树，计算出这时候模型的Objective_L；
2）接着将带缺失值的数据导向右子树，计算出这时候模型的Objective_R；
3）最后比较Objective_L和Objective_R； - 假设Objective_L更小，那么在预测时所有变量A是缺失值的数据在这个结点上都会被导向左边，当作A<=0处理；
离散值的处理
- 在Xgb中需要将离散特征one-hot编码，和连续特征一起输入训练，这样做是为了达到在cart树中处理离散特征的方式一致，即每次选择一个离散特征对应的样本作为一类，剩下的所有特征值对应的样本作为一类。不按照扫描切分，因为扫描切分会导致后续的子树中特征组合变少；
- 对于类别有序的类别型变量，比如 age 等，当成数值型变量处理可以的。对于非类别有序的类别型变量，推荐 one-hot。但是 one-hot 会增加内存开销以及训练时间开销；类别型变量在范围较小时（tqchen 给出的是[10,100]范围内）推荐使用；
- 无序特征：one-hot encoding，比如城市；
- 有序特征：label encoding，比如版本号；
重要参数
树停止生长条件
- 当树达到最大深度时，停止建树，因为树的深度太深容易出现过拟合，这里需要设置一个超参数max_depth；
- 当新引入的一次分裂所带来的增益Gain<0时，放弃当前的分裂。这是训练损失和模型结构复杂度的博弈过程；
- 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值，也会放弃此次分裂。这涉及到一个超参数：最小样本权重和，是指如果一个叶子节点包含的样本数量太少也会放弃分裂，防止树分的太细；
剪枝
- 在目标函数中增加了正则项：使用叶子结点的数目和叶子结点权重的L2模的平方，控制树的复杂度；
- 在结点分裂时，定义了一个阈值，如果分裂后目标函数的增益小于该阈值，则不分裂；
- 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值（最小样本权重和），也会放弃此次分裂；
- XGBoost 先从顶到底建立树直到最大深度，再从底到顶反向检查是否有不满足分裂条件的结点，进行剪枝；
并行化
- 由于XGBoost是一种boosting算法，树的训练是串行的，不能并行；
- 这里的并行指的是特征维度的并行；
- 在训练之前，每个特征按特征值对样本进行预排序，并存储为Block结构，在后面查找特征分割点时可以重复使用，而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算；
防止过拟合
- 在目标函数中添加了正则化：叶子节点个数+叶子节点权重的L2正则化；
- 列抽样：训练时只使用一部分的特征；
- 子采样：每轮计算可以不使用全部样本，类似bagging；
- early stopping：如果经过固定的迭代次数后，并没有在验证集上改善性能，停止训练过程；
- shrinkage：调小学习率增加树的数量，为了给后面的训练留出更多的空间。
- 调参：
1）控制模型的复杂度：包括max_depth,min_child_weight,gamma 等参数；
2）增加随机性，从而使得模型在训练时对于噪音不敏感：包括subsample,colsample_bytree；
3）减小learning rate，但需要同时增加estimator 参数；
正则项
- 叶子节点个数和叶子节点权重的L2正则；
用于特征选择时，如何评价特征重要性
XGBoost中有三个参数可以用于评估特征重要性：
- weight ：该特征在所有树中被用作分割样本的总次数；
- gain ：该特征在其出现过的所有树中产生的平均增益；
- cover ：该特征在其出现过的所有树中的平均覆盖范围。覆盖范围这里指的是一个特征用作分割点后，其影响的样本数量，即有多少样本经过该特征分割到两个子节点；
选择最佳分裂点
- XGBoost在训练前预先将特征按照特征值进行了排序，并存储为block结构，以后在结点分裂时可以重复使用该结构；
- 因此，可以采用特征并行的方法利用多个线程分别计算每个特征的最佳分割点，根据每次分裂后产生的增益，最终选择增益最大的那个特征的特征值作为最佳分裂点。如果在计算每个特征的最佳分割点时，对每个样本都进行遍历，计算复杂度会很大，这种全局扫描的方法并不适用大数据的场景；
- XGBoost还提供了一种直方图近似算法，对特征排序后仅选择常数个候选分裂位置作为候选分裂点，极大提升了结点分裂时的计算效率；
XGBoost和GBDT的不同点
- GBDT是机器学习算法，XGBoost是该算法的工程实现；
- 在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力；
- GBDT在模型训练时只是用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。（好处：相对于GBDT的一阶泰勒展开，XGBoost采用二阶泰勒展开，可以更为精准的逼近真实的损失函数。需要注意的是，损失函数需要二阶可导。）
- 传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器；
- 传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行列采样；
- 传统的GBDT没有涉及对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略；
- 特征维度上的并行化。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度；
本人关于树的其他文章：