决策树模型

决策树是机器学习中最直观的一类模型。它不断提出类似“年龄是否小于 30”“收入是否大于某个阈值”的问题，把样本空间切分成越来越小的区域，最后在叶节点中给出预测结果。

它的优势是结构容易解释、能够处理非线性关系、几乎不需要特征缩放，并且可以自然地处理数值特征和类别特征。它的弱点也很鲜明：单棵深树很容易记住训练集，导致过拟合；当数据发生轻微变化时，树的上层分裂有时也会明显改变。

因此，理解决策树不能只停留在“画一棵树”。真正重要的问题是：每一步如何选择分裂、不同算法的指标有什么区别、树什么时候应该停止生长，以及已经长出的树如何剪枝。

1. 一棵决策树在做什么

设训练集为

\[\mathcal D=\{(\boldsymbol x_i,y_i)\}_{i=1}^{n},\]

其中 \(\boldsymbol x_i\) 是特征，\(y_i\) 是标签。决策树把特征空间划分成若干个互不重叠的区域 \(R_1,R_2,\ldots,R_M\)，并在每个区域中给出一个常数预测：

\[\hat f(\boldsymbol x)=\sum_{m=1}^{M}c_m\,\mathbf 1(\boldsymbol x\in R_m).\]

从这个角度看，决策树是一种分段常数模型。内部节点负责提出条件，分支表示条件的不同结果，叶节点保存预测值。

一棵树的预测过程可以写成：

从根节点开始
    根据当前节点的分裂条件选择一条分支
    如果到达叶节点，返回叶节点中的预测值
    否则继续向下判断

例如，一个二分类树可能长成这样：

图中每个内部节点都是一次分裂判断，叶节点则给出最终的分类结果。训练时，算法会在候选特征和候选阈值中选择能够最大程度降低不纯度的分裂。

树的训练就是在所有候选问题中，找出一个能够让子节点“更纯”的问题，然后在每个子节点中重复这个过程。

2. 贪心分裂的统一形式

设当前节点包含样本集合 \(S\)，候选分裂把它分成 \(S_1,S_2,\ldots,S_K\)。令 \(I(S)\) 表示节点的不纯度，那么这个分裂带来的不纯度下降为

\[\Delta I =I(S)-\sum_{k=1}^{K}\frac{|S_k|}{|S|}I(S_k).\]

算法选择使 \(\Delta I\) 最大的特征和切分点：

\[(j^*,t^*) =\operatorname*{argmax}_{j,t}\Delta I(j,t).\]

这里的 \(I\) 取什么形式，就决定了树的具体算法：

算法或任务	常用不纯度/目标	典型分裂形式
ID3 分类	熵、信息增益	类别特征多叉分裂
C4.5 分类	熵、信息增益率	类别特征可多叉，数值特征二叉
CART 分类	Gini 指数	始终二叉分裂
CART 回归	方差、平方误差	始终二叉分裂
Boosting 树	梯度和二阶梯度带来的损失下降	由目标函数决定

这种分裂是“贪心”的：当前节点只选择眼下最好的切分，并不穷举所有可能的完整树。因此，训练速度较快，但不保证得到全局最优的树结构。

3. 分类树的分裂指标

3.1 熵与信息增益

如果一个节点中有 \(K\) 个类别，类别 \(k\) 的比例为 \(p_k\)，则熵为

\[H(S)=-\sum_{k=1}^{K}p_k\log_2p_k.\]

约定 \(0\log 0=0\)。当节点中的样本全部属于同一类时，熵为 0；当各类均匀分布时，熵最大。

对于特征 \(A\) 的一个分裂，信息增益为

\[\operatorname{Gain}(S,A) =H(S)-\sum_{v\in\operatorname{Values}(A)} \frac{|S_v|}{|S|}H(S_v).\]

信息增益越大，说明分裂后剩余的不确定性越小。ID3 直接选择信息增益最大的特征。

例如，当前节点中正负样本各占一半，分裂前熵为 1。如果某次分裂后两个子节点都只包含单一类别，那么分裂后的加权熵为 0，信息增益就是 1。

3.2 信息增益的缺点

