03 | 决策树 ¶

ID3¶

如何理解信息熵 _ 哔哩哔哩 _bilibili

C4.5¶

不连续处理 ¶

CART¶

要注意 CART 认为是二叉树

从零实现 CART 决策树算法 - 知乎

不连续处理 ¶

剪枝处理 ¶

决策树：CART 决策树剪枝算法（超详细）_cart 采用什么剪枝策略 -CSDN 博客

多分类 ¶

缺失值处理 ¶

随机森林（Bagging 集成方法）¶

简单概括就是，使用 bagging 进行集成的基础上，每次在 n 个特征里面随机选取 \(m\) 个进行决策

variable importance¶

随机森林特征重要性（Variable importance）评估方法 -CSDN 博客 | 比较项 | MDI（Mean Decrease in Impurity） | MDA（Mean Decrease Accuracy） | | ---------- | ------------------------------ | --------------------------- | | 原理 | 特征导致的 impurity 减少量 | 特征打乱后模型性能下降量 | | 是否用验证集 | ❌ 不使用，只基于训练集 | ✅ 需要验证集（或OOB） | | 是否易计算 | ✅ 快速计算 | ❌ 需打乱、重算预测 | | 是否受变量相关性影响 | ✅ 是（共线变量重要性被分散） | ✅ 是（打乱一个变量可能影响其他变量） | | 偏好 | 偏向高基数特征（如ID类、连续变量） | 更公平但计算量大 |

MDI¶

MDI 的核心思想：

衡量某个变量在所有树中用来分裂节点时，导致的平均“纯度（impurity）下降”总和。

这是一种基于模型结构本身的变量重要性度量方法。

设有特征 \(X_j\)，其 MDI 计算如下：

其中：

• 节点 \(n\)：所有使用 \(X_j\) 的决策树节点
• \(p(n)\)：该节点所占样本比例（例如左子树 + 右子树样本数占总体的比例）
• \(\Delta i(n)\)：该节点进行分裂带来的 impurity 减少（如 Gini impurity 或 entropy 的下降）

换句话说，一个变量的重要性等于它在所有树上每次被用来分裂时带来的 impurity 降低的总和。

MDA¶

MDA 的核心思想是：通过打乱一个变量的值（破坏其与目标的关联），观察模型性能下降的程度，来判断该变量的重要性。

对于每个特征 \(X_j\)，其 MDA 值定义为：

其中：

• \(T\)：树的数量（比如在随机森林中）
• \(\text{Acc}_{\text{original}}^{(t)}\)：第 \(t\) 棵树在未打乱特征时的验证集精度
• \(\text{Acc}_{\text{permuted}}^{(t,j)}\)：第 \(t\) 棵树在打乱特征 \(X_j\) 后的验证集精度

最终，这个差值越大，说明该特征对模型越重要。

• MDA 容易受特征之间的相关性影响：打乱一个特征可能同时影响另一个特征的作用。
• 对于分类问题和回归问题都适用
• 在训练数据不平衡或特征分布极不均匀时，MDA 可能不稳定。

Bias Varience & consistency¶

• 输入只有一个特征 \(X \sim \text{Uniform}[0, 1]\)
• 输出是回归任务： \(Y = f(X) + \epsilon\)
• \(f(X)\) 是 L-Lipschitz 连续函数
• 构建决策树时：每次固定在当前节点中位数处分裂（不依赖数据标签）

在这个设定下：随机森林 ≈ Histogram Estimator

• 每次分裂都将区间等分为两半 → 二叉树结构 → 类似直方图分桶

• 设置叶子节点最小样本数为 \(k\)，则：

  • 树深度大约为 \(\log_2(n/k)\)
  • 每个叶节点对应的区间长度（带宽）为 \(2^{-\log_2(n/k)} = \frac{k}{n}\)
  • 每个叶节点估计 \(\bar{y}\)：节点内平均值

尽管上述分析是“固定分裂点”的简化情况，但真实随机森林具备：

• 自适应选择分裂变量
• 自适应选择分裂点
• 在多维空间中，自动进行局部带宽调整
• 在特征具有不同信号强度时，自动倾向于选择“更有用”的特征（Lin and Jeon, 2006）

Normality¶

• 随机森林是由多个子模型（树）在不同 bootstrap 样本上训练后平均得来的模型。
• 这类“平均型”估计器可以用统计理论中的 U- 统计量理论 来分析其偏差、方差与渐近分布。
• 目标是推导随机森林在样本量 \(n \to \infty\) 时，估计量的方差与分布，并说明它近似服从正态分布（CLT）。

1. U- 统计量视角下的随机森林

• \(Z_i = (X_i, Y_i)\)：观测数据点
• \(h(Z_{i_1}, \dots, Z_{i_r})\)：一个基本估计器，例如一棵基于 \(r\) 个样本构建的树（可以是 subsample，而非 bootstrap）
• \(\theta = \mathbb{E}[h]\)：我们想要估计的目标（如某点的预测值）

✳️ 构造 U 统计量：

U- 统计量是所有可能的样本子集上平均的估计器：

即遍历所有组合子集，平均每个子集上的函数 \(h\)。

2. 方差估计与协方差结构

• 当 \(r \ll n\) 时，U- 统计量的方差近似为：

其中：

解释：

• 两个估计器之间仅共享一个样本 \(Z_1\)，其余都是不同的观测
• \(\zeta_{1,r}\) 衡量“部分重叠”导致的相关性

• 每棵树可以视为 \(h(\cdot)\)：一个基于 \(r\) 个样本（subsample 或 bootstrap）的估计器
• 随机森林的最终预测是多个这样的树的平均
• 但我们没有用完所有子集（因为太多了！）：这被称为 incomplete U-statistics

根据 U- 统计量理论，当 \(n \to \infty\) 且满足一定条件时：

这说明：

• 随机森林预测是渐近正态的
• 可用于构造置信区间、显著性检验等

对比 ¶