第九章：树模型与随机森林

本章将讨论一类极为重要的非参数学习方法——决策树（Decision Trees）及其集成扩展（Ensemble Methods）。以分类与回归树（Classification and Regression Trees, CART）为代表的树模型，通过递归地将特征空间划分（Recursive Partitioning）为若干个互不重叠的超矩形区域，并在每个区域内部进行简单常数预测。我们将系统推导其分裂准则、剪枝算法，并深入分析随机森林（Random Forest）的渐近正态性与 U-统计量理论。

1. 分类与回归树（CART）基本设定

定义 1.1 (特征空间的递归划分)

给定训练数据集 \(\mathcal{D}_{n}=\{(x_{i}, y_{i})\}_{i=1}^{n}\)，其中特征向量 \(x_{i} \in \mathbb{R}^p\)。一个深度为 \(M\) 的决策树将整个输入特征空间 \(X\) 划分为 \(M\) 个互不相交的超矩形区域（Hyper-rectangular Regions） \(R_1, R_2, \dots, R_M\)。

其对应的预测函数表达式具有如下通用分段常数形式：

\[ f(x) = \sum_{m=1}^M c_m \mathbb{I}(x \in R_m) \]

1.1 回归树的最优参数选择

对于回归问题，若采用常用的平方损失函数（Squared Error Loss），则在每个划分区域 \(R_m\) 内的最优预测常数 \(c_m\) 为该区域内所有训练样本响应变量的样本均值：

\[ \hat{c}_m = \text{avg}(y_i \mid x_i \in R_m) \]

2. 分裂准则与局部最优化（贪心算法）

在特征空间中寻找能使全局全局残差平方和最小的区域划分是一个 NP-Hard 问题。在实际应用中，CART 采用贪心算法（Greedy Algorithm）进行自顶向下的逐层最优二叉分裂。

定义 2.1 (最佳二叉分裂优化目标)

考虑某一个当前待分裂的节点区域 \(R\)。我们选择第 \(j\) 个特征作为分裂变量，并选择 \(s\) 作为分裂切分点（Split Point），以此将该区域划分为两个子区域：

\[ R_1(j, s) = \{x \mid x_j \le s\}, \quad R_2(j, s) = \{x \mid x_j > s\} \]

对于回归树，切分变量 \(j\) 和切分点 \(s\) 的局部最优化求解目标可表示为：

\[ \min_{j, s} \left[ \min_{c_1} \sum_{x_i \in R_1(j, s)} (y_i - c_1)^2 + \min_{c_2} \sum_{x_i \in R_2(j, s)} (y_i - c_2)^2 \right] \]

2.1 分类树的不纯度度量（Impurity Measures）

对于分类树问题，由于响应变量 \(y_i \in \{1, 2, \dots, K\}\) 是离散标签，我们首先定义节点 \(m\) 中属于第 \(k\) 类的样本经验概率为：

\[ \hat{p}_{mk} = \frac{1}{|R_m|} \sum_{x_i \in R_m} \mathbb{I}(y_i = k) \]

为了衡量节点的不纯度，通常采用以下两种非线性度量指标替代分类错误率：

基尼指数（Gini Index）：

\[ H_m = \sum_{k=1}^K \hat{p}_{mk} (1 - \hat{p}_{mk}) = 1 - \sum_{k=1}^K \hat{p}_{mk}^2 \]

交叉熵（Cross-Entropy / Information Entropy）：

\[ H_m = -\sum_{k=1}^K \hat{p}_{mk} \ln \hat{p}_{mk} \]

3. 代价复杂度剪枝算法（Cost-Complexity Pruning）

若任由树模型无限制地生长，直至每个叶节点只包含一个样本，会导致模型过拟合，估计方差极大。为了控制模型复杂度，需要对完全生长的原始树 \(T_0\) 进行剪枝。

定义 3.1 (代价复杂度目标函数)

设 \(T \subset T_0\) 是由 \(T_0\) 剪枝得到的任意子树。令 \(|T|\) 表示子树 \(T\) 的叶节点总数，\(R_m\) 为第 \(m\) 个叶节点覆盖的区域，\(Q_m(T)\) 为该节点对应的不纯度总损失。引入正则化调整参数 \(\alpha \ge 0\)，其代价复杂度定义为：

\[ C_\alpha(T) = \sum_{m=1}^{|T|} |R_m| Q_m(T) + \alpha |T| \]

定理 3.1 (最弱叶节点剪枝性质)

对于任意给定的复杂度惩罚因子 \(\alpha\)，存在一个唯一的最小最优化子树 \(T_\alpha = \arg\min_{T \subset T_0} C_\alpha(T)\)。随着 \(\alpha\) 从 0 连续增大到 \(\infty\)，最优子树序列是有限且嵌套的。

证明：单节点内部剪枝临界点 \(\alpha\) 的推导

