机器学习算法详解之决策树(二)

港控/mmm° 2022-09-17 04:19 384阅读 0赞

**目录**

生成决策树模型的递归什么时候停止

如果让递归一直持续下去

剪枝处理

前剪枝

后剪枝

样本数据的处理

离散化

缺失值处理

回顾经典决策树CART、ID3、C4.5

ID3和C4.5比较

CART

回归树

原理

怎样对输入空间进行划分？即如何选择划分点？

CART回归算法流程：

示例

最后几个决策树的比较图

--------------------

# 生成决策树模型的递归什么时候停止 #

## 如果让递归一直持续下去 ##

决策树生成算法是递归地生成决策树，知道不能终止。这样产生的决策树往往分类精细，对训练数据集分类准确，但是对未知数据集却没有那么准确，有比较严重的过拟合问题。

## 剪枝处理 ##

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16][]

剪枝解决过拟合的一个有效方法。当树训练得过于茂盛的时候会出现在测试集上的效果比训练集上差不少的现象，即过拟合。可以采用如下两种剪枝策略

### 前剪枝 ###

该策略就是在对一个节点进行划分前进行估计，如果不能提升决策树泛化精度，就停止划分，将当前节点设置为叶节点。那么怎么测量泛化精度，就是留出一部分训练数据当做测试集，每次划分前比较划分前后的测试集预测精度。

优点：降低了过拟合风险，降低了训练所需的时间。

缺点：预剪枝是一种贪心操作，可能有些划分暂时无法提升精度，但是后续划分可以提升精度。故产生了欠拟合的风险。

前剪枝可以在使用决策树时初始化参数中选择指标。

### 后剪枝 ###

该策略是首先正常建立一个决策树，然后对整个决策树进行剪枝。按照**决策树的广度优先搜索的反序**，依次对内部节点进行剪枝，如果将某以内部节点为根的子树换成一个叶节点，可以提高泛化性能，就进行剪枝。

优先：降低过拟合风险，降低欠拟合风险，决策树效果提升比预剪枝强

缺点：时间开销大得多

常见三种后剪枝方法：

1.REP—错误率降低剪枝

2.PEP—悲观剪枝（C4.5），悲观剪枝一般很多框架内部自动实现了

3.CCP—代价复杂度剪枝（CART）

# 样本数据的处理 #

## 离散化 ##

决策树一定要做数据离散化，一般采用one-hot编码，连续性的数据可通过分段定义转换。

## 缺失值处理 ##

决策树对缺失值是非常敏感的，所以要对缺失值进行处理。

C4.5中采用的方法是：测试样本在该属性值上有缺失值，那么就同时探查（计算）所有分支，然后算每个类别的概率，取概率最大的类别赋值给该样本。

# 回顾经典决策树CART、ID3、C4.5 #

## **ID3和C4.5比较** ##

ID3（Iterative Dichotomiser 3，迭代二叉树3代）由Ross Quinlan于1986年提出。1993年，他对ID3进行改进设计出了C4.5算法。

我们已经知道ID3与C4.5的不同之处在于，ID3根据信息增益选取特征构造决策树，而C4.5则是以信息增益率为核心构造决策树。既然C4.5是在ID3的基础上改进得到的，那么这两者的优缺点分别是什么？

使用信息增益会让**ID3算法更偏向于选择值多的属性**。信息增益反映给定一个条件后不确定性减少的程度，必然是分得越细的数据集确定性更高，也就是信息熵越小，信息增益越大。因此，在一定条件下，值多的属性具有更大的信息增益。而C4.5则使用信息增益率选择属性。信息增益率通过引入一个被称作分裂信息(Split information)的项来惩罚取值较多的属性，分裂信息用来衡量属性分裂数据的广度和均匀性。这样就改进了ID3偏向选择值多属性的缺点。

相对于ID3只能处理离散数据，C4.5还能对连续属性进行处理，具体步骤为：

