机器学习笔记(5)：决策树

基本概念

决策树（Decision Tree） 是一种基础的监督学习模型，广泛应用于分类与回归任务。其核心思想是通过一个树状结构来对实例进行决策。该结构本质上是一系列if-then规则的集合，具有很强的可解释性。

一个决策树模型包含以下几个基本组成部分：

根节点 (Root Node): 整棵树的起点，代表了对数据集的第一个划分问题。
内部节点 (Internal Node): 也叫决策节点，代表一个特征或属性的判断问题。
分支 (Branch): 从内部节点延伸出来的路径，代表对问题的一个可能回答（比如“是”或“否”，“大于”或“小于”等）。
叶子节点 (Leaf Node): 也叫终端节点，代表最终的决策结果或分类标签。从根节点到叶子节点的每一条路径，都构成了一条决策规则。

决策树的目标是构建一个泛化能力强，且尽可能简单的模型。它通过从数据特征中学习，自动生成一套简单有效的“决策规则”，从而对新的数据进行预测。例如，根据一个人的年龄、收入、职业等特征，来预测他是否会购买某个产品。其基本流程遵循简单而直观的 “分而治之”(divide-and-conquer) 策略。

决策树的生成是一个递归过程，在基本算法中有三种情形会导致递归返回：
1. 当前结点包含的样本全属于同一类别，无需划分；
2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
3. 当前结点包含的样本集合为空，不能划分。

划分选择

由上述算法可以看出，决策树学习的关键是选择最优划分属性。决策树的目标是，通过每次提问（划分），让数据的“不确定性”变得越来越小，让划分后的每个分支都尽可能地“纯粹”，即结点的 “纯度”(purity) 越来越高。衡量“纯度”的最常用的数学指标有信息熵 (Information Entropy) 和 基尼不纯度 (Gini Impurity) ，后者也称为 “基尼指数”(Gini index)。

信息熵与信息增益

”信息熵(information entropy) 是信息论中的一个概念，它衡量的是一个系统（在这里就是我们的数据集）的 不确定性 或 混乱程度 。

熵越大 ，代表系统越混乱，不确定性越高。
熵越小 ，代表系统越有序，不确定性越低。

假定当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k(k=1,2,\dots,|\mathcal{Y}|)$ ，则 $D$ 的信息熵定义为：

$$ Ent(D) = -\sum_{k=1}^{|\mathcal{Y}|} p_k \log_2 p_k $$

$Ent(D)$ 的值越小，则 $D$ 的纯度越高。

信息增益 (Information Gain) 则是用来衡量一个特征划分“好不好”的指标。它的思想很简单：

$$ 信息增益 = 划分前的信息熵 - 划分后的信息熵 $$

假定离散属性 $a$ 有 $V$ 个可能的取值 $\{a^1, a^2, \dots, a^V \}$ ，那么使用 $a$ 来划分就会产生 $V$ 个分支结点，每个结点的信息熵之和就是划分后的信息熵。考虑到不同的分支结点包含的样本数不同，给分支结点赋予权重 $|D^v|/|D|$ ，即样本数越多的分支结点的影响越大，于是可计算出信息增益：

$$ \text{Gain}(D, a) = \text{Ent}(D) - \sum_{v=1}^{V} \frac{|D^v|}{|D|} \text{Ent}(D^v) $$

一般来说，信息增益越大，说明数据集不确定性减少的程度越大，即纯度提升越大。因此决策树会选择信息增益最大的特征进行划分。

信息增益率

思考一个极端情况。假设我们的数据集中有一个特征是“学号”或“订单ID”，这个特征的特点是，每个人的学号或 ID 都是独一无二的。如果决策树使用信息增益作为划分标准，那么按照 ID 来划分数据时，每个分支都只会包含一个样本。此时每个分支的“纯度”都达到了100%，信息熵为0，于是决策树会选择“学号”或 ID 来作为根节点划分，但是这样的划分没有意义，我们称之为 过拟合(Overfitting) 。
结论：信息增益准则对那些“可取值数目较多”的特征有所偏好。

为了修正这种偏好，我们引出"信息增益率"的概念。它出自 C4.5 决策树算法。

