CART树

小象实战讲义 · 机器学习算法精讲

上节课我们学习了决策树如何利用信息增益进行特征分割，解决分类问题。本节课，我们将深入探讨决策树的另一个强大分支——CART（Classification and Regression Tree），它不仅能做分类，还能做回归预测。我们将理解CART如何将输入空间分割成多个区域，并学习其用于回归和分类的核心算法与损失函数。

💡 核心导读

• CART是什么：了解CART（分类与回归树）的提出背景与核心思想，即通过树结构同时处理分类与回归任务。
• 从分类到回归：直观理解决策树如何从输出类别标签（如0/1）扩展到输出连续值（如均值），实现回归预测。
• 回归树的损失函数：掌握CART回归树用于寻找最优分割点的平方误差损失函数及其最小化过程。
• 算法流程与示例：通过一维和二维的具体例子，一步步拆解CART如何选择特征和分割点来构建树。
• 分类树的基尼指数：了解CART分类树使用基尼指数（Gini index）作为不纯度度量进行特征分割。

CART：分类与回归树

CART，全称Classification and Regression Tree，由统计学家Leo Breiman提出。它扩展了决策树的能力，使其不仅能处理输出为离散类别的分类问题，还能处理输出为连续值的回归问题。

决策树的本质是在输入空间（特征空间）中进行一系列垂直分割。例如，在二维空间中，我们可能先根据特征 $x_1$ 是否小于等于 $\alpha$ 将空间分为左右两部分，然后在左半部分根据特征 $x_2$ 是否小于等于 $\beta_1$ 进一步分割，如此递归进行，最终将整个空间划分成若干个互不重叠的矩形区域。

对于分类问题，每个区域会被赋予一个类别标签（如C1或C2）。当一个新的数据点落入某个区域，就预测它属于该区域对应的类别。

对于回归问题，思路是类似的。每个区域不再对应一个类别，而是对应一个连续的预测值。这个值通常取为该区域内所有训练样本输出值 $y$ 的均值。因此，CART回归树的预测函数是一个分段常数函数：在同一个区域内的所有点，预测值相同。

CART回归树算法