1.把需要处理的样本(对应根节点)或样本子集(对应子树)按照连续变量的大小从小到大进行排序。  
2.假设该属性对应的不同的属性值一共有N个，那么总共有N−1个可能的候选分割阈值点，每个候选的分割阈值点的值为上述排序后的属性值中两两前后连续元素的中点，根据这个分割点把原来连续的属性分成bool属性。实际上可以不用检查所有N−1个分割点。(连续属性值比较多的时候，由于需要排序和扫描，会使C4.5的性能有所下降。)  
3.用信息增益比率选择最佳划分。

C4.5的其他优缺点：

优点：

1）在树的构造过程中可以进行剪枝，缓解过拟合；

2）能够对连续属性进行离散化处理（二分法）；

3）能够对**缺失值**进行处理；

缺点：构造树的过程需要对数据集进行多次顺序扫描和排序，导致**算法低效**；

刚才我们提到信息增益对可取值数目较多的属性有所偏好；而信息增益率对可取值数目较少的属性有所偏好！那么两者结合一下就好了，方法是：先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。而不是大家常说的直接选择信息增益率最高的属性！

## CART ##

CART（Classification And Regression Tree，分类回归树）由L.Breiman，J.Friedman，R.Olshen和C.Stone于1984年提出，是一种应用相当广泛的决策树学习方法。值得一提的是，**CART和C4.5一同被评为数据挖掘领域十大算法**。

CART算法采用一种二分递归分割的技术，将当前的样本集分为两个子样本集，使得生成的的每个非叶子节点都有两个分支。因此，CART算法生成的决策树是结构简洁的二叉树。

基尼系数的计算公式:

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16][]

同熵一样，如果样本集合D被某个属性A是否取某个值分成两个样本集合D1和D2，则在属性A的条件下，集合D的基尼指数定义为：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_9_color_FFFFFF_t_70_g_se_x_16][]

在一定程度上基尼指数（Gini(D)）反应的是集合D的不确定程度，跟熵类似。Gini(D, A)反应的是经过特征A划分后集合D的不确定程度。基尼系数越大，样本集合的不确定性也就越大。因此最好的属性划分是使得Gini(D, A)最小的划分。

下图显示了二分类问题中基尼系数、熵（单位比特）之半1/2\*H(p)和分类误差率的关系。横坐标表示概率p，纵坐标表示损失。可以看出基尼系数和熵之半曲线很接近，都可以近似的代表分类误差率。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_12_color_FFFFFF_t_70_g_se_x_16][]

每一次选择使基尼系数最小的属性作为切分点直到满足停止条件为止。算法的停止条件是节点中的样本个数小于预定阈值，或者样本集的基尼系数小于预定阈值（样本基本属于同一类），或者没有更多特征。

## 回归树 ##

### 原理 ###

除了分类功能之外，CART还支持回归任务。

理论解释：

假设X和Y分别为输入和输出变量，Y为连续变量，训练数据集D为

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_9_color_FFFFFF_t_70_g_se_x_16 1][]

一个回归树对应着输入空间(即特征空间)的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为M个单元R1,R2,…,RM，在每个单元Rm上有个固定的输出Cm，于是回归树表示为：

![711bf6e77ba24efc9020499c702c771a.png][]

当输入空间的划分确定时，可以用平方误差![6febc5699b11455f8b96716fb97ff75c.png][] 来，表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元Rm上的cm的最优值![f2c0aea435ed474baf54a24a389628c9.png][]是Rm上所有输入实例xi对应的输出yi的均值，即：

![f2c0aea435ed474baf54a24a389628c9.png][]= ave(yi | xi![52aa59ca4fbc4069ab41e99dc54a9f01.png][]Rm)

### **怎样对输入空间进行划分？即如何选择划分点？** ###

