Course 2：决策树与集成方法

课程简介

决策树、随机森林、XGBoost 原理与实践。

🎬 本课程视频：Machine Learning Specialization (2022) — 新版机器学习

一、决策树基础

1.1 什么是决策树

决策树是一种基于树结构的监督学习算法，可以用于分类和回归。它通过一系列的 if-then-else 规则对数据进行划分。

树的组成部分：
- 根节点：包含所有训练样本
- 内部节点：对应一个特征的测试条件
- 叶节点：对应一个预测输出（类别或数值）

从根节点到叶节点的路径对应一条决策规则。

1.2 决策树的训练过程

递归地选择最佳分割特征，将数据划分为更纯的子集：

1. 从根节点开始，包含所有训练数据
2. 选择一个特征和分割阈值，将数据分为左右子节点
3. 对每个子节点，递归重复步骤 2
4. 当满足停止条件时，将当前节点设为叶节点

二、分割标准

2.1 基尼不纯度

基尼不纯度衡量一个节点中样本的"不纯"程度：

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

其中 p_k 是节点中第 k 类样本的比例。当节点中所有样本属于同一类别时，基尼系数为 0（最纯）；当各类别等比例分布时，基尼系数最大。

分割后的加权基尼系数：

$$Gini_{split} = \frac{m_{left}}{m} Gini_{left} + \frac{m_{right}}{m} Gini_{right}$$

2.2 信息增益与熵

熵衡量节点的不确定性：

$$H(p) = -\sum_{k=1}^{K} p_k \log_2(p_k)$$

信息增益是分割前后熵的减少量：

$$IG = H(parent) - \sum_{j} \frac{m_j}{m} H(child_j)$$

2.3 回归树的均方误差

对于回归任务，使用均方误差作为分割标准：

$$MSE = \frac{1}{m} \sum_{i \in node} (y^{(i)} - \bar{y}_{node})^2$$

分割目标是最大化 MSE 的减少量。

def compute_gini(y):
    classes, counts = np.unique(y, return_counts=True)
    probs = counts / len(y)
    return 1 - np.sum(probs ** 2)

def find_best_split(X, y):
    best_gini = float('inf')
    best_feature, best_threshold = None, None

    for feature in range(X.shape[1]):
        values = np.sort(np.unique(X[:, feature]))
        for i in range(len(values) - 1):
            threshold = (values[i] + values[i+1]) / 2
            left_mask = X[:, feature] <= threshold
            right_mask = ~left_mask

            gini_left = compute_gini(y[left_mask])
            gini_right = compute_gini(y[right_mask])
            gini_split = (np.sum(left_mask) * gini_left + np.sum(right_mask) * gini_right) / len(y)

            if gini_split < best_gini:
                best_gini = gini_split
                best_feature = feature
                best_threshold = threshold

    return best_feature, best_threshold

三、防止过拟合

决策树很容易过拟合——如果让树无限生长，每个叶节点只包含一个样本，训练误差为 0 但泛化能力极差。

3.1 预剪枝

在树生长过程中提前停止：
- 最大深度限制（max_depth）
- 节点最小样本数（min_samples_split）
- 叶节点最小样本数（min_samples_leaf）
- 不纯度减少阈值（min_impurity_decrease）

3.2 后剪枝

先生成完整的树，然后从下往上拆除对泛化能力贡献不大的分支。

在实际应用中，预剪枝更常用也更容易调参。

四、随机森林

4.1 Bagging

Bagging（Bootstrap Aggregating）的核心思想：用有放回抽样生成多个不同的训练子集，在每个子集上独立训练决策树，预测时取所有树的平均（回归）或多数投票（分类）。

$$\hat{y} = \frac{1}{T} \sum_{t=1}^{T} f_t(x) \quad \text{（回归）}$$

$$\hat{y} = \text{mode}{f_1(x), f_2(x), ..., f_T(x)} \quad \text{（分类）}$$

4.2 随机森林的改进

随机森林在 Bagging 的基础上增加了特征随机性：在每个节点分裂时，不是从所有特征中选择最佳分割，而是随机选择一部分特征（通常为 sqrt(n_features)）。

这种"双重随机性"（样本随机 + 特征随机）让树之间的相关性更低，集成的效果更好。

4.3 特征重要性

随机森林可以自然地计算特征重要性：对每个特征，计算它在所有树中作为分割点时所减少的不纯度之和。特征重要性可以帮助我们理解数据和做特征选择。

from sklearn.ensemble import RandomForestClassifier

model = RandomForestClassifier(
    n_estimators=100,       # 树的数量
    max_depth=10,           # 最大深度
    min_samples_split=5,    # 内部节点最小样本数
    min_samples_leaf=2,     # 叶节点最小样本数
    max_features='sqrt',    # 每棵树使用的特征比例
    random_state=42
)
model.fit(X_train, y_train)

# 特征重要性
importances = model.feature_importances_

五、XGBoost

5.1 Boosting vs Bagging

Boosting 与 Bagging 的核心理念不同：
- Bagging：并行训练多个独立模型，平均它们的预测
- Boosting：顺序训练模型，每个新模型专注于纠正前一个模型的错误

5.2 XGBoost 的核心思想

XGBoost（Extreme Gradient Boosting）是梯度提升的优化实现。它的目标函数：

$$\mathcal{L} = \sum_{i=1}^{m} l(y_i, \hat{y}i) + \sum{k=1}^{K} \Omega(f_k)$$

其中 l 是可微损失函数，Ω 是树的复杂度惩罚项（L1 正则化 + L2 正则化 + 叶节点数控制）。

XGBoost 使用二阶泰勒展开近似损失函数，相比一阶方法收敛更快。

5.3 XGBoost 的特点

• 自动处理缺失值
• 内置交叉验证
• 支持自定义损失函数
• 列块结构支持并行计算
• 缓存优化和核外计算

import xgboost as xgb

model = xgb.XGBClassifier(
    n_estimators=100,
    max_depth=6,
    learning_rate=0.1,    # 学习率（shrinkage）
    subsample=0.8,        # 样本采样比例
    colsample_bytree=0.8, # 特征采样比例
    reg_lambda=1.0,       # L2 正则化
    reg_alpha=0.0,        # L1 正则化
    random_state=42
)
model.fit(X_train, y_train)

# 特征重要性
xgb.plot_importance(model)

六、实践选择指南

延伸阅读

• 📺 B 站播放列表：Machine Learning Specialization (2022) — 新版机器学习
• 📚 更多学习资源，请访问 deeplearning.ai 官网