决策树出现过拟合的原因及解决办法

原因：

在决策树构建的过程中，对决策树的生长没有进行合理的限制（剪枝）；

样本中有一些噪声数据，没有对噪声数据进行有效的剔除；

解决办法

选择合理的参数进行剪枝，可以分为预剪枝和后剪枝，我们一般采用后剪枝的方法；

利用K-folds交叉验证，将训练集分为K份，然后进行K次交叉验证，每次使用K-1份作为训练样本数据集，另外一份作为测试集；

减少特征，计算每一个特征和响应变量的相关性，常见得为皮尔逊相关系数，将相关性较小的变量剔除；当然还有一些其他的方法来进行特征筛选，比如基于决策树的特征筛选，通过正则化的方式来进行特征选取等（决策的正则化，例如，L1和L2正则，具体是对谁的正则呢？怎样正则的呢？）。

4.如何对决策树进行剪枝？

剪枝是防止决策树过拟合的方法。一棵完全生长的决策树很可能失去泛化能力，因此需要剪枝。

1）剪枝的策略

剪枝分为预剪枝和后剪枝两种，预剪枝是在构建决策树时抑制它的生长，后剪枝是决策树生长完全后再对叶子节点进行修剪。

2）预剪枝

设置一个树的最大高度/深度或者为树设置一个最大节点数，达到这个值即停止生长

对每个叶子节点的样本数设置最小值，生长时叶子节点样本数不能小于这个值

判断每次生长对系统性能是否有增益

方法 3 里，对于一个决策树，每次生长前，可以判断生长后系统在验证集上准确度是否提升，如果经过一次生长，系统在验证集上的准确度降低了，那么中止这次生长。

3）后剪枝

后剪枝方法是对一棵已经完全生长的决策树进行剪枝

错误率降低剪枝（Reduced-Error Pruning）

悲观剪枝（Pessimistic Error Pruning）

代价复杂度剪枝（Cost-Complexity Pruning）

我们重点介绍第一种。错误率降低剪枝的方法比较直观，从下至上遍历所有非叶子节点的子树，每次把子树剪枝（所有数据归到该节点，将数据中最多的类设为结果），与之前的树在验证集上的准确率进行比较，如果有提高，则剪枝，否则不剪，直到所有非叶子节点被遍历完。

4）预剪枝和后剪枝的优缺点比较

时间成本方面，预剪枝在训练过程中即进行剪枝，后剪枝要在决策树完全生长后自底向上逐一考察。显然，后剪枝训练时间更长。预剪枝更适合解决大规模问题。

剪枝的效果上，预剪枝的常用方法本质上是基于贪心的思想，但贪心法却可能导致欠拟合，后剪枝的欠拟合风险很小，泛化性能更高。

另外，预剪枝的有些方法使用了阈值，如何设置一个合理的阈值也是一项挑战。

决策树的优缺点

决策树的优缺点

优点

决策树可以可视化，易于理解和解释；

数据准备工作很少。其他很多算法通常都需要数据规范化，需要创建虚拟变量并删除空值等；

能够同时处理数值和分类数据，既可以做回归又可以做分类。其他技术通常专门用于分析仅具有一种变量类型的数据集；

效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度；能够处理多输出问题，即含有多个标签的问题，注意与一个标签中含有多种标签分类的问题区别开；

是一个白盒模型，结果很容易能够被解释。如果在模型中可以观察到给定的情况，则可以通过布尔逻辑轻松解释条件。相反，在黑盒模型中（例如，在人工神经网络中），结果可能更难以解释。

缺点

递归生成树的方法很容易出现过拟合。

决策树可能是不稳定的，因为即使非常小的变异，可能会产生一颗完全不同的树；

如果某些分类占优势，决策树将会创建一棵有偏差的树。因此，建议在拟合决策树之前平衡数据集。

xgboost相比传统gbdt有何不同？

传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。

xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。

Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）

列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。

对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。

xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

GBDT采用的是数值优化的思维, 用的最速下降法去求解Loss Function的最优解, 其中用CART决策树去拟合负梯度, 用牛顿法求步长.

XGboost用的解析的思维, 对Loss Function展开到二阶近似, 求得解析解, 用解析解作为Gain来建立决策树, 使得Loss Function最优.

LightGBM主要改进点

