决策树

一个人去看医生，医生问：你发烧吗？是的。咳嗽吗？是的。呼吸困难吗？不。那么，可能是普通支气管炎。

这就是决策树的工作模式：通过一系列有序的问题，逐步将问题缩小到一个答案。它是最接近人类直觉推理的机器学习模型。

决策树由 Ross Quinlan 在 1986 年提出 ID3 算法系统化，随后发展出 C4.5（1993）和 C5.0。与此同时，Leo Breiman 等人在 1984 年独立提出了 CART（Classification and Regression Trees）框架。如今，在随机森林和梯度提升树（XGBoost）中，决策树作为基础学习器，仍是结构化数据上最强大的工具之一。

树的结构#

决策树是一棵二叉树（或多叉树），由以下节点构成：

• 内部节点（Internal Node）：包含一个特征和一个分裂条件（如"年龄 > 30？"）
• 分支（Branch）：每个内部节点引出两个（或更多）分支，对应条件的不同结果
• 叶节点（Leaf Node）：最终的预测结果（分类标签或回归值）

预测过程：从根节点出发，根据样本的特征值沿分支向下，直到到达叶节点，返回其对应的预测值。

决策树的可解释性极强——可以直接打印成 if-else 规则，这是神经网络等"黑盒"模型无法比拟的优点，在医疗、法律、金融等需要可解释性的场景尤为重要。

如何选择最优分裂？#

构建决策树的核心问题：在每个节点，选择哪个特征、哪个阈值进行分裂？

目标：选择使子节点"更纯"（更均匀）的分裂，减少预测的不确定性。

信息增益与熵（ID3/C4.5）#

熵（Entropy）度量一个节点的"不纯度"：

$$H(S) = -\sum_{c} p_c \log_2 p_c$$

$p_c$ 是类别 $c$ 在样本集 $S$ 中的比例。若所有样本属于同一类，$H = 0$（完全纯）；若各类均匀分布，$H$ 最大。

信息增益（Information Gain）：分裂后的熵减少量：

$$\text{IG}(S, A) = H(S) - \sum_{v} \frac{|S_v|}{|S|} H(S_v)$$

其中 $S_v$ 是特征 $A$ 取值为 $v$ 时的子集。ID3 选择最大化信息增益的特征分裂。

信息增益率（Information Gain Ratio，C4.5）：信息增益除以特征自身的熵，修正 ID3 倾向于选择取值多的特征的偏差。

基尼不纯度（CART）#

CART 用基尼不纯度（Gini Impurity）而非熵：

$$\text{Gini}(S) = 1 - \sum_{c} p_c^2$$

基尼不纯度和熵在数值上非常接近，但计算更简单（无需对数运算）。CART 始终产生二叉树（每次分裂成两个子集）。

熵还是基尼？选择背后的逻辑#

实践中，熵和基尼不纯度给出的树几乎总是高度相似——两者都是不纯度的凹函数，都在纯节点取 0、在类别均匀分布时取最大，曲线形状相差无几。真正影响结果的差别在别处。

• 计算成本：熵需要逐样本算对数，基尼只需乘法和减法。在 1980 年代这有实际意义；今天的硬件上差别可以忽略。
• 分裂方式的差异比准则的差异更重要。C4.5 允许多路分裂（一个取值一个分支），CART 只做二叉分裂。多路分裂一次就把数据切成很多份，每个子节点的样本量骤降，后续分裂的统计可靠性随之崩坏——这被称为数据碎片（Data Fragmentation）问题。C4.5 引入信息增益率的深层动机也正在此：取值极多的特征（如"客户编号"）可以一路切到每个叶节点只剩一个样本，信息增益漂亮，泛化能力为零。
• 准则不是瓶颈：决定树质量的主要是停止条件与剪枝策略，而不是选熵还是选基尼。工程上的常见做法是默认基尼，把调参精力留给剪枝与集成。

过拟合与剪枝#

决策树容易过拟合：若允许树无限生长，最终每个叶节点只有一个训练样本，训练误差为 0，但泛化能力极差。

预剪枝（Pre-pruning）：在生长过程中提前停止。停止条件： - 当前节点样本数少于阈值（如少于 20 个样本） - 信息增益小于阈值 - 树深度达到上限

