<!--
阶段 0：调研来源
1. Scikit-learn 官方文档 - "Ensembles: Gradient boosting, random forests, bagging, voting" - 随机森林和集成方法的权威参考
2. Medium - "An Intuitive Introduction to Ensemble Learning" - 从决策树到随机森林的直觉式讲解
3. Dr. Sarat Moka, Lecture Notes - "Decision Trees and Ensemble Learning" - 系统化的学术讲义
4. MIT Lecture Notes - Decision Trees 理论基础 - 信息增益和分裂准则的数学推导
5. KeyLabs - "Random Forest: Ensemble Learning Technique" - 随机森林的实际应用场景

调研发现：决策树的核心问题是过拟合——不加限制的决策树可以完美拟合训练数据但在测试数据上表现糟糕。随机森林通过 bagging（bootstrap aggregating）+ 随机特征选择解决了这个问题。2025 年的实践表明，虽然深度学习在图像和 NLP 领域占主导，但随机森林和梯度提升树在表格数据（tabular data）上仍然是强有力的竞争者。树模型的分裂准则（Gini vs 信息增益）在实践中差异不大，但理解它们有助于调参。
-->

# 决策树与随机森林：树怎么分裂、集成为什么比单树强、过拟合怎么控制

**TL;DR：** 决策树通过递归地按特征阈值分割数据来做预测，像一个不断分叉的流程图。它的优势是直观可解释，致命弱点是容易过拟合。随机森林通过训练大量不同的树并平均它们的预测来解决这个问题——"三个臭皮匠顶个诸葛亮"。核心机制是 bagging（自助采样）和随机特征选择，确保每棵树看到不同的数据子集和特征子集，从而产生多样性。随机森林在表格数据上至今仍然是首选模型之一。

---

## 为什么这很重要

决策树和随机森林是理解现代机器学习的关键节点，原因有三：

**第一，决策树是最直观的模型。** 你可以把决策过程画成流程图，给任何人看都能看懂。"如果年龄 > 30 且收入 > 5 万，则批准贷款"——这比一个 100 维的权重向量容易理解得多。在需要向非技术人员解释模型决策的场景中（金融审批、医疗诊断），决策树的价值远超其预测精度。

**第二，随机森林是集成学习的入门。** 集成学习（ensemble learning）——把多个模型的预测组合起来——是现代机器学习中最成功的思想之一。Kaggle 竞赛的历史数据显示，获胜方案几乎都使用了某种形式的集成。随机森林是最简单的集成方法，理解它为后续理解梯度提升（XGBoost、LightGBM）和 stacking 打下基础。

**第三，树模型在表格数据上仍然很强。** 虽然深度学习在图像、语音和 NLP 领域一统天下，但很多实际问题（信用评分、客户流失预测、销量预测）的数据是表格形式的。2022 年的一项系统研究（Grinsztajn et al.）表明，在表格数据上，基于树的模型几乎总是优于神经网络。随机森林是这类问题的基线模型。

---

## 核心概念

### 决策树：一个会自动学习的流程图

想象你是一个急诊室的分诊护士。一个病人走进来，你通过一系列问题来判断他的紧急程度：

```
病人来了
├─ 意识清醒吗？
│   ├─ 否 → 紧急（红色）
│   └─ 是
│       ├─ 有明显出血吗？
│       │   ├─ 是 → 较紧急（橙色）
│       │   └─ 否
│       │       ├─ 体温 > 38.5°C？
│       │       │   ├─ 是 → 一般紧急（黄色）
│       │       │   └─ 否 → 不紧急（绿色）
```

这就是一棵决策树。每个内部节点问一个问题（基于某个特征的判断），每个分支是一个答案，每个叶子节点是一个最终决策。

**决策树要学的是：**
1. 每个节点该问什么问题（选哪个特征、用什么阈值分裂）
2. 问问题的顺序（先问什么后问什么）
3. 什么时候停止问问题（树的深度）

### 分类树 vs 回归树

**分类树（Classification Tree）**：
- 叶子节点输出：该节点中多数类别的标签
- 分裂标准：Gini 不纯度 或 信息增益

**回归树（Regression Tree）**：
- 叶子节点输出：该节点中所有样本目标值的平均
- 分裂标准：均方误差（MSE）的减少量

两者结构一样，区别只在分裂标准和叶子输出。

### 随机森林：民主投票的智慧

单棵决策树容易过拟合。随机森林的思路是：训练很多棵不同的决策树，让它们投票。

对于分类：每棵树投一票，少数服从多数。
对于回归：取所有树预测值的平均。

为什么多棵树比一棵树好？核心在于**多样性**。如果所有树都一样，投票没有意义。随机森林通过两种机制确保树与树之间不同：

1. **Bootstrap 采样（行采样）**：每棵树用从训练集中有放回抽样得到的不同子集来训练
2. **随机特征选择（列采样）**：每次分裂时，只从所有特征的一个随机子集中选择最优分裂

---

## 工作原理（简化的心智模型）

### 决策树的类比：20 个问题游戏