1、单边梯度抽样算法

GBDT 算法的梯度大小可以反应样本的权重，梯度越小说明模型拟合的越好，单边梯度抽样算法（Gradient-based One-Side Sampling, GOSS）利用这一信息对样本进行抽样，减少了大量梯度小的样本，在接下来的计算锅中只需关注梯度高的样本，极大的减少了计算量。

GOSS 算法保留了梯度大的样本，并对梯度小的样本进行随机抽样，为了不改变样本的数据分布，在计算增益时为梯度小的样本引入一个常数进行平衡。具体算法如下所示：

我们可以看到 GOSS 事先基于梯度的绝对值对样本进行排序（无需保存排序后结果），然后拿到前 a% 的梯度大的样本，和总体样本的 b%，在计算增益时，通过乘上 （1-a）/b 来放大梯度小的样本的权重。一方面算法将更多的注意力放在训练不足的样本上，另一方面通过乘上权重来防止采样对原始数据分布造成太大的影响。

1. Histogram算法： 直方图算法的基本思想是先把连续的浮点特征值离散化成k个整数（其实又是分桶的思想，而这些桶称为bin，比如[0,0.1)→0, [0.1,0.3)→1），同时构造一个宽度为k的直方图。

在遍历数据的时候，根据离散化后的值作为索引在直方图中累积统计量，当遍历一次数据后，直方图累积了需要的统计量，然后根据直方图的离散值，遍历寻找最优的分割点

带深度限制的Leaf-wise的叶子生长策略 在XGBoost中，树是按层生长的，称为Level-wise tree growth，同一层的所有节点都做分裂，最后剪枝，如下图所示：

Level-wise过一次数据可以同时分裂同一层的叶子，容易进行多线程优化，也好控制模型复杂度，不容易过拟合。但实际上Level-wise是一种低效的算法，因为它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

直方图差加速

在树中，一个叶子的直方图可以由它的父亲节点的直方图与它兄弟的直方图做差得到。利用这个方法，LightGBM可以在构造一个叶子的直方图后，可以用非常微小的代价得到它兄弟叶子的直方图，在速度上可以提升一倍。

优点：

1）速度较快，是XGBoost速度的16倍，内存占用率为XGBoost的1/6

2）采用了直方图算法，将连续的浮点型特征值离散化成K个整数

3）使用带有深度限制的leaf-wise的叶子生长策略。

缺点：

1）可能会长出比较深的决策树，产生过拟合。因此LightGBM在Leaf-wise之上增加了一个最大深度限制，在保证高效率的同时防止过拟合

2）基于偏差的算法，会对噪点较为敏感

3）在寻找最优解时，依据的最优切分变量，没有将最优解是全部特征的综合这一理念来考虑。

SGD全称Stochastic Gradient Descent，随机梯度下降，1847年提出。每次选择一个mini-batch，而不是全部样本，使用梯度下降来更新模型参数。它解决了随机小批量样本的问题，但仍然有自适应学习率、容易卡在梯度较小点等问题。

catboost主要改进点

对分类型特征的处理。这使得我们在训练模型之前可以考虑不用再通过特征工程去处理分类型特征

预测偏移处理。这可以减少模型的过拟合，提升模型预测效果

CatBoost算法用的基模型是对称树，也是决策树的一种，对称树的优点是训练速度快，不太容易过拟合，关于对称树的原理说明可参考这篇博客的介绍(你可能不知道的对称树和GBM模型的快速预测 - 云+社区 - 腾讯云)。

在GBDT算法中，每一棵树都是为了拟合前一棵树上的梯度，构造树时所有的样本都参与了，一个样本参与了建树，然后又用这棵树去估计样本值，这样的估计就不是无偏估计，当测试集和训练集上的样本分布不一致时，模型就会因过拟合而性能不佳，即在测试集上产生了预测偏移

常见的激活函数

关于激活函数，首先要搞清楚的问题是，激活函数是什么，有什么用？不用激活函数可不可以？答案是不可以。激活函数的主要作用是提供网络的非线性建模能力。如果没有激活函数，那么该网络仅能够表达线性映射，此时即便有再多的隐藏层，其整个网络跟单层神经网络也是等价的。因此也可以认为，只有加入了激活函数之后，深度神经网络才具备了分层的非线性映射学习能力。 那么激活函数应该具有什么样的性质呢？

