决策树

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₁，R₂,...,R_M,各个区域的输出值分别为c₁,c₂,...,c_M，求导易得当c_i为各区域输出的平均值时误差最小。
     • 对每个属性的每个取值进行二元划分，取划分后误差最小的属性的取值进行划分。

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上无缺失值的样本所占比例。

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

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

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

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

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

决策树

原文：https://www.cnblogs.com/lyq2021/p/14253778.html