机器学习期末复习——第四章

一、重点知识点回顾

1. 决策树概述

决策树（Decision Tree）是一种基于树结构的决策工具，其中每个内部节点代表一个属性上的测试，每个分支代表一个测试结果，每个叶节点代表一种决策结果。

不难发现，对于决策树而言，从根节点到每个叶节点的路径对应了一个判定测试序列。如果把这一整条路径看作一条规则，那么一颗决策树相当于一个规则集，既可以做分类也可以做回归。

2. 划分选择

在构建决策树的过程中，显然我们需要不断地选择节点的特征（也就是分类依据），并且需要保证：特征的分类效果越好，那么其对应的节点在决策树中的层次也要更高（例如决策树的根节点的分类效果肯定需要是最好的）。

当然，还需要说明的一点是，随着划分过程的不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别（纯度越来越高），我们可以据此来判断当前划分选择的合理性和优越性。下面就是一些常见的能够衡量结点纯度及其变化的方法：

（1）信息增益

i. 计算数据集的总信息熵

信息熵（Information Entropy）是判断样本集合纯度最常用的一种指标，假定当前样本集合$D$中第$k$类样本所占的比例为$p_k$，则$D$的信息熵定义为：

$$\text{Ent}\left( D \right) =-\sum_{k=1}^{\left| y \right|}{p_k\log _2p_k}$$

显然，$\text{Ent}\left( D \right)$的值越小，$D$的纯度越高。

ii. 计算条件熵

接下来，在考虑使用某个属性，以属性$a$为例，对数据集$D$进行划分时，如果该属性有$V$个属性值，那么接下来$D$肯定会被划分为$V$个子集$D^v$，此时，条件熵就是各个子集熵的加权和：

$$\text{Ent}\left( D|A \right) =\sum_{v=1}^V{\frac{\left| D^v \right|}{\left| D \right|}\text{Ent}\left( D^v \right)}$$

iii. 计算信息增益

那么信息增益即为总信息熵与条件熵之差：

$$\text{Gain}\left( D,a \right) =\text{Ent}\left( D \right) -\text{Ent}\left( D|A \right)$$

一般而言，信息增益越大，则意味着使用属性$a$来进行划分所获得的“纯度提升”就越大。ID3算法就是一种在决策树递归构建的过程中以信息增益为准则来选择划分属性的算法。

（2）增益率

信息增益虽然直观且易于理解，但它天然地倾向于选择取值数目较多的属性。以一个较为极端的情况为例，如果我们直接以人员信息表中的身份证号作为候选属性，那么以此划分产生的子集纯度极高（仅含一个样本，信息熵为0），从而产生极大的信息增益。但这种划分方式显然是过拟合的，所以增益率（Gain Ratio）被提出，它通过引入一个被称为固有值的惩罚因子来缓解上述效应：

$$\left\{ \begin{array}{l} \text{Gain\_ratio}\left( D,a \right) =\frac{\text{Gain}\left( D,a \right)}{\text{IV}\left( a \right)}\\ \\ \text{IV}\left( \text{a} \right) =-\sum_{v=1}^V{\frac{\left| D^v \right|}{\left| D \right|}\log _2\frac{\left| D^v \right|}{\left| D \right|}}\\ \end{array} \right.$$

不难发现，属性$a$的属性值越多，则IV$(a)$通常就越大，从而限制上述极端情况的发生。当然，这也会反过来导致增益率更偏好属性值较少的属性。

C4.5算法是一种使用增益率思想的算法。

（3）基尼系数

和信息熵类似，基尼值也一种度量数据集D纯度的指标，其被定义为：

$$\text{Gini}\left( D \right) =1-\sum_{k=1}^{\left| y \right|}{p_{k}^{2}}$$

和信息增益类似，属性a的基尼系数被定义为：

$$\text{Gini\_index}\left( D,a \right) =\sum_{v=1}^V{\frac{\left| D^v \right|}{\left| D \right|}\text{Gini}\left( D^v \right)}$$

基尼系数越小，则候选属性越适合作为最优划分属性。

CART决策树使用基尼系数来选择划分属性。

3. 剪枝处理

在使用决策树时，为了尽可能地正确分类训练样本，有可能造成分支过多，进而产生过拟合的风险，那么我们就可以通过主动去掉一些分支来降低过拟合的风险，这就是剪枝处理。需要注意的是，和划分选择的各种准则相比，合理的剪枝能够带来更为明显的性能提升。

（1）预剪枝

预剪枝 (pre-pruning)是指在决策树生成过程中，对每个节点在划分之前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分，并将当前节点标记为叶节点。

（2）后剪枝

预剪枝 (pre-pruning)是指先从训练集生成一颗完整的决策树，然后自底向上对非叶子结点进行考察，若将该结点对应的子树替换为叶子节点能带来决策树泛化性能提升，则将该子树替换为叶结点。

相较而言，预剪枝后训练时间开销降低，测试时间开销降低，过拟合风险降低，欠拟合风险增加；后剪枝后训练时间开销增加，测试时间开销降低，过拟合风险降低，欠拟合风险基本不变。因此，总的来说，后剪枝的泛化性能通常由于预剪枝。

二、重点题目回顾