假设我们有一个训练数据集 $D = \lbrace (\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \dots, (\mathbf{x}_N, y_N)\rbrace$，其中 $\mathbf{x}_i$ 是一个 $p$ 维特征向量，$y_i$ 是连续值输出。

CART回归树采用二叉递归分割。在每一步，我们需要选择一个特征 $j$（$1 \le j \le p$）和一个分割点 $s$，将当前节点对应的数据区域 $R$ 划分为两个子区域：

• $R_1(j, s) = \lbrace \mathbf{x} | x^{(j)} \le s\rbrace$
• $R_2(j, s) = \lbrace \mathbf{x} | x^{(j)} > s\rbrace$

我们的目标是找到最优的 $(j, s)$，使得划分后两个子区域内的预测误差之和最小。对于回归问题，最常用的误差度量是平方误差。因此，我们最小化以下损失函数：

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

其中，$c_1$ 和 $c_2$ 分别是区域 $R_1$ 和 $R_2$ 内的最优预测值。可以证明，当损失函数为平方误差时，区域 $R_m$ 内的最优预测值 $c_m$ 就是该区域内所有 $y_i$ 的均值：

$$c_m = \frac{1}{N_m} \sum_{\mathbf{x}_i \in R_m} y_i$$

这里 $N_m$ 是区域 $R_m$ 中样本的数量。

因此，算法步骤可以简化为：

1. 遍历所有特征 $j$。
2. 对每个特征 $j$，遍历所有可能的分割点 $s$（通常取相邻样本值之间的中点，如代码里的 1.5、2.5、…、9.5）。
3. 对于每一对 $(j, s)$，按规则划分区域，并计算两个区域的均值 $c_1, c_2$。
4. 计算当前划分下的总平方误差损失 $L(j, s) = \sum_{\mathbf{x}_i \in R_1} (y_i - c_1)^2 + \sum_{\mathbf{x}_i \in R_2} (y_i - c_2)^2$。
5. 选择使 $L(j, s)$ 最小的 $(j, s)$ 作为当前节点的分割规则。
6. 对得到的两个子区域 $R_1$ 和 $R_2$，递归地重复步骤1-5，直到满足停止条件（如区域样本数过少、深度限制等）。

下面，我们通过一个极简的一维例子来演示这个过程。

import math

# 训练数据：一维特征x，连续目标值y
# 这里构造一个简单的线性关系 y ≈ x - 1，但算法并不知道这个关系
data = [(1, 0), (2, 1), (3, 2), (4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (9, 8), (10, 9)]

# 计算给定分割点s下的损失
def calculate_loss_for_split(s, data):
    R1 = [y for x, y in data if x <= s]
    R2 = [y for x, y in data if x > s]
    
    if not R1 or not R2:  # 如果有一个区域为空，返回一个很大的损失
        return float('inf'), None, None
    
    c1 = sum(R1) / len(R1)
    c2 = sum(R2) / len(R2)
    
    loss = sum((y - c1)**2 for y in R1) + sum((y - c2)**2 for y in R2)
    return loss, c1, c2

# 可能的分割点（取相邻x值的中点）
possible_splits = [x + 0.5 for x in range(1, 10)]

print("分割点 s | 左区域均值 c1 | 右区域均值 c2 | 损失 L(s)")
print("-------------------------------------------------------")

results = []
for s in possible_splits:
    loss, c1, c2 = calculate_loss_for_split(s, data)
    results.append((s, c1, c2, loss))
    print(f"   {s:.1f}    |     {c1:.2f}      |     {c2:.2f}      |   {loss:5.2f}   ")

# 找到最优分割点
best_split = min(results, key=lambda x: x[3])
print(f"\n最优分割点 s = {best_split[0]:.1f}")
print(f"此时左区域均值 c1 = {best_split[1]:.2f}, 右区域均值 c2 = {best_split[2]:.2f}")
print(f"最小损失 L(s) = {best_split[3]:.2f}")

分割点 s | 左区域均值 c1 | 右区域均值 c2 | 损失 L(s)
-------------------------------------------------------
   1.5    |     0.00      |     5.00      |   60.00   
   2.5    |     0.50      |     5.50      |   42.50   
   3.5    |     1.00      |     6.00      |   30.00   
   4.5    |     1.50      |     6.50      |   22.50   
   5.5    |     2.00      |     7.00      |   20.00   
   6.5    |     2.50      |     7.50      |   22.50   
   7.5    |     3.00      |     8.00      |   30.00   
   8.5    |     3.50      |     8.50      |   42.50   
   9.5    |     4.00      |     9.00      |   60.00   

最优分割点 s = 5.5
此时左区域均值 c1 = 2.00, 右区域均值 c2 = 7.00
最小损失 L(s) = 20.00

从结果可以看出，当分割点 $s=5.5$ 时，总平方误差损失最小，为20.0。这意味着将数据在 $x=5.5$ 处一分为二，左区域用均值2.0预测，右区域用均值7.0预测，是当前所有二分方案中最优的。讲师在课上还口头验算了两刀：$s=1.5$ 时左区域只有 $y=0$、右区域均值是 5；$s=4.5$ 时左均值 1.5、右均值 6.5——与表中数字一致。这完成了第一次分割。接下来，我们可以对左区域（$x \le 5.5$）和右区域（$x > 5.5$）分别递归地进行同样的分割过程，从而构建出一棵更深的树。

为什么每次只二分、不一次切三块五块？讲师的解释很直接：先切两大块，每一大块再各切两小块就成四块，四块再切就是八块——按 2 的幂次推进，同样能达到把区域切细的目的。所以每次只需要求”最优二分点”就够了。

多维时怎么选特征？把所有特征轮一遍：比如有 5 个特征，分别求出各自的最优分割损失，假设结果是 20、18、10、19、31——那就选第 3 个特征（损失最小 10）作为根节点的切割维度，正如决策树选根一样。之后在每个子区域里重新循环剩余特征继续找最优二分（讲师的演示里跳过了已用过的维度，只在其余特征里找切点；实践中二叉分割也允许在不同深度重复使用同一特征）。

CART分类树与基尼指数

对于分类问题，CART树通常使用基尼指数（Gini Index） 来衡量一个区域的不纯度（Impurity），并以此选择最优分割。基尼指数定义为：

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

其中，$K$ 是类别总数，$p_k$ 是区域中样本属于第 $k$ 类的比例。基尼指数越小，表示区域的纯度越高（样本越属于同一类）。

对于二分类问题（类别为0和1），若正类比例为 $p$，则基尼指数为 $2p(1-p)$。

在构建分类树时，对于每个候选分割 $(j, s)$ 将区域 $R$ 划分为 $R_1$ 和 $R_2$，我们计算划分后的加权基尼指数：

$$\text{Gini}_{\text{split}} = \frac{N_1}{N} \text{Gini}(R_1) + \frac{N_2}{N} \text{Gini}(R_2)$$

其中 $N$ 是 $R$ 中样本总数，$N_1, N_2$ 分别是 $R_1, R_2$ 的样本数。我们选择使 $\text{Gini}_{\text{split}}$ 最小的 $(j, s)$ 进行分割。

下面的代码演示了一个简化的CART分类树分割过程。

import random
random.seed(42)

# 生成简单的二维分类数据
def generate_classification_data():
    # 类别0大致在左下，类别1大致在右上
    data = []
    # 类别0的样本
    data.append(([1, 2], 0))
    data.append(([2, 3], 0))
    data.append(([6, 5], 0))
    # 类别1的样本
    data.append(([3, 1], 1))
    data.append(([4, 4], 1))
    data.append(([5, 2], 1))
    data.append(([7, 1], 1))
    data.append(([8, 3], 1))
    return data

# 计算一个区域的基尼指数
def gini_index(region_labels):
    if not region_labels:
        return 0
    total = len(region_labels)
    # 统计各类别数量
    from collections import Counter
    label_counts = Counter(region_labels)
    gini = 1.0
    for count in label_counts.values():
        prob = count / total
        gini -= prob ** 2
    return gini

# 寻找最优分割
def find_best_split_classification(data):
    n_features = len(data[0][0])
    best_gini = float('inf')
    best_feature = None
    best_split_value = None
    best_left_pred = None
    best_right_pred = None
    
    # 遍历每个特征
    for j in range(n_features):
        # 收集该特征所有可能的分割点（取样本特征值的中点）
        feature_values = sorted(list(set([x[j] for x, _ in data])))
        split_candidates = [(feature_values[i] + feature_values[i+1]) / 2 for i in range(len(feature_values)-1)]
        
        for s in split_candidates:
            left_labels = []
            right_labels = []
            for x, label in data:
                if x[j] <= s:
                    left_labels.append(label)
                else:
                    right_labels.append(label)
            
            # 计算加权基尼指数
            n_left, n_right = len(left_labels), len(right_labels)
            n_total = n_left + n_right
            if n_left == 0 or n_right == 0:
                continue
                
            weighted_gini = (n_left / n_total) * gini_index(left_labels) + (n_right / n_total) * gini_index(right_labels)
            
            if weighted_gini < best_gini:
                best_gini = weighted_gini
                best_feature = j
                best_split_value = s
                # 预测值为区域内的多数类
                from collections import Counter
                best_left_pred = Counter(left_labels).most_common(1)[0][0]
                best_right_pred = Counter(right_labels).most_common(1)[0][0]
    
    return best_feature, best_split_value, best_left_pred, best_right_pred, best_gini

# 主程序
data = generate_classification_data()
print("分类训练数据:")
for i, (x, label) in enumerate(data):
    print(f"  样本{i}: x={x}, 类别={label}")

print("\n开始训练简化CART分类树...")
best_feature, best_split, left_pred, right_pred, min_gini = find_best_split_classification(data)

print(f"最优分割特征: 第{best_feature}个，分割点: {best_split:.2f}")
print(f"左区域预测类别: {left_pred}, 右区域预测类别: {right_pred}")
print(f"最小加权基尼指数: {min_gini:.4f}")

# 预测测试
print("\n预测测试:")
test_points = [[2.5, 2], [5.5, 3]]
for test_x in test_points:
    if test_x[best_feature] <= best_split:
        pred = left_pred
    else:
        pred = right_pred
    print(f"  测试点 {test_x} 的预测类别为: {pred}")

分类训练数据:
  样本0: x=[1, 2], 类别=0
  样本1: x=[2, 3], 类别=0
  样本2: x=[6, 5], 类别=0
  样本3: x=[3, 1], 类别=1
  样本4: x=[4, 4], 类别=1
  样本5: x=[5, 2], 类别=1
  样本6: x=[7, 1], 类别=1
  样本7: x=[8, 3], 类别=1

开始训练简化CART分类树...
最优分割特征: 第0个，分割点: 2.50
左区域预测类别: 0, 右区域预测类别: 1
最小加权基尼指数: 0.2083

预测测试:
  测试点 [2.5, 2] 的预测类别为: 0
  测试点 [5.5, 3] 的预测类别为: 1

结果显示，算法选择在第一个特征（索引0）的 $x_0 = 2.5$ 处进行分割，使得加权基尼指数最小（0.2083）。左区域（$x_0 \le 2.5$）的样本都属于类别0，右区域（$x_0 > 2.5$）的样本大多属于类别1。这完成了分类树的第一次有效分割。

📝 动手练一练

1. 概念辨析：在CART回归树的损失函数中，为什么区域 $R_m$ 内的最优预测值 $c_m$ 是 $y_i$ 的均值？如果我们将损失函数从平方误差 $(y_i - c_m)^2$ 改为绝对误差 $|y_i - c_m|$，那么 $c_m$ 的最优值应该是什么？

   👉 点击查看参考答案

   当损失函数为平方误差 $L = \sum (y_i - c)^2$ 时，令其关于 $c$ 的导数为零：
   $\frac{dL}{dc} = -2\sum (y_i - c) = 0$
   解得 $\sum y_i = N c$，即 $c = \frac{1}{N}\sum y_i$，为均值。
   
   如果损失函数改为绝对误差 $L = \sum |y_i - c|$，则最优的 $c$ 是 $y_i$ 的中位数。因为中位数是使绝对误差和最小的点。你可以尝试修改上面回归示例的代码，将平方误差计算改为绝对误差，观察最优分割点和预测值的变化。

2. 代码实践：在上面回归树的示例代码中，我们只评估了特征 $x$ 的分割。请扩展代码，模拟一个二维特征 $\mathbf{x} = (x_1, x_2)$ 的数据集，并实现完整的 $(j, s)$ 遍历搜索，找到全局最优的第一个分割特征和分割点。

   👉 点击查看参考答案

   关键步骤是构造二维数据，并循环遍历两个特征。以下是核心修改思路： ```text # 假设二维数据 data_2d = [([x1, x2], y), ...]（伪代码示意） best_loss = float('inf') best_j = None best_s = None for j in range(2): # 遍历两个特征 # 提取第j个特征的所有值并排序，生成候选分割点 feat_vals = sorted(list(set([x[j] for x, _ in data_2d]))) split_candidates = [(feat_vals[i]+feat_vals[i+1])/2 for i in range(len(feat_vals)-1)] for s in split_candidates: # 划分区域并计算损失 loss = compute_loss_for_2d_split(data_2d, j, s) if loss < best_loss: best_loss, best_j, best_s = loss, j, s ``` 你需要实现 `compute_loss_for_2d_split` 函数，根据特征 `j` 和分割点 `s` 划分数据并计算平方误差损失。通过这个练习，你能更深刻理解CART如何在高维空间中选择分割维度。

本章小结

本节课我们深入学习了CART树，它把分类与回归统一到了同一个决策树框架下。核心在于理解其通过递归二叉分割来划分特征空间，并针对不同任务（回归/分类）采用不同的损失度量（平方误差/基尼指数）来指导分割点的选择。

📋 行动清单

• 理解分割过程：在纸上画出一个二维特征空间和若干样本点，手动模拟一次CART回归树的分割过程，计算不同分割点下的平方误差损失。
• 运行示例代码：将讲义中的代码复制到本地Python环境运行，并尝试修改数据点，观察最优分割点如何变化。
• 对比ID3：回顾上章的 ID3 决策树（信息增益、多路分叉、只做分类），思考它与 CART（基尼/平方误差、二叉分叉、能做回归）在分割准则与应用场景上有何异同。

—— 小象教研组