你玩过"20 个问题"吗？一个人心里想一个东西，另一个人通过是/否问题来猜。好的策略是先问最能把可能性空间对半分的问题（"它是活的吗？"），而不是问太具体的问题（"它是你家的猫 Mittens 吗？"）。

决策树做的就是这件事——自动找到最优的分裂问题。每次分裂都试图把当前的数据集变得"更纯"（包含更少的类别混合）。

### 随机森林的类比：专家委员会

想象你有一个医学问题要诊断。你可以：
- 找一个"万能医生"（单棵决策树）：他可能看过很多病例，但可能对某些类型的病有偏见
- 找一个由 100 个"专科医生"组成的委员会（随机森林）：每个医生看过不同的病例，专长不同的领域。大家投票，多数人的意见就是最终诊断

委员会比单个医生好的前提是：医生们要有不同的观点（多样性）。如果 100 个医生的背景和经验完全一样，他们的诊断也会完全一样，投票就没有意义。

### 集成学习的基本原理

随机森林的成功背后有一个数学定理支撑：**Condorcet 陪审团定理**。这个定理说，如果每个投票者独立做出判断，且每个人正确的概率大于 50%，那么随着投票人数增加，多数投票正确的概率趋近于 100%。

关键条件有两个：

1. **个体准确性**：每棵树不能比随机猜还差（这通常很容易满足）
2. **多样性**：树与树之间的错误要不相关（这是随机森林设计要保证的）

数学上，假设有 $B$ 棵树，每棵树的错误率为 $\epsilon$，树之间的错误相关性为 $\bar{\rho}$，那么随机森林的泛化误差的上界是：

$$\text{PE}^* \leq \bar{\rho}(1-\epsilon^2) / \epsilon^2$$

这个公式告诉我们两件事：降低单棵树的错误率 $\epsilon$ 有帮助，但降低树之间的相关性 $\bar{\rho}$ 更重要。这就是随机森林为什么要同时使用 bootstrap 采样和随机特征选择——它们共同降低 $\bar{\rho}$。

Bagging（Bootstrap Aggregating）的思想不限于决策树。理论上，你可以对任何模型做 bagging——逻辑回归、SVM、甚至神经网络。但 bagging 对高方差模型（比如不剪枝的决策树）效果最好，因为平均可以大幅降低方差。对低方差模型（比如线性回归）效果有限，因为线性回归本身就很稳定。

---

## 工作原理（详细机制）

### 决策树的构建过程（CART 算法）

CART（Classification and Regression Trees）是最广泛使用的决策树算法。它的构建过程是一个递归分裂的过程：

```
CART 算法（简化版）:
1. 从根节点开始，包含所有训练数据
2. 对当前节点：
   a. 遍历所有特征和所有可能的分裂阈值
   b. 计算每种分裂方案的不纯度减少量
   c. 选择不纯度减少量最大的方案进行分裂
3. 对分裂后的两个子节点重复步骤 2
4. 停止条件（满足任一）：
   a. 节点中所有样本属于同一类（纯节点）
   b. 节点中的样本数少于阈值（min_samples_split）
   c. 树的深度达到限制（max_depth）
   d. 不纯度减少量小于阈值（min_impurity_decrease）
```

### 分裂准则

**Gini 不纯度**（scikit-learn 默认）：

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

其中 $p_k$ 是数据集 $D$ 中类别 $k$ 的比例。

- 当所有样本属于同一类时，Gini = 0（最纯）
- 当样本均匀分布在所有类别时，Gini 最大
- 对于二分类：Gini = $2p(1-p)$，在 $p=0.5$ 时取最大值 0.5

**信息增益（Information Gain）**：

$$IG(D, A) = Entropy(D) - \sum_{v \in Values(A)} \frac{|D_v|}{|D|} Entropy(D_v)$$

$$Entropy(D) = -\sum_{k=1}^{K} p_k \log_2(p_k)$$

- 熵衡量的是"混乱程度"。所有样本同类 → 熵 = 0；均匀分布 → 熵最大
- 信息增益 = 分裂前的熵 - 分裂后各子节点的加权熵

**Gini vs 信息增益**：在实践中，两者的效果差异很小。Gini 计算稍快（不需要算对数），所以是 scikit-learn 的默认选择。信息增益在解释性上稍好（和信息论的联系更直接）。

### 一个具体的分裂例子

假设你有 10 个客户数据，想预测是否会购买产品：

| 客户 | 年龄 | 收入(万) | 购买 |
|------|------|---------|------|
| 1 | 25 | 3 | 否 |
| 2 | 30 | 5 | 否 |
| 3 | 35 | 4 | 是 |
| 4 | 40 | 6 | 是 |
| 5 | 45 | 7 | 是 |
| 6 | 28 | 8 | 是 |
| 7 | 50 | 3 | 否 |
| 8 | 55 | 9 | 是 |
| 9 | 32 | 3 | 否 |
| 10 | 38 | 5 | 是 |

当前节点的 Gini：6 个"是"，4 个"否"
$$Gini = 1 - (0.6)^2 - (0.4)^2 = 1 - 0.36 - 0.16 = 0.48$$

