ID3

ID3是用信息增益作为分割的准则，信息增益=信息熵-条件熵： 其中$\frac{|C_k|}{D}$表示第k类样本的数据占数据集D样本总数的比例。

假设每个记录有一个属性“ID”，若按照ID来进行分割的话，由于ID是唯一的，因此在这一个属性上，能够取得的特征值等于样本的数目，也就是说ID的特征值很多。那么无论以哪个ID为划分，叶子结点的值只会有一个，纯度很大，得到的信息增益会很大，但这样划分出来的决策树是没意义的。由此可见，ID3决策树偏向于取值较多的属性进行分割，存在一定的偏好，所以搞了ID4.5作为优化

ID4.5

信息增益比率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的属性。 上式，分子计算与ID3一样，分母是由属性A的特征值个数决定的，个数越多，IV值越大，信息增益率越小，这样就可以避免模型偏好特征值多的属性，但是聪明的人一看就会发现，如果简单的按照这个规则来分割，模型又会偏向特征数少的特征。因此C4.5决策树先从候选划分属性中找出信息增益高于平均水平的属性，在从中选择增益率最高的。

CART

CART是一棵二叉树，采用二元切分法，每次把数据切成两份，分别进入左子树、右子树。而且每个非叶子节点都有两个孩子，所以CART的叶子节点比非叶子多1。相比ID3和C4.5，CART应用要多一些，既可以用于分类也可以用于回归。CART分类时，使用基尼指数（Gini）来选择最好的数据分割的特征，gini描述的是纯度，与信息熵的含义相似。CART中每一次迭代都会降低GINI系数。

$$\begin{gathered} Gini(D)=1-\sum _{i=0}^n(\frac{|C_i|}{|D|}{)}^2 \\ Gini(D|A)=\sum _{i=0}^n\frac{|D_i|}{|D|}Gini(D_i) \end{gathered}$$ Ci表示D中Category的数量 Di表示以A是属性值划分成n个分支里第i个分支的数目 Gini(D)反映了数据集D的纯度，值越小，纯度越高。我们在候选集合中选择使得划分后基尼指数最小的属性作为最优化分属性。

决策树剪枝

典型的剪枝有两种：

预剪枝：例如树高到一定程度，停止树的生长；样本数量小于一定数值，停止树的生长等等后剪枝：典型的方法有代价剪枝（Cost Complexity Prune，CCP），就是把决策树所有的子树都列出来，拿去挨个剪，剪了以后看误差增加率，误差增加率不高的子树就剪掉

Bagging

Bagging是Bootstrap Aggregate的简称，意思就是再抽样，即每一次从原始数据中根据均匀概率分布有放回的抽取和原始数据大小相同的样本集合，样本点可能出现重复，然后对每一次产生的训练集构造一个分类器，再对分类器进行组合。

Bagging是减小方差的优化。假设有n个完全独立的模型，每个方差为${\sigma }^2$，也就是说$Var(X_i)={\sigma }^2$，那么 $$Var(\frac{1}{n}\sum _{i=1}^n{X}_i)=\frac{1}{n^2}Var(\sum _{i=1}^n{X}_i)=\frac{{\sigma }^2}{n}$$ 但是Bagging的过程中有放回，假设单模型的相关系数是p，那么 $$Var(\frac{1}{n}\sum _{i=1}^n{X}_i)=p{\sigma }^2+(1-p)\frac{{\sigma }^2}{n}$$,随着n增大，最终趋向于$\frac{p}{n}{\sigma }^2$，因此Bagging会是减小方差的优化

Boosting

提升是减少偏差的优化。在训练好一个弱分类器后，我们需要计算弱分类器的错误或者残差，作为下一个分类器的输入。这个过程本身就是在不断减小损失函数，来使模型不断逼近“靶心”，使得模型偏差不断降低。

GBDT

GBDT是以决策树（CART）为基学习器的GB算法，是迭代树，而不是分类树。Boost是"提升"的意思，一般Boosting算法都是一个迭代的过程，每一次新的训练都是为了改进上一次的结果 GBDT的核心就在于：每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学习。

