机器学习：决策树和剪枝

一、决策树基本知识

（一）概念

决策树（decision tree）是一种监督学习算法，是一种树形结构，树中每个内部节点表示一个特征上的判断，每个分支代表一个判断结果的输出，每个叶子节点代表一种分类结果。

（二）决策树建立过程

1.特征选择：选取有较强分类能力的特征；

2.决策树生成：根据选择的特征生成决策树；

3.决策树也易过拟合，采用剪枝的方法缓解过拟合。

二、决策树生成

（一）ID3决策树：基于信息增益构建的决策树。

信息熵：熵在信息论中代表随机变量不确定度的度量；熵越大，数据的不确定性度越高；熵越小，数据的不确定性越低。

公式：

信息增益：集合$D$的熵$H(D)$与特征A给定条件下D的熵$H(D|A)$之差。

公式：

根据信息增益选择特征构建子树方法是：对训练数据集D，计算其每个特征的信息增益，并比较它们的大小，并选择信息增益最大的特征进行划分。

例：
已知6个样本，根据特征a：


ID3决策树构建流程：

1. 计算每个特征的信息增益
2. 使用信息增益最大的特征将数据集 S 拆分为子集
3. 使用该特征（信息增益最大的特征）作为决策树的一个节点
4. 使用剩余特征对子集重复上述（1，2，3）过程

（二）C4.5决策树

信息增益率：

1. Gain_Ratio 表示信息增益率；
2. IV 表示分裂信息、内在信息；
3. 信息增益率= 特征的信息增益 ➗ 内在信息。

特点：

1. 如果某个特征的特征值种类较多，则其内在信息值就越大。即：特征值种类越多，除以的系数就越大。
2. 如果某个特征的特征值种类较小，则其内在信息值就越小。即：特征值种类越小，除以的系数就越小。

信息增益率本质： 是在信息增益的基础之上乘上一个惩罚参数。特征个数较多时，惩罚参数较小；特征个数较少时，惩罚参数较大。惩罚参数：数据集D以特征A作为随机变量的熵的倒数。

根据信息增益率选择特征构建子树方法：对训练数据集D，计算其每个特征的信息增益率，并比较它们的大小，并选择信息增益率最大的特征进行划分。

例：

特征a的信息增益率：

1. 信息增益：1-0.5408520829727552=0.46
2. 特征熵：-4/6*math.log(4/6, 2) -2/6*math.log(2/6, 2)=0.9182958340544896
3. 信息增益率：信息增益/分裂信息=0.46/0.9182958340544896=0.5

特征b的信息增益率：

1. 信息增益：1
2. 特征熵：-1/6*math.log(1/6, 2) * 6=2.584962500721156
3. 信息增益率：信息增益/信息熵=1/2.584962500721156=0.38685280723454163

由计算结果可见，特征1的信息增益率大于特征2的信息增益率，根据信息增益率，我们应该选择特征1作为分裂特征。

（三）CART决策树

Cart模型是一种决策树模型，它即可以用于分类，也可以用于回归。

分类和回归树模型采用不同的最优化策略。Cart回归树使用平方误差最小化策略，Cart分类生成树采用的基尼指数最小化策略。

基尼指数：

Gini为基尼值，Gini_index为基尼指数，基尼指数值越小（cart），则说明优先选择该特征。

平方损失：

1.CART分类决策树

例：

计算“是否有房”的基尼指数：

首先，根据是否有房将目标值划分为两部分：

1. 计算有房子的基尼值： 有房子有 1、4、7 共计三个样本，对应：3个no、0个yes：

   $Gini(\text{是否有房，yes })=1-{\left(\frac{0}{3}\right)}^2-{\left(\frac{3}{3}\right)}^2=0$

2. 计算无房子的基尼值：无房子有 2、3、5、6、8、9、10 共七个样本，对应：4个no、3个yes：

   $\mathrm{Gini}(\text{是否有房，no })=1-{\left(\frac{3}{7}\right)}^2-{\left(\frac{4}{7}\right)}^2=0.4898$

3. 计算基尼指数：第一部分样本数量占了总样本的 3/10、第二部分样本数量占了总样本的 7/10：

   $\mathrm{Gin}{\mathrm{i}}_{-}in\mathrm{dex}(D,\text{ 是否有房 })=\frac{7}{10}\ast 0.4898+\frac{3}{10}\ast 0=0.343$

计算“婚姻状况”的基尼指数：