信息增益偏爱取值很多的特征。假设有一个“样本编号”特征，每个样本的编号都不同，那么按照编号切分后，每个叶节点都可能只剩一个样本，熵会降到 0，但这只是记住了训练数据，并没有学到可泛化的规律。

这也是 ID3 容易过拟合的重要原因之一。

3.3 信息增益率与 C4.5

C4.5 用分裂信息修正信息增益。先定义

\[\operatorname{SplitInfo}(S,A) =-\sum_v\frac{|S_v|}{|S|} \log_2\frac{|S_v|}{|S|},\]

再定义信息增益率

\[\operatorname{GainRatio}(S,A) =\frac{\operatorname{Gain}(S,A)}{\operatorname{SplitInfo}(S,A)}.\]

分裂得越细，分裂信息通常越大，因此信息增益率会惩罚把数据切成很多小块的特征。

实际的 C4.5 通常不会在所有特征中直接选择增益率最大者，而是先筛掉信息增益低于平均水平的候选特征，再从剩下的特征中选择增益率较高者。这样可以减轻增益率在分母很小时产生异常大值的问题。

3.4 Gini 指数与 CART

Gini 指数定义为

\[Gini(S)=1-\sum_{k=1}^{K}p_k^2.\]

它也可以理解为：从节点中随机抽取一个样本，并按照节点中的类别比例随机预测，预测错误的概率。

二分类情况下，如果正类比例为 \(p\)，则

\[Gini(S)=1-p^2-(1-p)^2=2p(1-p).\]

当 \(p=0\) 或 \(p=1\) 时，节点最纯，Gini 为 0；当 \(p=0.5\) 时，Gini 最大。

CART 分类树选择使加权 Gini 最小、或者 Gini 下降最大的分裂：

\[\Delta Gini =Gini(S)-\sum_{k=1}^{2}\frac{|S_k|}{|S|}Gini(S_k).\]

与 ID3 的多叉分裂不同，CART 每次都只产生两个子节点。这让树的结构更统一，也方便后续进行代价复杂度剪枝。

3.5 分类错误率

节点中用多数类作为预测时，分类错误率为

\[Error(S)=1-\max_k p_k.\]

它很容易理解，但在节点还没有很纯时不够敏感。例如，类别比例从 \((0.51,0.49)\) 变为 \((0.60,0.40)\)，错误率只下降了 \(0.09\)；熵和 Gini 对这种变化的反映通常更平滑。因此，分类错误率更常用于剪枝评估或最终解释，而不是作为常规的生长指标。

4. 回归树的分裂指标

回归树的叶节点不再保存一个类别，而是保存一个数值。对于平方误差损失，叶节点的最优预测值是该叶中样本的均值：

\[\hat c_m=\frac{1}{|R_m|}\sum_{\boldsymbol x_i\in R_m}y_i.\]

4.1 均方误差与方差下降

节点 \(S\) 的均方误差可以写成

\[MSE(S)=\frac{1}{|S|}\sum_{i\in S}(y_i-\bar y_S)^2,\]

其中 \(\bar y_S\) 是节点内目标值的均值。候选分裂的加权误差为

\[MSE_{split} =\sum_{k=1}^{K}\frac{|S_k|}{|S|}MSE(S_k).\]

算法选择让这个值最小的分裂。等价地，也可以比较平方误差和的下降：

\[SSE(S)=\sum_{i\in S}(y_i-\bar y_S)^2.\]

4.2 MAE、Huber 与分位数回归树

如果目标值中存在异常值，平方误差会对大残差施加过重惩罚。使用绝对误差时，叶节点的最优预测值变成中位数：

\[\hat c_m=\operatorname{median}\{y_i:\boldsymbol x_i\in R_m\}.\]

一些实现还支持 Huber 损失，它在残差较小时近似平方损失，在残差较大时近似绝对损失；分位数回归树则让叶节点预测某个条件分位数，适合构造预测区间或处理不对称的业务损失。

5. 数值特征、类别特征和缺失值

5.1 连续特征的切分

对数值特征 \(x_j\)，树通常先将不同取值排序，再只考虑相邻取值之间的候选阈值。例如特征取值为 \(2,5,8\)，候选阈值可以是

\[t_1=3.5,\qquad t_2=6.5.\]