信息增益率 (Information Gain Ratio) 在信息增益的基础上，增加了一个惩罚项，这个惩罚项会随着特征的可取值数目增多而变大，从而抑制了模型对这类特征的偏好。增益率定义为：

$$ \text{Gain\_ratio}(D, a) = \frac{\text{Gain}(D, a)}{\text{IV}(a)} $$

其中，

$\text{Gain}(D, a)$ 是信息增益。
$\text{IV}(a)$ 就是新增的惩罚项，它被称为特征 $a$ 的 **固有值(Intrinsic Value) ** 或 分裂信息(Split Information)。

固有值 $\text{IV}(a)$ 的计算公式为：

$$ \text{IV}(a) = - \sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|} $$

可以发现这个公式与信息熵的计算公式非常相似，不同之处在于：

信息熵 衡量的是 类别标签 的混乱程度（比如“是/否”购买的比例）。
固有值 衡量的是 特征取值 的混乱程度（比如特征“天气”有“晴天、阴天、下雨”3个值的比例）

如果一个特征的取值越多，每个取值下的样本数就越少，那么计算出的 $\text{IV}(a)$ 值通常会越大。把它作为分母，就可以有效地惩罚那些取值数目过多的特征。

值得注意的是，增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的特征，而是采用一种启发式策略：
1. 先从候选划分特征中找出信息增益高于平均水平的特征。
2. 然后再从这些特征中选择信息增益率最高的那个。
这样做可以平衡信息增益和增益率，避免了对取值数目少的特征产生不公平。

基尼指数

基尼指数(Gini index) ，也称为 基尼不纯度(Gini Impurity) ，是另一个衡量数据不确定性的指标，它比信息熵的计算速度更快一些，在很多决策树算法(如 CART (Classification and Regression Tree) 决策树算法)中被广泛使用。

基尼指数的含义是：从一个数据集中随机抽取两个样本，其类别标签不一致的概率。

基尼指数越小，代表数据集的纯度越高。
基尼指数越大，代表数据集的纯度越低。

对于一个数据集 $D$ ，其基尼指数的定义为：

$$ \begin{align*} \text{Gini}(D) &= \sum_{k=1}^{|\mathcal{Y}|} \sum_{k^{'} \neq k} p_kp_{k^{'}} \\ & = 1 - \sum_{k=1}^{|\mathcal{Y}|} p_k^2 \end{align*} $$

在评估“划分”时，我们用“基尼指数”指代一次划分操作的优劣程度。在这种情况下，“基尼指数”指的是划分后，所有子节点基尼不纯度的加权平均值 ：

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

此时，在候选属性集合 $A$ 中，选择那个使得划分后基尼指数最小的属性作为最优划分属性，即 $a_* = \arg \min_{a\in A} \text{Gini\_index}(D, a)$ 。

剪枝处理

到目前为止，我们已经知道决策树是如何通过选择最优特征来一步步构建起来的。但一个关键问题是：这棵树应该长到什么时候才停下来？ 如果让它一直生长，直到每个叶子节点都只包含一种类型的样本（即达到100%纯度），这样就是最好的吗？答案是否定的。这会引出机器学习中一个非常普遍且重要的问题——过拟合。

过拟合

过拟合指的是一个模型在训练数据上表现得过于完美，以至于把训练数据中的一些噪声、特例和无关紧要的细节都学习了进去，导致模型的泛化能力下降。这样的模型，在面对它“背过答案”的训练集时，准确率可能高达100%；但一旦遇到新的、没见过的数据（测试集），表现就会非常糟糕。

为了解决过拟合问题，我们需要对决策树进行简化，这个过程就叫做剪枝 (Pruning)。剪枝是一种正则化技术，它通过主动去掉一些分支来降低模型的复杂度，从而提高模型的泛化能力。

剪枝分为两大类：预剪枝 (Pre-pruning) 和 后剪枝 (Post-pruning)。

预剪枝

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

判断决策树泛化性能是否提升，可以考虑使用模型评估与选择一节中的性能评估方法，比如采用留出法，预留一部分数据用作”验证集“以进行性能评估。除此之外，还有一些更简单的预剪枝策略：

