决策树CART回归算法

目录

1. 引言：CART回归树是什么？
2. 第一部分：回归问题与分类问题的区别
3. 第二部分：CART回归树的核心概念
4. 第三部分：方差与不纯度度量
5. 第四部分：CART回归树的分裂准则
6. 第五部分：CART回归树算法原理
7. 第六部分：完整实例演示
8. 第七部分：决策树构建过程详解
9. 第八部分：CART回归树的优缺点
10. 总结与回顾

引言：CART回归树是什么？

决策树的两大应用场景

决策树算法可以解决两大类问题：

1. 分类问题（Classification）

   • 预测离散的类别标签
   • 例如：预测天气（晴/雨/阴）、预测邮件是否为垃圾邮件（是/否）
   • 使用基尼不纯度或信息熵作为不纯度度量

2. 回归问题（Regression）

   • 预测连续的数值
   • 例如：预测房价、预测温度、预测销售额
   • 使用方差或平均绝对误差作为不纯度度量

什么是CART回归树？

CART（Classification and Regression Trees）回归树是CART算法在回归问题中的应用，通过构建二叉树来预测连续的目标变量。

CART回归树的特点：

1. 二叉树结构：每个节点只有两个分支（是/否）
2. 方差最小化：使用方差作为不纯度度量
3. 连续预测：叶节点输出连续数值（通常是该节点样本的平均值）
4. 特征选择：选择使方差减少最多的特征和分裂点

为什么需要CART回归树？

CART回归树的优势：

1. 可解释性强：树结构直观，易于理解
2. 处理非线性关系：可以捕捉特征之间的复杂交互
3. 特征选择：自动选择重要特征
4. 无需数据预处理：可以处理连续和离散特征
5. 统一框架：分类和回归使用相同的框架

第一部分：回归问题与分类问题的区别

1.1 问题类型的区别

分类问题：

• 目标变量：离散的类别（如：是/否、A/B/C）
• 预测结果：某个类别
• 评估指标：准确率、精确率、召回率、F1分数
• 不纯度度量：基尼不纯度、信息熵

回归问题：

• 目标变量：连续的数值（如：价格、温度、身高）
• 预测结果：某个数值
• 评估指标：均方误差（MSE）、平均绝对误差（MAE）、R²分数
• 不纯度度量：方差、平均绝对偏差

1.2 数据示例对比

分类问题示例：

回归问题示例：

1.3 叶节点的区别

分类树：

• 叶节点存储类别标签（如："是"或"否"）
• 预测时返回该类别

回归树：

• 叶节点存储数值（通常是该节点样本的平均值）
• 预测时返回该数值

第二部分：CART回归树的核心概念

2.1 回归树的基本结构

                    [根节点：所有样本]
                           |
                    [特征：X1 ≤ 5?]
                    /            \
            [是:样本子集1]    [否:样本子集2]
            /                      \
    [特征：X2 ≤ 3?]        [特征：X3 ≤ 10?]
    /            \          /            \
[叶:均值=20.5] [叶:均值=15.2] [叶:均值=25.8] [叶:均值=30.1]

2.2 回归树的工作流程

1. 训练阶段：

   • 从根节点开始，包含所有训练样本
   • 选择最优特征和分裂点，使方差减少最多
   • 递归分裂，直到满足停止条件
   • 叶节点存储该节点样本的平均值

2. 预测阶段：

   • 从根节点开始，根据特征值选择分支
   • 沿着树向下遍历，直到到达叶节点
   • 返回叶节点存储的数值

2.3 回归树的关键问题

1. 如何选择分裂特征和分裂点？

   • 选择使方差减少最多的特征和分裂点

2. 如何计算叶节点的预测值？

   • 使用该节点样本的平均值

3. 何时停止分裂？

   • 样本数量小于阈值
   • 方差小于阈值
   • 树的深度达到最大值
   • 无法进一步减少方差

第三部分：方差与不纯度度量

3.1 方差的定义

方差（Variance）：衡量数据集的离散程度

对于数据集 $D$，包含 $n$ 个样本，目标值为 $y_1, y_2, ..., y_n$：

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

其中：

• $\bar{y} = \frac{1}{n} \sum_{i=1}^{n} y_i$ 是数据集的平均值
• $y_i$ 是第 $i$ 个样本的目标值

等价形式（展开）：

$$
Var(D) = \frac{1}{n} \sum_{i=1}^{n} y_i^2 - \bar{y}^2 = E[y^2] - E[y]^2
$$

3.2 方差的直观理解

方差衡量：样本值相对于平均值的分散程度

• 方差 = 0：所有样本值相同（完全纯净）
• 方差越大：样本值越分散（越不纯净）
• 方差越小：样本值越集中（越纯净）

例子：
假设有5个样本，目标值分别为：{10, 10, 10, 10, 10}

• 平均值：$\bar{y} = 10$
• 方差：$Var = \frac{1}{5}[(10-10)^2 + (10-10)^2 + (10-10)^2 + (10-10)^2 + (10-10)^2] = 0$

假设有5个样本，目标值分别为：{5, 10, 15, 20, 25}

• 平均值：$\bar{y} = 15$
• 方差：$Var = \frac{1}{5}[(5-15)^2 + (10-15)^2 + (15-15)^2 + (20-15)^2 + (25-15)^2] = \frac{1}{5}[100 + 25 + 0 + 25 + 100] = 50$

3.3 条件方差

条件方差（Conditional Variance）：在已知特征 $A$ 的条件下，数据集的不纯度

$$
Var(D|A) = \sum_{v=1}^{V} \frac{|D_v|}{|D|} Var(D_v)
$$

其中：

• $A$：特征
• $V$：特征 $A$ 的分裂数量（对于CART，通常是2）
• $D_v$：特征 $A$ 满足第 $v$ 个条件的样本子集
• $|D_v|$：子集 $D_v$ 的样本数量
• $|D|$：数据集 $D$ 的样本数量

3.4 方差减少量（Variance Reduction）

方差减少量（Variance Reduction）：使用特征 $A$ 后，方差的减少量

$$
VarReduction(D, A) = Var(D) - Var(D|A)
$$

其中：

• $Var(D)$：数据集 $D$ 的原始方差
• $Var(D|A)$：使用特征 $A$ 后的条件方差

