1. 什么是决策树

   ​	决策树表示基于特征对实例进行分类的树形结构，从给定的训练数据集中，递归选择最优划分特征，依据此特征对训练数据集进行划分，直到结点符合停止条件。决策树可以看作是一系列 `if-then` 规则的集合。

2. 停止条件

   - 当前结点所有样本属于同一类别。
   - 当前结点属性集为空，或者是所有样本在所有属性上取值相同。
   - 当前结点无样本。

3. 决策树分类

   - ID3

     - 信息熵：

     $$
     Ent(D)=-\sum_{k=1}^{|y|}p_k\log{p_k}
     $$
     - 信息增益：

     $$
     Gain(D,a)=Ent(D)-\sum_{v=1}^{V}\frac{|D^v|}{|D|}Ent(D^v)
     $$
     其中，a为所选属性，V为所选属性的取值数量，$|D^v|$为子集$D^v$的样本数量。

     - ID3算法选择信息增益最大的属性进行划分。

     - 缺点：偏向于选择取值较多的属性，容易形成一棵浅而宽的树

   - C4.5

     - 信息增益比（信息增益率）：
       $$
       Gain_{ratio}(D,a)=\frac{Gain(D,a)}{H_a(D)}
       $$
       其中
       $$
       H_a(D)=-\sum_{v=1}^V\frac{|D^v|}{|D|}\log{\frac{|D^v|}{|D|}}
       $$
       为将属性a作为label时的经验熵。

     - 缺点：偏向于选择取值较少的属性，因此并不是直接选择信息增益率最大的特征，而是先在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

   - CART（分类树）

     - 基尼不纯度：
       $$
       Gini(D)=\sum_{y=1}^{|y|}p_k(1-p_k)=1-\sum_{y=1}^{|y|}p_k^2
       $$
       基尼不纯度为被错误分类的期望值，选择划分后基尼不纯度最小的属性来进行划分。

     - CART树为二叉树，每次对每个属性进行二元化分，对于离散属性只区分是不是等于该取值，对于连续属性则以是否大于该取值划分。

   - CART（回归树）
     - 输出y为连续变量，将输出划分为M个区域R<sub>1</sub>，R<sub>2</sub>,...,R<sub>M</sub>,各个区域的输出值分别为c<sub>1</sub>,c<sub>2</sub>,...,c<sub>M</sub>，求导易得当c<sub>i</sub>为各区域输出的平均值时误差最小。
     - 对每个属性的每个取值进行二元划分，取划分后误差最小的属性的取值进行划分。

4. 决策树为什么不需要归一化

   因为数值缩放不影响分裂点位置，对树模型的结构不造成影响。 按照特征值进行排序的，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。而且，树模型是不能进行梯度下降的，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的，因此树模型是阶跃的，阶跃点是不可导的，并且求导没意义，也就不需要归一化。

   既然树形结构（如决策树、RF）不需要归一化，那为何非树形结构比如AdaBoost、SVM、LR、KNN、KMeans之类则需要归一化。

   对于线性模型，特征值差别很大时，运用梯度下降的时候，损失等高线是椭圆形，需要进行多次迭代才能到达最优点。 但是如果进行了归一化，那么等高线就是圆形的，促使SGD往原点迭代，从而导致需要的迭代次数较少。

