决策树算法详解：信息熵、信息增益、Gini 系数与剪枝

决策树是一种可解释性较强的监督学习算法，可用于分类和回归。模型通过不断选择特征并划分数据，让同一叶子节点中的样本尽可能相似。

决策树如何工作

一棵分类树通常包含三类节点：

• 根节点：包含全部训练样本。
• 内部节点：根据某个特征和判断条件拆分数据。
• 叶子节点：给出最终类别或预测值。

训练的核心问题是：每一步应该选择哪个特征，才能让划分后的数据更“纯”。

信息熵

设数据集中共有 $K$ 个类别，第 $k$ 类所占比例为 $p_k$，信息熵为：

$$ H(D)=-\sum_{k=1}^{K}p_k\log_2p_k $$

当样本全部属于同一类别时，熵为 0；类别越混杂，熵通常越大。

某个特征 $A$ 带来的信息增益为：

$$ Gain(D,A)=H(D)-\sum_{v=1}^{V}\frac{|D_v|}{|D|}H(D_v) $$

信息增益越大，说明使用该特征划分后不确定性下降得越多。ID3 算法使用信息增益选择特征。

信息增益率

信息增益容易偏向取值数量较多的特征。C4.5 使用信息增益率进行修正：

$$ GainRatio(D,A)=\frac{Gain(D,A)}{IV(A)} $$

其中 $IV(A)$ 表示特征自身取值分布带来的固有信息。

Gini 系数

CART 分类树常使用 Gini 不纯度：

$$ Gini(D)=1-\sum_{k=1}^{K}p_k^2 $$

Gini 值越小，节点中的样本越集中于少数类别。二分类中，如果正样本比例为 $p$，则：

$$ Gini(D)=2p(1-p) $$

熵和 Gini 都用于衡量数据纯度，但计算形式不同，不能简单理解为完全相同。

回归树

回归树的叶子节点输出连续数值，通常使用均方误差选择划分点。一个常见做法是让左右子节点内部的平方误差之和最小：

$$ \sum_{x_i\in D_L}(y_i-\bar{y}L)^2+ \sum{x_i\in D_R}(y_i-\bar{y}_R)^2 $$

叶子节点预测值通常是该节点训练样本目标值的平均数。

如何防止过拟合

决策树不断分裂后很容易记住训练数据。常见控制方法包括：

• 限制树的最大深度。
• 限制叶子节点的最少样本数。
• 设置节点继续划分所需的最少样本数。
• 要求划分带来的纯度提升达到阈值。
• 先生成完整树，再通过验证集进行后剪枝。

决策树、随机森林和 XGBoost

随机森林通过训练多棵相互有差异的决策树，再对结果投票或取平均，以降低单棵树的方差。

XGBoost 属于梯度提升树。它按顺序添加弱学习器，让新树拟合前面模型尚未解释好的部分：

$$ \hat{y}i=\sum{t=1}^{T}f_t(x_i) $$

其中 $f_t$ 表示第 $t$ 棵树。XGBoost 还在目标函数中加入模型复杂度正则项，以控制过拟合。

小结

• ID3：主要使用信息增益。
• C4.5：主要使用信息增益率。
• CART：分类使用 Gini，回归常使用平方误差。
• 随机森林：并行训练多棵树后集成。
• XGBoost：按顺序进行梯度提升并加入正则化。