CART回归树的核心思想：
选择方差减少量最大的特征（或特征分裂点）进行分裂！

3.5 方差与基尼不纯度的对比

第四部分：CART回归树的分裂准则

4.1 分裂准则的目标

目标： 选择使方差减少最多的特征和分裂点

数学表达：

$$
\arg\max_{A, s} VarReduction(D, A, s) = \arg\max_{A, s} [Var(D) - Var(D|A, s)]
$$

其中：

• $A$：特征
• $s$：分裂点（对于连续特征）或分组（对于离散特征）

4.2 连续特征的分裂

对于连续特征：

假设特征 $X$ 是连续值，需要找到一个阈值 $t$，将数据分成两部分：

• $D_{left} = {样本 | X \leq t}$
• $D_{right} = {样本 | X > t}$

计算步骤：

1. 对特征值排序：$x_1 \leq x_2 \leq ... \leq x_n$
2. 尝试所有可能的分裂点：
   • 通常选择相邻值的中间点：$t_i = \frac{x_i + x_{i+1}}{2}$
3. 对于每个分裂点 $t_i$：
   • 计算 $D_{left}$ 和 $D_{right}$ 的方差
   • 计算条件方差：$Var(D|X \leq t_i) = \frac{|D_{left}|}{|D|} Var(D_{left}) + \frac{|D_{right}|}{|D|} Var(D_{right})$
   • 计算方差减少量：$VarReduction = Var(D) - Var(D|X \leq t_i)$
4. 选择方差减少量最大的分裂点

4.3 离散特征的分裂

对于离散特征：

假设特征 $X$ 有 $m$ 个取值：${v_1, v_2, ..., v_m}$，需要将所有取值分成两组：

• $D_{left} = {样本 | X \in S_{left}}$
• $D_{right} = {样本 | X \in S_{right}}$

其中 $S_{left} \cup S_{right} = {v_1, v_2, ..., v_m}$，$S_{left} \cap S_{right} = \emptyset$

计算步骤：

1. 尝试所有可能的分组方式（共 $2^{m-1} - 1$ 种）
2. 对于每个分组：
   • 计算 $D_{left}$ 和 $D_{right}$ 的方差
   • 计算条件方差和方差减少量
3. 选择方差减少量最大的分组

注意： 对于有 $m$ 个取值的离散特征，需要尝试 $2^{m-1} - 1$ 种分组方式（排除空集和全集）。

4.4 叶节点的预测值

叶节点的预测值： 该节点所有样本目标值的平均值

$$
\hat{y}{leaf} = \frac{1}{|D{leaf}|} \sum_{i \in D_{leaf}} y_i = \bar{y}_{leaf}
$$

其中：

• $D_{leaf}$：叶节点包含的样本集合
• $|D_{leaf}|$：叶节点的样本数量
• $y_i$：第 $i$ 个样本的目标值

为什么使用平均值？

平均值是使均方误差最小的预测值：

$$
\arg\min_{c} \sum_{i \in D_{leaf}} (y_i - c)^2 = \bar{y}_{leaf}
$$

证明：
$$
\frac{\partial}{\partial c} \sum_{i \in D_{leaf}} (y_i - c)^2 = -2 \sum_{i \in D_{leaf}} (y_i - c) = 0
$$

$$
\Rightarrow \sum_{i \in D_{leaf}} y_i = |D_{leaf}| \cdot c
$$

$$
\Rightarrow c = \frac{1}{|D_{leaf}|} \sum_{i \in D_{leaf}} y_i = \bar{y}_{leaf}
$$

第五部分：CART回归树算法原理

5.1 CART回归树算法的基本思想

CART回归树算法采用自顶向下的贪心策略构建二叉树：

1. 从根节点开始，包含所有训练样本
2. 选择最优特征和分裂点：
   • 对于每个特征，找到最优的分裂点/分组
   • 计算每个特征的方差减少量
   • 选择方差减少量最大的特征和分裂点
3. 分裂节点：根据选定的特征和分裂点，将数据分成两个子集
4. 递归构建：对每个子集递归执行步骤2-3
5. 停止条件：
   • 样本数量小于阈值
   • 方差小于阈值
   • 无法进一步减少方差
   • 树的深度达到最大值
6. 叶节点赋值：叶节点存储该节点样本的平均值

5.2 CART回归树算法的伪代码

函数 CART_Regression(数据集D, 特征集A, 深度):
    如果 深度 >= 最大深度:
        返回 叶节点(平均值(D))
    
    如果 |D| < 最小样本数:
        返回 叶节点(平均值(D))
    
    如果 Var(D) < 最小方差阈值:
        返回 叶节点(平均值(D))
    
    最佳特征 = None
    最佳分裂点 = None
    最佳减少量 = -∞
    
    对于每个特征 a ∈ A:
        如果 a是连续特征:
            对于 a的每个可能阈值 t:
                计算方差减少量
                如果 方差减少量 > 最佳减少量:
                    更新最佳特征、分裂点、减少量
        否则 (a是离散特征):
            对于 a的每个可能分组:
                计算方差减少量
                如果 方差减少量 > 最佳减少量:
                    更新最佳特征、分裂点、减少量
    
    如果 最佳减少量 <= 0:
        返回 叶节点(平均值(D))
    
    创建节点，标记为特征 a* 和分裂点
    
    创建左分支: D_left = {样本 | 样本满足分裂条件}
    创建右分支: D_right = {样本 | 样本不满足分裂条件}
    
    左子树 = CART_Regression(D_left, A, 深度+1)
    右子树 = CART_Regression(D_right, A, 深度+1)
    
    返回 节点

函数 平均值(数据集D):
    返回 sum(D中所有样本的目标值) / |D|

5.3 CART回归树算法的特点

优点：

• 二叉树结构简洁，易于理解和实现
• 可以处理非线性关系
• 自动特征选择
• 无需数据预处理
• 可解释性强

缺点：

• 可能产生较深的树
• 对噪声敏感
• 可能过拟合（需要剪枝）
• 不稳定（数据的小幅变化可能导致树结构的显著变化）

第六部分：完整实例演示

6.1 数据集描述

我们使用一个房价预测的简化数据集：

数据集统计：