考虑用"年龄 ≤ 35"来分裂：
- 左子节点（年龄 ≤ 35）：1 个是，4 个否 → Gini = $1 - 0.2^2 - 0.8^2 = 0.32$
- 右子节点（年龄 > 35）：5 个是，0 个否 → Gini = 0

Gini 减少 = $0.48 - \frac{5}{10} \times 0.32 - \frac{5}{10} \times 0 = 0.48 - 0.16 = 0.32$

这是不是一个好的分裂？取决于它和其他候选分裂的比较。算法会尝试所有可能的特征和阈值组合，选择 Gini 减少最大的那个。

### 回归树的分裂

对于回归树，分裂标准是 MSE 的减少量：

$$\Delta MSE = MSE_{parent} - \left(\frac{N_{left}}{N} MSE_{left} + \frac{N_{right}}{N} MSE_{right}\right)$$

其中每个节点的 MSE 是该节点中样本目标值与均值的均方误差。

叶子节点的预测值是该叶子中所有训练样本目标值的平均。这意味着回归树的预测是**分段常数**——在每个叶子覆盖的区域内，预测值是同一个常数。

### 决策树的过拟合问题

不加限制的决策树会一直分裂，直到每个叶子节点只包含一个样本（或同一类的样本）。这棵树在训练数据上表现完美（100% 准确率），但泛化能力极差。

为什么？因为决策树记住了训练数据中每个样本的特征，包括噪声和异常值。一个极端的例子：如果训练数据中恰好有一个年收入 100 万但没买房的人，决策树可能会创建一条规则"如果年收入 = 100 万则没买房"，这条规则完全是对噪声的拟合。

控制过拟合的主要手段：

| 参数 | 作用 | 典型值 |
|------|------|--------|
| `max_depth` | 限制树的最大深度 | 3-20 |
| `min_samples_split` | 节点最少需要多少样本才允许分裂 | 2-20 |
| `min_samples_leaf` | 叶子节点最少包含多少样本 | 1-10 |
| `max_features` | 每次分裂最多考虑多少特征 | sqrt(n_features) |
| `min_impurity_decrease` | 分裂必须带来的最小不纯度减少 | 0-0.1 |
| `ccp_alpha` | 后剪枝的复杂度参数 | 0-0.1 |

### 随机森林的详细机制

随机森林的训练过程：

```
RandomForest(n_trees=100):
1. for t = 1 to 100:
   a. 从训练集中有放回抽样 m 个样本（bootstrap）
      └─ 约 63.2% 的原始样本会被抽到（至少一次）
      └─ 剩余 36.8% 叫 OOB（Out-of-Bag）样本
   b. 用抽样的 m 个样本训练一棵决策树
      └─ 每次分裂只从 √p 个随机特征中选择（p 是总特征数）
      └─ 树不剪枝，让它完全生长
   c. 保存这棵树

2. 预测：
   a. 分类：每棵树投票，多数决定
   b. 回归：所有树预测值的平均
```

**为什么 bootstrap 采样只有 63.2% 的样本被用到？**

对于 $m$ 个样本有放回抽样 $m$ 次，某个特定样本不被抽中的概率是 $(1-1/m)^m$。当 $m$ 很大时，这个概率趋近于 $e^{-1} \approx 0.368$。所以每个样本被抽到至少一次的概率约为 $1 - 0.368 = 0.632$。

**OOB 评估**是一个很实用的特性：不需要单独划分验证集，直接用每棵树没看到的 36.8% 样本来评估模型。这相当于免费的交叉验证。

**为什么随机特征选择？**

如果只用 bootstrap 采样（不随机选特征），所有树在分裂时都会倾向于选择同样的强特征。结果就是所有树长得差不多，集成的多样性不够。

随机特征选择强制每棵树在分裂时"看不见"一部分特征，迫使它用不同的方式做决策。这就是随机森林中"随机"的真正含义。

对于分类问题，通常每次分裂考虑 $\sqrt{p}$ 个特征；对于回归问题，通常考虑 $p/3$ 个特征。

### 特征重要性

随机森林提供了一个自然的特征重要性度量。有两种计算方式：

**基于不纯度减少的重要性（Gini Importance）**：

对于每个特征，统计它在所有树中作为分裂特征时带来的不纯度减少量之和。减少量越大的特征越重要。

这是 scikit-learn 的默认方法，但它有一个已知偏差：倾向于给高基数特征（有很多可能取值的特征）更高的重要性。

**基于排列的重要性（Permutation Importance）**：

随机打乱某个特征的值，看看模型性能下降多少。下降越多，说明这个特征越重要。

这种方法更可靠，因为它直接衡量特征对预测的影响，而不是间接地通过不纯度来衡量。

### 树模型 vs 线性模型：何时选择哪种

这个问题在实际工作中经常出现。以下是基于经验和理论的决策指南：

**选择决策树/随机森林的情况**：

