简述决策树原理？

决策树是一种自上而下，对样本数据进行树形分类的过程，由节点和有向边组成。节点分为内部节点和叶节点，其中每个内部节点表示一个特征或属性，叶节点表示类别。从顶部节点开始，所有样本聚在一起，经过根节点的划分，样本被分到不同的子节点中，再根据子节点的特征进一步划分，直至所有样本都被归到某个类别。

为什么要对决策树进行减枝？如何进行减枝？

剪枝是决策树解决过拟合问题的方法。在决策树学习过程中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，于是可能将训练样本学得太好，以至于把训练集自身的一些特点当作所有数据共有的一般特点而导致测试集预测效果不好，出现了过拟合现象。因此，可以通过剪枝来去掉一些分支来降低过拟合的风险。

决策树剪枝的基本策略有“预剪枝”和“后剪枝”。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

预剪枝使得决策树的很多分支都没有"展开”，这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。但另一方面，有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降?但在其基础上进行的后续划分却有可能导致性能显著提高；预剪枝基于"贪心"本质禁止这些分支展开，给预剪枝决策树带来了欠拟含的风险。

后剪枝决策树通常比预剪枝决策树保留了更多的分支，一般情形下后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树 。但后剪枝过程是在生成完全决策树之后进行的 并且要白底向上对树中的所有非叶结点进行逐 考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

简述决策树的生成策略？

决策树主要有ID3、C4.5、CART，算法的适用略有不同，但它们有个总原则，即在选择特征、向下分裂、树生成中，它们都是为了让信息更“纯”。

举一个简单例子，通过三个特征：是否有喉结、身高、体重，判断人群中的男女，是否有喉结把人群分为两部分，一边全是男性、一边全是女性，达到理想结果，纯度最高。 通过身高或体重，人群会有男有女。 上述三种算法，信息增益、增益率、基尼系数对“纯”的不同解读。如下详细阐述：

img

img

img

​ 综上，ID3采用信息增益作为划分依据，会倾向于取值较多的特征，因为信息增益反映的是给定条件以后不确定性减少的程度，特征取值越多就意味着不确定性更高。C4.5对ID3进行优化，通过引入信息增益率，对特征取值较多的属性进行惩罚。

随机森林

Bagging（套袋法）

bagging的算法过程如下：

  1. 从原始样本集中使用Bootstraping方法随机抽取n个训练样本，共进行k轮抽取，得到k个训练集。（k个训练集之间相互独立，元素可以有重复）
  2. 对于k个训练集，我们训练k个模型（这k个模型可以根据具体问题而定，比如决策树，knn等）
  3. 对于分类问题：由投票表决产生分类结果；对于回归问题：由k个模型预测结果的均值作为最后预测结果。（所有模型的重要性相同）

Boosting（提升法）

boosting的算法过程如下：

  1. 对于训练集中的每个样本建立权值wi，表示对每个样本的关注度。当某个样本被误分类的概率很高时，需要加大对该样本的权值。
  2. 进行迭代的过程中，每一步迭代都是一个弱分类器。我们需要用某种策略将其组合，作为最终模型。（例如AdaBoost给每个弱分类器一个权值，将其线性组合最为最终分类器。误差越小的弱分类器，权值越大）
    • 提升就是指每一步我都产生一个弱预测模型，然后加权累加到总模型中，然后每一步弱预测模型生成的的依据都是损失函数的负梯度方向，这样若干步以后就可以达到逼近损失函数局部最小值的目标。

Bagging，Boosting的主要区别

  1. 样本选择上：Bagging采用的是Bootstrap随机有放回抽样；而Boosting每一轮的训练集是不变的，改变的只是每一个样本的权重。

    • 每轮训练过后如何调整样本权重 [公式] ？

    • 如何确定最后各学习器的权重 [公式]

      这两个问题可由加法模型和指数损失函数推导出来。

  2. 样本权重：Bagging使用的是均匀取样，每个样本权重相等；Boosting根据错误率调整样本权重，错误率越大的样本权重越大。

  3. 预测函数：Bagging所有的预测函数的权重相等；Boosting中误差越小的预测函数其权重越大。

  4. 并行计算：Bagging各个预测函数可以并行生成；Boosting各个预测函数必须按顺序迭代生成。

下面是将决策树与这些算法框架进行结合所得到的新的算法：

1）Bagging + 决策树 = 随机森林

2）AdaBoost + 决策树 = 提升树 （自适应提升（AdaBoost））

3）Gradient Boosting + 决策树 = GBDT

  • 梯度下降提升树（GDBT）

  • 首先既然是树，那么它的基函数肯定就是决策树啦，而损失函数则是根据我们具体的问题去分析，但方法都一样，最终都走上了梯度下降的老路，比如说进行到第m步的时候，首先计算残差

    img

    有了残差之后，我们再用（xi,rim）去拟合第m个基函数，假设这棵树把输入空间划分成j个空间R1m，R2m……，Rjm，假设它在每个空间上的输出为bjm，这样的话，第m棵树可以表示如下：

    img

    下一步，对树的每个区域分别用线性搜索的方式寻找最佳步长，这个步长可以和上面的区域预测值bjm进行合并，最后就得到了第m步的目标函数

    img

    当然了，对于GDBT比较容易出现过拟合的情况，所以有必要增加一点正则项，比如叶节点的数目或叶节点预测值的平方和，进而限制模型复杂度的过度提升，这里在下面的实践中的参数设置我们可以继续讨论。

构造随机森林的 4 个步骤：

  1. 假如有N个样本，则有放回的随机选择N个样本(每次随机选择一个样本，然后返回继续选择)。这选择好了的N个样本用来训练一个决策树，作为决策树根节点处的样本。

  2. 当每个样本有M个属性时，在决策树的每个节点需要分裂时，随机从这M个属性中选取出m个属性，满足条件m « M。然后从这m个属性中采用某种策略（比如说信息增益）来选择1个属性作为该节点的分裂属性。

  3. 策树形成过程中每个节点都要按照步骤2来分裂（很容易理解，如果下一次该节点选出来的那一个属性是刚刚其父节点分裂时用过的属性，则该节点已经达到了叶子节点，无须继续分裂了）。一直到不能够再分裂为止。注意整个决策树形成过程中没有进行剪枝。

  4. 按照步骤1~3建立大量的决策树，这样就构成了随机森林了。

随机森林的优缺点

优点

  1. 它可以出来很高维度（特征很多）的数据，并且不用降维，无需做特征选择
  2. 它可以判断特征的重要程度
  3. 可以判断出不同特征之间的相互影响
  4. 不容易过拟合
  5. 训练速度比较快，容易做成并行方法
  6. 实现起来比较简单
  7. 对于不平衡的数据集来说，它可以平衡误差。
  8. 如果有很大一部分的特征遗失，仍可以维持准确度。

缺点

  1. 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟合。
  2. 对于有不同取值的属性的数据，取值划分较多的属性会对随机森林产生更大的影响，所以随机森林在这种数据上产出的属性权值是不可信的