重读统计学习方法：决策树

跳过了MLP，KNN，从决策树再开始温习，也为了后面的XGBoost，LGBM和CATBoost打一下基础。

顺便一提，今天见证了DeepSeek刷榜Github，从没见过这么夸张的刷榜，TOP10有6个都是DS的项目。

决策树

单棵决策树很好理解，就是根据条件判断来得到预测的分类或数值。当条件变多时，就会通过加深层数的方式来提高模型蕴含的信息量。

决策树的核心思想还是通过特征划分数据，并最终递归的构建成一棵树。这需要达成互斥且完备，也就是每个路径都是唯一的。因此如何划分数据，就成了决策树中的关键问题，常说的ID3/C45/CART的区别就在此。

ID3：信息增益

首先有熵的定义：$H(D) = -\sum_{i=1}^{k} p_i \log_2{p_i}$，用于衡量数据集的不确定性，其中，$p_i$ 是类别$i$的概率。熵在信息论中被定义为系统的混乱程度，熵越大，系统的不确定性越大。

信息增益衡量某个特征$A$在划分数据集$D$后，信息熵的减少量：$IG(D, A) = H(D) - \sum_{v \in A} \frac{|D_v|}{|D|} H(D_v)$。其中$H(D)$是原始数据集的熵，$D_v$ 是按特征$A$取值$v$分割后的数据子集。熵减的越多，说明特征在数据中越重要。

在实际操作时，先以目标变量计算经验熵，随后递归的对不同特征进行信息增益的计算，并且每次取信息增益大的特征作为下一分割点。

C4.5：信息增益比

ID3里，某一特征的独立值越大，被任务它所蕴含的信息越大，因此会倾向于选择多值特征。为了解决这个问题，C4.5 使用信息增益比进行改进，从减改成比：$GainRatio(D, A) = \frac{IG(D, A)}{IV(A)}$。其中，IV(A)（信息值） 是特征$A$的熵：$IV(A) = -\sum_{v \in A} \frac{|D_v|}{|D|} \log_2 \frac{|D_v|}{|D|}$。

IV值同样在风控领域被广泛用到，两边公式有点类似：风控领域使用基于WOE（证据权重）的差距度量，计算公式为：$IV = \sum_{i=1}^{n} (WOE_i \times (p_i - q_i))$

其中， $WOE_i = \log \frac{p_i}{q_i}$，$p_i$ = 该分组中的 好用户占比（未违约用户数 / 总未违约用户数），$q_i$ = 该分组中的 坏用户占比（违约用户数 / 总违约用户数）。

  • 其中的IV值里，$p_i - q_i$衡量了该分组相对总体分布的不均衡性。
  • $WOE_i$衡量了该分组对好/坏用户的区分能力。
  • 乘积 $WOE_i \times (p_i - q_i)$体现了该分组在整体上的影响力，最终 IV 通过累加所有分组的影响力得到一个特征的重要性评分。

CART ：基尼系数

CART树被改进后，支持分类和回归任务。它被设计为递归的生成二叉树，在分类任务上使用基尼系数最小化作为特征选择的准则，回归任务上使用MSE最小化作为特征选择的准则。

基尼指数（Gini Index） 衡量数据集的纯度：$Gini(D) = 1 - \sum_{i=1}^{k} p_i^2$

特征$A$的基尼指数：$GiniIndex(D, A) = \sum_{v \in A} \frac{|D_v|}{|D|} Gini(D_v)$

决策树的优缺点

优点 缺点
直观易理解 容易过拟合
训练速度快 对噪声敏感
适用于分类和回归 不擅长处理连续变量
适用于小数据集 可能受特征选择影响

随着树深度的增长，决策树容易陷入过拟合，这时一般通过剪枝或Bagging/Boosting的方法提高鲁棒性。

此外，由于每次特征筛选时都要计算全量数据的对应特征熵，可想而知在大数据情况下，构建决策树将会非常慢。

回归树

决策树原本只能预测离散变量，后续的CART支持了连续变量的预测，其中的修改主要是两点：损失函数由交叉熵变为MSE/RMSE之类的传统连续变量损失函数，预测目标由分类变成子节点均值。

例如，根据某一特征进行分裂后，取这一特征下，所有目标变量的均值作为这一特征节点下的预测目标变量。

抄一下GPT给出的计算流程：

回归树的构造过程如下：

计算分裂前的目标变量均值

假设数据集$D$共有$n$个样本，目标变量的均值为：

$\bar{y} = \frac{1}{n} \sum_{i=1}^{n} y_i$

如果此时直接停止分裂，那么整个数据集的均值 $\bar{y}$就是最终的预测值。

选择最优分裂点

回归树的目标是通过最小化均方误差（MSE, Mean Squared Error） 来选择分裂特征和分裂点：

$MSE = \sum_{i=1}^{n} (y_i - \bar{y})^2$

如果选择特征$A$和分裂点$s$进行划分，数据集被分成左子集$D_1$和右子集 $D_2$，均值分别为$\frac{1}{|D_1|} \sum_{y_i: y_i \in D_1} y_i$和$\frac{1}{|D_2|} \sum_{y_i: y_i \in D_2} y_i$

会选择能使Loss最小的$A,s$作为最优分裂点。

递归分裂，直到叶子节点

  • 如果满足停止条件（如样本数小于最小叶子样本数），则停止分裂。

  • 叶子节点的最终预测值 就是该叶子节点所有样本的目标变量均值

📌 示例： 假设一个回归树用于预测房价，数据集如下：

面积 (㎡) 房价（万元）
50 150
55 160
70 180
75 190
90 220
100 250

构造回归树步骤：

  1. 计算整个数据集的目标变量均值： $\bar{y} = \frac{150 + 160 + 180 + 190 + 220 + 250}{6} = 191.67$
  2. 选择最佳分裂点（如面积 70 ㎡），划分数据集：
    • 左子树（面积 ≤ 70）：$\bar{y}_1 = \frac{150 + 160 + 180}{3} = 163.33$
    • 右子树（面积 > 70）：$\bar{y}_2 = \frac{190 + 220 + 250}{3} = 220.00$

预测房价：

  • 如果面积 ≤ 70，预测值是 163.33 万。
  • 如果面积 > 70，预测值是 220.00 万。

2025/2/3 于苏州