决策树 (Decision Tree)

概述

决策树 (Decision Tree) 是机器学习中最基础、最直观的模型之一。它的核心思想非常简单：通过一系列 if-then 规则将数据不断划分，最终做出预测。决策树既可以用于分类 (Classification Tree) 也可以用于回归 (Regression Tree, 简称 CART)。

A decision tree is a flowchart-like structure where each internal node represents a “test” on a feature, each branch represents the outcome of the test, and each leaf node represents a class label (classification) or a continuous value (regression). It is the foundation of ensemble methods like Random Forest and Gradient Boosting.

直观理解

想象你在教一个从未见过水果的人区分苹果和橙子：

问题1: 颜色是红色的吗？
├── 是 → 问题2: 直径大于7cm吗？
│        ├── 是 → 苹果
│        └── 否 → 樱桃
└── 否 → 问题3: 颜色是橙色的吗？
         ├── 是 → 橙子
         └── 否 → 问题4: 形状是细长的吗？
                  ├── 是 → 香蕉
                  └── 否 → 梨

这就是一棵决策树。每个问题是一个节点，每个答案是一个分支，最终的水果名称是叶子节点的预测结果。

决策树的三要素

1. 特征选择 (选择哪个特征来分裂)

决策树在每个节点需要选择一个”最好”的特征来划分数据。衡量”好”的标准有：

信息增益 (Information Gain) — ID3 算法

信息增益 = 划分前的熵 - 划分后的加权熵
IG(D, A) = H(D) - Σ(|D_v|/|D|) · H(D_v)

熵 (Entropy) 衡量数据的”混乱程度”：

H(D) = -Σ p_k · log₂(p_k)

熵越小，数据越纯 (同一类)
熵越大，数据越混乱 (各类混合)

信息增益率 (Gain Ratio) — C4.5 算法

Gain_Ratio(D, A) = IG(D, A) / H_A(D)

解决信息增益偏向取值较多的特征的问题。

基尼指数 (Gini Index) — CART 算法

Gini(D) = 1 - Σ p_k²

基尼指数越小，数据越纯
计算比熵更快 (没有对数运算)
CART 分类树默认使用基尼指数

2. 决策树生成 (如何构建树)

递归地执行以下步骤：

从根节点开始，包含所有训练数据
选择一个最优特征，根据该特征的不同取值将数据分成子集
对每个子集递归地重复步骤 2
直到满足停止条件：
- 节点中所有样本属于同一类
- 没有更多特征可用
- 达到预设的最大深度

3. 剪枝 (Pruning, 防止过拟合)

如果不加限制，决策树会一直生长直到每个叶子节点只有一个样本，这会导致严重的过拟合。

预剪枝 (Pre-pruning)

在树的生长过程中提前停止：

限制最大深度 (max_depth)
限制叶子节点最少样本数 (min_samples_leaf)
限制分裂所需的最小样本数 (min_samples_split)
限制分裂所需的最小信息增益

后剪枝 (Post-pruning)

先让树充分生长，然后自底向上剪掉不重要的分支：

代价复杂度剪枝 (Cost Complexity Pruning): 在树的准确度和复杂度之间寻找平衡
使用验证集评估剪枝前后的效果

决策树的类型

算法	提出者	年份	分裂标准	任务类型	树结构
ID3	Quinlan	1986	信息增益	分类	多叉树
C4.5	Quinlan	1993	信息增益率	分类	多叉树
CART	Breiman	1984	基尼指数/平方误差	分类+回归	二叉树

CART (Classification And Regression Tree) 是目前最常用的决策树算法，scikit-learn 的 DecisionTreeClassifier 和 DecisionTreeRegressor 均基于 CART 实现。

决策树 vs 其他基础模型

维度	决策树	逻辑回归	KNN	朴素贝叶斯
可解释性	极高	高	低	中等
数据预处理	几乎不需要	需标准化	需标准化	需离散化
非线性	天然支持	需手动构造	天然支持	需假设独立
缺失值	可处理	需填充	需填充	需填充
类别特征	天然支持	需编码	需编码	天然支持
过拟合	容易 (需剪枝)	较轻	较轻	较轻
训练速度	快	快	极快 (惰性)	快
小样本	尚可	好	好	好

优缺点

优点

可解释性极强: 可以直观地看到决策路径，适合需要解释的领域 (医疗、金融)
几乎不需要数据预处理: 不需要标准化、归一化，天然处理类别特征
自动发现特征交互: 树结构天然捕获特征间的非线性关系
特征重要性: 可以输出每个特征对预测的贡献度
白盒模型: 完全可追踪，不会产生”黑盒”预测

缺点

容易过拟合: 如果没有剪枝，树会变得非常复杂，完美记忆训练数据
不稳定: 数据的微小变化可能导致完全不同的树结构
偏向多值特征: 倾向于选择取值多的特征进行分裂
外推能力差: 对于回归任务，无法预测超出训练集范围的值
贪心算法: 每次选择局部最优分裂，不能保证全局最优
对不平衡数据敏感: 需要处理类别不平衡

来源

Quinlan, J. R. (1986). Induction of Decision Trees. Machine Learning. https://doi.org/10.1007/BF00116251
Breiman, L., et al. (1984). Classification and Regression Trees. Wadsworth.
scikit-learn Decision Trees: https://scikit-learn.org/stable/modules/tree.html