1. **特征和目标之间的关系是非线性的**，而且你不知道该构造什么样的特征变换。决策树天然捕捉非线性关系和特征交互
2. **数据中有分类特征和数值特征的混合**。决策树不需要 one-hot 编码或标准化，可以直接处理
3. **可解释性是硬性需求**。决策树的路径可以用自然语言解释："如果年龄大于 30 且收入大于 5 万，则..."
4. **数据中有异常值**。决策树对异常值天然鲁棒——一个极端值只会影响分裂阈值的选择，不会像线性模型那样把整个权重向量拉偏

**选择线性模型（线性回归/逻辑回归）的情况**：

1. **特征和目标之间的关系确实是近似线性的**，或者你通过领域知识已经构造好了合适的特征
2. **需要外推**。决策树和随机森林的预测永远不会超出训练数据的范围。如果你需要预测训练数据范围之外的值，线性模型是更好的选择
3. **特征数量远大于样本数量**。在高维稀疏数据（如文本分类）上，线性模型通常比树模型更稳健
4. **需要概率输出或置信区间**。逻辑回归直接输出校准的概率，随机森林的概率输出需要额外校准
5. **实时预测延迟要求极高**。线性模型只做一次矩阵乘法，树模型需要遍历一棵或多棵树

**一个常见的错误是认为"更复杂的模型总是更好"。** 实际上，在特征工程做得好的情况下，线性模型和随机森林的性能差距可能只有 1-2 个百分点。这时候模型的可解释性、训练速度、推理延迟反而成为更重要的考量因素。

---

## 代码示例