• 总样本数：8
• 特征：面积（连续）、楼层（离散：低/中/高）、房龄（连续）
• 目标变量：价格（连续）
• 价格范围：45 ~ 105 万元

6.2 第一步：计算根节点的方差

数据集 $D$ 的方差：

首先计算平均值：

$$
\bar{y} = \frac{1}{8}(45 + 55 + 75 + 85 + 95 + 105 + 50 + 70) = \frac{580}{8} = 72.5
$$

计算方差：

$$
Var(D) = \frac{1}{8} \sum_{i=1}^{8} (y_i - 72.5)^2
$$

$$
= \frac{1}{8}[(45-72.5)^2 + (55-72.5)^2 + (75-72.5)^2 + (85-72.5)^2 + (95-72.5)^2 + (105-72.5)^2 + (50-72.5)^2 + (70-72.5)^2]
$$

$$
= \frac{1}{8}[756.25 + 306.25 + 6.25 + 156.25 + 506.25 + 1056.25 + 506.25 + 6.25]
$$

$$
= \frac{1}{8} \times 3300 = 412.5
$$

根节点方差：$Var(D) = 412.5$

6.3 第二步：计算各特征的方差减少量

6.3.1 特征"面积"的方差减少量

特征"面积"是连续特征，需要找到最优阈值。

面积值排序：60, 80, 80, 100, 100, 120, 140, 160

尝试分裂点：

分裂点1：面积 ≤ 70（即面积 ≤ (60+80)/2 = 70）

• $D_{left}$：样本1（面积=60，价格=45）
• $D_{right}$：样本2,3,4,5,6,7,8（面积≥80）

计算：

• $\bar{y}{left} = 45$，$Var(D{left}) = 0$（只有一个样本）
• $\bar{y}_{right} = \frac{1}{7}(55+75+85+95+105+50+70) = \frac{535}{7} = 76.43$
• $Var(D_{right}) = \frac{1}{7}[(55-76.43)^2 + (75-76.43)^2 + (85-76.43)^2 + (95-76.43)^2 + (105-76.43)^2 + (50-76.43)^2 + (70-76.43)^2]$
• $= \frac{1}{7}[459.18 + 2.04 + 73.47 + 345.18 + 816.33 + 697.18 + 41.33] = \frac{2435.71}{7} = 347.67$

$$
Var(D|面积 \leq 70) = \frac{1}{8} \times 0 + \frac{7}{8} \times 347.67 = 304.21
$$

$$
VarReduction(面积 \leq 70) = 412.5 - 304.21 = 108.29
$$

分裂点2：面积 ≤ 90（即面积 ≤ (80+100)/2 = 90）

• $D_{left}$：样本1,2,7（面积≤80，价格=45,55,50）
• $D_{right}$：样本3,4,5,6,8（面积≥100，价格=75,85,95,105,70）

计算：

• $\bar{y}{left} = \frac{1}{3}(45+55+50) = 50$，$Var(D{left}) = \frac{1}{3}[(45-50)^2 + (55-50)^2 + (50-50)^2] = \frac{1}{3}[25+25+0] = 16.67$
• $\bar{y}_{right} = \frac{1}{5}(75+85+95+105+70) = \frac{430}{5} = 86$
• $Var(D_{right}) = \frac{1}{5}[(75-86)^2 + (85-86)^2 + (95-86)^2 + (105-86)^2 + (70-86)^2] = \frac{1}{5}[121+1+81+361+256] = \frac{820}{5} = 164$

$$
Var(D|面积 \leq 90) = \frac{3}{8} \times 16.67 + \frac{5}{8} \times 164 = 6.25 + 102.5 = 108.75
$$

$$
VarReduction(面积 \leq 90) = 412.5 - 108.75 = 303.75
$$

分裂点3：面积 ≤ 110（即面积 ≤ (100+120)/2 = 110）

• $D_{left}$：样本1,2,3,7,8（面积≤100，价格=45,55,75,50,70）
• $D_{right}$：样本4,5,6（面积≥120，价格=85,95,105）

计算：

• $\bar{y}{left} = \frac{1}{5}(45+55+75+50+70) = \frac{295}{5} = 59$，$Var(D{left}) = \frac{1}{5}[(45-59)^2 + (55-59)^2 + (75-59)^2 + (50-59)^2 + (70-59)^2] = \frac{1}{5}[196+16+256+81+121] = \frac{670}{5} = 134$
• $\bar{y}{right} = \frac{1}{3}(85+95+105) = 95$，$Var(D{right}) = \frac{1}{3}[(85-95)^2 + (95-95)^2 + (105-95)^2] = \frac{1}{3}[100+0+100] = 66.67$

$$
Var(D|面积 \leq 110) = \frac{5}{8} \times 134 + \frac{3}{8} \times 66.67 = 83.75 + 25 = 108.75
$$

$$
VarReduction(面积 \leq 110) = 412.5 - 108.75 = 303.75
$$

分裂点4：面积 ≤ 130（即面积 ≤ (120+140)/2 = 130）

• $D_{left}$：样本1,2,3,4,7,8（面积≤120，价格=45,55,75,85,50,70）
• $D_{right}$：样本5,6（面积≥140，价格=95,105）

计算：

• $\bar{y}{left} = \frac{1}{6}(45+55+75+85+50+70) = \frac{380}{6} = 63.33$，$Var(D{left}) = \frac{1}{6}[(45-63.33)^2 + (55-63.33)^2 + (75-63.33)^2 + (85-63.33)^2 + (50-63.33)^2 + (70-63.33)^2] = \frac{1}{6}[335.99+69.44+136.11+469.44+177.78+44.44] = \frac{1237.2}{6} = 206.2$
• $\bar{y}{right} = \frac{1}{2}(95+105) = 100$，$Var(D{right}) = \frac{1}{2}[(95-100)^2 + (105-100)^2] = \frac{1}{2}[25+25] = 25$

$$
Var(D|面积 \leq 130) = \frac{6}{8} \times 206.2 + \frac{2}{8} \times 25 = 154.65 + 6.25 = 160.9
$$

$$
VarReduction(面积 \leq 130) = 412.5 - 160.9 = 251.6
$$

分裂点5：面积 ≤ 150（即面积 ≤ (140+160)/2 = 150）

