决策树算法的原理（接地气版）

蔚落 2022-11-29 12:44 90阅读 0赞

#  #

![format_png][]

> ❝
> 
> 决策树（）是一类很常见很经典的机器学习算法，既可以作为分类算法也可以作为回归算法。同时也适合许多集成算法，如,，以后会逐一介绍。本篇介绍一下决策树算法的原理。❞

决策树算法不像前面介绍的SVM那样，散发着浓厚的数学气味。这个算法还是比较**接地气**的。

##     ##

## **信息论基础** ##

![format_png 1][]这个语法结构大家应该不陌生。怎样准确地定量选择后面的条件，也就是要找到一个**性能指标**来衡量这个条件的好坏。（就像SVM中引入了来衡量一条直线的好坏）。

70年代，一个名为昆兰的大牛找到了信息论中的**「熵」**来度量决策树的决策选择过程。注意，信息论中的**熵**是香农提出的。昆兰只是将**熵**应用于决策树的人。

熵度量了事物的不确定性(可以联想化学里的熵，混乱程度)，越不确定的事物，它的熵就越大。具体的，随机变量X的熵的表达式如下：

##     ##

## **决策树构造** ##

决策树的组成：

*  根节点：第一个选择点
 *  非叶子节点与分支：中间过程
 *  叶子节点：最终的决策结果![format_png 2][]就像这张图展示的，第一个节点就是根节点，绿色的代表也就是叶子节点，其它的节点也就是非叶子节点(用于决策)，也就是。

那么如何构造决策树呢？

**「第一步，选择根节点」**。

问题来了，特征不唯一，选哪一个作根节点最优？

这就涉及到了衡量标准，一般而言，随着划分过程不断进行，我们希望节点的熵能够迅速地降低。因为**随机变量的熵越大，随机变量的不确定性越大，代表纯度越低**。所以希望**节点的熵能够迅速降低，使得纯度不断增加**。所以以**「信息增益」**作为衡量标准。

引入一个**信息增益**()的概念。

> ❝
> 
> **「定义」**：特征对训练数据集的信息增益，定义为集合的经验熵与特征给定条件下的经验条件熵之差，即
> 
> ❞

**信息增益**也就**度量了熵降低的程度**。  
以信息增益作为衡量标准的算法被称为ID3算法。

**「第二步，选择子节点」**

依然是采用信息增益的标准进行选择。

**「第三步，何时停止」**

其实这一步就涉及到**剪枝**，下文详解。

如果对这些概念还是有点模糊，可以结合下面的实例再思考思考。

##     ##

## **实例** ##

