什么是CART回归树

CART（Classification and Regression Tree，分类与回归树） 是一种决策树算法，既可以用于分类问题（Classification）也可以用于回归问题（Regression）。当应用于分类时，称为CART分类树；当应用于回归时，称为CART回归树。

什么是 CART 回归树？

CART回归树是一种决策树算法，用于解决回归问题。与分类树不同，回归树的目标是预测一个连续值，而不是离散的类别标签。CART 回归树通过递归地划分数据集，将数据集分成多个子集，每个叶子节点代表一个预测值（通常是子集中数据的平均值）。

CART 回归树的核心思想是：

• 寻找最优的分裂点（划分特征和特征取值），使得划分后的子集能够最好地拟合数据。
• 分裂后的子集的目标值之间的差异要尽可能小，达到最佳的拟合效果。

CART 回归树的构建步骤

1. 选择分裂特征和分裂点：
   CART 回归树的核心是通过选择最优的特征和分裂点，将数据集划分为两个子集。目标是使得划分后子集中的数据更加“纯”，即子集中目标变量（预测值）的方差或误差最小。

2. 计算分裂的优化标准：
   CART 回归树通过最小化平方误差（Mean Squared Error, MSE） 来选择最优分裂点：

   • 对于一个节点的数据集 D D D，目标是找到某个特征 X j X_j Xj​ 及其取值 s s s 作为分裂点，将数据集分成两个子集 D 1 D_1 D1​ 和 D 2 D_2 D2​，使得分裂后的误差最小化。

   • 误差可以用以下公式来衡量（基于均方误差 MSE）：
     MSE ( D ) = 1 ∣ D ∣ ∑ i ∈ D ( y i − y ^ ) 2 \text{MSE}(D) = \frac{1}{|D|} \sum_{i \in D} (y_i - \hat{y})^2 MSE(D)=∣D∣1​i∈D∑​(yi​−y^​)2

     其中 y i y_i yi​ 是第 i i i 个样本的真实值， y ^ \hat{y} y^​ 是该节点中所有样本的均值， ∣ D ∣ |D| ∣D∣ 是数据集的大小。

   • CART 回归树在每一步选择使 MSE 最小化的分裂点，即通过最小化方差来选择最佳分裂点。

3. 递归划分数据集：
   在找到最优的分裂点后，数据集会被划分为两个子集，分别递归地构建子树。这个过程不断重复，直到满足停止条件（如节点样本数太小，或误差过小）。

4. 叶子节点的预测：
   当树构建完成时，叶子节点将对应一个预测值，通常是叶子节点中样本的均值。对于新样本，回归树根据其特征值沿着树的分支一路下行，直到到达某个叶子节点，返回叶子节点的预测值作为最终输出。

树的分裂标准 - 最小化方差

CART 回归树的分裂标准是通过最小化方差（也称为总方差降低，或基于均方误差 MSE 的最小化）来选择最优分裂点。

假设当前数据集 D D D 被分裂为 D 1 D_1 D1​ 和 D 2 D_2 D2​，我们想通过分裂点 s s s 使得这两个子集的方差最小，定义如下：
Var ( D ) = 1 ∣ D ∣ ∑ i ∈ D ( y i − y ˉ ) 2 \text{Var}(D) = \frac{1}{|D|} \sum_{i \in D} (y_i - \bar{y})^2 Var(D)=∣D∣1​i∈D∑​(yi​−yˉ​)2

其中， y ˉ \bar{y} yˉ​ 是数据集 D D D 中目标变量的均值。

我们希望通过找到某个特征 X j X_j Xj​ 和分裂点 s s s，将数据集 D D D 划分为两个子集 D 1 D_1 D1​ 和 D 2 D_2 D2​，使得分裂后的总方差减少最大：
Total Var ( D ) = ∣ D 1 ∣ ∣ D ∣ Var ( D 1 ) + ∣ D 2 ∣ ∣ D ∣ Var ( D 2 ) \text{Total Var}(D) = \frac{|D_1|}{|D|} \text{Var}(D_1) + \frac{|D_2|}{|D|} \text{Var}(D_2) Total Var(D)=∣D∣∣D1​∣​Var(D1​)+∣D∣∣D2​∣​Var(D2​)

目标是找到一个 s s s 使得划分后的总方差最小。

预测过程

当一棵 CART 回归树构建完成后，预测过程非常直观：

1. 对于一个新输入的样本，从根节点开始，检查该样本的特征值。
2. 根据特征值与分裂点的比较，选择左子树或右子树。
3. 继续沿树下降，直到到达某个叶子节点。
4. 返回该叶子节点中的均值作为该样本的预测值。

树的剪枝（Pruning）

为了防止过拟合，CART 回归树通常使用剪枝技术。在树构建过程中，树会继续生长，直到达到某个停止条件（如所有叶子节点的样本数都很小）。这种完全生长的树可能会导致过拟合，因此在实际应用中，通常会使用剪枝技术来简化树结构，防止模型过度复杂。

CART 通常使用代价复杂度剪枝（Cost Complexity Pruning），即通过在考虑树的复杂度（叶子节点的数量）和拟合误差之间进行权衡，来选择合适的剪枝策略。

CART 回归树的优点

1. 简单直观：CART 回归树的算法逻辑简单易懂，结果也容易解释。
2. 处理连续值：CART 回归树特别适合处理连续值的回归任务，能够很好地拟合复杂的数据集。
3. 可处理多种类型数据：既可以处理数值型特征，也可以处理分类特征。
4. 自动特征选择：通过信息增益、方差等标准，自动选择最优的特征进行划分，无需手动选择特征。

举例说明

假设我们有一个数据集，包含房屋面积（square footage）和价格（price）两列，目标是根据房屋面积预测价格。我们可以用 CART 回归树来构建预测模型。

数据如下：

• CART 回归树首先会计算在某个面积上进行划分是否能最大程度减少房价的方差。例如，它可能在 1300 平方英尺上进行第一次划分，将数据集分为两个子集：

  • 子集 1：房屋面积 ≤ 1300。
  • 子集 2：房屋面积 > 1300。

• 在每个子集中，它会递归继续寻找最优的分裂点，直到达到某个停止条件（如叶子节点样本数过少）。

最终构建出的 CART 回归树会对房价做出预测，例如，如果房屋面积在 1000 到 1300 之间，预测的房价可能是 350,000 美元。

总结

• CART回归树是一种用于解决回归问题的决策树算法，它的核心是通过最小化方差来选择最佳分裂点，将数据集不断划分，直到满足停止条件。
• 分裂标准基于最小化平方误差（MSE）或方差，最终目的是构建出能够较好拟合数据的树模型。
• 预测过程中，CART 回归树通过递归遍历树结构，最终返回叶子节点中的均值作为预测值。
• 通过剪枝技术，CART 回归树能够避免过拟合，提高模型的泛化能力。