CART回归树采用启发式的方法对输入空间进行划分，选择第j个变量xj，和它取的值s，作为切分变量(splitting variable)和切分点(splitting point)，并定义两个区域：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_11_color_FFFFFF_t_70_g_se_x_16][]

然后寻找最优切分变量j和最优切分点s。具体地，求解：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_12_color_FFFFFF_t_70_g_se_x_16 1][]

每一个切分变量和切分点对(j,s)都将输入空间分成两个区域，然后分别求每个区域的输出值，使得误差最小，很显然输出值应该是那个区域所有样本值的平均值，即：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_8_color_FFFFFF_t_70_g_se_x_16][]

### CART回归算法流程： ###

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_14_color_FFFFFF_t_70_g_se_x_16][]

### 示例 ###

基于以下数据试用平方误差损失准则生成一个二叉回归树。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_18_color_FFFFFF_t_70_g_se_x_16][]

寻找最优切分变量j和最优切分点s的方法为：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16][]

其中![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_11_color_FFFFFF_t_70_g_se_x_16 1][]

例如，取s=1。此时R1=\{1\},R2=\{2,3,4,5,6,7,8,9,10\} ，这两个区域的输出值分别为：

C1=4.50

C2=1/9 (4.75 + 4.91 + 5.34 + 5.80 + 7.05 + 7.90 +8.23 +8.70 +9.00) = 6.85

根据上面的计算方法，可以得到下表：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

把C1、C2的值带入到均方差中：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

同理，可以获得下表：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_16_color_FFFFFF_t_70_g_se_x_16][]

可以看s=5时m(s)最小，第一个最优切分变量为j=x、最优切分点为s=5，切分后数据划分的两个区域分别是：R1=\{1,2,3,4,5\},R2=\{6,7,8,9,10\}

然后依然重复上述操作，先计算C1和C2 ....直到满足停止条件为止。这样就生成了一颗回归树。此时的回归树成为最小二乘回归树（least squares regression tree）。

# 最后几个决策树的比较图 #

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

参考:[决策树学习（下）——ID3、C4.5、CART深度剖析及源码实现\_老杨的博客-CSDN博客][ID3_C4.5_CART_-CSDN]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3c2214a39a3243bd98483a5b0812f4c5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_7_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/df3dd03b4860494abeb084e01aa72290.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_9_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ab910105f1764a1a96f5e29402ad37bc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/ab3a562e3a764f6ba1a1faf858a1320a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_9_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/381c4b308c5244cf86b5ce003d008fcf.png
[711bf6e77ba24efc9020499c702c771a.png]: /images/20220828/4f237e605729453197dc623fc58bd0a9.png
[6febc5699b11455f8b96716fb97ff75c.png]: https://img-blog.csdnimg.cn/6febc5699b11455f8b96716fb97ff75c.png
[f2c0aea435ed474baf54a24a389628c9.png]: /images/20220828/16932680a9624ec8a6d2df3fbd43894f.png
[52aa59ca4fbc4069ab41e99dc54a9f01.png]: /images/20220828/0d81a0925c7744dda1237bcc63727854.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d545a0ed752c475ba8d9b6f62e16d3d5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_12_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/846e89934d5a4b57b21c9349adc415e2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_8_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/aec72fcbd3674930a0455fcdab9c68b1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/867cde2e797d4c1999845e10ed18047e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d516ecf2ab25405a887e81a98dfa5543.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/755850fc26ff4ba7bf2b9b94cb7aad93.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_11_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/8b9031a8ac2e4d44a376add191fcc0fa.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/97a26f33d92b402a82649a3ed72e5525.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/37b821f73d904744a0dcce08a8b53ad3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/dadfd16081404ba188db33e897e1577f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAUmF5Q2hpdTc1NzM3NDgxNg_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/880801c14a0c45d5bc83758a80171c4b.png
[ID3_C4.5_CART_-CSDN]: https://blog.csdn.net/yangmuted/article/details/47906143