• $D_{left}$：样本1,2,3,4,5,7,8（面积≤140，价格=45,55,75,85,95,50,70）
• $D_{right}$：样本6（面积≥160，价格=105）

计算：

• $\bar{y}{left} = \frac{1}{7}(45+55+75+85+95+50+70) = \frac{475}{7} = 67.86$，$Var(D{left}) = \frac{1}{7}[(45-67.86)^2 + (55-67.86)^2 + (75-67.86)^2 + (85-67.86)^2 + (95-67.86)^2 + (50-67.86)^2 + (70-67.86)^2] = \frac{1}{7}[522.45+165.18+50.98+293.88+736.73+319.45+4.58] = \frac{2097.25}{7} = 299.61$
• $\bar{y}{right} = 105$，$Var(D{right}) = 0$（只有一个样本）

$$
Var(D|面积 \leq 150) = \frac{7}{8} \times 299.61 + \frac{1}{8} \times 0 = 262.16
$$

$$
VarReduction(面积 \leq 150) = 412.5 - 262.16 = 150.34
$$

特征"面积"的最佳分裂点：

• 分裂点1（≤70）：方差减少量 = 108.29
• 分裂点2（≤90）：方差减少量 = 303.75（最大）
• 分裂点3（≤110）：方差减少量 = 303.75
• 分裂点4（≤130）：方差减少量 = 251.6
• 分裂点5（≤150）：方差减少量 = 150.34

特征"面积"的最佳方差减少量：303.75（分裂点：面积 ≤ 90）

6.3.2 特征"楼层"的方差减少量

特征"楼层"是离散特征，取值：{低, 中, 高}

需要尝试所有可能的分组方式（共 $2^{3-1} - 1 = 3$ 种）：

分组1：{低} vs {中, 高}

• $D_{left}$：样本1,2（楼层=低，价格=45,55）
• $D_{right}$：样本3,4,5,6,7,8（楼层∈{中,高}，价格=75,85,95,105,50,70）

计算：

• $\bar{y}{left} = \frac{1}{2}(45+55) = 50$，$Var(D{left}) = \frac{1}{2}[(45-50)^2 + (55-50)^2] = \frac{1}{2}[25+25] = 25$
• $\bar{y}{right} = \frac{1}{6}(75+85+95+105+50+70) = \frac{480}{6} = 80$，$Var(D{right}) = \frac{1}{6}[(75-80)^2 + (85-80)^2 + (95-80)^2 + (105-80)^2 + (50-80)^2 + (70-80)^2] = \frac{1}{6}[25+25+225+625+900+100] = \frac{1900}{6} = 316.67$

$$
Var(D|楼层={低} vs {中,高}) = \frac{2}{8} \times 25 + \frac{6}{8} \times 316.67 = 6.25 + 237.5 = 243.75
$$

$$
VarReduction(楼层={低} vs {中,高}) = 412.5 - 243.75 = 168.75
$$

分组2：{中} vs {低, 高}

• $D_{left}$：样本3,4,7（楼层=中，价格=75,85,50）
• $D_{right}$：样本1,2,5,6,8（楼层∈{低,高}，价格=45,55,95,105,70）

计算：

• $\bar{y}{left} = \frac{1}{3}(75+85+50) = \frac{210}{3} = 70$，$Var(D{left}) = \frac{1}{3}[(75-70)^2 + (85-70)^2 + (50-70)^2] = \frac{1}{3}[25+225+400] = \frac{650}{3} = 216.67$
• $\bar{y}{right} = \frac{1}{5}(45+55+95+105+70) = \frac{370}{5} = 74$，$Var(D{right}) = \frac{1}{5}[(45-74)^2 + (55-74)^2 + (95-74)^2 + (105-74)^2 + (70-74)^2] = \frac{1}{5}[841+361+441+961+16] = \frac{2620}{5} = 524$

$$
Var(D|楼层={中} vs {低,高}) = \frac{3}{8} \times 216.67 + \frac{5}{8} \times 524 = 81.25 + 327.5 = 408.75
$$

$$
VarReduction(楼层={中} vs {低,高}) = 412.5 - 408.75 = 3.75
$$

分组3：{高} vs {低, 中}

• $D_{left}$：样本5,6,8（楼层=高，价格=95,105,70）
• $D_{right}$：样本1,2,3,4,7（楼层∈{低,中}，价格=45,55,75,85,50）

计算：

• $\bar{y}{left} = \frac{1}{3}(95+105+70) = \frac{270}{3} = 90$，$Var(D{left}) = \frac{1}{3}[(95-90)^2 + (105-90)^2 + (70-90)^2] = \frac{1}{3}[25+225+400] = \frac{650}{3} = 216.67$
• $\bar{y}{right} = \frac{1}{5}(45+55+75+85+50) = \frac{310}{5} = 62$，$Var(D{right}) = \frac{1}{5}[(45-62)^2 + (55-62)^2 + (75-62)^2 + (85-62)^2 + (50-62)^2] = \frac{1}{5}[289+49+169+529+144] = \frac{1180}{5} = 236$

$$
Var(D|楼层={高} vs {低,中}) = \frac{3}{8} \times 216.67 + \frac{5}{8} \times 236 = 81.25 + 147.5 = 228.75
$$

$$
VarReduction(楼层={高} vs {低,中}) = 412.5 - 228.75 = 183.75
$$

特征"楼层"的最佳分组：

• 分组1（{低} vs {中,高}）：方差减少量 = 168.75
• 分组2（{中} vs {低,高}）：方差减少量 = 3.75
• 分组3（{高} vs {低,中}）：方差减少量 = 183.75（最大）

特征"楼层"的最佳方差减少量：183.75（分组：{高} vs {低, 中}）

6.3.3 特征"房龄"的方差减少量

特征"房龄"是连续特征，取值：5, 10, 15

房龄值排序：5, 5, 5, 10, 10, 10, 15, 15

尝试分裂点：

分裂点1：房龄 ≤ 7.5（即房龄 ≤ (5+10)/2 = 7.5）

• $D_{left}$：样本1,3,5（房龄=5，价格=45,75,95）
• $D_{right}$：样本2,4,6,7,8（房龄≥10，价格=55,85,105,50,70）

计算：