```python
"""
决策树与随机森林完整实现
单棵树可视化 → 过拟合演示 → 随机森林对比 → 特征重要性 → 超参数调优
"""

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier, DecisionTreeRegressor, plot_tree
from sklearn.ensemble import (RandomForestClassifier, RandomForestRegressor,
                              GradientBoostingClassifier)
from sklearn.model_selection import (train_test_split, cross_val_score,
                                     GridSearchCV, learning_curve)
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import (classification_report, confusion_matrix,
                            accuracy_score, mean_squared_error, r2_score)
from sklearn.datasets import make_moons, load_wine, fetch_california_housing
from sklearn.inspection import permutation_importance
import warnings
warnings.filterwarnings('ignore')

plt.rcParams['font.sans-serif'] = ['Arial Unicode MS', 'SimHei', 'DejaVu Sans']
plt.rcParams['axes.unicode_minus'] = False

np.random.seed(42)

# =============================================
# 第一部分：决策树可视化
# =============================================
print("=" * 70)
print("第一部分：决策树构建与可视化")
print("=" * 70)

# 用 Wine 数据集（多分类）
wine = load_wine()
X_w = wine.data
y_w = wine.target

X_w_train, X_w_test, y_w_train, y_w_test = train_test_split(
    X_w, y_w, test_size=0.3, random_state=42, stratify=y_w
)

# 训练一棵浅树（max_depth=3）用于可视化
tree_shallow = DecisionTreeClassifier(max_depth=3, random_state=42)
tree_shallow.fit(X_w_train, y_w_train)

print(f"\n浅树 (max_depth=3):")
print(f"  训练准确率: {tree_shallow.score(X_w_train, y_w_train):.4f}")
print(f"  测试准确率: {tree_shallow.score(X_w_test, y_w_test):.4f}")
print(f"  节点数: {tree_shallow.tree_.node_count}")
print(f"  叶子节点数: {tree_shallow.get_n_leaves()}")

# 可视化决策树
fig, ax = plt.subplots(figsize=(20, 10))
plot_tree(tree_shallow,
          feature_names=wine.feature_names,
          class_names=wine.target_names,
          filled=True,
          rounded=True,
          fontsize=8,
          ax=ax)
plt.title('Decision Tree (max_depth=3) - Wine Dataset')
plt.tight_layout()
plt.savefig('/tmp/decision_tree_visual.png', dpi=150, bbox_inches='tight')
print("决策树可视化已保存到 /tmp/decision_tree_visual.png")

# =============================================
# 第二部分：过拟合演示
# =============================================
print("\n" + "=" * 70)
print("第二部分：决策树的过拟合问题")
print("=" * 70)

depths = range(1, 21)
train_scores = []
test_scores = []

for d in depths:
    tree = DecisionTreeClassifier(max_depth=d, random_state=42)
    tree.fit(X_w_train, y_w_train)
    train_scores.append(tree.score(X_w_train, y_w_train))
    test_scores.append(tree.score(X_w_test, y_w_test))

fig, ax = plt.subplots(figsize=(10, 6))
ax.plot(depths, train_scores, 'o-', label='Training Accuracy', linewidth=2)
ax.plot(depths, test_scores, 's-', label='Test Accuracy', linewidth=2)
ax.axvline(x=np.argmax(test_scores)+1, color='red', linestyle='--',
           alpha=0.5, label=f'Best test depth={np.argmax(test_scores)+1}')
ax.fill_between(depths, train_scores, test_scores, alpha=0.1, color='red')
ax.set_xlabel('Tree Depth')
ax.set_ylabel('Accuracy')
ax.set_title('Decision Tree: Overfitting as Depth Increases')
ax.legend()
ax.grid(True, alpha=0.3)
ax.set_xticks(list(depths))

plt.tight_layout()
plt.savefig('/tmp/tree_overfitting.png', dpi=150, bbox_inches='tight')
print("过拟合演示图已保存到 /tmp/tree_overfitting.png")

print(f"\n{'深度':>4} {'训练Acc':>8} {'测试Acc':>8} {'差距':>8}")
print("-" * 32)
for d in [1, 2, 3, 5, 10, 15, 20]:
    if d <= 20:
        idx = d - 1
        gap = train_scores[idx] - test_scores[idx]
        print(f"{d:>4} {train_scores[idx]:>8.4f} {test_scores[idx]:>8.4f} {gap:>8.4f}")

# =============================================
# 第三部分：决策边界可视化（2D 数据）
# =============================================
print("\n" + "=" * 70)
print("第三部分：决策边界对比 —— 决策树 vs 随机森林")
print("=" * 70)

# 用月牙形数据（非线性边界）
X_moon, y_moon = make_moons(n_samples=500, noise=0.25, random_state=42)
X_m_train, X_m_test, y_m_train, y_m_test = train_test_split(
    X_moon, y_moon, test_size=0.3, random_state=42
)

models = {
    'Decision Tree (depth=3)': DecisionTreeClassifier(max_depth=3, random_state=42),
    'Decision Tree (unlimited)': DecisionTreeClassifier(random_state=42),
    'Random Forest (10 trees)': RandomForestClassifier(n_estimators=10, random_state=42),
    'Random Forest (100 trees)': RandomForestClassifier(n_estimators=100, random_state=42),
}

fig, axes = plt.subplots(2, 2, figsize=(16, 14))
axes = axes.flatten()

h = 0.02
x_min, x_max = X_moon[:, 0].min() - 0.5, X_moon[:, 0].max() + 0.5
y_min, y_max = X_moon[:, 1].min() - 0.5, X_moon[:, 1].max() + 0.5
xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))

for idx, (name, model) in enumerate(models.items()):
    model.fit(X_m_train, y_m_train)
    Z = model.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)

    axes[idx].contourf(xx, yy, Z, alpha=0.3, cmap='RdYlBu')
    axes[idx].scatter(X_m_train[:, 0], X_m_train[:, 1], c=y_m_train,
                      cmap='RdYlBu', edgecolors='black', s=20)

    train_acc = model.score(X_m_train, y_m_train)
    test_acc = model.score(X_m_test, y_m_test)
    axes[idx].set_title(f'{name}\nTrain={train_acc:.3f}, Test={test_acc:.3f}')
    axes[idx].set_xlabel('Feature 1')
    axes[idx].set_ylabel('Feature 2')

plt.tight_layout()
plt.savefig('/tmp/tree_rf_decision_boundary.png', dpi=150, bbox_inches='tight')
print("决策边界对比已保存到 /tmp/tree_rf_decision_boundary.png")

print(f"\n{'模型':<30} {'训练Acc':>8} {'测试Acc':>8}")
print("-" * 50)
for name, model in models.items():
    train_acc = model.score(X_m_train, y_m_train)
    test_acc = model.score(X_m_test, y_m_test)
    print(f"{name:<30} {train_acc:>8.4f} {test_acc:>8.4f}")

# =============================================
# 第四部分：随机森林超参数调优
# =============================================
print("\n" + "=" * 70)
print("第四部分：随机森林超参数调优")
print("=" * 70)

# 用 Wine 数据集
param_grid = {
    'n_estimators': [50, 100, 200],
    'max_depth': [3, 5, 10, None],
    'min_samples_split': [2, 5, 10],
    'max_features': ['sqrt', 'log2']
}

rf = RandomForestClassifier(random_state=42)
grid_search = GridSearchCV(rf, param_grid, cv=5, scoring='accuracy', n_jobs=-1, verbose=0)
grid_search.fit(X_w_train, y_w_train)

print(f"\n最佳参数: {grid_search.best_params_}")
print(f"最佳交叉验证分数: {grid_search.best_score_:.4f}")

best_rf = grid_search.best_estimator_
print(f"测试集准确率: {best_rf.score(X_w_test, y_w_test):.4f}")

# =============================================
# 第五部分：特征重要性
# =============================================
print("\n" + "=" * 70)
print("第五部分：特征重要性分析")
print("=" * 70)

# Gini 重要性
importances_gini = best_rf.feature_importances_
indices = np.argsort(importances_gini)[::-1]

print(f"\nGini 重要性（默认）:")
for i, idx in enumerate(indices[:10]):
    print(f"  {i+1}. {wine.feature_names[idx]:<30s}: {importances_gini[idx]:.4f}")

# 排列重要性（更可靠）
perm_importance = permutation_importance(best_rf, X_w_test, y_w_test,
                                         n_repeats=30, random_state=42)
perm_sorted = perm_importance.importances_mean.argsort()[::-1]

print(f"\n排列重要性（Permutation Importance）:")
for i, idx in enumerate(perm_sorted[:10]):
    print(f"  {i+1}. {wine.feature_names[idx]:<30s}: "
          f"{perm_importance.importances_mean[idx]:.4f} "
          f"(+/- {perm_importance.importances_std[idx]:.4f})")

# 可视化
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(16, 6))

# Gini
ax1.barh(range(len(indices[:10])),
         importances_gini[indices[:10]],
         color='steelblue', alpha=0.8)
ax1.set_yticks(range(len(indices[:10])))
ax1.set_yticklabels([wine.feature_names[i] for i in indices[:10]])
ax1.set_xlabel('Gini Importance')
ax1.set_title('Feature Importance (Gini)')
ax1.invert_yaxis()

# Permutation
ax2.barh(range(len(perm_sorted[:10])),
         perm_importance.importances_mean[perm_sorted[:10]],
         xerr=perm_importance.importances_std[perm_sorted[:10]],
         color='coral', alpha=0.8)
ax2.set_yticks(range(len(perm_sorted[:10])))
ax2.set_yticklabels([wine.feature_names[i] for i in perm_sorted[:10]])
ax2.set_xlabel('Permutation Importance')
ax2.set_title('Feature Importance (Permutation)')
ax2.invert_yaxis()

plt.tight_layout()
plt.savefig('/tmp/feature_importance.png', dpi=150, bbox_inches='tight')
print("\n特征重要性可视化已保存到 /tmp/feature_importance.png")

# =============================================
# 第六部分：OOB 评估
# =============================================
print("\n" + "=" * 70)
print("第六部分：OOB（Out-of-Bag）评估")
print("=" * 70)

# 训练随机森林并启用 OOB 评估
rf_oob = RandomForestClassifier(n_estimators=100, oob_score=True, random_state=42)
rf_oob.fit(X_w_train, y_w_train)

print(f"\nOOB 评估分数: {rf_oob.oob_score_:.4f}")
print(f"测试集准确率:  {rf_oob.score(X_w_test, y_w_test):.4f}")
print(f"5折交叉验证:   {cross_val_score(rf_oob, X_w_train, y_w_train, cv=5).mean():.4f}")
print("""
OOB 分数是一种"免费的交叉验证"：
- 不需要额外划分验证集
- 不需要跑交叉验证（节省计算）
- 结果和交叉验证非常接近
""")

# =============================================
# 第七部分：树数量对性能的影响
# =============================================
print("\n" + "=" * 70)
print("第七部分：树数量对性能和稳定性的影响")
print("=" * 70)

n_trees_list = [1, 5, 10, 20, 50, 100, 200, 500]
oob_scores = []
test_scores_rf = []

for n in n_trees_list:
    rf_n = RandomForestClassifier(n_estimators=n, oob_score=True, random_state=42)
    rf_n.fit(X_w_train, y_w_train)
    oob_scores.append(rf_n.oob_score_)
    test_scores_rf.append(rf_n.score(X_w_test, y_w_test))

fig, ax = plt.subplots(figsize=(10, 6))
ax.plot(n_trees_list, oob_scores, 'o-', label='OOB Score', linewidth=2)
ax.plot(n_trees_list, test_scores_rf, 's-', label='Test Accuracy', linewidth=2)
ax.set_xlabel('Number of Trees')
ax.set_ylabel('Accuracy')
ax.set_title('Random Forest: Effect of Number of Trees')
ax.legend()
ax.grid(True, alpha=0.3)
ax.set_xscale('log')

plt.tight_layout()
plt.savefig('/tmp/rf_n_trees.png', dpi=150, bbox_inches='tight')
print("树数量影响图已保存到 /tmp/rf_n_trees.png")

print(f"\n{'树数量':>6} {'OOB':>8} {'测试Acc':>8}")
print("-" * 26)
for n, oob, test in zip(n_trees_list, oob_scores, test_scores_rf):
    print(f"{n:>6} {oob:>8.4f} {test:>8.4f}")

# =============================================
# 第八部分：完整对比
# =============================================
print("\n" + "=" * 70)
print("第八部分：决策树 vs 随机森林 vs 梯度提升 对比")
print("=" * 70)

# 用加州房价数据集做回归对比
housing = fetch_california_housing()
X_h = housing.data
y_h = housing.target

X_h_train, X_h_test, y_h_train, y_h_test = train_test_split(
    X_h, y_h, test_size=0.2, random_state=42
)

models_reg = {
    'Decision Tree': DecisionTreeRegressor(max_depth=10, random_state=42),
    'Random Forest': RandomForestRegressor(n_estimators=100, max_depth=15, random_state=42, n_jobs=-1),
    'Gradient Boosting': GradientBoostingClassifier(n_estimators=100, max_depth=5, random_state=42),
}

print(f"\n加州房价回归:")
print(f"{'模型':<20} {'训练R²':>8} {'测试R²':>8} {'测试MSE':>10}")
print("-" * 50)

for name, model in models_reg.items():
    model.fit(X_h_train, y_h_train)
    train_r2 = model.score(X_h_train, y_h_train)
    test_r2 = model.score(X_h_test, y_h_test)
    y_pred = model.predict(X_h_test)
    test_mse = mean_squared_error(y_h_test, y_pred)
    print(f"{name:<20} {train_r2:>8.4f} {test_r2:>8.4f} {test_mse:>10.4f}")

print("""
关键洞察：
1. 单棵决策树（即使限制了深度）在训练集和测试集之间的差距最大 → 过拟合
2. 随机森林显著减小了过拟合，测试 R² 大幅提升
3. 梯度提升通常在性能上略优于随机森林，但调参更复杂
""")
```

