决策树

1. 决策树相关问题
   1. 树形结构为什么不需要归一化？

因为数值缩放不影响分裂点位置，对树模型的结构不造成影响。 按照特征值进行排序的，排序的顺序不变，那么所属的分支以及分裂点就不会有不同。而且，树模型是不能进行梯度下降的，因为构建树模型（回归树）寻找最优点时是通过寻找最优分裂点完成的，因此树模型是阶跃的，阶跃点是不可导的，并且求导没意义，也就不需要归一化。
对线性模型，特征值差别很大时，运用梯度下降的时候，损失等高线是椭圆形，需要进行多次迭代才能到达最优点。 但是如果进行了归一化，那么等高线就是圆形的，促使SGD往原点迭代，导致需要的迭代次数较少。

1. 决策树与LR模型的区别
2. 递归返回条件
   1. 当前节点包含的样本全属于同一类别，无需划分
   2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分

节点类别设定为该节点所含样本最多的类别

1. 当前节点包含的样本集合为空，不能划分

节点类别设定为其父节点所含样本最多的类别

1. 划分选择
   1. ID3信息增益

缺点：信息增益对可取数目较多的属性有偏好。例如“编号”这一类别，有17个分支，每个分支只包含一个样本，如果按照这个属性划分，信息增益会很大，因为这些分支节点的信息熵（纯度）已经达到最大。

“信息熵”是度量样本集合纯度最常用的一种指标。集合D中第k类样本所占的比例为pk(k=1,2…)，则D的信息熵定义为：

Ent(D)的值越小，则D的纯度越高，样本集合的类别越统一。

划分前的信息熵—划分后的信息熵=信息增益。表示的是向纯度方向迈出的“步长”。信息增益越大，意味着使用属性a进行划分所获得的“纯度提升”越大。

1. C4.5增益率

为了解决信息增益的问题，引入一个信息增益率：


属性a的可能取值数目越多(即V越大)，则IV(a)的值通常就越大。信息增益比本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。不过有一个缺点：信息增益率偏向取值较少的特征。
使用信息增益率：基于以上缺点，并不是直接选择信息增益率最大的特征，而是先在候选特征中找出信息增益高于平均水平的特征，然后在这些特征中再选择信息增益率最高的特征。

1. CART基尼指数

表示在样本集合中一个随机选中的样本被分错的概率。举例来说，现在一个袋子里有3种颜色的球若干个，伸手进去掏出2个球，颜色不一样的概率。Gini(D)越小，数据集D的纯度越高。

1. 决策树剪枝

决策树的剪枝基本策略有 预剪枝 (Pre-Pruning) 和 后剪枝 (Post-Pruning)。

• 预剪枝：其中的核心思想就是，在每一次实际对结点进行进一步划分之前，先采用验证集的数据来验证如果划分是否能提高划分的准确性。如果不能，就把结点标记为叶结点并退出进一步划分；如果可以就继续递归生成节点。

优点：降低过拟合风险，减少决策树的训练时间和测试时间开销
缺点：有欠拟合风险

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

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