决策树

发表于 2023-01-04 更新于 2023-01-30 阅读次数：本文字数： 3.9k 阅读时长 ≈ 14 分钟

决策树

基本流程

决策树基于树结构进行决策，每个内部节点对应某个属性上的“测试”（test），每个分支对应于该测试的一种可能结果，每个叶结点对应于一个预测结果。

学习过程：通过对训练样本的分析来确定“划分属性”；

预测过程：将测试实例从根节点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶子结点。

基本流程：分治：从上往下递归，在每个中间节点找到“划分”属性

停止条件：

当前节点包含的样本全部属于同一类别，无需划分；
当前属性集为空，或是所有样本在所有属性上取值相同，无法划分：我们把当前结点标记为叶结点，其类别设定为该结点所含样本最多的类别；
当前节点包含的样本集合为空，不能划分：我们把当前结点标记为叶结点，其类别设定为其父节点所含样本最多的类别。

注意，第二类和第三类处理实质不同：第二类是利用当前结点的后验分布，第三类是把父节点的样本分布作为当前结点的先验分布。

划分选择

由上面的算法可以发现，决策树学习的关键在于第十行的“选择最优划分属性”。随着划分过程不断进行，我们希望决策树的分支结点包含的样本尽可能属于同一类别，即“纯度”越来越高。

信息增益

信息熵是度量样本集合“纯度”最常用的一种指标。

假设当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k$ ，则 $D$ 的信息熵定义为

\operatorname{Ent}(D) = -\sum\limits_{k=1}^{|\mathcal{Y}|}p_k\log _2(p_k)

其中 $\mathcal{Y}$ 为样本类型集合。由于取负号，则 $Ent(D)$ 的值越小， $D$ 的纯度越高。

我们约定，如果 $p = 0$ ，则 $p\log_2p = 0$ 。容易得到，信息熵 $\operatorname{Ent}(D)$ 的最小值为 $0$ ，当所占比例均等时，最大值为 $\log_2|\mathcal{Y}|$ 。

假设离散属性 $a$ 有 $V$ 个可能的取值 $\left\{a^1, a^2, \dots, a^V\right\}$ ，如果使用属性 $a$ 为样本集进行划分，则会产生 $V$ 个分支结点，其中第 $v$ 个分支结点包含了 $D$ 中所有属性为 $a^v$ 的样本，记为 $D^v$ 。我们用下式表示属性 $a$ 对样本集 $D$ 进行划分所获得的“信息增益”

\operatorname{Gain}(D, a) = \operatorname{Ent}(D) - \sum\limits_{v = 1}^V{\dfrac{|D^v|}{|D|}\operatorname{Ent}(D^v)}

信息增益也被称为互信息，表示已知一个随机变量的信息后，另一个随机变量的不确定性减少的程度。

一般而言，信息增益越大，则意味着使用属性 $a$ 来进行划分所获得的“纯度提升”越大。因此，选择最优属性时我们可以采用属性 $a_* = \underset{a \in A}{\arg\max}\operatorname{Gain}(D, a)$ 。

举例：

上表所示的数据集中包含 17 个训练数据，用以学习一棵预测没剖开的是不是好瓜的决策树。显然， $|\mathcal Y| = 2$ ，正例所占比例为 $p_1 = \frac {8}{17}$ ，负例所占比例为 $p_2 = \frac 9{17}$ ，于是根结点的信息熵为

\operatorname{Ent}(D) = -\sum\limits_{k=1}^2{p_k\log_2p_k} = -\left(\dfrac 8{17} \log_2 \dfrac 8{17} + \dfrac9{17} \log_2 \dfrac 9{17}\right) \approx 0.998.

之后，我们要计算当前属性集合 $\left\{\text{色泽，根蒂，敲声，纹理，脐部，触感}\right\}$ 中每个属性的信息增益。