• $\bar{y}{left} = \frac{1}{3}(45+75+95) = \frac{215}{3} = 71.67$，$Var(D{left}) = \frac{1}{3}[(45-71.67)^2 + (75-71.67)^2 + (95-71.67)^2] = \frac{1}{3}[711.11+11.11+544.44] = \frac{1266.66}{3} = 422.22$
• $\bar{y}{right} = \frac{1}{5}(55+85+105+50+70) = \frac{365}{5} = 73$，$Var(D{right}) = \frac{1}{5}[(55-73)^2 + (85-73)^2 + (105-73)^2 + (50-73)^2 + (70-73)^2] = \frac{1}{5}[324+144+1024+529+9] = \frac{2030}{5} = 406$

$$
Var(D|房龄 \leq 7.5) = \frac{3}{8} \times 422.22 + \frac{5}{8} \times 406 = 158.33 + 253.75 = 412.08
$$

$$
VarReduction(房龄 \leq 7.5) = 412.5 - 412.08 = 0.42
$$

分裂点2：房龄 ≤ 12.5（即房龄 ≤ (10+15)/2 = 12.5）

• $D_{left}$：样本1,2,3,4,5,6（房龄≤10，价格=45,55,75,85,95,105）
• $D_{right}$：样本7,8（房龄=15，价格=50,70）

计算：

• $\bar{y}{left} = \frac{1}{6}(45+55+75+85+95+105) = \frac{460}{6} = 76.67$，$Var(D{left}) = \frac{1}{6}[(45-76.67)^2 + (55-76.67)^2 + (75-76.67)^2 + (85-76.67)^2 + (95-76.67)^2 + (105-76.67)^2] = \frac{1}{6}[1002.78+469.44+2.78+69.44+336.11+802.78] = \frac{2682.33}{6} = 447.06$
• $\bar{y}{right} = \frac{1}{2}(50+70) = 60$，$Var(D{right}) = \frac{1}{2}[(50-60)^2 + (70-60)^2] = \frac{1}{2}[100+100] = 100$

$$
Var(D|房龄 \leq 12.5) = \frac{6}{8} \times 447.06 + \frac{2}{8} \times 100 = 335.3 + 25 = 360.3
$$

$$
VarReduction(房龄 \leq 12.5) = 412.5 - 360.3 = 52.2
$$

特征"房龄"的最佳方差减少量：52.2（分裂点：房龄 ≤ 12.5）

6.4 第三步：选择根节点特征

各特征的方差减少量汇总：

结论： 特征"面积"的分裂点"面积 ≤ 90"的方差减少量最大（303.75），因此选择"面积"作为根节点的分裂特征，分裂条件为：面积 ≤ 90？

第七部分：决策树构建过程详解

7.1 第一层分裂：根节点

根据"面积"特征进行分裂，分裂条件：面积 ≤ 90？

                    [根节点：D(8个样本)]
                    Var(D) = 412.5
                           |
                    [特征：面积≤90?]
                    VarReduction = 303.75
                    /            \
            [是:3]            [否:5]
         Var=16.67        Var=164

子集划分：

• $D_{left}$（面积≤90，3个样本）：样本1,2,7

  • 价格：45, 55, 50
  • 平均值：$\bar{y}_{left} = 50$
  • 方差：$Var(D_{left}) = 16.67$

• $D_{right}$（面积>90，5个样本）：样本3,4,5,6,8

  • 价格：75, 85, 95, 105, 70
  • 平均值：$\bar{y}_{right} = 86$
  • 方差：$Var(D_{right}) = 164$

7.2 第二层分裂：处理"面积≤90"分支

当前数据集： $D_{left}$（3个样本，面积≤90）

计算方差：
$$
Var(D_{left}) = 16.67
$$

计算各特征的方差减少量（在$D_{left}$上）：

7.2.1 特征"面积"的进一步分裂

由于面积已经被使用，但我们可以考虑面积的进一步分裂：

• 当前节点：面积≤90（即面积∈{60,80}）

• 可以进一步分裂：面积 ≤ 70

• $D_{left-left}$：样本1（面积=60，价格=45）

• $D_{left-right}$：样本2,7（面积=80，价格=55,50）

计算：

• $\bar{y}{left-left} = 45$，$Var(D{left-left}) = 0$
• $\bar{y}{left-right} = \frac{1}{2}(55+50) = 52.5$，$Var(D{left-right}) = \frac{1}{2}[(55-52.5)^2 + (50-52.5)^2] = \frac{1}{2}[6.25+6.25] = 6.25$

$$
Var(D_{left}|面积 \leq 70) = \frac{1}{3} \times 0 + \frac{2}{3} \times 6.25 = 4.17
$$

$$
VarReduction(D_{left}, 面积 \leq 70) = 16.67 - 4.17 = 12.5
$$

7.2.2 特征"楼层"的方差减少量

分组1：{低} vs {中, 高}

• $D_{left-left}$：样本1,2（楼层=低，价格=45,55）
• $D_{left-right}$：样本7（楼层=中，价格=50）

计算：

• $\bar{y}{left-left} = 50$，$Var(D{left-left}) = 25$
• $\bar{y}{left-right} = 50$，$Var(D{left-right}) = 0$

$$
Var(D_{left}|楼层={低} vs {中,高}) = \frac{2}{3} \times 25 + \frac{1}{3} \times 0 = 16.67
$$

$$
VarReduction(D_{left}, 楼层={低} vs {中,高}) = 16.67 - 16.67 = 0
$$

分组2：{中} vs {低, 高}

• $D_{left-left}$：样本7（楼层=中，价格=50）
• $D_{left-right}$：样本1,2（楼层∈{低}，价格=45,55）

计算：

• $\bar{y}{left-left} = 50$，$Var(D{left-left}) = 0$
• $\bar{y}{left-right} = 50$，$Var(D{left-right}) = 25$

$$
Var(D_{left}|楼层={中} vs {低,高}) = \frac{1}{3} \times 0 + \frac{2}{3} \times 25 = 16.67
$$

$$
VarReduction(D_{left}, 楼层={中} vs {低,高}) = 16.67 - 16.67 = 0
$$

分组3：{高} vs {低, 中}

• $D_{left-left}$：无样本
• $D_{left-right}$：样本1,2,7（楼层∈{低,中}，价格=45,55,50）