后剪枝（Post-pruning）：先让树充分生长，再从底向上剪去不必要的子树：

代价复杂度剪枝（Cost-Complexity Pruning，CART）：给训练误差加上一项复杂度惩罚，把目标改为最小化

$$R_\alpha(T) = R(T) + \alpha \cdot |T|$$

$R(T)$ 是树的训练误差，$|T|$ 是叶节点数，$\alpha$ 控制"每多一个叶节点要付多少代价"。$\alpha = 0$ 时最优解是完全生长的树；$\alpha$ 足够大时最优解退化为单个根节点。

CART 的精妙之处在于不直接搜索 $\alpha$，而是做最弱链接剪枝（Weakest-Link Pruning）：对每个内部节点计算"剪掉这棵子树后误差上升多少、换来叶节点减少几个"，即每片叶子的边际误差代价 $\alpha_{\text{eff}}$。从 $\alpha_{\text{eff}}$ 最小的子树开始剪，一路剪到根，得到一个嵌套的子树序列 $T0 \supset T1 \supset \cdots \supset \{\text{根}\}$，每个 $\alpha$ 区间恰好对应序列中的一棵树。最后用交叉验证在这个序列里挑泛化误差最小的那棵。

为什么从"最弱"开始剪？因为单位叶节点误差代价最小的分支，恰恰是训练数据支撑最弱的分支——它只对极少样本的预测有影响，保留它主要是在拟合噪声。

规约误差剪枝（Reduced Error Pruning，Quinlan）：在验证集上，若删除某子树后误差不增加，则剪去。

工程实现的关键细节#

教科书里的决策树算法只有几行，但高效实现有几个不平凡的细节。

连续特征的阈值搜索：对"收入"这类连续特征找最优切点，朴素做法是逐候选阈值扫描、每次重算不纯度。高效做法是先按该特征排序（$O(n \log n)$），再一次线性扫描——在有序序列上，相邻候选切点的不纯度可以由前一个切点的统计量增量更新，避免每个切点都全量重算。

缺失值处理：CART 用代理分裂（Surrogate Splits）——为主分裂特征预先找好几个"替身"特征（分裂结果与主分裂最接近的），样本缺主特征值时用替身分流。C4.5 则用分数样本：缺失样本按各分支已知样本的比例加权，同时进入多个分支。

类别特征的高基数问题：有 $m$ 个取值的类别特征，二叉分裂共有 $2^{m-1} - 1$ 种分法，穷举不可行。CART 证明了一个有用的捷径：对二分类问题，把类别按"该类别下正样本的比例"排序后，最优分裂一定出现在排序序列的某个切点上，$m$ 次比较即可，不必穷举。

回归树#

CART 框架不仅用于分类，也用于回归：叶节点输出连续值（预测目标的均值）。

分裂准则改为最小化方差（MSE，均方误差）而非熵/基尼。

回归树可以拟合任意分段线性函数——增大叶节点数量，可以以任意精度逼近连续函数。

从单棵树到集成学习#

单棵决策树有两大缺陷： 1. 高方差：对训练数据的小变动敏感，容易过拟合 2. 不稳定性：稍微改变训练数据，树的结构可能完全不同

这两点其实是同一枚硬币的两面，用偏差-方差分解（Bias-Variance Decomposition）看得最清楚：充分生长的深树偏差很低（它能拟合任意复杂的边界），但方差极高。根源在于树的学习过程是"贪心加离散"的——每次分裂都是一次不可撤销的硬决策，根节点附近的微小变化沿路径层层放大，整棵树的形状随之改写。这就是为什么单棵树的预测方差在常见模型里几乎是最高的。

集成能起效，靠的是一个简单的统计事实：对 $B$ 个方差为 $\sigma^2$、两两相关系数为 $\rho$ 的预测取平均，方差变成

$$\rho\,\sigma^2 + \frac{1-\rho}{B}\,\sigma^2$$

增加树的数量 $B$ 只能消掉第二项；第一项由树之间的相关性 $\rho$ 决定，加再多树也降不下去。所以集成的真正杠杆有两个：多种树（压低含 $B$ 的项），以及让树彼此不同（压低 $\rho$）——Bagging 的自助采样和随机森林的特征随机化，目标都是后者。

集成学习（Ensemble Learning）用多棵树解决这些问题：