每个阈值产生二叉分裂：

\[S_{left}=\{i:x_{ij}\le t\},\qquad S_{right}=\{i:x_{ij}>t\}.\]

实际实现通常只在相邻样本标签发生变化或目标统计发生变化的位置重点搜索，以减少计算量。

5.2 类别特征的处理

类别特征有多种处理方式：

• ID3 可以按类别取值进行多叉分裂。
• C4.5 也可以进行多叉分裂，并且通过增益率降低高基数特征的偏好。
• CART 需要二叉分裂，可以把类别集合分成两组，例如 {北京, 上海} 与 {广州, 深圳}。
• 许多工程实现会先把类别特征做独热编码，再交给普通数值树。
• CatBoost 会利用有序目标统计等方法直接处理高基数类别特征。

独热编码会增加特征数量，但实现简单；直接枚举类别子集可能很昂贵，且容易产生过拟合。选择哪种方式，需要结合类别数量、样本量和使用的树模型。

5.3 缺失值

常见的缺失值处理方式有：训练前填充、把缺失作为一个特殊类别、在每个节点学习缺失样本应该走左支还是右支，以及给样本分配多个分支的权重。

XGBoost 会在训练时为每个分裂学习默认方向；LightGBM 也会为缺失值保留默认路径。需要注意的是，“树可以处理缺失值”并不意味着所有库都以相同方式处理，训练和预测阶段的缺失规则必须保持一致。

6. ID3、C4.5 与 CART

6.1 ID3

ID3 是较早的决策树算法，核心步骤是：

1. 计算当前节点的熵。
2. 对每个候选类别特征计算信息增益。
3. 选择信息增益最大的特征进行多叉分裂。
4. 对每个子节点递归执行上述过程。

ID3 适合教学和理解信息增益，但原始形式存在几个限制：只处理离散特征、偏爱取值多的特征、对缺失值处理不完整，并且没有完善的剪枝机制。

6.2 C4.5

C4.5 可以看作对 ID3 的重要改进：

• 用信息增益率缓解高基数特征偏好。
• 通过阈值处理连续特征。
• 支持缺失值和样本权重。
• 可以把树转换成规则，便于阅读和化简。
• 使用基于误差估计的后剪枝降低过拟合。

C4.5 的多叉结构通常更接近原始类别语义，但树可能变得宽而复杂。工程实践中，C4.5 的思想仍然体现在许多树模型的分裂和剪枝设计中。

6.3 CART

CART，即 Classification and Regression Tree，同时支持分类与回归：

• 分类通常使用 Gini 指数。
• 回归通常使用平方误差或其他损失。
• 每次分裂都是二叉分裂。
• 使用代价复杂度剪枝生成一系列子树。

CART 的二叉结构非常适合递归实现，也是随机森林、GBDT 以及许多现代树模型的重要基础。

三者可以这样记忆：

维度	ID3	C4.5	CART
主要指标	信息增益	信息增益率	Gini/平方误差
分裂方式	多叉	多叉或二叉	二叉
连续特征	原始形式不支持	支持	支持
回归	不支持	原始形式不以回归为主	支持
剪枝	较弱	支持	代价复杂度剪枝

7. 其他常见的树模型

“决策树模型”在实际工作中通常也包括以树为基本学习器的集成方法。它们不再只训练一棵树，而是通过多棵树降低方差或偏差。

7.1 决策树桩

决策树桩只有一层分裂。它本身表达能力很弱，但作为弱学习器非常有用，尤其常见于 AdaBoost。树桩的优点是简单、稳定、训练快；缺点是只能表达非常有限的决策边界。

7.2 随机森林

随机森林使用 Bagging 思想训练多棵树：每棵树从训练集进行有放回抽样，同时在每个节点只随机选择一部分特征参与分裂。最终分类采用多数投票，回归采用平均：

\[\hat f_{RF}(\boldsymbol x) =\frac{1}{B}\sum_{b=1}^{B}\hat f_b(\boldsymbol x).\]

随机抽样和随机选特征会降低树之间的相关性。单棵深树的方差很大，但把许多相关性较低的树平均起来，整体方差会下降。

随机森林的特点：