这个分组无效（左分支为空）。

特征"楼层"的最佳方差减少量：0

7.2.3 特征"房龄"的方差减少量

分裂点1：房龄 ≤ 7.5

• $D_{left-left}$：样本1（房龄=5，价格=45）
• $D_{left-right}$：样本2,7（房龄=10,15，价格=55,50）

计算：

• $\bar{y}{left-left} = 45$，$Var(D{left-left}) = 0$
• $\bar{y}{left-right} = \frac{1}{2}(55+50) = 52.5$，$Var(D{left-right}) = 6.25$

$$
Var(D_{left}|房龄 \leq 7.5) = \frac{1}{3} \times 0 + \frac{2}{3} \times 6.25 = 4.17
$$

$$
VarReduction(D_{left}, 房龄 \leq 7.5) = 16.67 - 4.17 = 12.5
$$

分裂点2：房龄 ≤ 12.5

• $D_{left-left}$：样本1,2（房龄≤10，价格=45,55）
• $D_{left-right}$：样本7（房龄=15，价格=50）

计算：

• $\bar{y}{left-left} = 50$，$Var(D{left-left}) = 25$
• $\bar{y}{left-right} = 50$，$Var(D{left-right}) = 0$

$$
Var(D_{left}|房龄 \leq 12.5) = \frac{2}{3} \times 25 + \frac{1}{3} \times 0 = 16.67
$$

$$
VarReduction(D_{left}, 房龄 \leq 12.5) = 16.67 - 16.67 = 0
$$

特征"房龄"的最佳方差减少量：12.5（分裂点：房龄 ≤ 7.5）

方差减少量汇总：

结论： 选择"面积"或"房龄"都可以（方差减少量相同）。这里选择"面积"继续分裂，分裂条件：面积 ≤ 70？

分裂结果：

• $D_{left-left}$（面积≤70，1个样本）：样本1

  • 价格：45
  • 平均值：45（叶节点）

• $D_{left-right}$（面积>70且≤90，2个样本）：样本2,7

  • 价格：55, 50
  • 平均值：52.5（叶节点）

7.3 第二层分裂：处理"面积>90"分支

当前数据集： $D_{right}$（5个样本，面积>90）

计算方差：
$$
Var(D_{right}) = 164
$$

计算各特征的方差减少量（在$D_{right}$上）：

7.3.1 特征"面积"的进一步分裂

当前节点：面积>90（即面积∈{100,120,140,160}）

分裂点1：面积 ≤ 110

• $D_{right-left}$：样本3,8（面积=100，价格=75,70）
• $D_{right-right}$：样本4,5,6（面积≥120，价格=85,95,105）

计算：

• $\bar{y}{right-left} = \frac{1}{2}(75+70) = 72.5$，$Var(D{right-left}) = \frac{1}{2}[(75-72.5)^2 + (70-72.5)^2] = \frac{1}{2}[6.25+6.25] = 6.25$
• $\bar{y}{right-right} = \frac{1}{3}(85+95+105) = 95$，$Var(D{right-right}) = \frac{1}{3}[(85-95)^2 + (95-95)^2 + (105-95)^2] = \frac{1}{3}[100+0+100] = 66.67$

$$
Var(D_{right}|面积 \leq 110) = \frac{2}{5} \times 6.25 + \frac{3}{5} \times 66.67 = 2.5 + 40 = 42.5
$$

$$
VarReduction(D_{right}, 面积 \leq 110) = 164 - 42.5 = 121.5
$$

分裂点2：面积 ≤ 130

• $D_{right-left}$：样本3,4,8（面积≤120，价格=75,85,70）
• $D_{right-right}$：样本5,6（面积≥140，价格=95,105）

计算：

• $\bar{y}{right-left} = \frac{1}{3}(75+85+70) = \frac{230}{3} = 76.67$，$Var(D{right-left}) = \frac{1}{3}[(75-76.67)^2 + (85-76.67)^2 + (70-76.67)^2] = \frac{1}{3}[2.78+69.44+44.44] = \frac{116.66}{3} = 38.89$
• $\bar{y}{right-right} = \frac{1}{2}(95+105) = 100$，$Var(D{right-right}) = \frac{1}{2}[(95-100)^2 + (105-100)^2] = \frac{1}{2}[25+25] = 25$

$$
Var(D_{right}|面积 \leq 130) = \frac{3}{5} \times 38.89 + \frac{2}{5} \times 25 = 23.33 + 10 = 33.33
$$

$$
VarReduction(D_{right}, 面积 \leq 130) = 164 - 33.33 = 130.67
$$

分裂点3：面积 ≤ 150

• $D_{right-left}$：样本3,4,5,8（面积≤140，价格=75,85,95,70）
• $D_{right-right}$：样本6（面积≥160，价格=105）

计算：

• $\bar{y}{right-left} = \frac{1}{4}(75+85+95+70) = \frac{325}{4} = 81.25$，$Var(D{right-left}) = \frac{1}{4}[(75-81.25)^2 + (85-81.25)^2 + (95-81.25)^2 + (70-81.25)^2] = \frac{1}{4}[39.06+14.06+189.06+126.56] = \frac{368.74}{4} = 92.19$
• $\bar{y}{right-right} = 105$，$Var(D{right-right}) = 0$

$$
Var(D_{right}|面积 \leq 150) = \frac{4}{5} \times 92.19 + \frac{1}{5} \times 0 = 73.75
$$

$$
VarReduction(D_{right}, 面积 \leq 150) = 164 - 73.75 = 90.25
$$

特征"面积"的最佳方差减少量：130.67（分裂点：面积 ≤ 130）

7.3.2 特征"楼层"的方差减少量

分组1：{低} vs {中, 高}

• $D_{right-left}$：无样本
• $D_{right-right}$：样本3,4,5,6,8（楼层∈{中,高}，价格=75,85,95,105,70）

这个分组无效（左分支为空）。

分组2：{中} vs {低, 高}

• $D_{right-left}$：样本3,4（楼层=中，价格=75,85）
• $D_{right-right}$：样本5,6,8（楼层∈{高}，价格=95,105,70）

计算：

