> 通过本课掌握"决策树"这种经典算法。
> 本课学习时长评估：6小时。
## 决策树定义
决策树是一种基本的分类与回归方法。
* 是一种根据样本为基础的归纳学习，采用的是自顶而下的递归方法：开始数据都在根节点，递归的进行数据分片
* 通过剪枝的方法，防止过拟合
## 决策树使用场景
* 对未知数据进行分类
* 特征逐层向下，直到叶子节点，叶子节点的类型为预测类型
## 决策树的构造过程
* 特征选择
* 树生成，启发函数：ID3、C4.5、CART
* 剪枝
## 下面计算过程使用的样本数据
| 人 | 年龄 | 长相 | 工资 | 写代码 | 类别 |
| --- | --- | --- | --- | --- | --- |
| 小A | 老 | 帅 | 高 | 不会 | 不见 |
| 小B | 年轻 | 一般 | 中等 | 会 | 见 |
| 小C | 年轻 | 丑 | 高 | 不会 | 不见 |
| 小D | 年轻 | 一般 | 高 | 会 | 见 |
| 小L | 年轻 | 一般 | 低 | 不会 | 不见 |
## 树生成过程中的启发函数
### 理解熵（entropy）
熵（entropy）在统计学中是一个很重要的概念，是衡量信息量的度量单位，用于特征的选择，衡量结果的不确定性， 信息熵越小， 结果越简单。
如果信息都是一个类别，那么熵就是0。
**信息熵的计算公式：**
`$ H(D) = -\sum_{i=1}^{n}P_i\log_{2}{P_i} $`
`$ P_i $`代表，第i份样本出现的概率，小于1，所以`$ log_{2}{P_i} $`是小于0的，所以`$ \sum $`前面需要有负号。
关于熵的更多讲解，可以看这个视频：[视频链接](https://www.bilibili.com/video/BV1Hx411J7pW)。
### ID3 最大信息增益
**对于样本集合D，类别为K（不见/见），数据集D的经验熵如下：**
`$ H(D) = -\sum_{k=1}^{K}\frac{|C_k|}{|D|}\log_{2}{\frac{|C_k|}{|D|}} $`
**特征A（比如年龄），对于数据集的经验条件熵如下**：
`$ H(D|A) = \sum_{i=1}^{n}H(D_i) $`
实际代表的意义，就是特征A的所有取值分类（比如老、年轻）：计算权重*经验熵*，然后相加。
#### 第一步：计算经验熵
`$ H(D) = -\frac{3}{5}\log_{2}{\frac{3}{5}}-\frac{2}{5}\log_{2}{\frac{2}{5}} = 0.971 $`
#### 第二步：计算经验条件熵
`$ H(D|年龄) = \frac{1}{5}H(老) + \frac{4}{5}H(年轻) = \frac{1}{5}(-0) + \frac{4}{5}\left (-\frac{2}{4}\log_{2}{\frac{2}{4}}-\frac{2}{4}\log_{2}{\frac{2}{4}}\right ) = 0.8 $`
`$ H(D|长相) = \frac{1}{5}H(帅) + \frac{3}{5}H(一般) + \frac{1}{5}H(丑) = 0 + \frac{3}{5}\left (-\frac{2}{3}\log_{2}{\frac{2}{3}}-\frac{1}{3}\log_{2}{\frac{1}{3}}\right ) + 0 = 0.551 $`
`$ H(D|工资) = \frac{3}{5}H(高) + \frac{1}{5}H(中等) + \frac{1}{5}H(低) = \frac{3}{5}\left (-\frac{2}{3}\log_{2}{\frac{2}{3}}-\frac{1}{3}\log_{2}{\frac{1}{3}}\right ) + 0 + 0 = 0.551 $`
`$ H(D|写代码) = \frac{3}{5}H(不会) + \frac{2}{5}H(会) = \frac{3}{5}(0) + \frac{2}{5}(0) = 0 $`
#### 第三步：计算信息增益
𝑔(𝐷,年龄) = 0.171
𝑔(𝐷,长相) = 0.42
𝑔(𝐷,工资) = 0.42
𝑔(𝐷,写代码) = 0.971
#### 第四步：计算结果分析
特性"写代码"的信息增益最大，所以的样本根据此特征，可以直接被分到叶节点（见或不见），完成决策树的生长。当然，实际应用中，不回通过一个特性就完成构建，需要在经验熵非0的类别中继续生长，也不会无限生长，需要根据"预剪枝"决定何时停止生长。
#### ID3的缺陷
* 当某一个特征值的取值种类非常多时，对应每一个属性取值的样本子集，其分类的信息熵可能会变得很小，极端例子：DNA特性分割，分割后信息熵为0。
* 信息增益对属性较多的特征有所偏好。
以上，带来的实际是过拟合问题。
### C4.5 最大信息增益比
信息增益比公式对value值多的情况进行的惩罚处理(尽管如此，还是要剪枝)。
**特征A对于数据集D的信息增益比定义为：**
`$ g_R(D,A) = \frac{g(D,A)}{H_A(D)} $`
**以上，分子是信息增益，分母成为数据集D关于A的取值熵，如下：**
`$ H_A(D) = -\sum_{i=1}^{n}\frac{|D_i|}{|D|}\log_{2}{\frac{|D_i|}{|D|}} $`
特征A的取值越多，取值熵越大，也就是分母越大。
#### 第一步：计算取值熵
`$ H_{年龄}(D) = 0.722 $`
`$ H_{长相}(D) = 1.371 $`
`$ H_{工资}(D) = 1.371 $`
`$ H_{写代码}(D) = 0.971 $`
#### 第二步：计算信息增益比
`$ g_{R}(D,年龄) = 0.236 $`
`$ g_{R}(D,长相) = 0.402 $`
`$ g_{R}(D,工资) = 0.402 $`
`$ g_{R}(D,写代码) = 1 $`
#### 第三步：计算结果分析
特征"年龄"对应的指标上升了，特性"长相"和"工资"有所下降。
### CART 最大基尼指数(Gini)
Gini描述的是数据的纯度，与信息熵含义类似。
`$ Gini(D) = 1 - \sum_{k=1}^{n}\left(\frac{{C_k}}{|D|}\right )^{2} $`
CART在每一次迭代中选择Gini最小的"特征及其对应的切分点"进行分类。
CART是一颗二叉树，每一步按照特征的取值切成两份，进入**左右子树**。
**特征A的Gini指数定义如下：**
`$ Gini(D|A) = \sum_{i=1}^{n}Gini(D_i) $`
因为二分，以上i实际就两个取值，分别代表：特征A的取值/非特征A的取值
#### 第一步：计算各个特征的Gini指数
`$ Gini(D|年龄=老) = \frac{1}{5}Gini(老) + \frac{4}{5}Gini(不老) = \frac{1}{5}\left(1-\frac{0}{1}^2 - \frac{1}{1}^2\right) + \frac{4}{5}\left(1-\frac{2}{4}^2 - \frac{2}{4}^2\right) = 0.4 $`
`$ Gini(D|年龄=年轻) = 0.4 $`
`$ Gini(D|长相=帅) = 0.4 $`
`$ Gini(D|长相=丑) = 0.4 $`
`$ Gini(D|长相=一般) = 0.27 $`
`$ Gini(D|写代码=会) = 0 $`
`$ Gini(D|写代码=不会) = 0 $`
`$ Gini(D|工资=高) = 0.47 $`
`$ Gini(D|工资=中等) = 0.3 $`
`$ Gini(D|工资=低) = 0.4 $`
#### 第二步：计算结果分析
以上，我们可以发现"写代码"的Gini指数最小为0，因此选择"写代码"作为最优特征，"写代码=会"为最优切分点。
## 如何对决策树进行剪枝
一颗完全生长的决策树会面临一个很严重的问题，即过拟合。
因此，需要对决策树进行剪枝，剪掉一些枝叶，提升模型的泛化能力。
通常的剪枝方法：Pre-Pruning、Post-Pruning
### 预剪枝(Pre-Pruning)
在决策树的生成过程中，提前停止决策树的生长。
**何时停止决策树的生长：**
* 当树到达一定的深度时，停止树的生长
* 当到达当前节点的样本数量小于某个阈值时，停止树的生长
* 计算每次分裂对测试集的准确度的提升，当小于某个阈值的时候，不再继续扩展。
**预剪枝的特点：**
* 思想直接、算法简单、效率高，适合解决大规模问题
* 以上阈值，需要一定的经验判断
* 有欠拟合的风险。
### 后剪枝(Post-Pruning)
在已生成的过拟合的决策树上进行剪枝，得到简化版的剪枝决策树。
**常见的后剪枝方法：**
* 错误率降低剪枝(Reduced Error Pruning, REP)
* 悲观剪枝(Pessimistic Error Pruning, PEP)
* 代价复杂度剪枝(Cost Complexity Pruning, CCP)
* 最小误差剪枝(Minimum Error Pruning, MEP)
* CVP(Critical Value Pruning)
* OPP(Optimal Pruning)
**代价复杂度剪枝(CCP)简介：**
* 从完整决策树`$ T_0 $`开始，生成一个子树序列{`$ T_0 $`,`$ T_1 $`...`$ T_n $`}，其中`$ T_{i+1} $`由`$ T_i $`生成，`$ T_n $`为树的跟节点。
* 在子树序列中，根据真实误差选择最佳的决策树。
* 误差增加率计算公式：`$ \alpha = \frac{R_{(t)} - R_{(T_t)}}{|L_{(T_t)}|-1} $`，分子：剪枝后的节点误差-剪枝前的节点误差，分母：子树`$ T_t $`的叶子节点个数-1，每一步都选择`$ \alpha $`最小的节点进行剪枝。
**后剪枝的特点：**
* 通常可以得到泛化能力更强的决策树
* 时间开销会更大。
## 学习资料
* 《百面机器学习》第3章-第3节
* [40分钟搞懂机器学习算法系列 - 决策树 /理论/实战](https://www.bilibili.com/medialist/play/ml969336500)