• 对特征缩放不敏感。
• 能处理复杂的非线性和特征交互。
• 通常不需要像单棵树一样精细剪枝。
• 可以用袋外样本估计泛化误差。
• 特征重要性可能偏爱取值多或连续的特征，最好配合置换重要性或 SHAP。

7.3 ExtraTrees

ExtraTrees，也叫 Extremely Randomized Trees，比随机森林引入更强的随机性。它通常不仅随机选择特征，还随机生成候选切分点，再从候选中选择较好的切分。

随机性更强可能进一步降低树之间的相关性，训练也可能更快，但单棵树的分裂质量会下降。随机森林和 ExtraTrees 没有绝对优劣，应该通过验证集比较。

7.4 AdaBoost

AdaBoost 依次训练弱树，每一轮提高前一轮被错误分类样本的权重。分类时对各棵树进行加权投票：

\[F(x)=\operatorname{sign}\left( \sum_{m=1}^{M}\alpha_m h_m(x) \right),\]

其中 \(h_m\) 是第 \(m\) 棵弱树，\(\alpha_m\) 与该树的错误率有关。

AdaBoost 主要通过逐步降低训练误差来减少偏差，对噪声和异常值可能比较敏感。实践中常使用深度为 1 到 3 的浅树。

7.5 GBDT

梯度提升决策树不是对数据做并行平均，而是让后面的树拟合前面模型的残差或负梯度。设当前模型为 \(F_{m-1}(x)\)，新的树 \(h_m(x)\) 近似损失函数对当前预测的负梯度：

\[r_{im}=-\left[ \frac{\partial L(y_i,F(x_i))}{\partial F(x_i)} \right]_{F=F_{m-1}}.\]

然后更新：

\[F_m(x)=F_{m-1}(x)+\eta h_m(x),\]

其中 \(\eta\) 是学习率。学习率越小，通常需要更多树，但模型可能更容易获得较好的泛化性能。

7.6 XGBoost

XGBoost 在 GBDT 基础上加入了正则化、二阶梯度、缺失值默认方向和高效工程实现。它在第 \(t\) 轮优化近似目标：

\[\mathcal L^{(t)} \simeq \sum_{i=1}^{n} \left[g_i f_t(x_i)+\frac12 h_i f_t^2(x_i)\right] +\Omega(f_t),\]

其中 \(g_i\) 和 \(h_i\) 分别是一阶、二阶梯度，\(f_t\) 是当前要添加的树，\(\Omega\) 用来惩罚树的复杂度。常见复杂度项可以包含叶节点数量和叶权重平方：

\[\Omega(f)=\gamma T+\frac12\lambda\sum_{j=1}^{T}w_j^2.\]

XGBoost 的重要参数包括 n_estimators、max_depth、learning_rate、subsample、colsample_bytree、min_child_weight、gamma 和 reg_lambda。

7.7 LightGBM

LightGBM 主要使用基于直方图的分裂搜索，把连续特征离散到有限个桶中，从而降低内存和计算开销。它常使用按叶节点生长的策略：每次选择当前增益最大的叶子继续分裂。

叶子优先通常能更快降低训练误差，但如果不限制 num_leaves、max_depth 和 min_data_in_leaf，更容易过拟合。LightGBM 还使用 GOSS、EFB 等技术提升大规模数据上的效率。

7.8 CatBoost

CatBoost 特别重视类别特征和目标泄漏问题。它使用有序目标统计与有序提升，尽量避免在计算类别统计时直接使用当前样本标签造成泄漏。

CatBoost 对类别特征较多的数据往往很方便，通常不需要手工进行大规模独热编码。它仍然需要通过深度、学习率、迭代次数、正则化和早停来控制复杂度。

8. 什么时候停止生长

如果不设置限制，树会不断切分，直到叶节点中只剩很少样本，甚至每个训练样本都有自己的叶节点。训练误差可能降到接近 0，但测试误差反而变大。

常见的预剪枝条件包括：

• max_depth：限制最大深度。
• min_samples_split：节点至少有多少样本才允许继续分裂。
• min_samples_leaf：每个叶节点至少保留多少样本。
• max_leaf_nodes：限制叶节点总数。
• min_impurity_decrease：只有不纯度下降达到阈值才分裂。
• max_features：每次分裂最多考虑多少特征。
• Boosting 中的 learning_rate 和树的数量：共同控制每棵树的贡献。