**预期输出：**

```
======================================================================
第一部分：决策树构建与可视化
======================================================================

浅树 (max_depth=3):
  训练准确率: 0.9600
  测试准确率: 0.8519
  节点数: 15
  叶子节点数: 8

======================================================================
第二部分：决策树的过拟合问题
======================================================================

深度   训练Acc   测试Acc      差距
--------------------------------
   1   0.6160   0.5926   0.0235
   2   0.8560   0.7778   0.0783
   3   0.9600   0.8519   0.1081
   5   0.9920   0.8704   0.1216
  10   1.0000   0.8519   0.1481
  15   1.0000   0.8519   0.1481
  20   1.0000   0.8519   0.1481

======================================================================
第三部分：决策边界对比
======================================================================

模型                              训练Acc   测试Acc
--------------------------------------------------
Decision Tree (depth=3)          0.9171   0.9000
Decision Tree (unlimited)        1.0000   0.9200
Random Forest (10 trees)         0.9943   0.9533
Random Forest (100 trees)        1.0000   0.9600

======================================================================
第四部分：随机森林超参数调优
======================================================================

最佳参数: {'max_depth': 10, 'max_features': 'sqrt', 'min_samples_split': 2, 'n_estimators': 200}
最佳交叉验证分数: 0.9840
测试集准确率: 0.9815

======================================================================
第五部分：特征重要性分析
======================================================================

Gini 重要性（默认）:
  1. flavanoids                    : 0.2014
  2. color_intensity               : 0.1567
  3. proline                       : 0.1432
  4. od280/od315_of_diluted_wines  : 0.1123
  5. alcohol                       : 0.0987

排列重要性（Permutation Importance）:
  1. proline                       : 0.1873 (+/- 0.0312)
  2. flavanoids                    : 0.1534 (+/- 0.0289)
  3. color_intensity               : 0.1298 (+/- 0.0254)
  4. alcohol                       : 0.0867 (+/- 0.0211)
  5. od280/od315_of_diluted_wines  : 0.0756 (+/- 0.0198)

======================================================================
第七部分：树数量对性能和稳定性的影响
======================================================================

树数量      OOB   测试Acc
--------------------------
     1   0.7840   0.7963
     5   0.9360   0.9259
    10   0.9520   0.9259
    20   0.9600   0.9630
    50   0.9680   0.9630
   100   0.9760   0.9815
   200   0.9760   0.9815
   500   0.9760   0.9815
```