考虑树 \(T_0\) 中的某一个内部单节点 \(t\)。

设以 \(t\) 为根节点的子树为 \(T_t\)（包含多个叶子节点）。如果不剪枝，该局部子树的代价复杂度贡献为：

\[ C_\alpha(T_t) = R(T_t) + \alpha |T_t| \]

其中 \(R(T_t) = \sum_{m \in \text{leaves}(T_t)} |R_m| Q_m(T)\)。

如果将以 \(t\) 为根的子树剪掉，即将其强行塌陷合并为一个单叶子节点 \(t\)，此时它的代价复杂度贡献为：

\[ C_\alpha(\{t\}) = R(t) + \alpha \]

当 \(\alpha\) 较小时，不剪枝的精度收益大，有 \(C_\alpha(T_t) < C_\alpha(\{t\})\)。然而，当 \(\alpha\) 增大到某个临界点时，两者相等。通过令 \(C_\alpha(T_t) = C_\alpha(\{t\})\) 可反解出：

\[ R(T_t) + \alpha |T_t| = R(t) + \alpha \implies \alpha (|T_t| - 1) = R(t) - R(T_t) \]

解得关键的临界剪枝阈值函数：

\[ \alpha = \frac{R(t) - R(T_t)}{|T_t| - 1} \]

在整个大树结构中，通过依次遍历计算所有内部节点的 \(\alpha\) 值，并优先剪去 \(\alpha\) 最小的节点，即证可以自底向上构造出离散的最优嵌套子树链。

4. 随机森林与袋外估计（OOB）

随机森林（Random Forest）通过自助法（Bootstrap Aggregation, Bagging）和随机特征选择（Random Feature Selection）进一步降低了单棵决策树的方差。

4.1 算法核心机制

Bootstrap 抽样：从原始拥有 \(n\) 个样本的数据集中，进行 \(B\) 次有放回的重采样，每次抽样规模同样为 \(n\)。
随机构造节点：在每棵树的每个节点进行分裂时，不从全部 \(p\) 个特征中搜寻，而是随机无放回抽样选择 \(m \ll p\)（通常取 \(m = \sqrt{p}\)）个特征子集，再从中选择最优分裂点。

4.2 袋外估计（Out-of-Bag Error Estimation）

由于 Bootstrap 抽样是有放回的，对于任意一个样本 \(i\)，它在某次重采样中从未被抽中的概率为：

\[ P(\text{样本 } i \text{ 未被抽中}) = \left( 1 - \frac{1}{n} \right)^n \xrightarrow{n \to \infty} e^{-1} \approx 0.368 \]

这表明平均每棵树有约 36.8% 的训练数据未参与构建，这部分数据被称为该树的袋外数据（Out-of-Bag, OOB）。我们可以直接利用袋外样本作为验证集，计算泛化误差，从而免去了繁琐的交叉验证（Cross Validation）。

5. 随机森林渐近正态性与 U-统计量理论

近年来，随机森林的渐近统计性质通过 U-统计量（U-statistics） 理论得到了严格证明。该理论为估计随机森林的预测方差和构建置信区间奠定了数学基础。

定义 5.1 (基于不完全子样本的 U-统计量预测器)

设 \(Z_i = (X_i, Y_i)\)。令 \(h(Z_{i_1}, \dots, Z_{i_r})\) 表示基于大小为 \(r\) (\(r < n\)) 的不放回抽样非完全子样本构建的单棵树估计器。若精细遍历所有可能的 \(\binom{n}{r}\) 种组合，其最小方差无偏估计器（完全 U-统计量）形式为：

\[ U_n = \frac{1}{\binom{n}{r}} \sum_{(i)} h(Z_{i_1}, \dots, Z_{i_r}) \]

5.1 共享单样本渐近方差定理

随机森林的预测结果可以近似视为这种 U-统计量的变体。

定理 5.1 (Mentch & Hooker 渐近正态性定理)

在高维大样本设定下，随着总体样本 \(n \to \infty\) 且单棵树的样本容量 \(r\) 满足 \(r = o(\sqrt{n})\) 时，不完全 U-统计量架构下的随机森林预测值满足渐近正态性：

\[ \frac{\sqrt{n}(U_n - \theta)}{\sqrt{r^2 \zeta_{1,r}}} \xrightarrow{d} N(0, 1) \]

其中，核心关键协方差指标 \(\zeta_{1,r}\) 定义为两棵相互独立的树在仅仅共享一个相同观测样本时的协方差：

\[ \zeta_{1,r} = \text{Cov}\left( h(Z_1, Z_2, \dots, Z_r), h(Z_1, Z_2', \dots, Z_r') \right) \]

通过这一理论，我们仅需提取随机森林中那些只包含单个共同样本的决策树对的预测结果并计算其样本协方差，即可在实际中实现预测点处的方差量化。