分类模型1-决策树

• 简介
• 决策树三要素
• 1. 特征的选择
  • 1. ID3
  • 2. C4.5
  • 3. CART
• 2. 剪枝处理
  • 0. 剪枝的作用
  • 1. 预剪枝
  • 2. 后剪枝
• QA
  • 1. ID3, C4.5, CART 这三种决策树的区别
  • 2. 树形结构为何不需要归一化？
  • 3. 分类决策树与回归决策树的区别
  • 4. 为何信息增益会偏向多取值特征？

算法	划分标准
ID3	信息增益
C4.5	信息增益率
CART	基尼系数

简介

决策树是一个分而治之的递归过程。

• 开始，构建根节点，将所有训练数据都放在根节点。
• 然后，选择一个最优特征，按照这一特征将训练数据集分割成子集，使得各个子集有一个在当前条件下最好的分类。
• 如果子集未分类完毕，则在子集中选择一个最优特征，继续进行划分，直到所有训练数据子集都被正确分类或没有合适的特征为止。

决策树三要素

• 特征选择： 从训练数据中众多的特征中选择一个特征作为当前节点的分裂标准，如何选择特征有着很多不同量化评估标准标准，从而衍生出不同的决策树算法。
• 决策树生成：根据选择的特征评估标准，从上至下递归地生成子节点，直到数据集不可分则停止决策树停止生长。
• 决策树的修剪：决策树容易过拟合，一般来需要剪枝，缩小树结构规模、缓解过拟合。剪枝技术有预剪枝和后剪枝两种。

1. 特征的选择

有三种方法进行特征选择：ID3: 信息增益，C4.5: 信息增益比，CART: 基尼系数

1. ID3

思想： 计算所有特征划分数据集D，得到多个特征划分数据集D的信息增益，从这些信息增益中选择最大的，因而当前结点的划分特征便是使信息增益最大的划分所使用的特征。

1.对当前例子集合，计算各属性的信息增益；
2.选择信息增益最大的属性Ak；
3.把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；
4.对既含正例又含反例的子集，递归调用建树算法；
5.若子集仅含正例或反例，对应分枝标上P或N，返回调用处。

信息增益： 度量以某特征划分数据集前后的信息熵的差值。 信息熵能够表示样本集合的不确定性，因此我们能够通过前后集合信息熵的差值来衡量使用当前特征对于样本集合D划分效果的好坏。

假设划分前样本集合D的熵为 $H(D)$。使用某个特征A划分数据集D，计算划分后的数据子集的熵为 $H(D|A)$ 。

$$信息熵：H(D) = - \sum_{k=1}^k \frac{|C_k|}{|D|} log_2 \frac{|C_k|}{|D|} \\ 条件熵： H(D|A) = \sum_{i=1}^n \frac{|D_i|}{|D|} H(D_i) \\ 信息增益： g(D,A)=H(D)-H(D|A)$$

注意： 在决策树构建中，我们总是希望集合往最快到达纯度更高 的子集合发展，因此我们总是选择是的信息增益最大的特征来划分当前集合。

• 缺点：信息增益对分支较多的属性有所偏好，因此有人提出采用信息增益比来划分特征。

2. C4.5

信息增益比本质：在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。

$$信息增益比 = 惩罚参数 \times 信息增益 \\ 信息增益比：g_R(D,A) = \frac{g(D,A)}{H(D)}$$

信息增益比对可取值数目较少的属性有所偏好。C4.5 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择信息增益比最高的。

相对于 ID3 算法的改进：用信息增益比来选择属性，克服了用信息增益选择属性偏向选择多值属性的不足

3. CART

CART 既可以用于分类，也可以用于回归。

基尼系数 $Gini(D)$ 表示集合 D 的不确定性，基尼系数 $Gini(D, A=a)$ 表示集合 D 经过 A = a 分割后的不确定性。 基尼系数越小，样本的不确定性越小。

分类问题中，假设有 K 个类，样本点属于第 k 类的概率为 $p_k$， 则概率分布的基尼系数定义为

$$Gini(D) = \sum_{k=1}^{|K|}p_k(1-p_k)= 1 - \sum_{k=1}^{K} p_k^2$$

如果样本集合 $D$ 根据特征 $A$ 是否取一可能值 $a$ 被分割成 $D_1$ 和 $D_2$ 两部分， 那么在特征 A 的条件下， 集合 D 的基尼系数定义为：

$$Gini(D, A=a) = \frac{D_1}{D}Gini(D_1) + \frac{D_2}{d} Gini(D_2)$$

• 从根节点开始，对节点计算现有特征的基尼系数，对于每一个特征，根据 “是” 与 “否” 划分为两个部分，根据上式计算划分过后的基尼系数。

• 在所有可能的特征 A 以及该特征所有的可能取值aa中，选择基尼指数最小的特征及其对应的取值作为最优特征和最优切分点。然后根据最优特征和最优切分点，将本节点的数据集二分，生成两个子节点。

• 对两个字节点递归地调用上述步骤，直至节点中的样本个数小于阈值，或者样本集的基尼指数小于阈值，或者没有更多特征后停止。

2. 剪枝处理

0. 剪枝的作用

剪枝处理是决策树学习算法用来解决过拟合的一种办法。

在决策树算法中，为了尽可能正确分类训练样本， 节点划分过程不断重复， 有时候会造成决策树分支过多，以至于将训练样本集自身特点当作泛化特点， 而导致过拟合。 因此可以采用剪枝处理来去掉一些分支来降低过拟合的风险。

1. 预剪枝

在决策树生成过程中，在每个节点划分前先估计其划分后的泛化性能， 如果不能提升，则停止划分，将当前节点标记为叶结点。

2. 后剪枝

生成决策树以后，再自下而上对非叶结点进行考察， 若将此节点标记为叶结点可以带来泛化性能提升，则修改之。

---

QA

1. ID3, C4.5, CART 这三种决策树的区别

• ID3 决策树优先选择信息增益大的属性来对样本进行划分， 但是这样的划分方法有一个很大的缺点： 当一个属性可取值数目较多时， 可能在这个属性对应值下的样本只有一个或者很少个， 此时它的信息增益将很高， ID3会认为这个属性很适合划分。
• C4.5树：不采用信息增益作为划分依据，而是采用信息增益率作为划分依据。但是仍不能完全解决以上问题,而是有所改善。
• CART树：它使用gini系数作为节点的分裂依据。

2. 树形结构为何不需要归一化？

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

3. 分类决策树与回归决策树的区别

4. 为何信息增益会偏向多取值特征？

从直观的理解上来说，当特征取值较多时， 根据此特征划分得到的子集纯度有更大的可能性会更高（对比取值较少的特征）， 因此划分之后的熵会更低，而又由于划分之前的熵是一定的，因此信息增益更大。