决策树

发表于 阅读次数： Waline： 本文字数： 1.9k 阅读时长 ≈ 7 分钟

基本流程

决策树（decision tree，亦称判定树）是一类常见的学习方法[1]。

以二分类任务为例，我们希望从给定训练数据集学得一个模型用以对新示例进行分类，这个把样本分类的任务，可看作对「当前样本属于正类吗？」这个问题的「决策」或「判定」过程。

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试；每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。

决策树学习的目的是为了产生一棵泛化能力强的决策树，对未见示例能做出正确的判定。

基本流程是遵循分而治之（divide-and-conquer）策略。是一个自根至叶的递归过程，在每个中间结点寻找一个划分（split or test）属性：

停止条件：

  1. 当前结点包含的样本全属于同一类别，无需划分；
  2. 当前属性集为空，或所有样本在所有属性上取值相同，无法划分；
  3. 当前结点包含的样本集合为空，不能划分。

在第 2. 种情形下，把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在第 3. 种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。

这两种情形处理实质不同：情形 2. 是在利用当前结点的后验分布，而情形 3. 则是把父结点的样本分布作为当前结点的先验分布。

划分选择

由算法伪代码可以看出，决策树学习的关键在于如何选择最优划分属性。

一般而言，随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度（purity）越来越高。

信息增益

信息熵（information entropy）是度量样本集合纯度最常用的一种指标。

假定当前样本集合 DD 中第 k∈{1,2,⋯ ,∣Y∣}k \in \left\lbrace 1, 2, \cdots, |\mathcal{Y}| \right\rbrace 类样本所占的比例为 pkp_k，则 DD 的信息熵定义为[2]：

Ent⁡(D)=−∑k=1∣Y∣pklog⁡2pk\operatorname{Ent}(D) = - \sum_{k=1}^{|\mathcal{Y}|} p_k \log_2 p_k

显然 Ent⁡(D)\operatorname{Ent}(D) 最小值为 00，最大值为 log⁡2∣Y∣\log_2 |\mathcal{Y}|。具体证明过程见 2022 年 2 月 22 日博文《初遇信息熵 Information Entropy》。

Ent⁡(D)\operatorname{Ent}(D) 的值越小，样本集合 DD 的纯度越高。

假定离散属性 aa 有 VV 个可能的取值 {a1,a2,⋯ ,aV}\left\lbrace a^1, a^2, \cdots, a^V \right\rbrace，若使用 aa 来对样本集合 DD 进行划分，则会产生 VV 个分支结点，其中第 vv 个分支结点包含了 DD 中所有在属性 aa 上取值为 ava^v 的样本，记为 DvD^v。

可根据定义计算出 DvD^v 的信息熵，再考虑到不同分支结点所包含的样本数不同，给分支结点赋予权重 ∣Dv∣∣D∣\dfrac{|D^v|}{|D|} ，即样本数越多的分支结点的影响越大，于是可计算出属性 aa 对样本集 DD 进行划分所获得的信息增益（information gain）：

Gain⁡(D,a)=Ent⁡(D)−∑v=1V∣Dv∣∣D∣Ent⁡(Dv)\operatorname{Gain}(D, a) = \operatorname{Ent}(D) - \sum_{v=1}^V \dfrac{|D^v|}{|D|} \operatorname{Ent}(D^v)

一般而言，信息增益越大，意味着使用属性 aa 来进行划分所获得的「纯度提升」越大。

因此，我们可用信息增益来进行决策树的划分属性选择。即在算法中选择属性 a∗=arg max⁡a∈AGain⁡(D,a)a_{*} = \argmax\limits_{a \in A} \operatorname{Gain}(D, a)。

著名的 ID3 决策树学习算法就是以「信息增益」为准则来选择划分属性的。

增益率

若一个划分属性可以使得每个分支结点仅包含一个样本，此时分支结点纯度已达最大，但是这样的决策树显然不具有泛化能力，无法对新样本进行有效预测。例如「编号」属性，可以产生很多个分支，每个分支结点仅包含一个样本。

「信息增益准则」对可取值数目较多的属性有所偏好，为了减少这种偏好可能带来的不利影响，C4.5 决策树算法使用了增益率（gain ratio）来选择最优划分属性。

增益率定义为：

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

其中

IV⁡(a)=−∑v=1V∣Dv∣∣D∣log⁡2∣Dv∣∣D∣\operatorname{IV}(a) = - \sum_{v=1}^V \dfrac{|D^v|}{|D|} \log_2 \dfrac{|D^v|}{|D|}

称为属性 aa 的固有值（intrinsic value）。属性 aa 的可能取值数目越多（即 VV 越大），则 IV⁡(a)\operatorname{IV}(a) 的值通常会越大。

「增益率准则」对可取值数目较少的属性有所偏好，因此 C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼指数

CART 决策树使用基尼指数（Gini index）来选择最优划分属性。

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

Gini⁡(D)=∑k=1∣Y∣∑k′≠kpkpk′=1−∑k=1∣Y∣pk2\begin{aligned} \operatorname{Gini}(D) & = \sum_{k=1}^{|\mathcal{Y}|} \sum_{k' \neq k} p_k p_{k'} \\ & = 1 - \sum_{k=1}^{|\mathcal{Y}|} p_k^2 \end{aligned}

直观来说，Gini⁡(D)\operatorname{Gini}(D) 反映了从数据集 DD 中随机抽取两个样本，其类别标记不一致的概率。因此，Gini⁡(D)\operatorname{Gini}(D) 越小，数据集 DD 的纯度越高。

属性 aa 的基尼指数定义为：

Gini_index⁡(D,a)=∑v=1V∣Dv∣∣D∣Gini⁡(Dv)\operatorname{Gini\_index}(D, a) = \sum_{v=1}^V \dfrac{|D^v|}{|D|} \operatorname{Gini}(D^v)

于是我们在侯选属性集合 AA 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 a∗=arg min⁡a∈AGini_index⁡(D,a)a_{*} = \argmin\limits_{a \in A} \operatorname{Gini\_index}(D, a)。

剪枝处理

剪枝（pruning）是决策树学习算法对付「过拟合」的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得「太 好」了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致过拟合。因此，可通过主动去掉一些分支来降低过拟合的风险。

决策树剪枝基本策略有两种：

  • 预剪枝（pre-pruning）是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。
  • 后剪枝（post-pruning）则是先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。

如何判断决策树泛化性能是否提升呢？这可使用前面介绍的性能评估方法。

预剪枝

  1. 「决策树」有时指的是学习方法，有时指的是学得的树。 ↩︎

  2. 约定若 p=0p = 0，则 plog⁡p=0p \log p = 0。 ↩︎