随机森林（Random Forest，Breiman 2001）#

训练：用 $B$ 次 Bootstrap 抽样，每次有放回地抽取原训练集大小的样本，训练 $B$ 棵决策树。每次分裂时，随机选取 $\sqrt{p}$ 个特征（$p$ 为总特征数），只在这些特征中找最优分裂。

预测：分类——多数投票；回归——均值。

随机森林通过两种随机化降低了各棵树之间的相关性，大幅减少方差，几乎不过拟合（增加树的数量通常只会提高性能，不会过拟合）。

特征重要性：随机森林附带"免费"的特征重要性评估——基于每个特征在分裂时平均减少的不纯度。

梯度提升树（Gradient Boosting Trees，Friedman 2001）#

与随机森林的并行集成（Bagging）不同，梯度提升是串行集成（Boosting）：每棵新树专门拟合前一棵树的残差（误差），逐步修正。

$$F_m(x) = F_{m-1}(x) + \eta \cdot h_m(x)$$

$h_m$ 是拟合残差的新树，$\eta$ 是学习率。

XGBoost（Chen & Guestrin，2016 KDD Best Paper）是梯度提升树的工程实现，加入正则化、列采样、缓存优化等，在结构化数据竞赛中统治多年，被称为"数据科学竞赛的神器"。

LightGBM（微软，2017）和CatBoost（Yandex，2017）是更快的替代实现，针对大规模数据和类别特征做了专门优化。

决策树的可解释性与 GDPR#

决策树的可解释性在监管合规中极为重要。

欧盟 GDPR（2018）引入了"解释权"——用户有权要求对自动决策过程作出解释。

神经网络等黑盒模型难以满足这一要求，而决策树可以直接导出"因为你的年收入低于 5 万且信用评分低于 650，所以拒绝贷款申请"这样的规则。

在医疗诊断、刑事司法（假释决定）、银行贷款审核等高风险场景，决策树（或树的集成配合 SHAP/LIME 等解释工具）是合规性要求下的首选模型。

跨域连接#

• 统计学：单棵深树几乎无偏而方差极大，训练数据挪动一点，分裂点就换位置、整棵树的形状随之改变。不稳定性不是纯粹的缺陷而是可利用的性质——正因为树对扰动敏感，重采样得到的树之间才足够不相关，平均之后方差才降得下来。剪枝走的是另一条路：主动加偏差换方差，代价是牺牲对细结构的拟合。
• 随机森林：把一个高方差学习器变成低方差集成，靠的是让树之间的误差尽量不相关。这条假设是可以被违反的：所有树都用同一批强特征分裂时，它们会一起犯同样的错，加树只是把相同的偏差重复许多遍。每次分裂随机选特征这一步不是为了加速，正是为了强制去相关。
• 临床诊断：分诊流程与诊断标准本身就是人工构造的树。差别在阈值从哪里来：专家树的切点来自共识与安全裕度，学出来的树的切点来自训练人群的分布，因而绑定了那个人群的患病率。同一棵树换一家医院，阳性预测值会变而树的结构看不出来——这是校准问题，不是准确率问题。
• 生命之树与系统发育：两种树的方向相反。这里的树是被设计出来的判别流程，节点是问题；系统发育树是被推断的历史，节点是共同祖先。把分类准确当成历史真实是常见越界——一份能把物种分对的检索表，完全可以按与演化无关的性状分裂，比如按野外可观察性而不是按信息增益选特征。
• 人工智能治理与监控：当自动决策必须给出理由时，模型选择就不再只是精度问题。但要区分两种可解释性：树能直接导出一条判决规则，属于机制可见；事后归因方法给出的是对黑箱的近似解释。两者在能否被复核、能否被申诉上完全不同，条款写的是哪一种，直接决定哪些模型出局。

参考文献#

• Quinlan, J.R. "Induction of Decision Trees." Machine Learning 1(1), 1986.
• Breiman, L. et al. Classification and Regression Trees (CART). Chapman & Hall, 1984.
• Breiman, L. "Random Forests." Machine Learning 45(1), 2001.
• Chen, T. & Guestrin, C. "XGBoost: A Scalable Tree Boosting System." KDD, 2016.
• Friedman, J.H. "Greedy Function Approximation: A Gradient Boosting Machine." Annals of Statistics 29(5), 2001.