• $\bar{y}{right-left} = \frac{1}{2}(75+85) = 80$，$Var(D{right-left}) = \frac{1}{2}[(75-80)^2 + (85-80)^2] = \frac{1}{2}[25+25] = 25$
• $\bar{y}{right-right} = \frac{1}{3}(95+105+70) = 90$，$Var(D{right-right}) = \frac{1}{3}[(95-90)^2 + (105-90)^2 + (70-90)^2] = \frac{1}{3}[25+225+400] = \frac{650}{3} = 216.67$

$$
Var(D_{right}|楼层={中} vs {低,高}) = \frac{2}{5} \times 25 + \frac{3}{5} \times 216.67 = 10 + 130 = 140
$$

$$
VarReduction(D_{right}, 楼层={中} vs {低,高}) = 164 - 140 = 24
$$

分组3：{高} vs {低, 中}

• $D_{right-left}$：样本5,6,8（楼层=高，价格=95,105,70）
• $D_{right-right}$：样本3,4（楼层∈{中}，价格=75,85）

计算：

• $\bar{y}{right-left} = 90$，$Var(D{right-left}) = 216.67$
• $\bar{y}{right-right} = 80$，$Var(D{right-right}) = 25$

$$
Var(D_{right}|楼层={高} vs {低,中}) = \frac{3}{5} \times 216.67 + \frac{2}{5} \times 25 = 130 + 10 = 140
$$

$$
VarReduction(D_{right}, 楼层={高} vs {低,中}) = 164 - 140 = 24
$$

特征"楼层"的最佳方差减少量：24

7.3.3 特征"房龄"的方差减少量

分裂点1：房龄 ≤ 7.5

• $D_{right-left}$：样本3,5（房龄=5，价格=75,95）
• $D_{right-right}$：样本4,6,8（房龄≥10，价格=85,105,70）

计算：

• $\bar{y}{right-left} = \frac{1}{2}(75+95) = 85$，$Var(D{right-left}) = \frac{1}{2}[(75-85)^2 + (95-85)^2] = \frac{1}{2}[100+100] = 100$
• $\bar{y}{right-right} = \frac{1}{3}(85+105+70) = \frac{260}{3} = 86.67$，$Var(D{right-right}) = \frac{1}{3}[(85-86.67)^2 + (105-86.67)^2 + (70-86.67)^2] = \frac{1}{3}[2.78+336.11+277.78] = \frac{616.67}{3} = 205.56$

$$
Var(D_{right}|房龄 \leq 7.5) = \frac{2}{5} \times 100 + \frac{3}{5} \times 205.56 = 40 + 123.33 = 163.33
$$

$$
VarReduction(D_{right}, 房龄 \leq 7.5) = 164 - 163.33 = 0.67
$$

分裂点2：房龄 ≤ 12.5

• $D_{right-left}$：样本3,4,5,6（房龄≤10，价格=75,85,95,105）
• $D_{right-right}$：样本8（房龄=15，价格=70）

计算：

• $\bar{y}{right-left} = \frac{1}{4}(75+85+95+105) = 90$，$Var(D{right-left}) = \frac{1}{4}[(75-90)^2 + (85-90)^2 + (95-90)^2 + (105-90)^2] = \frac{1}{4}[225+25+25+225] = \frac{500}{4} = 125$
• $\bar{y}{right-right} = 70$，$Var(D{right-right}) = 0$

$$
Var(D_{right}|房龄 \leq 12.5) = \frac{4}{5} \times 125 + \frac{1}{5} \times 0 = 100
$$

$$
VarReduction(D_{right}, 房龄 \leq 12.5) = 164 - 100 = 64
$$

特征"房龄"的最佳方差减少量：64（分裂点：房龄 ≤ 12.5）

方差减少量汇总：

结论： 选择"面积"作为分裂特征，分裂条件：面积 ≤ 130？

分裂结果：

• $D_{right-left}$（面积>90且≤130，3个样本）：样本3,4,8

  • 价格：75, 85, 70
  • 平均值：76.67
  • 方差：38.89

• $D_{right-right}$（面积>130，2个样本）：样本5,6

  • 价格：95, 105
  • 平均值：100
  • 方差：25

7.4 第三层分裂：处理"面积>90且≤130"分支

当前数据集： $D_{right-left}$（3个样本）

由于样本数量较少（3个），我们可以选择停止分裂，将其作为叶节点，预测值为76.67。

但为了演示，我们继续计算：

计算方差：
$$
Var(D_{right-left}) = 38.89
$$

由于样本数量少，方差减少量会很小。我们选择停止分裂，将其作为叶节点。

7.5 第三层分裂：处理"面积>130"分支

当前数据集： $D_{right-right}$（2个样本）

样本数量为2，停止分裂，将其作为叶节点，预测值为100。

7.6 完整的决策树结构

                        [根节点：D(8个样本)]
                        Var(D) = 412.5
                                 |
                        [特征：面积≤90?]
                        VarReduction = 303.75
                        /            \
                  [是:3]          [否:5]
                Var=16.67      Var=164
                    |                |
        [特征：面积≤70?]    [特征：面积≤130?]
        VarReduction=12.5   VarReduction=130.67
        /            \      /            \
  [是:1]        [否:2]  [是:3]      [否:2]
  Var=0       Var=6.25 Var=38.89   Var=25
    |            |        |            |
[叶:45]    [叶:52.5] [叶:76.67]  [叶:100]

7.7 决策树的文本表示

如果 面积 ≤ 90：
    如果 面积 ≤ 70：
        返回 45
    否则（面积 > 70 且 ≤ 90）：
        返回 52.5
否则（面积 > 90）：
    如果 面积 ≤ 130：
        返回 76.67
    否则（面积 > 130）：
        返回 100

7.8 决策树的ASCII图示

                    ┌─────────────────┐
                    │  根节点(8样本)  │
                    │  Var(D) = 412.5 │
                    └────────┬────────┘
                             │
                    ┌────────▼────────┐
                    │  特征：面积≤90? │
                    │ VarReduction=   │
                    │    303.75       │
                    └───┬────────────┘
                        │
            ┌───────────┴───────────┐
            │                       │
    ┌───────▼──────┐       ┌───────▼──────┐
    │ 是 (3样本)   │       │ 否 (5样本)   │
    │ Var=16.67    │       │ Var=164      │
    └───────┬──────┘       └───────┬──────┘
            │                      │
    ┌───────▼────────┐     ┌───────▼────────┐
    │ 特征：面积≤70? │     │ 特征：面积≤130?│
    │ VarReduction=  │     │ VarReduction=  │
    │    12.5        │     │   130.67       │
    └───┬────────────┘     └───┬────────────┘
        │                      │
    ┌───┴────┐            ┌───┴────┐
    │        │            │        │