预剪枝速度快，但停止条件是在局部节点上决定的，可能会过早停止。后剪枝则先长出较大的树，再根据验证误差或复杂度删掉不必要的分支，通常更加灵活。

9. 后剪枝与代价复杂度

9.1 reduced-error pruning

减少错误剪枝的做法是准备一份验证集，从树的底部开始尝试把某个子树替换成叶节点：

1. 用当前子树在验证集上计算误差。
2. 把整个子树替换为一个叶节点，叶节点预测该区域的多数类或均值。
3. 如果验证误差没有明显变差，就保留剪枝。
4. 反复进行，直到没有可剪分支。

这种方法直观，但需要额外的验证数据。

9.2 CART 的代价复杂度剪枝

对一棵树 \(T\)，令 \(R(T)\) 表示经验风险，\(|\mathcal L(T)|\) 表示叶节点数。代价复杂度目标为

\[R_\alpha(T)=R(T)+\alpha|\mathcal L(T)|,\]

其中 \(\alpha\ge 0\) 是复杂度参数。第一项希望拟合数据，第二项惩罚树过于复杂。

当 \(\alpha=0\) 时，模型倾向于保留大树；随着 \(\alpha\) 增大，更多分支会被删除，最终可能只剩根节点。

对内部节点 \(t\) 及其子树 \(T_t\)，可以比较：

\[g(t)=\frac{R(t)-R(T_t)}{|\mathcal L(T_t)|-1}.\]

它表示保留这棵子树每增加一个叶节点所带来的风险下降。当某个分支的收益最小，就优先剪掉它。这样可以生成一系列嵌套子树，再通过交叉验证选择合适的 \(\alpha\)。

10. 训练代码示例

下面用 scikit-learn 展示分类树、回归树和代价复杂度剪枝。真正项目中应该把预处理、模型和交叉验证放进同一个流程，避免验证集信息泄漏。

10.1 分类树

from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.metrics import accuracy_score, classification_report

X, y = load_breast_cancer(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, stratify=y, random_state=42
)

tree = DecisionTreeClassifier(
    criterion="gini",       # 也可以使用 "entropy" 或 "log_loss"
    max_depth=5,
    min_samples_leaf=4,
    class_weight="balanced",
    random_state=42,
)
tree.fit(X_train, y_train)

pred = tree.predict(X_test)
print("accuracy:", accuracy_score(y_test, pred))
print(classification_report(y_test, pred))

类别不平衡时，不能只看 accuracy。还应该观察 precision、recall、F1、ROC-AUC 或业务真正关心的代价，并考虑 class_weight="balanced" 或样本权重。

10.2 回归树

from sklearn.datasets import load_diabetes
from sklearn.model_selection import train_test_split
from sklearn.tree import DecisionTreeRegressor
from sklearn.metrics import mean_absolute_error, mean_squared_error

X, y = load_diabetes(return_X_y=True)
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42
)

tree = DecisionTreeRegressor(
    criterion="squared_error",
    max_depth=5,
    min_samples_leaf=5,
    random_state=42,
)
tree.fit(X_train, y_train)

pred = tree.predict(X_test)
print("MAE:", mean_absolute_error(y_test, pred))
print("RMSE:", mean_squared_error(y_test, pred) ** 0.5)

10.3 用交叉验证选择剪枝参数

对于 sklearn 的 CART，可以先得到不同复杂度参数对应的剪枝路径：

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score

base_tree = DecisionTreeClassifier(random_state=42)
path = base_tree.cost_complexity_pruning_path(X_train, y_train)

best_alpha = None
best_score = float("-inf")

for alpha in path.ccp_alphas:
    candidate = DecisionTreeClassifier(
        random_state=42,
        ccp_alpha=alpha,
        min_samples_leaf=3,
    )
    score = cross_val_score(
        candidate, X_train, y_train, cv=5, scoring="roc_auc"
    ).mean()
    if score > best_score:
        best_score = score
        best_alpha = alpha