XGBoost

XGBoost对目标函数和数值计算做了大量优化的工作，假设现在有t-1棵树，那么第t棵树就是拟合现在的残差，让残差达到最小。用$F_{t-1}(x_i)$表示现有的t-1棵树的最优解，用$f_t(x_i)$表示当前这棵树，用l(x,y)表示两个结果之间的残差，那么残差的函数$L_t$表示成

$$\begin{gathered} L_t=\sum _{i}l(y_i,F_t(x_i))+\Omega (f_t) \\ {L}_t=\sum _{i}l(y_i,F_{t-1}(x_i)+f_t(x_i))+\Omega (f_t) \end{gathered}$$ 现在$f_t(x_i)$函数在l函数里面，用泰勒展开把$f_t(x_i)$甩在l函数外面，泰勒展开的公式是 $$f(x+\Delta x)\approx f(x)+\Delta x{f}^{{}^{\prime }}(x)+\frac{1}{2}\Delta x{f}^{{}^{\prime \prime }}(x)$$ 现在把$f_t(x_i)$看成泰勒展开公式里的 $\Delta x$，把整个l看成$f(x+\Delta x)$，那么可以得到 $$L_t=\sum _i(l[y_i,F_{t-1}(x_i)]+g_i{f}_t(x_i)+\frac{1}{2}{h}_i{f}_t^2(x_i))+\Omega (f_t)$$ 而${\sum }_i(l[y_i,F_{t-1}(x_i)])$其实已知了，目前是个const，$g_i$和$h_i$分别是一阶导和二阶导数。因此直接考虑l函数外面针对$f_t$这颗树的情况就可以了。假设$f_t$这棵树有T个叶子节点，每个叶子节点决定了一定数量的训练数据的归属。同时给正则项赋值为$\Omega (f_t)=\gamma T+\frac{1}{2}\lambda {\sum }_{j=1}^T{f}_t^2(x_i)$，其实就是加了二阶正则和一个常数，一会儿从最终的表达式可以看出为啥要加这两项，同时我们用$w_j$来代替$f_t(x_i)$，$w_j$表示第j个叶子节点上若干训练数据对应的预测值的和。所以现在的$L_t$是： $$L_t=\sum _{j=1}^T(G_j{w}_j+\frac{1}{2}(H_j+\lambda )w_j^2)+\gamma T$$ 注意这里的$G_j$就是某个叶子节点上所有训练样本的$g_i$的和，$H_j$就是某个叶子节点上所有训练样本的$h_i$的和，某个叶节点预测值的和$w_j$肯定正比于所有梯度的和，也是说这个叶子节点上的所有训练数据给一个同样的微分dx,整个叶子节点预测值的变化dy是和梯度和成正比的，所以直接求和就可以。 给$w_j$求偏导得到最优的$w_j^{\ast }$如下表达式： $$w_j^{\ast }=-\frac{G_j}{H_j+\lambda }$$ 把$w_j^{\ast }$代回到$L_t$，可以得到 $$L_t^{\ast }=-\frac{1}{2}\sum _{j=1}^T\frac{G_j^2}{H_j+\lambda }+\gamma T$$ 所以分裂前后的损失函数的差值是 $$Gain=\frac{G_L^2}{H_L+\lambda }+\frac{G_R^2}{H_R+\lambda }-\frac{(G_L+G_R{)}^2}{H_L+H_R+\lambda }-\gamma$$

XGBoost采用最大化这个差值作为准则来进行决策树的构建，因此GBDT和XGBoost的区别可以总结成几个方面：