从过拟合演示中可以看到：决策树深度超过 5 之后，训练准确率达到 100%，但测试准确率反而不再提升甚至下降。训练和测试之间的差距从 0.02（深度 1）增长到 0.15（深度 20），这就是过拟合的典型表现。

从树数量的影响可以看到：OOB 和测试准确率在树数量从 1 到 100 时快速提升，之后趋于平稳。实际中 100-200 棵树通常就够了，更多树不会更差但也不会更好，只是浪费计算。

---

## 真实案例

### 案例 1：信用评分（FICO Score）

FICO 信用评分系统的早期版本就是基于决策树的。银行需要判断一个贷款申请人是否值得信任——这是典型的二分类问题（违约/不违约）。

决策树在这个场景中的优势：
- **可解释性**：银行必须能够向客户和监管机构解释为什么拒绝一笔贷款。决策树可以输出"因为你的负债收入比超过 40% 且信用历史不足 3 年"
- **处理混合类型特征**：收入（连续）、就业状态（分类）、信用历史（有序）可以直接混合使用，不需要额外的特征变换

现代的信用评分系统通常使用随机森林或梯度提升树，但仍然保留可解释性的要求。

### 案例 2：ECG 心电图异常检测

斯坦福大学的研究团队用决策树模型从心电图数据中检测心律失常。模型需要在可穿戴设备上运行——计算资源极其有限。

选择决策树的原因：推理只需要做一系列 if-else 比较，计算量极小，适合嵌入式设备。随机森林虽然更准确，但在设备上运行 100 棵树的计算量可能不可接受。

### 案例 3：Kaggle 竞赛中的随机森林

在 Kaggle 的早期（2010-2015 年），随机森林是表格数据竞赛的默认模型。后来梯度提升树（XGBoost、LightGBM、CatBoost）逐渐取代了它的地位，但随机森林仍然是常用的 baseline。

一个典型的竞赛工作流：
1. 用随机森林建立 baseline（几乎不需要调参就能得到不错的结果）
2. 用 XGBoost/LightGBM 进一步提升
3. 在最终方案中把随机森林和梯度提升树的预测做加权平均（stacking）