以属性“色泽”为例，若使用该属性对 $D$ 进行划分，可得到三个子集，分别记为 $D^1\left(\text{色泽}=\text{青绿}\right)$ ， $D^2\left(\text{色泽}=\text{乌黑}\right)$ ， $D^3\left(\text{色泽}=\text{浅白}\right)$ 。 $D^1$ 包含编号为 $\left\{1, 4, 6, 10, 13, 17\right\}$ 的 6 个样例，正例占 $p_1 = \frac 36$ , 负例占 $p_2 = \frac 36$ ；另两个子集类似，之后算出用“色泽”划分之后获得的三个分支结点的信息熵为

\begin{aligned} \operatorname{Ent}\left(D^1\right) &= -\left(\dfrac 36 \log_2 \dfrac 36 + \dfrac 36 \log_2 \dfrac 36\right) = 1.000 \\ \operatorname{Ent}\left(D^2\right) &= -\left(\dfrac 46 \log_2 \dfrac 46 + \dfrac 26 \log_2 \dfrac 26\right) \approx 0.918 \\ \operatorname{Ent}\left(D^3\right) &= -\left(\dfrac 15 \log_2 \dfrac 15 + \dfrac 45 \log_2 \dfrac 45\right) \approx 0.722 \end{aligned}

于是可以计算出“色泽”的信息增益为

\begin{aligned} \operatorname{Gain}\left(D, \text{色泽}\right) &= \operatorname{Ent}(D) - \sum\limits_{v=1}^3{\dfrac{|D^v|}{|D|}\operatorname{Ent}\left(D^v\right)} \\ &= 0.998 - \left(\dfrac 6{17} \times 1.000 + \dfrac 6{17} \times 0.918 + \dfrac 5{17} \times 0.722\right) \\ &= 0.109 \end{aligned}

类似地，我们可以计算出其他属性的信息增益：

\begin{aligned} \operatorname{Gain}\left(D, \text{根蒂}\right) &= 0.143;\ \operatorname{Gain}\left(D, \text{敲声}\right) = 0.141; \\ \operatorname{Gain}\left(D, \text{纹理}\right) &= 0.381;\ \operatorname{Gain}\left(D, \text{脐部}\right) = 0.289; \\ \operatorname{Gain}\left(D, \text{触感}\right) &= 0.006; \end{aligned}

由于“纹理”的信息增益最大，于是它被选为划分属性，划分结果如下图所示：

再对每个子集继续划分，最终得到决策树：

增益率

在上面的例子中，我们特意省略了“编号”这一特征，这是因为，如果计算编号的信息增益，可以发现其高达 0.998，这也是容易理解的：如果按照编号分类，将会产生 17 个分支，每个分支仅包含一个结点。这样的决策树显然不具有泛化能力，无法对新样本进行有效的预测。

实际上，信息增益准则对可取值数目较多的属性有所偏好，为了避免这种影响，由 Quinlan 在 1993 年提出的 C4.5 决策树算法不直接使用信息增益，而是使用“增益率”来选择最优划分属性，定义为

\operatorname{Gain\_ratio}(D, a) = \dfrac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)}

其中

\operatorname{IV}(a) = -\sum\limits_{v=1}^V{\dfrac{|D^v|}{|D|} \log_2 \dfrac{|D^v|}{|D|}}

称为属性 $a$ 的“固有值”。属性 $a$ 的可能取值数目越多（即 $V$ 越大），则 $\operatorname{IV}(a)$ 的值通常会越大。

需注意的是，增益率准则对可取值数目较少的属性有所偏好，因此，C4.5 算法采用了一种启发式的做法：先找出信息增益高于平均水平的属性，再从其中选择增益率最高的。

基尼指数

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

数据集 $D$ 的纯度可用基尼值来度量：

\begin{aligned} \operatorname{Gini}(D) &= \sum\limits_{k=1}^{|\mathcal Y|}{\sum\limits_{k' \neq k}p_kp_{k'}} \\ &=1 - \sum\limits_{k=1}^{|\mathcal Y|} p_k^2 \end{aligned}