可微性： 当优化方法是基于梯度的时候，这个性质是必须的。

单调性： 当激活函数是单调的时候，单层网络能够保证是凸函数。

输出值的范围： 当激活函数输出值是有限的时候，基于梯度的优化方法会更加稳定，因为特征的表示受有限权值的影响更显著;当激活函数的输出是无限的时候，模型的训练会更加高效，不过在这种情况小，一般需要更小的learning rate

从目前来看，常见的激活函数多是分段线性和具有指数形状的非线性函数

Sigmoid函数：

sigmoid函数也叫Logistic函数，用于隐藏层的输出，输出在(0,1)之间，它可以将一个实数映射到(0,1)的范围内，可以用来做二分类。在特征相差比较复杂或是相差不是特别大的时候效果比较好。该函数将大的负数转换成0，将大的正数转换为1

优点：

Sigmoid的取值范围在(0, 1)，而且是单调递增，比较容易优化

Sigmoid求导比较容易，可以直接推导得出。

缺点：

Sigmoid函数收敛比较缓慢

由于Sigmoid是软饱和，容易产生梯度消失，对于深度网络训练不太适合（从图上sigmoid的导数可以看出当x趋于无穷大的时候，也会使导数趋于0）

Sigmoid函数并不是以（0,0）为中心点

Tanh激活函数

tanh为双切正切曲线，过（0,0）点。如图所示，可看作是Sigmoid函数向下平移和收缩的结果。

- 优点：

函数输出以（0,0）为中点

收敛速度相对于Sigmoid更快

- 缺点：

tanh并没有解决sigmoid梯度消失的问题

即在z很大或很小时，梯度几乎为零，因此使用梯度下降优化算法更新网络很慢。

Relu(修正线性单元)激活函数

很常用的激活函数，从表达式和图像可以明显地看出：Relu其实就是个取最大值的函数。

ReLU函数其实是分段线性函数，把所有的负值都变为0，而正值不变，这种操作被成为单侧抑制。

优点：

没有饱和区，不存在梯度消失问题；

没有复杂的指数运算，计算简单、效率提高；

实际收敛速度较快，比 Sigmoid/tanh 快很多；

比 Sigmoid 更符合生物学神经激活机制

缺点：

在训练过程中容易出现神经元失活，之后梯度永远为0的情况。比如一个特别大的梯度结果神经元之后，我们调整权重参数，就会造成这个ReLU神经元对后来来的输入永远都不会被激活，这个神经元的梯度永远都会是0，造成不可逆的死亡。举例：一个非常大的梯度流过一个 ReLU 神经元，更新过参数之后，这个神经元再也不会对任何数据有激活现象了。如果这个情况发生了，那么这个神经元的梯度就永远都会是0.实际操作中，如果你的learning rate 很大，那么很有可能你网络中的40%的神经元都”dead”了。 当然，如果你设置了一个合适的较小的learning rate，这个问题发生的情况其实也不会太频繁。

Softmax激活函数

Softmax 是用于多类分类问题的激活函数，在多类分类问题中，超过两个类标签则需要类成员关系。对于长度为 K 的任意实向量，Softmax 可以将其压缩为长度为 K，值在（0，1）范围内，并且向量中元素的总和为 1 的实向量

Softmax 激活函数的主要缺点是：

在零点不可微；

负输入的梯度为零，这意味着对于该区域的激活，权重不会在反向传播期间更新，因此会产生永不激活的死亡神经元。

讲讲常见的优化器

五大优化器其实分为两类，SGD、SGDM，和Adagrad、RMSProp、Adam。使用比较多的是SGDM和Adam。

如上所示，SGDM在CV里面应用较多，而Adam则基本横扫NLP、RL、GAN、语音合成等领域。所以我们基本按照所属领域来使用就好了。比如NLP领域，Transformer、BERT这些经典模型均使用的Adam，及其变种AdamW。

深度学习与传统机器学习的异同点

线性分类界面是啥样的

在数学上，线性函数关系是直线，而非线性函数关系是非直线，包括各种曲线、折线、不连续的线等；线性方程满足叠加原理，非线性方程不满足叠加原理；线性方程易于求出解析解，而非线性方程一般不能得出解析解