GBDT是机器学习算法，XGBoost是该算法的一个具体实现XGBoost加入了正则项来控制模型复杂度，从而防止过拟合，提高模型的泛化能力XGBoost的代价函数用了二阶导数，GBDT只用了一阶导数传统GBDT用CART作为基分类器，XGBoost支持多种基分类器，例如线性分类器传统GBDT每轮迭代要用全部的数据，XGBoost只是采样传统GBDT没有设计对缺失值进行处理的策略，XGBoost能够有设计这方面的策略，具体为： -在某列特征上寻找分裂节点时，不会对缺失的样本进行遍历，只会对非缺失样本上的特征值进行遍历，这样减少了为稀疏离散特征寻找分裂节点的时间开销。 -另外，训练时为了保证完备性，对于含有缺失值的样本，会分别把它分配到左叶子节点和右叶子节点，然后再选择分裂后增益最大的那个方向，作为预测时特征值缺失样本的默认分支方向。 -如果训练集中没有缺失值，但是测试集中有，那么默认将缺失值划分到右叶子节点方向。特征维度上的并行化。XGBoost预先将每个特征按特征值排好序，存储为块结构，分裂结点时可以采用多线程并行查找每个特征的最佳分割点，极大提升训练速度。利用列块进行并行计算：在我们训练过程中我们主要是做分支处理，分支处理就要对每一列（特征）找出适合的分裂点。通常来说，我们更青睐使用csc存储，这样我们就方便取出来。再者我们在分支的时候都会预先对数据按照其特征值进行排序。所以我们将数据按照列存储成一个数据块方便我们在分支的时候并行处理。所以我们要知道XGB的并行计算的粒度不在树上，而是在特征上，尤其是不同分支节点上（leaf-wise）。当然这也成为XGB的一个问题所在，需要额外的空间存储pre-sort的数据。而且每次分支后，我们都要找处落在下一个子节点上的样本，并组织好它。后来就有了LightGBM，下次我再将其整理出来。

XGBoost算法防止过拟合的方法有哪些？

在目标函数中添加了正则化。叶子节点个数+叶子节点权重的L2正则化。 列抽样。训练时只使用一部分的特征。子采样。每轮计算可以不使用全部样本，类似bagging。early stopping。如果经过固定的迭代次数后，并没有在验证集上改善性能，停止训练过程。shrinkage。调小学习率增加树的数量，为了给后面的训练留出更多的空间。

XGBoost中的一棵树的停止生长条件

当树达到最大深度时，停止建树，因为树的深度太深容易出现过拟合，这里需要设置一个超参数max_depth。当新引入的一次分裂所带来的增益Gain<0时，放弃当前的分裂。这是训练损失和模型结构复杂度的博弈过程。当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值，也会放弃此次分裂。这涉及到一个超参数:最小样本权重和，是指如果一个叶子节点包含的样本数量太少也会放弃分裂，防止树分的太细。

XGBoost如何选择最佳分裂点？

XGBoost在训练前预先将特征按照特征值进行了排序，并存储为block结构，以后在结点分裂时可以重复使用该结构。

因此，可以采用特征并行的方法利用多个线程分别计算每个特征的最佳分割点，根据每次分裂后产生的增益，最终选择增益最大的那个特征的特征值作为最佳分裂点。如果在计算每个特征的最佳分割点时，对每个样本都进行遍历，计算复杂度会很大，这种全局扫描的方法并不适用大数据的场景。XGBoost还提供了一种直方图近似算法，对特征排序后仅选择常数个候选分裂位置作为候选分裂点，极大提升了结点分裂时的计算效率。

XGBoost可以做特征选择，它是如何评价特征重要性的？

特征重要性可以用来做模型可解释性，这在风控等领域是非常重要的方面。xgboost实现中Booster类get_score方法输出特征重要性，其中importance_type参数支持三种特征重要性的计算方法：

importance_type=weight（默认值），特征重要性使用特征在所有树中作为划分属性的次数。importance_type=gain，特征重要性使用特征在作为划分属性时loss平均的降低量。importance_type=cover，特征重要性使用特征在作为划分属性时对样本的覆盖度。

总结过程中参考了以下书和博客，对一些内容作了展开，在此表示感谢：

https://zhuanlan.zhihu.com/p/34534004葫芦书https://zhuanlan.zhihu.com/p/81368182知乎文章https://www.zhihu.com/question/63728763/answer/355319175知乎文章https://zhuanlan.zhihu.com/p/36794802