决策树（Decision Tree）

决策树是最直观的监督学习模型之一，既能做分类也能做回归。它做的事很单纯：对数据反复问”某个特征是否满足条件”这种是非题，把样本一层层分到更”纯”的组里，直到能直接给出预测。 预测时只要顺着树从根走到叶子，看落在哪片叶子就输出那片的结论。

一句话类比：决策树就像玩”二十个问题”猜物体，或者一张流程图 / if-this-then-that 规则。比如判断”要不要约会”，先问”天气好吗？”→ 好再问”对方有趣吗？”→ ……逐层筛到最后给出 yes/no。每个内部节点是一道是非题，每片叶子是一个结论。

关联：前面 gradient-descent.md、single-layer-perceptron.md 都是参数化模型（靠调权重）。决策树是非参数 / 基于规则的模型，不学权重、只学”怎么切分数据”，思路完全不同，但同样是监督学习的基本构件。

1. 为什么需要它：可解释的”分而治之”

很多真实问题天然是”先按 A 分、再按 B 分”的结构（风控、医疗、诊断）。决策树用**递归二分（分而治之）**把复杂决策拆成一连串简单判断：

优点：无需特征缩放、能混用连续/类别特征、天然处理非线性、极其易解释（路径即可读成规则）。
代价：单棵大树容易过拟合、对数据扰动不稳定。

2. 核心概念

术语	含义
根节点 (Root)	整棵树起点，对全量数据做第一次切分
内部节点 (Decision Node)	一道是非题：`特征 < 阈值 ?`
叶子 (Leaf)	最终预测：分类里是某类（或类分布），回归里是数值
深度 (Depth)	从根到叶的最长路径长度
不纯度 (Impurity)	节点里样本”有多混杂”，越纯越接近 0
分裂 (Split)	选一个特征+阈值，把节点样本分成两堆

            特征 X1 < 0.5 ?
            ├── Yes ──▶ 叶子：类 A
            └── No  ──▶ 特征 X2 < 0.3 ?
                         ├── Yes ──▶ 叶子：类 B
                         └── No  ──▶ 叶子：类 C

预测苹果是 A/B/C，只需沿路径答两道题。这条路径本身 = 一条可解释规则：if X1>=0.5 and X2<0.3 then B。

3. 工作原理：怎么选”该问哪道题”

建树的核心是每次选能把不纯度降得最多的那道题来分裂节点，然后递归。衡量”降了多少”靠不纯度指标：

分类：Gini 不纯度或信息熵（Entropy）
回归：节点内方差 / MSE（选分裂使子节点方差加权和最小）

流程（CART 风格，二分递归）：

1. 从根（全部训练样本）开始
2. 对每个特征、每个候选阈值，算"分裂后的不纯度加权下降量"
3. 选下降最多的 (特征, 阈值) 做本次分裂
4. 把样本分到左右子节点，对每个子节点递归重复 2-4
5. 直到满足停止条件（见第 6 节）→ 该节点变叶子，给出预测

4. 关键公式（不纯度与信息增益）

Gini 不纯度（CART 默认，计算快）： $G ini = 1 - \sum_{i = 1}^{k} p_{i}^{2}$ $p_{i}$ 是节点中第 $i$ 类样本占比；纯节点（只有一类） $G ini = 0$ 。

信息熵（ID3/C4.5 用）： $E n t r o p y = - \sum_{i = 1}^{k} p_{i} lo g_{2} p_{i}$

信息增益 (Information Gain) = 分裂前不纯度 − 分裂后子节点不纯度的加权和： $I G = H (父) - \sum_{v \in {L, R}} \frac{∣ D _{v} ∣}{∣ D ∣} H (D_{v})$ 选使 $I G$ 最大的分裂。回归里对应 方差减少 (Variance Reduction)。

符号	含义
$p_{i}$	节点内第 $i$ 类比例
$H$	不纯度（Gini 或 Entropy）
$	D_v
$	D

5. 三大经典算法辨析

算法	分裂准则	树结构	特征处理
ID3	信息增益（Entropy）	多叉（每特征可取多值）	仅离散
C4.5	信息增益比（惩罚多取值特征）	多叉	离散+连续（自动阈值化）
CART	Gini（或回归用 MSE）	二叉	连续/离散统一，sklearn 默认

实践里用得最多的是 CART（sklearn 的 DecisionTreeClassifier 就是它）。

6. 停止条件与剪枝（防止过拟合）

单棵决策树会一路分到每个叶子只有一个样本（完美拟合训练集但泛化极差）。常用刹车：

预剪枝 (pre-pruning)：设超参数提前停——max_depth、min_samples_split、min_samples_leaf、max_leaf_nodes。
后剪枝 (post-pruning)：先长满再自底向上剪掉”对验证集没帮助”的分支（如 CCP 代价复杂度剪枝）。

7. 代码（sklearn 最简流程）

from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.model_selection import train_test_split
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt
 
X, y = load_iris(return_X_y=True)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0)
 
# criterion="gini" 即第 4 节公式；max_depth 做预剪枝
clf = DecisionTreeClassifier(max_depth=3, criterion="gini", random_state=0)
clf.fit(X_tr, y_tr)
 
print(clf.score(X_te, y_te))   # 测试集准确率
plot_tree(clf, filled=True)    # 直接可视化成流程图，可解释性来源
plt.show()

# 手写一个 Gini 计算，理解"纯度"怎么算
def gini(y):
    p = [ (y == c).mean() for c in set(y) ]   # 每类占比
    return 1 - sum(pi**2 for pi in p)         # 1 - Σp_i²
 
# 父节点混 3 类 vs 分裂后两子节点各纯 → Gini 下降 = 信息增益

8. 典型工作流 / 何时用

数据是表格型 (tabular)、特征混合连续/类别、且想要可解释规则 → 决策树很合适。
设 max_depth 等防过拟合超参，训练、用 plot_tree 看规则。
单棵树偏弱不稳 → 上集成：随机森林（多棵树投票）、梯度提升（XGBoost/LightGBM，逐棵纠错）。

9. 常见误区（复习重点）

❌ “树越深越准” → 单棵深树严重过拟合；用 max_depth/min_samples_leaf 剪枝或改用集成。
❌ “决策树能拟合任意边界” → 它只会轴对齐 (axis-aligned) 切分，对旋转/斜线边界要很多节点；必要时做特征组合或用核方法。
❌ “一棵树就够稳” → 决策树方差高、对数据扰动敏感（换个样本树形大变）；用 Random Forest / Boosting 降低方差。
❌ “要先对特征做归一化” → 不需要。决策树按阈值切分，对特征尺度不敏感（这点不同于 gradient-descent.md 里的模型）。
❌ “连续特征必须离散化” → CART 直接搜最优阈值，无需手动分箱。
❌ “信息增益越高越好” → 倾向于偏爱取值多的特征；C4.5 用增益比修正，sklearn 默认 Gini 也较稳。

10. 延伸阅读 / 关联概念

随机森林 (Random Forest) — 多棵决策树集成，解决单树不稳/过拟合；见 random-forest.md（待补）
梯度提升 / XGBoost / LightGBM — 逐棵纠错的强集成，表格数据 SOTA；见 gradient-boosting.md（待补）
交叉熵损失 — 分类任务的另一不纯度视角；见 cross-entropy-loss.md
梯度下降 / 感知机 — 参数化模型家族，与树的”分而治之”思路对照；见 gradient-descent.md、single-layer-perceptron.md
过拟合 / 正则 / 验证集 — 剪枝的本质就是正则化，见相关 ML 基础笔记

第二大脑 / Knowledge Bank

探索

decision-tree