1. 计算 {married} 和 {single,divorced} 情况下的基尼指数：

   结婚的基尼值，有 2、4、6、9 共 4 个样本，并且对应目标值全部为 no：

   $Gini\_index(D,\text{married})=0$

   不结婚的基尼值，有 1、3、5、7、8、10 共 6 个样本，并且对应 3 个 no，3 个 yes：

   $Gini\_index(D,\text{ single,divorced })=1-{\left(\frac{3}{6}\right)}^2-{\left(\frac{3}{6}\right)}^2=0.5$

   以 married 作为分裂点的基尼指数：

   $Gini\_index(D,\text{ married })=\frac{4}{10}\ast 0+\frac{6}{10}\ast \left[1-{\left(\frac{3}{6}\right)}^2-{\left(\frac{3}{6}\right)}^2\right]=0.3$

2. 计算 {single} | {married,divorced} 情况下的基尼指数

   $Gini\_index(D,\text{婚姻状况})=\frac{4}{10}\ast 0.5+\frac{6}{10}\ast \left[1-{\left(\frac{1}{6}\right)}^2-{\left(\frac{5}{6}\right)}^2\right]=0.367$

3. 计算 {divorced} | {single,married} 情况下基尼指数

   $Gini\_index(D,\text{ 婚姻状况 })=\frac{2}{10}\ast 0.5+\frac{8}{10}\ast \left[1-{\left(\frac{2}{8}\right)}^2-{\left(\frac{6}{8}\right)}^2\right]=0.4$

4. 最终：该特征的基尼值为 0.3，并且预选分裂点为：{married} 和 {single,divorced}

计算“年收入”的基尼指数：

先将数值型属性升序排列，以相邻中间值作为待确定分裂点：

以年收入 65 将样本分为两部分，计算基尼指数:

$节点为65时:年收入=\frac{1}{10}\ast 0+\frac{9}{10}\ast \left[1-{\left(\frac{6}{9}\right)}^2-{\left(\frac{3}{9}\right)}^2\right]=0.4$

以此类推计算所有分割点的基尼指数，我们发现最小的基尼指数为 0.3。

此时，我们发现：

1. 以是否有房作为分裂点的基尼指数为：0.343
2. 以婚姻状况为分裂特征、以 married 作为分裂点的基尼指数为：0.3
3. 以年收入作为分裂特征、以 97.5 作为分裂点的的基尼指数为：0.3

最小基尼指数有两个分裂点，我们随机选择一个即可，假设婚姻状况，则可确定决策树如下：

重复上面步骤，直到每个叶子结点纯度达到最高。

2.CART回归决策树

例：

假设：数据集只有 1 个特征 x, 目标值值为 y，如下图所示：

由于只有 1 个特征，所以只需要选择该特征的最优划分点，并不需要计算其他特征。

1. 先将特征 x 的值排序，并取相邻元素均值作为待划分点，如下图所示：

   s	1.5	2.5	3.5	4.5	5.5	6.5	7.5	8.5	9.5

2. 计算每一个划分点的平方损失，例如：1.5 的平方损失计算过程为：

   R1 为 小于 1.5 的样本个数，样本数量为：1，其输出值为：5.56

   $R_1=5.56$

   R2 为 大于 1.5 的样本个数，样本数量为：9 ，其输出值为：

   $R_2=(5.7+5.91+6.4+6.8+7.05+8.9+8.7+9+9.05)/9=7.50$

   该划分点的平方损失：

   $L(1.5)=(5.56-5.56{)}^2+\left[(5.7-7.5{)}^2+(5.91-7.5{)}^2+\dots +(9.05-7.5{)}^2\right]=0+15.72=15.72$

3. 以此方式计算 2.5、3.5… 等划分点的平方损失，结果如下所示：

   s	1.5	2.5	3.5	4.5	5.5	6.5	7.5	8.5	9.5
   m(s)	15.72	12.07	8.36	5.78	3.91	1.93	8.01	11.73	15.74

4. 当划分点 s=6.5 时，m(s) 最小。因此，第一个划分变量：特征为 X, 切分点为 6.5，即：j=x, s=6.5**
   

5. 对左子树的 6 个结点计算每个划分点的平方式损失，找出最优划分点：

   x	1	2	3	4	5	6
   y	5.56	5.7	5.91	6.4	6.8	7.05

   s	1.5	2.5	3.5	4.5	5.5
   c1	5.56	5.63	5.72	5.89	6.07
   c2	6.37	6.54	6.75	6.93	7.05

   s	1.5	2.5	3.5	4.5	5.5
   m(s)	1.3087	0.754	0.2771	0.4368	1.0644

6. s=3.5时，m(s) 最小，所以左子树继续以 3.5 进行分裂:

