机器学习实战（六）决策树（下）CART详解

Bertha 。 2021-11-22 09:00 493阅读 0赞

### 文章目录 ###

*   *  一、CART分类树回归树简介
     *  二、CART分类树分裂属性的选择
     *  三、CART回归树分类属性的选择
     *  四、剪枝的原理及分类
     *  五、CART分类回归树的剪枝
     *  六、简单总结
     *  七、优缺点

**前言：**  
决策树可以分成ID3、C4.5和CART。上一篇博客，已经讲了ID3、C4.5，感兴趣的可以参考下： [https://blog.csdn.net/qs17809259715/article/details/97231726][https_blog.csdn.net_qs17809259715_article_details_97231726]

CART与ID3和C4.5相同都由特征选择，树的生成，剪枝组成。但ID3和C4.5用于分类，CART可用于分类与回归。

ID3和C4.5生成的决策树可以是多叉的，每个节点下的叉树由该节点特征的取值种类而定，比如特征年龄分为（青年，中年，老年），那么改节点下可分为3叉。而CART为假设决策树为二叉树，内部结点特征取值为”是”和”否”。

## 一、CART分类树回归树简介 ##

*  CART分类回归树是一种典型的二叉决策树，可以做分类或者回归。
 *  如果待预测结果是离散型数据，则CART生成分类决策树；
 *  如果待预测结果是连续型数据，则CART生成回归决策树。
 *  数据对象的属性特征为离散型或连续型，并不是区别分类树与回归树的标准，例如表1中，数据对象xi的属性A、B为离散型或连续型，并是不区别分类树与回归树的标准。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]  
作为分类决策树时，待预测样本落至某一叶子节点，则输出该叶子节点中所有样本所属类别最多的那一类（即叶子节点中的样本可能不是属于同一个类别，则多数为主）；作为回归决策树时，待预测样本落至某一叶子节点，则输出该叶子节点中所有样本的均值。

## 二、CART分类树分裂属性的选择 ##

**CART的前提条件，决策树必须为二叉树**

选择具有最小Gini的属性及其属性值，作为最优分裂属性以及最优分裂属性值。Gini值越小，说明二分之后的子样本的“纯净度”越高，即说明选择该属性（值）作为分裂属性（值）的效果越好。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 2]  
简单来说，基尼指数反映了数据集合的混乱程度。当基尼指数越大时，当前数据越混沌的，分布均匀时取极值。

## 三、CART回归树分类属性的选择 ##

**1.区别于分类树，回归树的待预测结果为连续型数据。**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 3]  
**2.举个栗子**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 4]

## 四、剪枝的原理及分类 ##

**1.算法目的:**  
决策树对训练属于有很好的分类能力，但是对于未知的测试集未必有好的分类能力，泛化能力弱，即可能发生过拟合现象。为防止过拟合，我们需要进行剪枝。  
三种决策树的剪枝过程算法相同，区别是对于当前树的评价标准不同。

剪枝分为预剪枝和后剪枝：

**2.预剪枝：**  
（1）每一个结点所包含的最小样本数目，例如10，则该结点总样本数小于10时，则不再分；  
（2）指定树的高度或者深度，例如树的最大深度为4；  
（3）指定结点的熵小于某个值，不再划分。  
**3.后剪枝：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 6]  
**4.后剪枝算法**

后剪枝算法有很多种，这里简要总结如下：