限制树的深度 (Max Depth)：规定决策树最多能长多深，一旦达到指定深度就停止生长。
限制叶子节点的最少样本数 (Min Samples Leaf)：规定一个叶子节点至少要包含多少个样本，如果分裂后某个子节点的样本数少于这个阈值，则不进行分裂。
限制节点划分的最小样本数 (Min Samples Split)：规定一个节点至少要有多少个样本才能进行划分。
限制信息增益的阈值：规定信息增益（或基尼增益）必须大于某个阈值，否则不进行分裂。

预剪枝的优点在于，在书的构建过程中就提前停止，速度快，计算开销小，同时生成的决策树通常规模更小，更简单等；而它的缺点是具有“短视”的风险，有些划分可能当前看起来收益不大（甚至会降低验证集准确率），但它后续的划分却可能会带来巨大的收益。预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

后剪枝

后剪枝 (Post-pruning) 与预剪枝相反。它允许决策树先完全生长，然后再从下往上地审视每个结点，尝试将一些子树替换为单个叶子结点，看看这样做能否提升模型的泛化能力。

最常见的后剪枝方法是降低错误剪枝 (Reduced Error Pruning, REP)：

将数据分为训练集和验证集。
用训练集生成一棵完整的决策树。
从下往上遍历树中的每一个非叶子结点。
尝试将这个结点对应的子树替换成一个叶子结点（该叶子结点的类别由子树中占多数的样本决定）。
用验证集评估，如果剪枝后的树在验证集上的准确率更高或持平，则确定进行剪枝，用叶子结点替换该子树。
重复这个过程，直到无法再通过剪枝提升验证集准确率。

后剪枝的优点是眼光更长远，因为它是在一棵完全长成的树上进行全局考察，通常能保留更多有用的分支，所以剪枝后模型的泛化性能往往优于预剪枝；缺点是计算开销大，同时需要先生成一棵完整的树，所以时间成本更高。

两种剪枝策略对比

对比项	预剪枝 (Pre-pruning)	后剪枝 (Post-pruning)
时机	决策树构建时进行，边建边剪。	决策树构建完成后进行，先建后剪。
优点	训练时间开销小，生成的树更简单。	泛化能力通常更强，不容易错过有潜力的划分，欠拟合风险小。
缺点	存在“短视”问题，可能因局部判断而过早停止，有欠拟合风险。	计算开销大，时间成本更高。

连续值与缺失值

目前为止我们讨论的例子，特征都是 离散值 (Categorical Values) ，但在现实学习任务重，数据往往包含了大量的 连续值 (Continuous Values) 。同时，数据也常常不完整，存在 缺失值 (Missing Values) 。一个完善的算法必须能够妥善处理这些情况。

连续值处理

对于连续的特征（如温度、长度等），我们无法像离散特征那样，为每个可能的值都创建一个分支。因为连续值的可能性有无穷多个。此时，可以使用 连续值离散化 (Discretization) 。其核心思想是，将连续特征转换为一个离散的二分特征。具体来说，就是寻找一个最优的 “切分点” (Split Point) ，将数据一分为二，比如将“温度”特征变为“温度 ≤ 24.5℃”和“温度 > 24.5℃”两个分支。

关于如何找到这个最优的切分点，C4.5算法提供了一个简单有效的方法：

排序：给定样本集 $D$ 和连续属性 $a$ ，假定 $a$ 在 $D$ 上出现了 $n$ 个不同的取值，将这些值从小到大进行排序。假设排序后的值为 ${a^1,a^2,\dots,a^n}$ ；
生成候选切分点 ：基于划分点 $t$ 可将 $D$ 分为 $D_t^-$ 和 $D_t^+$ 。显然对于相邻的属性取值 $a^i$ 与 $a^{i+1}$ 来说，$t$ 在区间 $[a^i, a^{i+1})$ 中取任意值所产生的划分结果相同。因此可以将每两个相邻值的中点作为候选切分点，此时可以得到包含 $n-1$ 个元素的候选切分点集合：
$$T_a = \left\{\frac{a^i + a^{i+1}}{2} | 1 \leq i \leq n-1 \right\}；$$
选择最优切分点 ：此时，像计算离散特征一样，我们可以计算每次二次划分的信息增益，从而得到最优切分点对应的划分
$$\begin{align*} \text{Gain}(D,a) &= \max_{t \in T_a} \text{Gain}(D,a,t) \\ &= \max_{t \in T_a} \text{Ent}(D) - \sum_{\lambda \in\{-,+\}}\frac{|D_t^{\lambda}|}{|D|} \text{Ent}(D_t^{\lambda}) \end{align*}$$
其中 $\text{Gain}(D,a,t)$ 是样本集 $D$ 基于划分点 $t$ 二分后的信息增益，于是我们就可以选择使 $\text{Gain}(D,a,t)$ 最大化的划分点。

缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失，我们需要解决两个问题：(1) 如何在属性值缺失的情况下进行划分属性选择？(2) 给定划分属性，若样本在该属性上的值缺失，该如何对样本进行划分？C4.5算法巧妙地解决了这个问题，主要分两步：

第一步：在计算信息增益时

假设特征 $A$ 有缺失值：

首先，忽略掉所有在特征 $A$ 上有缺失值的样本，得到一个无缺失的数据子集 $\widetilde{D}$ ；
只用这个无缺失子集 $\widetilde{D}$ 来正常计算特征 $A$ 的信息增益 $\text{Gain}(\widetilde{D},A)$；
最后，将计算出的信息增益乘以一个权重。这个权重就是 无缺失样本所占的比例。
例如，总共有100条数据，特征 A 在其中80条数据上没有缺失值，那么权重就是 80/100 = 0.8。最终特征 A 的信息增益就是 $0.8 \times \text{Gain}(\widetilde{D}, A)$ 。

这样做相当于对有缺失值的特征施加了一个“惩罚”，缺失值越多，它最终的信息增益就越低，被选中的概率也就越小。

第二步：在划分数据时

假设最终还是选择了有缺失值的特征 A 来进行划分（比如特征A有“取值1”和“取值2”两个分支）。那么，那条在特征 A 上有缺失值的样本该被分到哪个分支去呢？

C4.5的做法是，将这个缺失值样本按比例分配到所有的子节点中。这个比例，就是无缺失样本在各个分支中所占的比例。例如，在无缺失的样本中，有60%的样本被划入了“取值1”分支，40%被划入了“取值2”分支。那么，这个缺失值样本就会被赋予一个0.6的权重并划入“取值1”分支，同时被赋予一个0.4的权重并划入“取值2”分支。之后在子节点中继续计算信息熵时，这些带有权重的样本也会被相应地考虑进去。

总结

主要优缺点

优点

可解释性强：模型的结果易于理解和可视化，可以生成清晰的if-then规则，是典型的“白盒模型”。
数据准备要求低：通常无需对数据进行归一化或标准化，并且能同时处理数值型和类别型数据。
预测速度快：一旦决策树构建完成，对新样本的预测过程非常高效。

缺点

容易过拟合：若不加限制，决策树会倾向于完美拟合训练数据，导致泛化能力差，因此剪枝是必不可少的步骤。
不稳定性：训练数据中的微小变动可能会导致生成一棵完全不同的树。
贪心本质：决策树的生成过程是贪心的，在每一步都寻求局部最优解，但这并不能保证得到全局最优的树结构。
学习能力局限：决策树的划分边界与坐标轴平行，这使得它在学习某些具有对角线关系的数据时效率不高。

决策树在现代机器学习中的角色

尽管单个决策树存在上述缺点，但它依然是现代机器学习中极为重要的算法之一，因为它构成了许多强大**集成学习(Ensemble Learning)**模型的基础。

随机森林 (Random Forest)：通过构建大量的决策树，并让它们对结果进行“投票”，极大地克服了单个决策树不稳定的问题，是一种非常强大和流行的算法。
梯度提升决策树 (Gradient Boosted Decision Tree, GBDT)：通过迭代地构建决策树，每一棵新树都致力于修正前面所有树的残差。以GBDT为核心思想的XGBoost、LightGBM等算法，是当前在处理表格数据任务中最顶尖的算法之一。