┌───▼───┐ ┌─▼───┐    ┌───▼───┐ ┌─▼───┐
│是:1   │ │否:2 │    │是:3   │ │否:2 │
│Var=0  │ │Var= │    │Var=   │ │Var= │
│       │ │6.25 │    │38.89  │ │25   │
└───┬───┘ └─┬───┘    └───┬───┘ └─┬───┘
    │       │            │       │
┌───▼───┐ ┌─▼───┐    ┌───▼───┐ ┌─▼───┐
│叶:45  │ │叶:  │    │叶:    │ │叶:  │
│       │ │52.5 │    │76.67  │ │100  │
└───────┘ └─────┘    └───────┘ └─────┘

7.9 验证决策树

让我们用几个样本验证决策树：

样本1： 面积=60, 楼层=低, 房龄=5, 价格=45

• 路径：面积≤90？是 → 面积≤70？是 → 45 ✓（实际：45）

样本2： 面积=80, 楼层=低, 房龄=10, 价格=55

• 路径：面积≤90？是 → 面积≤70？否 → 52.5 ✓（实际：55，误差：2.5）

样本3： 面积=100, 楼层=中, 房龄=5, 价格=75

• 路径：面积≤90？否 → 面积≤130？是 → 76.67 ✓（实际：75，误差：1.67）

样本5： 面积=140, 楼层=高, 房龄=5, 价格=95

• 路径：面积≤90？否 → 面积≤130？否 → 100 ✓（实际：95，误差：5）

第八部分：CART回归树的优缺点

8.1 优点

1. 可解释性强

   • 树结构直观，易于理解
   • 可以清楚地看到每个特征如何影响预测结果

2. 处理非线性关系

   • 可以捕捉特征之间的复杂交互
   • 不需要假设线性关系

3. 自动特征选择

   • 自动选择重要特征
   • 忽略不重要的特征

4. 无需数据预处理

   • 可以处理连续和离散特征
   • 对缺失值有一定的容忍度

5. 统一框架

   • 分类和回归使用相同的框架
   • 只需改变不纯度度量方式

8.2 缺点

1. 可能产生较深的树

   • 二叉树可能需要更多层才能达到相同的预测效果
   • 需要剪枝来控制深度

2. 对噪声敏感

   • 虽然有所改善，但仍对噪声敏感
   • 需要剪枝来缓解

3. 可能过拟合

   • 如果不加限制，可能产生过深的树
   • 需要剪枝或设置停止条件

4. 不稳定

   • 数据的小幅变化可能导致树结构的显著变化
   • 可以通过集成方法（如随机森林）改善

5. 预测精度有限

   • 叶节点只能输出固定值（平均值）
   • 无法捕捉连续函数的光滑性

8.3 与其他回归方法的对比

总结与回顾

核心概念回顾

1. 方差 $Var(D)$

   • 衡量数据集的不纯度
   • 公式：$Var(D) = \frac{1}{n} \sum_{i=1}^{n} (y_i - \bar{y})^2$
   • 值域：[0, +∞)

2. 条件方差 $Var(D|A)$

   • 在已知特征 $A$ 的条件下，数据集的不纯度
   • 公式：$Var(D|A) = \sum_{v=1}^{V} \frac{|D_v|}{|D|} Var(D_v)$

3. 方差减少量 $VarReduction(D, A)$

   • 使用特征 $A$ 后，方差的减少量
   • 公式：$VarReduction(D, A) = Var(D) - Var(D|A)$
   • 方差减少量越大，特征越重要

4. CART回归树算法流程

   • 计算数据集的方差
   • 对每个特征尝试所有可能的分裂点/分组
   • 选择方差减少量最大的特征和分裂点
   • 递归构建二叉树
   • 直到满足停止条件
   • 叶节点存储该节点样本的平均值

关键公式汇总

方差：
$$
Var(D) = \frac{1}{n} \sum_{i=1}^{n} (y_i - \bar{y})^2 = \frac{1}{n} \sum_{i=1}^{n} y_i^2 - \bar{y}^2
$$

条件方差：
$$
Var(D|A) = \sum_{v=1}^{V} \frac{|D_v|}{|D|} Var(D_v)
$$

方差减少量：
$$
VarReduction(D, A) = Var(D) - Var(D|A)
$$

叶节点预测值：
$$
\hat{y}{leaf} = \frac{1}{|D{leaf}|} \sum_{i \in D_{leaf}} y_i = \bar{y}_{leaf}
$$

其中：

• $D$：数据集
• $y_i$：第 $i$ 个样本的目标值
• $\bar{y}$：数据集的平均值
• $A$：特征
• $D_v$：特征 $A$ 满足第 $v$ 个条件的样本子集
• $V$：特征 $A$ 的分裂数量（对于CART，通常是2）

方差 vs 基尼不纯度

学习要点

1. 理解方差的物理意义：衡量数值的分散程度
2. 掌握方差减少量的计算：这是CART回归树算法的核心
3. 理解二叉树分裂方式：对于连续特征需要尝试所有阈值，对于离散特征需要尝试所有分组
4. 注意停止条件：避免无限递归和过拟合
5. 理解叶节点的预测值：使用平均值是最优选择

实际应用建议

1. 特征选择：CART会自动选择重要特征
2. 连续特征处理：CART通过二分法自然处理连续特征
3. 剪枝：使用剪枝防止过拟合
4. 集成方法：可以使用随机森林等集成方法提高稳定性和精度
5. 超参数调优：调整最大深度、最小样本数等参数

延伸学习

• CART剪枝技术：如何剪枝防止过拟合
• CART分类树：如何使用CART处理分类问题
• 随机森林回归：集成多个CART回归树
• 梯度提升回归树：使用梯度提升方法优化CART
• XGBoost和LightGBM：基于CART的高效梯度提升框架