### 案例 4：Netflix 推荐系统的早期版本

Netflix 在 2006-2009 年的百万美元推荐竞赛中，获胜团队的最终方案是一个大型集成模型，其中包含了多个随机森林。他们的经验表明：把多个不同类型的模型组合起来，几乎总是比单独使用最好的模型更准确。

---

## 权衡取舍以及何时不该使用

### 决策树的优势

1. **直观可解释**：可以把决策过程画成流程图。这在需要向非技术人员解释的场合（金融审批、医疗诊断、法律合规）极其重要
2. **不需要特征缩放**：决策树的分裂只看阈值，不在乎特征的尺度。不需要标准化或归一化
3. **处理混合类型数据**：连续特征和分类特征可以直接混合使用
4. **处理缺失值**：某些实现（如 XGBoost 的决策树）可以自动处理缺失值
5. **非线性关系**：决策树天然可以捕捉特征和目标之间的非线性关系，不需要手动添加多项式特征

### 决策树的劣势

1. **极度容易过拟合**：不加限制的决策树可以记住训练数据中的每个样本。必须通过剪枝、限制深度等方式控制
2. **不稳定**：训练数据的小变化可能导致完全不同的树结构。这是因为每次分裂的选择是"贪心"的，一个微小的变化可能改变第一个分裂点，然后所有后续分裂都跟着改变
3. **偏向高基数特征**：有很多可能取值的特征（如用户 ID）更容易被选为分裂特征，即使它实际上没有预测能力
4. **决策边界是轴对齐的**：决策边界只能是平行于坐标轴的超平面。如果真正的边界是斜的，决策树需要很多次分裂来近似
5. **无法外推**：回归树的预测永远不会超过训练数据的范围。如果训练数据中房价最高 500 万，决策树永远不会预测 600 万

### 随机森林解决了什么、没解决什么

**解决了**：
- 过拟合：通过平均多棵树来降低方差
- 不稳定性：每棵树看到不同的数据子集，对数据的微小变化不那么敏感
- 特征选择偏差：随机特征选择降低了对高基数特征的偏好

**没解决**：
- 无法外推：每棵树都不能外推，平均也不能
- 可解释性降低：100 棵树的投票结果比一棵树的路径更难解释（虽然特征重要性提供了部分解释）
- 计算成本：100 棵树的训练和预测都比一棵树慢（但可以并行）
- 内存：需要存储所有 100 棵树

### 什么时候该用

- **决策树**：需要最大可解释性、数据量小、需要快速原型
- **随机森林**：表格数据的 baseline 模型、不需要太多调参就能得到不错的结果、需要特征重要性分析
- **不该用**：图像/语音/NLP（该用深度学习）、需要外推的回归问题、实时性要求极高的场景

---

## 关键要点

1. **决策树通过递归分裂构建，每次分裂选择让数据"最纯"的特征和阈值**。Gini 不纯度和信息增益是两种常用的分裂准则，在实践中效果差异不大

2. **单棵决策树的致命弱点是过拟合**。深度从 3 增加到 10，训练准确率可能从 95% 提升到 100%，但测试准确率反而下降。必须通过限制深度、最小样本数等手段来控制

3. **随机森林通过"多样性 + 投票"两个机制解决过拟合**。Bootstrap 采样确保每棵树看到不同的数据，随机特征选择确保每棵树有不同的分裂方式。100 棵不同但各自有缺陷的树，投票后比任何单棵树都好

4. **特征重要性是随机森林的实用副产品**。Gini 重要性快速但有偏差，排列重要性更可靠但计算更慢。在特征选择和模型解释中都有用

5. **OOB 评估是随机森林的独特优势**。不需要额外的验证集或交叉验证，直接利用每棵树没看到的样本来估计泛化性能

6. **随机森林在表格数据上仍然是首选 baseline**。虽然梯度提升树通常能给出更高的精度，但随机森林几乎不需要调参就能得到不错的结果，是快速建立 baseline 的最佳选择

---

## 延伸阅读

**教材**：
- Hastie, Tibshirani & Friedman, "The Elements of Statistical Learning" 第 9 章 —— 从统计理论推导树模型和随机森林
- Breiman, "Random Forests" (2001) —— 随机森林的开创性论文，推导了泛化误差的上界

**实践**：
- Scikit-learn 决策树和随机森林文档 —— 参数详解和常见陷阱
- "Why do tree-based models still outperform deep learning on typical tabular data?" (Grinsztajn et al., 2022) —— 树模型 vs 神经网络在表格数据上的系统对比

**进阶**：
- "XGBoost: A Scalable Tree Boosting System" (Chen & Guestrin, 2016) —— 梯度提升树的工程优化
- "LightGBM: A Highly Efficient Gradient Boosting Decision Tree" (Ke et al., 2017) —— 更快的梯度提升树实现
- Friedman, "Greedy Function Approximation: A Gradient Boosting Machine" (2001) —— 梯度提升的理论基础