其中 $|\mathcal Y|$ 为属性集的大小。直观上， $\operatorname{Gini}(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率，所以 $\operatorname{Gini}(D)$ 越小，则数据集 $D$ 的纯度越高。

属性 $a$ 的基尼指数定义为

\operatorname{Gini\_index}(D, a) = \sum\limits_{v = 1}^V{\dfrac{|D^v|}{|D|}\operatorname{Gini}(D^v)}

我们选择划分后基尼指数最小的属性作为最优划分属性，即 $a_* = \underset{a \in A}{\arg\min}\operatorname{Gini\_index}(D, a)$ 。

剪枝

剪枝是决策树学习算法避免“过拟合”，提高泛化能力的主要手段。在生成一棵决策树的过程中，为了尽可能正确地分类训练样本，划分结点的过程可能会不断重复，导致分支过多，以至于把训练集的一些特点当作所有数据都具有的一般性质而导致过拟合。

剪枝分为“预剪枝”和“后剪枝”两种。“预剪枝”是指在决策树生成过程中，对每个结点在划分前进行估计，如果划分后泛化能力无法提升，则停止划分并将当前结点标记为叶结点；

“后剪枝”则是先从训练集生成一棵完整的决策树，然后自下向上地对非叶结点进行考察，如果把该结点的子树替换为叶结点能提高泛化能力，则将该子树替换为叶结点。

以下我们默认采用“留出法”判断决策树的泛化能力。

基于上表，我们可以生成一棵未剪枝的决策树，为了方便讨论，对其中的部分结点做了标号，如下图所示：

预剪枝

首先讨论预剪枝。当只有一个根节点时，如果不划分，则该结点的类别为集合中出现次数最多的类别，不妨设为“好瓜”，使用验证集对其验证，得到准确率为 $\frac 37 \approx 42.9\%$ 。

用属性“脐部”划分后，准确率上升至 $\frac 57 = 71.4\%$ ，于是预剪枝的决策为“划分”。

可以看到，这是一棵仅有一层划分的决策树，也叫做“决策树桩”。

预剪枝使得决策树的很多分支都没有“展开”，这降低了过拟合的风险，减少了时间开销。但由于预剪枝基于贪心，只能找到局部最优解而不能找到全局最优解，有可能导致欠拟合的风险。

后剪枝

首先我们生成一棵完整的决策树，易知其准确率为 $42.9\%$ 。

自下往上地考察所有非叶结点，首先考察结点 6，替换为叶结点后包含编号为 $\left\{6, 7, 15\right\}$ 的训练例，叶结点类别标记为“好瓜”，验证集准确率为 $57.1\%$ ，于是决定剪枝。

在对所有非叶结点考虑结束后，得到的决策树如下图所示：

最终准确率为 $71.4\%$ 。

对比

时间开销：
- 预剪枝：训练时间开销降低，测试时间开销降低
- 后剪枝：训练时间开销增加，测试时间开销降低
过/欠拟合风险：
- 预剪枝：过拟合风险降低，欠拟合风险增加
- 后剪枝：过拟合风险降低，欠拟合风险基本不变
泛化性能：后剪枝通常优于预剪枝

连续与缺失值

连续值的处理

当属性连续时，不能直接根据连续属性的可取值来对结点进行划分，此时，我们需要将连续属性离散化。最简单的方法是二分法。

设给定样本集 $D$ 和连续属性 $a$ ， $a$ 在 $D$ 上出现了 $n$ 个不同的取值，从小到大排序后记为 $\left\{a^1, a^2, \dots, a^n\right\}$ 。

在取划分点时，基于划分点 $t$ 可将样本集 $D$ 分为子集 $D_t^-$ 和 $D_t^+$ ，其中 $D_t^-$ 包含在属性 $a$ 上取值不大于 $t$ 的样本，而 $D_t^+$ 则包含在属性 $a$ 上取值大于 $t$ 的样本。对于相邻的属性值 $a^i$ 和 $a^{i+1}$ 而言， $t$ 在区间 $[a^i, a^{i+1})$ 内取任意值所产生的划分结果都相同。

因此，对连续属性 $a$ ，我们可考察包含 $n - 1$ 个元素的候选划分点集合

T_a = \left\{\dfrac{a^i + a^{i + 1}}{2}, 1 \leq i \leq n - 1\right\}

即将区间的中点作为候选划分点，此时我们就可以像离散值一样考察这些划分点了。对于信息增益，我们可以稍加改造得到属性连续时的公式：

\begin{aligned} \operatorname{Gain}(D, a) &= \underset{t \in T_a}{\max} \operatorname{Gain}(D, a, t) \\ &= \underset{t \in T_a}{\max} \operatorname{Ent}(D) - \sum\limits_{\lambda \in \left\{-, +\right\}}{\dfrac{|D_t^\lambda|}{|D|}\operatorname{Ent}(D_t^\lambda)} \end{aligned}

其中 $\operatorname{Gain}(D, a, t)$ 是样本集 $D$ 根据划分点 $t$ 二分后的信息增益。

缺失值的处理

在实际数据中，往往会出现不完整样本，即样本的某些属性值缺失的情况。如果简单地放弃不完整样本，仅使用无缺失值的样本进行学习，会产生极大的浪费。因此，有必要考虑利用有缺失属性值的数据进行学习。

我们需要解决两个问题：

（1）如何在属性值缺失的情况下进行划分属性选择？
（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

给定训练集 $D$ 和属性 $a$ ，令 $\tilde{D}$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本子集。对于问题（1），我们可以仅通过 $\tilde{D}$ 来判断属性的优劣。

假定 $a$ 有 $V$ 个可取值 $\left\{a^1, a^2, \dots, a^V\right\}$ ，令 $\tilde{D}^v$ 表示 $\tilde{D}$ 中在属性 $a$ 上取值为 $a^v$ 的样本子集， $\tilde{D}_k$ 表示 $\tilde{D}$ 中属于第 $k$ 类（ $k = 1, 2, \dots, |\mathcal Y|$ ）的样本子集，则显然有

\begin{aligned} \tilde{D} &= \bigcup\limits_{k=1}^{|\mathcal Y|} \tilde{D}_k \\ \tilde{D} &= \bigcup\limits_{v=1}^V \tilde{D}^v \end{aligned}

假定我们为每个样本 $x$ 赋予一个权重 $w_x$ ，并定义

\begin{aligned} \rho &= \dfrac{\sum_{x \in \tilde{D}}w_x}{\sum_{x \in D} w_x} \\ \tilde{p}_k &= \dfrac{\sum_{x \in \tilde{D}_k} w_x}{\sum_{x \in D} w_x}\quad (1 \leq k \leq |\mathcal Y|) \\ \tilde{r}_v &= \dfrac{\sum_{x \in \tilde{D}^v} w_x}{\sum_{x \in D} w_x}\quad (1 \leq v \leq V) \end{aligned}

$\rho$ 表示无缺失值样本所占的比例， $\tilde{p}_k$ 表示无缺失值样本中第 $k$ 类所占比例， $\tilde{r}_v$ 表示无缺失值样本中在属性 $a$ 上取值为 $a^v$ 的样本所占的比例。
基于上述定义，我们可将信息增益的计算式推广为

\begin{aligned} \operatorname{Gain}(D, a) &= \rho \times \operatorname{Gain}(\tilde{D}, a) \\ &= \rho \times \left(\operatorname{Ent}\left(\tilde{D}\right) - \sum\limits_{v=1}^V{\tilde{r}_v\operatorname{Ent}\left(\tilde{D}^v\right)}\right) \end{aligned}

其中

\operatorname{Ent}(\tilde{D}) = -\sum\limits_{k=1}^{|\mathcal Y|}{\tilde{p}_k \log_2 \tilde{p}_k}

对问题（2）：

若样本 $x$ 在划分属性 $a$ 上的取值已知，则将 $x$ 划入与其取值对应的子结点，且样本权值在子结点中保持为 $w_x$ ；
若样本 $x$ 在划分属性 $a$ 上的取值未知，则将 $x$ 同时划入所有子结点，且样本权值在与属性值 $a^v$ 对应的子结点中调整为 $\tilde{r}_v \cdot w_x$ 。