pruned_tree = DecisionTreeClassifier(
    random_state=42,
    ccp_alpha=best_alpha,
    min_samples_leaf=3,
)
pruned_tree.fit(X_train, y_train)

剪枝参数也应该只通过训练集内部的交叉验证选择，最后再用从未参与选择的测试集进行一次评估。

11. 特征重要性与可解释性

决策树经常被称为可解释模型，但“能画出来”不代表解释一定可靠。

11.1 路径解释

对单个样本，可以沿着根到叶的路径查看：

收入 <= 8000
信用评分 > 650
年龄 <= 35
=> 预测为低风险

这能说明模型对该样本作出决定时使用了哪些局部条件。

11.2 不纯度重要性

很多实现会把某特征参与分裂所带来的不纯度下降加总，作为特征重要性：

\[Importance(j) =\sum_{t\text{ 使用特征 }j} \frac{|S_t|}{|S|}\Delta I_t.\]

它计算快，但会偏爱取值多的类别特征和连续特征，也可能把强相关特征的作用分散或集中到其中一个特征上。

11.3 置换重要性与 SHAP

置换重要性是在验证集上随机打乱某个特征，再观察性能下降多少。它更接近“该特征对当前预测性能的贡献”，但对强相关特征仍需要谨慎解释。

SHAP 则从合作博弈的角度把一次预测分解为基线值加上各特征贡献，适合分析单个样本和整体特征影响。不过 SHAP 的结果依赖背景数据和模型假设，不能把图上的排序直接理解成因果关系。

12. 决策树为什么会过拟合

单棵树的表达能力随着深度快速增加。树越深，能够描述越细的区域，也越容易把噪声当成规律。常见表现包括：

• 训练准确率接近 100%，验证准确率明显较低。
• 叶节点样本数过少。
• 特征重要性在不同抽样数据上变化很大。
• 树的上层分裂对少量样本变化非常敏感。
• 回归树出现大量阶梯状预测和极端局部值。

可以用以下顺序处理：

1. 先划分训练、验证和测试数据，确认问题确实是过拟合。
2. 限制 max_depth，增加 min_samples_leaf。
3. 使用交叉验证选择剪枝参数或树的数量。
4. 对随机森林使用特征采样和样本采样降低相关性。
5. 对 GBDT、XGBoost、LightGBM 和 CatBoost 使用学习率、早停、子采样与正则化。
6. 检查数据泄漏、异常标签和时间切分是否正确。

13. 什么时候使用哪种树

场景	可以优先考虑
需要一个容易展示的规则模型	浅层 CART 或剪枝后的决策树
特征数量不多、关系明显非线性	决策树、随机森林
希望获得稳定的强基线	随机森林、ExtraTrees
表格数据，追求预测效果	GBDT、XGBoost、LightGBM、CatBoost
类别特征很多	CatBoost，或经过合理编码的树模型
样本量很大、训练效率重要	LightGBM、XGBoost
噪声较多且希望降低方差	随机森林、ExtraTrees，并限制树深
需要概率预测	校准后的树模型或集成模型

需要注意，树模型通常不需要标准化。把特征从米转换为厘米，只会改变候选阈值的数值，不会改变样本的排序，因此不会像距离模型和梯度模型那样强依赖尺度。不过，标准化仍然可能是统一预处理流程的一部分，只是通常不是树模型的必要条件。

14. 总结

决策树的核心可以浓缩成三句话：

1. 用分裂把样本划分成更纯的子节点。
2. 用叶节点中的多数类、均值、中位数或其他最优常数给出预测。
3. 用停止条件、后剪枝或多棵树的集成控制复杂度。

ID3 让我们理解信息增益，C4.5 解决高基数特征和连续特征问题，CART 提供统一的二叉分类与回归框架。随机森林通过平均降低方差，Boosting 通过逐步修正残差降低偏差，而 XGBoost、LightGBM、CatBoost 则在目标函数、缺失值、类别特征和工程效率上继续改进。

真正使用决策树时，指标本身只是开始。树深、叶节点最小样本数、学习率、树数量、剪枝强度、验证方式和评估指标，往往共同决定了模型能否从“把训练集切得很漂亮”走向“在新数据上也可靠”。