5. 决策树的剪枝
   - 预剪枝：其中的核心思想就是，在每一次实际对结点进行进一步划分之前，先采用某一种指标来判断划分是否能提高增益，如验证集的数据的准确性、信息增益是否大于最低标准、样本个数是否小于最低标准等，如果是，就把结点标记为叶结点并退出进一步划分，否则就继续递归生成结点。

   - 后剪枝：后剪枝则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来泛化性能提升（如验证集的准确率），则将该子树替换为叶结点。

     具体地，对于ID3和C4.5，可以使用如下损失函数来判断是否剪枝：
     $$
     C_\alpha(T)=\sum_{t=1}^{|T|}N_tH_t(T)+\alpha|T|
     \\H_t(T)=-\sum_{k}\frac{N_{tk}}{N_t}\log \frac{N_{tk}}{N_t}
     $$
     其中T为叶结点数量，$\alpha$控制经验风险与结构风险所占比例，越小树越复杂，过拟合风险越大。

     若将非叶子结点替换为叶子结点后损失函数降低，则将该子树替换为叶结点。
     
     对于CART树，剪枝算法由两步组成：
   
     1. 剪枝，形成一个子树序列
     2. 通过交叉验证选取最优子树
     
     上述第二步无需多言，关键在第一步。
     
     定义子树的损失函数为：
     $$
     C_\alpha(T)=C(T)+\alpha|T|
     $$
     其中，T为任意子树，C(T)为对训练数据的预测误差（基尼指数、平方误差），|T|为子树的叶节点个数，$\alpha>0$为参数，$C_\alpha(T)$为参数是$\alpha$时T的整体损失，$\alpha$权衡训练数据的拟合程度与模型的复杂度。
     
     对固定的$\alpha$，一定存在使损失函数$C_\alpha(T)$最小的唯一最小子树。当$\alpha$较大时，子树偏小；当$\alpha$较小时，子树偏大。考虑将$\alpha$从小增大，得到$0=\alpha_0<\alpha_1<...<\alpha_n<+\infty$，每个区间$[\alpha_i,\alpha_{i+1})$都对应一棵剪枝得到的子树，子树序列为$\{T_0,T_1,...,T_n\}$，序列中的子树是嵌套的。
     
     对任意子树$T_t$，其剪枝前的损失为：
     $$
     C_\alpha(T_t)=C(T_t)+\alpha|T_t|
     $$
     以t为单结点的子树的损失为：
     $$
     C_\alpha(t)=C(t)+\alpha
     $$
     当$\alpha$为0或者充分小的时候，$C_\alpha(T_t)<C_\alpha(t)$。当$\alpha$从0开始增大时，$C_\alpha(T_t)$的增幅要比$C_\alpha(t)$大，因此存在一个$\alpha$使得二者相等，易得二者相等时：
     $$
     \alpha=\frac{C(t)-C(T_t)}{|T_t|-1}
     $$
     此时二者有相同的损失函数值，而t的结点少，所以选择对$T_t$剪枝。
     
     为此，对整体树$T_0$中每一个内部结点t计算：
     $$
     g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}
     $$
     它表示该内部结点被剪枝的阈值。为了得到一个从小到大的$\alpha$序列，每次选择剪去$g(t)$最小的内部结点。容易证明剪去该结点后包含该结点的剩余内部结点对应的阈值会增大，因此不必担心得到的$\alpha$序列不是单调递增的。
     
     具体地，CART剪枝算法的完整流程为：
     
     - 输入：CART算法生成的决策树$T_0$;
     
     - 最优决策树$T_\alpha$。
     
     - 1. 设k=0，$\alpha_0=0,T=T_0$；
     
       2. 设$\alpha=+\infty$；
     
       3. 自下而上地对各内部结点t计算：
          $$
          g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}
          $$
          更新$\alpha$：
          $$
          \alpha=\min (\alpha,g(t))
          $$
     
       4. 对$g(t)=\alpha$的内部结点t进行剪枝；
     
       5. 设k=k+1，$\alpha_k=\alpha,T_k=T$；
     
       6. 如果$T_k$不是由根结点及两个叶结点构成的树，则回到步骤2；否则令$T_k=T_n$；
     
       7. 采用交叉验证法在子树序列$\{T_0,T_1,...,T_n\}$中选取最优子树$T_\alpha$。
   
6. ID3和C4.5如何处理缺失值

   - 如何选取最优划分属性

     以信息增益作为划分依据为例，对于每一个属性，其信息增益为：
     $$
     Gain(D,a)=\rho*Gain(\hat D, a)
     $$
     其中a为所选属性，D为完整数据集，$\hat D$为属性a上无缺失值的样本子集，$\rho$为所占的属性a上无缺失值的样本所占比例。

   - 如何将带缺失值的训练样本划分到分支中

     对于当前选中属性为缺失值的训练样本，以不同权重将其划分到不同子树，权重等于无缺失值样本在每个分支中所占的比例。

   - 测试样本如有缺失值该如何判断其类别

     先对决策树做一点改动，对于每一个叶子节点，记录其总样本数以及属于每个类别的样本数。这样，当样本划分到该叶子节点时，得到的就是一个类别概率分布而不是一个单纯的类别。

     如果分类进入某个属性值未知的分支节点时，探索所有可能的分类结果并把所有结果结合起来考虑。这样，会存在多个路径，分类结果将是类别的分布而不是某一类别，从而选择概率最高的类别作为预测类别。