7. 假设在生成3个区域 之后停止划分，以上就是回归树。每一个叶子结点的输出为：挂在该结点上的所有样本均值。

x	1	2	3	4	5	6	7	8	9	10
y	5.56	5.7	5.91	6.4	6.8	7.05	8.9	8.7	9	9.05

1号样本真实值 5.56 预测结果：5.72

2号样本真实值是 5.7 预测结果：5.72

3 号样本真实值是 5.91 预测结果 5.72

三、决策树剪枝：防止过拟合

剪枝是指将一颗子树的子节点全部删掉，利用叶子节点替换子树(实质上是后剪枝技术)，也可以（假定当前对以root为根的子树进行剪枝）只保留根节点本身而删除所有的叶子，以下图为例：

（一）决策树剪枝的基本策略有"预剪枝" (pre-pruning）和"后剪枝"（post- pruning)

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

1.预剪枝（例）：

4. 假设: 当前树只有一个结点, 即编号为1的结点. 此时, 所有的样本预测类别为: 其类别标记为训练样例数最多的类别，假设我们将这个叶结点标记为 “好瓜”。此时, 在验证集上所有的样本都会被预测为 “好瓜”, 此时的准确率为: 3/7

5. 如果进行此次分裂, 则树的深度为 2, 有三个分支. 在用属性"脐部"划分之后，上图中的结点2、3、4分别包含编号为 {1，2，3， 14}、 {6，7， 15， 17}、 {10， 16} 的训练样例，因此这 3 个结点分别被标记为叶结点"好瓜"、 “好瓜”、 “坏瓜”。此时, 在验证集上 4、5、8、11、12 样本预测正确，准确率为: 5/7。很显然, 通过此次分裂准确率有所提升, 值得分裂.

6. 接下来，对结点2进行划分，基于信息增益准则将挑选出划分属性"色泽"。然而，在使用"色泽"划分后，编号为 {5} 的验证集样本分类结果会由正确转为错误，使得验证集精度下降为 57.1%。于是，预剪枝策略将禁止结点2被划分。

7. 对结点3，最优划分属性为"根蒂"，划分后验证集精度仍为 5/7. 这个 划分不能提升验证集精度，于是，预剪枝策略禁止结点3被划分。

8. 对结点4，其所含训练样例己属于同一类，不再进行划分.

于是，基于预剪枝策略从上表数据所生成的决策树如上图所示，其验证集精度为 71.4%. 这是一棵仅有一层划分的决策树。

2.后剪枝（例）:

后剪枝先从训练集生成一棵完整决策树，继续使用上面的案例，从前面计算，我们知前面构造的决策树的验证集精度为42.9%。

首先考察结点6，若将其领衔的分支剪除则相当于把6替换为叶结点。替换后的叶结点包含编号为 {7， 15} 的训练样本，于是该叶结点的类别标记为"好瓜", 此时决策树的验证集精度提高至 57.1%。

2. 然后考察结点5，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号为 {6，7，15}的训练样例，叶结点类别标记为"好瓜’；此时决策树验证集精度仍为 57.1%. 于是，可以不进行剪枝.
3. 对结点2，若将其领衔的子树替换为叶结点，则替换后的叶结点包含编号 为 {1， 2， 3， 14} 的训练样例，叶结点标记为"好瓜"此时决策树的验证集精度提高至 71.4%. 于是，后剪枝策略决定剪枝.
4. 对结点3和1，若将其领衔的子树替换为叶结点，则所得决策树的验证集 精度分别为 71.4% 与 42.9%，均未得到提高，于是它们被保留。
5. 最终, 基于后剪枝策略生成的决策树如上图所示, 其验证集精度为 71.4%。

（二） 剪枝方法对比

预剪枝优点：

• 预剪枝使决策树的很多分支没有展开，不单降低了过拟合风险，还显著减少了决策树的训练、测试时间开销

预剪枝缺点：

• 有些分支的当前划分虽不能提升泛化性能，甚至会导致泛化性能降低，但在其基础上进行的后续划分却有可能导致性能的显著提高
• 预剪枝决策树也带来了欠拟合的风险

后剪枝优点：

• 比预剪枝保留了更多的分支。一般情况下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝

后剪枝缺点：

• 但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中所有非叶子节点进行逐一考察，因此在训练时间开销比未剪枝的决策树和预剪枝的决策树都要大得多。

附赠1：ID3决策树、C4.5决策树、CART决策树对比（CART回归树采用平方损失，表中未说明）

附赠2：CART分类树与回归树对比

今天的分享到此结束。