![format_png 3][]**这是数据（14天的打球情况），有四种环境特征（outlook,humidity）,最后一列(play）代表最后有没有出去打球。**

**「首先，选择根节点」**。一共有四个特征，所以根节点的选择有四种。![format_png 4][]

在我们的原始数据（14天）有9天打球，5天不大，所以此时的熵为：

接着，四个特征逐一分析，先从(天气)下手：![format_png 5][]当时，  
  
当时，  
当时，

根据数据，取,,的概率分别为,  
熵值计算（几个特征属性熵的加权求和）：

信息增益：

同样的方式计算其它三个特征的信息增益：

四个特征中，的增益最大，所以选择作为根节点。  
**「接下来的子节点选择同上」**。

**「何时停止？」**  
上文也说了，"何时停止"涉及到剪枝。为什么要剪枝？  
决策树存在较大的过拟合风险，理论上，决策树可以将样本数据完全分开，但是这样就带来了非常大的过拟合风险，使得模型的泛化能力极差。![format_png 6][]剪枝和日常树木的修建是一个道理。这里介绍最常用的**「预****剪枝」**，在构造决策树的过程中，提前停止。  
具体的预剪枝策略有：

*  限制深度，例如，只构造到两层就停止。
 *  限制叶子节点个数，例如，叶子节点个数超过某个阈值就停止  
    等等

**Ensemble Learning  **

简单介绍一下**集成学习**（）。有两种类型，

*  Bagging ：训练多个分类器，最后可采取投票机制选择最终结果。这里的分类器常常是决策树。代表算法是
 *  Boosting：仍是训练多个分类器，将最后的结果加权求和，代表算法是,

这些算法在一些比赛中都是很常见的。

本篇主要介绍的ID3算法仍有一定缺陷，之后的文章会继续介绍。

转自：Python数据科学

往期推荐

[知识卡片 回归度量-MAE和RMSE][-MAE_RMSE]

[知识卡片 回归性能度量 Log Loss][Log_Loss]

[知识卡片  一致性评价 r和k][r_k]

[机器学习入门案例：鸢尾花数据集分类 绘制PR曲线][PR]

[特征工程 文本处理][Link 1]

[知识卡片 特征工程][Link 2]

[知识卡片 线性回归和多元回归][Link 3]

[特征工程 特征处理][Link 4]

[知识卡片 损失函数的正则化][Link 5]

好文章，我 在看❤

[format_png]: /images/20221124/784d7b2309534bf59a2d68419515f091.png
[format_png 1]: /images/20221124/55ca1bcd07964778b8d0085b77d4f065.png
[format_png 2]: /images/20221124/6582ac7e961149929293cc17968b64db.png
[format_png 3]: /images/20221124/c1aed90fee634f89a9cb6f655ab0f8db.png
[format_png 4]: /images/20221124/071b1d5d52b147a3875a2273df8c333f.png
[format_png 5]: /images/20221124/088c9cecef8d480090966997f78a148d.png
[format_png 6]: /images/20221124/9ef8f290692b4733bb5a5801e5dcb191.png
[-MAE_RMSE]: http://mp.weixin.qq.com/s?__biz=MzIwMTMxMTQxNQ%3D%3D&chksm=8157df55b62056433a1172419d42df402c815151b522317fc6d06042d094fea91b4fb1506a72&idx=2&mid=2454497933&scene=21&sn=3f8c04fb4be5d4b0fafab3b01eb8f60a#wechat_redirect
[Log_Loss]: http://mp.weixin.qq.com/s?__biz=MzIwMTMxMTQxNQ%3D%3D&chksm=8157def2b62057e4ceca489fb9a440bcf5874ce8bc1a427079d9adce740aa2e5ce06ac090c60&idx=2&mid=2454498090&scene=21&sn=e22909d8fc25a9707c65f3a6dc2ba05a#wechat_redirect
[r_k]: http://mp.weixin.qq.com/s?__biz=MzIwMTMxMTQxNQ%3D%3D&chksm=8157deb5b62057a3a6713386278e7d13cee3b6f9ee869eeaa3284409e115799e7db2d5fbbe27&idx=2&mid=2454498157&scene=21&sn=54891637028e97c9afec27fd7b57fe01#wechat_redirect
[PR]: http://mp.weixin.qq.com/s?__biz=MzIwMTMxMTQxNQ%3D%3D&chksm=8157deb5b62057a3c32202e93c0c33a57435712aed0817cd36bfb432ef718bbe3de19db77295&idx=1&mid=2454498157&scene=21&sn=96897edf66e0ddb9b1c27b9e95a99950#wechat_redirect
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzIwMTMxMTQxNQ%3D%3D&chksm=8157de6ab620577c099b9d56b1aacc6251ad7599251c21adb7a25b749bed1bc4532dd65f82de&idx=1&mid=2454498226&scene=21&sn=0eb18a4c992ce9fab7d9ed96532aff8d#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzIwMTMxMTQxNQ%3D%3D&chksm=8157de07b62057110772d8ee52088a0d4e8a0d8ef45bae61ba6b9e18869b136ed54e30f42405&idx=2&mid=2454498271&scene=21&sn=ac049ab131602bd1b6cc87c8a3a4756d#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzIwMTMxMTQxNQ%3D%3D&chksm=8157d994b62050822dcf9f06b0568bccdc30739d193881973136c0a6afcb92f6cf7251d1ae48&idx=2&mid=2454498380&scene=21&sn=efc9ef4606920e17d59e2377f74caf6b#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzIwMTMxMTQxNQ%3D%3D&chksm=8157d994b6205082e4bf449445bbea7f18440825e51961357a2b9d42a8309b97d4a94d17dcc8&idx=1&mid=2454498380&scene=21&sn=c48483369a7dc484e3dffa9437ec66ac#wechat_redirect
[Link 5]: http://mp.weixin.qq.com/s?__biz=MzIwMTMxMTQxNQ%3D%3D&chksm=8157d9b5b62050a36f1d4ddf8de35a09c29432bf8b2a7928bdc5d6344144dc0bc6ce4210d28f&idx=2&mid=2454498413&scene=21&sn=702a94a8b0d9da7220170d6c5d4e25d8#wechat_redirect