**Reduced-Error Pruning (REP,降低错误剪枝）**  
这个思路很直接，完全的决策树不是过度拟合么，我再搞一个测试数据集来纠正它。对于完全决策树中的每一个非叶子节点的子树，我们尝试着把它替换成一个叶子节点，该叶子节点的类别我们用子树所覆盖训练样本中存在最多的那个类来代替，这样就产生了一个简化决策树，然后比较这两个决策树在测试数据集中的表现，如果简化决策树在测试数据集中的错误比较少，那么该子树就可以替换成叶子节点。该算法以 **bottom-up** 的方式遍历所有的子树，直至没有任何子树可以替换使得测试数据集的表现得以改进时，算法就可以终止。

**Pessimistic Error Pruning (PEP，悲观剪枝）**  
PEP剪枝算法是在C4.5决策树算法中提出的， 把一颗子树（具有多个叶子节点）用一个叶子节点来替代（我研究了很多文章貌似就是用子树的根来代替）的话，比起REP剪枝法，它不需要一个单独的测试数据集。

**Error Based Pruning（基于错误剪枝 EBP）**

**Cost Complexity Pruning（代价-复杂度剪枝 CCP）**

**Minimum Error Pruning（最小错误剪枝 MEP）**  
等等

## 五、CART分类回归树的剪枝 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 10]  
详解可以参考这个博客：  
[https://blog.csdn.net/wjc1182511338/article/details/76793164?locationNum=6&fps=1][https_blog.csdn.net_wjc1182511338_article_details_76793164_locationNum_6_fps_1]

## 六、简单总结 ##

我们发现Gini指数不仅用来选取最优特征，还用来选择最优切分点。而在ID3和C4.5算法中，信息熵并没有用此来计算最优切分点而仅仅用来选择最优特征。当然，我们也可以自己实现信息熵的最优切分点来看看决策树的生成效果如何。

算法（CART生成算法）

输入：训练数据集D，停止计算的条件； 
    输出：CART决策树； 
    根据训练数据集，从根节点开始，递归地对每个结点进行以下操作，构建二叉决策树： 
    （1）设结点的训练数据集为D，计算现有特征对该数据集的基尼指数。此时对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或“否”将D分割成D1D1和D2D2两部分，利用基尼指数计算公式计算。 
    （2）在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。 
    （3）对两个子结点递归地调用（1），（2），直至满足停止条件。 
    （4）生成CART决策树 
    算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值，或者没有更多特征。

## 七、优缺点 ##

**优点:**

1.  模型特别容易解释,甚至比线性模型有更好的解释性.
2.  决策过程跟人的思维习惯特别接近.
3.  能很清楚的图形化显示模型.
4.  能很方便的处理一些定性的Feature.

**缺点:**

1.  一般来说,准确率不如其他的模型.但有很多解方案。
2.  不支持在线学习,有新样本来的时候,需要重建决策树.
3.  很容易产生过拟合.

注：博客内容，仅是博主一人理解整理所得，如有错误，不足之处，欢迎指正，定会细心更改！

**参考文档：**

\[1\]《统计学习方法》李航著

\[2\]《机器学习实战》Peter Harrington著

\[3\] [https://blog.csdn.net/zhihua\_oba/article/details/72230427][https_blog.csdn.net_zhihua_oba_article_details_72230427]

\[4\] [https://blog.csdn.net/u014688145/article/details/53326910][https_blog.csdn.net_u014688145_article_details_53326910]

\[5\] [https://blog.csdn.net/u014688145/article/details/53212112][https_blog.csdn.net_u014688145_article_details_53212112]

\[6\] [https://www.cnblogs.com/luban/p/9412339.html][https_www.cnblogs.com_luban_p_9412339.html]

\[7\] [http://leijun00.github.io/2014/10/decision-tree-2/][http_leijun00.github.io_2014_10_decision-tree-2]

\[8\] [https://www.cnblogs.com/csyuan/p/6535366.html][https_www.cnblogs.com_csyuan_p_6535366.html]

[https_blog.csdn.net_qs17809259715_article_details_97231726]: https://blog.csdn.net/qs17809259715/article/details/97231726
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]: /images/20211122/a95d3ca68c034cd7b5d9f9973b5a7d78.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 1]: /images/20211122/22692000775d48deb87cc0fdf1adf61f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 2]: /images/20211122/2ff4da582c7c4a11b52460139e13d727.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 3]: /images/20211122/8cceca2954f64d26802478d9b8a47b53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 4]: /images/20211122/4c64654ed0b749e0b14a2f48e5528edc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 5]: /images/20211122/423463646cd24ac0a5b70a8797507b9d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 6]: /images/20211122/fa56a5ddb18a4d83a7ec8290933ad557.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 7]: /images/20211122/517cad01acb041b4af35829b3e5d5bf5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 8]: /images/20211122/7ce946258a0b40ba82ebc0e190608717.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 9]: /images/20211122/ba720fc7487545cc844937a1f2f2cd37.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70 10]: /images/20211122/3fffd93848bc42b1914caff8b4bfc70a.png
[https_blog.csdn.net_wjc1182511338_article_details_76793164_locationNum_6_fps_1]: https://blog.csdn.net/wjc1182511338/article/details/76793164?locationNum=6&fps=1
[https_blog.csdn.net_zhihua_oba_article_details_72230427]: https://blog.csdn.net/zhihua_oba/article/details/72230427
[https_blog.csdn.net_u014688145_article_details_53326910]: https://blog.csdn.net/u014688145/article/details/53326910
[https_blog.csdn.net_u014688145_article_details_53212112]: https://blog.csdn.net/u014688145/article/details/53212112
[https_www.cnblogs.com_luban_p_9412339.html]: https://www.cnblogs.com/luban/p/9412339.html
[http_leijun00.github.io_2014_10_decision-tree-2]: http://leijun00.github.io/2014/10/decision-tree-2/
[https_www.cnblogs.com_csyuan_p_6535366.html]: https://www.cnblogs.com/csyuan/p/6535366.html