决策树CART分类算法

目录

1. 引言：CART是什么？
2. 第一部分：CART与ID3/C4.5的区别
3. 第二部分：基尼不纯度详解
4. 第三部分：基尼增益与特征选择
5. 第四部分：CART算法原理
6. 第五部分：完整实例演示
7. 第六部分：决策树构建过程详解
8. 第七部分：CART算法的优缺点
9. 总结与回顾

引言：CART是什么？

决策树算法的发展历程

决策树算法的发展经历了几个重要阶段：

1. ID3算法（1986年）

   • 使用信息熵和信息增益
   • 只能处理离散特征
   • 生成多叉树

2. C4.5算法（1993年）

   • 使用信息增益率
   • 可以处理连续特征和缺失值
   • 生成多叉树

3. CART算法（1984年）

   • 使用基尼不纯度
   • 可以处理分类和回归问题
   • 生成二叉树（重要特点）

什么是CART？

**CART（Classification and Regression Trees）**是一种决策树算法，由Leo Breiman等人在1984年提出。

CART的特点：

1. 二叉树结构：每个节点只有两个分支（是/否）
2. 基尼不纯度：使用基尼不纯度而不是信息熵
3. 分类和回归：可以处理分类问题和回归问题
4. 剪枝机制：有完善的剪枝策略

为什么需要CART？

CART的优势：

1. 二叉树更简洁：比多叉树更容易理解和实现
2. 计算效率高：二叉树的分裂计算更简单
3. 处理连续特征：通过二分法自然处理连续特征
4. 统一框架：分类和回归使用统一的框架

第一部分：CART与ID3/C4.5的区别

1.1 树结构的区别

ID3/C4.5： 多叉树

        [特征：天气]
        /   |   \
     [晴] [阴] [雨]

CART： 二叉树

        [特征：天气=晴?]
        /            \
    [是]            [否]
    /                  \
[特征：湿度=高?]    [特征：温度=高?]

1.2 选择标准的区别

1.3 基尼不纯度 vs 信息熵

信息熵：

• 基于信息论
• 使用对数函数
• 计算相对复杂

基尼不纯度：

• 基于概率论
• 使用平方函数
• 计算更简单
• 与信息熵在数学上等价（用于特征选择时）

1.4 CART的二叉树分裂方式

对于离散特征：

• 将特征取值分成两组
• 选择最优的分组方式
• 例如：天气 ∈ {晴, 阴, 雨}
  • 分组1：{晴} vs {阴, 雨}
  • 分组2：{阴} vs {晴, 雨}
  • 分组3：{雨} vs {晴, 阴}
  • 选择基尼增益最大的分组

对于连续特征：

• 选择一个阈值进行二分
• 例如：温度 > 25°C vs 温度 ≤ 25°C
• 选择最优的阈值

第二部分：基尼不纯度详解

2.1 基尼不纯度的定义

基尼不纯度（Gini Impurity）：衡量数据集的"不纯度"或"混乱程度"

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

其中：

• $D$：数据集
• $K$：类别数量
• $p_k$：第 $k$ 个类别的样本比例

等价形式：

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

2.2 基尼不纯度的直观理解

基尼不纯度衡量：随机选择一个样本，然后随机标记为某个类别，标记错误的概率

例子：
假设有10个样本，5个属于类别A，5个属于类别B：

• 随机选择一个样本，它是A的概率 = 0.5
• 随机标记为B的概率 = 0.5
• 标记错误的概率 = 0.5 × 0.5 = 0.25
• 同样，选择B标记为A的概率也是0.25
• 总错误概率 = 0.25 + 0.25 = 0.5

基尼不纯度 = 0.5（最大混乱）

2.3 基尼不纯度的性质

1. 非负性：$Gini(D) \geq 0$
2. 确定性：当所有样本属于同一类别时，$Gini(D) = 0$（完全纯净）
3. 最大值：当所有类别均匀分布时，基尼不纯度达到最大值

最大基尼不纯度：
对于 $K$ 个类别，当 $p_k = \frac{1}{K}$ 对所有 $k$ 成立时：

$$
Gini_{max}(D) = 1 - K \times \left(\frac{1}{K}\right)^2 = 1 - \frac{1}{K} = \frac{K-1}{K}
$$

二分类问题：

• 最大基尼不纯度 = $1 - \frac{1}{2} = 0.5$
• 当两个类别各占50%时达到最大值

2.4 基尼不纯度 vs 信息熵

二分类问题对比：

观察：

• 基尼不纯度和信息熵的趋势相同
• 都在类别均匀分布时达到最大值
• 基尼不纯度的值域是 [0, 0.5]（二分类）
• 信息熵的值域是 [0, 1]（二分类）

2.5 基尼不纯度的计算示例

示例1：二分类问题

假设数据集 $D$ 中有14个样本：

• 9个属于类别"是"（正类）
• 5个属于类别"否"（负类）

计算基尼不纯度：

$$
p(是) = \frac{9}{14} = 0.643
$$

$$
p(否) = \frac{5}{14} = 0.357
$$

$$
Gini(D) = 1 - [p(是)^2 + p(否)^2]
$$

$$
Gini(D) = 1 - [0.643^2 + 0.357^2]
$$

$$
Gini(D) = 1 - [0.414 + 0.127] = 1 - 0.541 = 0.459
$$

示例2：完全纯净的数据

假设数据集 $D$ 中有10个样本，全部属于类别"是"：

$$
p(是) = 1.0, \quad p(否) = 0.0
$$

$$
Gini(D) = 1 - [1.0^2 + 0.0^2] = 1 - 1 = 0
$$

示例3：完全混乱的数据

假设数据集 $D$ 中有10个样本，5个属于类别"是"，5个属于类别"否"：

$$
p(是) = 0.5, \quad p(否) = 0.5
$$

$$
Gini(D) = 1 - [0.5^2 + 0.5^2] = 1 - [0.25 + 0.25] = 0.5
$$

2.6 基尼不纯度的数学性质

基尼不纯度是凸函数：

• 对于二分类，$Gini(p) = 2p(1-p)$
• 这是一个开口向下的抛物线
• 在 $p = 0.5$ 时达到最大值

基尼不纯度与信息熵的关系：

• 两者都是衡量不确定性的指标
• 在特征选择时，它们的选择结果通常一致
• 基尼不纯度计算更简单（不需要对数运算）

第三部分：基尼增益与特征选择

3.1 条件基尼不纯度的定义

条件基尼不纯度：在已知特征 $A$ 的条件下，数据集的不纯度

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

其中：

• $A$：特征
• $V$：特征 $A$ 的可能取值数量（对于CART，通常是2）
• $D_v$：特征 $A$ 取值为 $v$ 的样本子集
• $|D_v|$：子集 $D_v$ 的样本数量
• $|D|$：数据集 $D$ 的样本数量

3.2 基尼增益的定义

基尼增益（Gini Gain）：使用特征 $A$ 后，基尼不纯度的减少量

$$
GiniGain(D, A) = Gini(D) - Gini(D|A)
$$

其中：

• $Gini(D)$：数据集 $D$ 的原始基尼不纯度
• $Gini(D|A)$：使用特征 $A$ 后的条件基尼不纯度

3.3 基尼增益的直观理解

基尼增益衡量：使用某个特征后，不纯度减少了多少

• 基尼增益 = 0：该特征对分类没有帮助
• 基尼增益 = 原始基尼不纯度：该特征能完全确定类别
• 基尼增益越大：该特征对分类的帮助越大

CART算法的核心思想：
选择基尼增益最大的特征（或特征分组）进行分裂！

3.4 CART的二叉树分裂

对于离散特征：

假设特征"天气"有3个取值：{晴, 阴, 雨}

需要尝试所有可能的分组方式：

• 分组1：{晴} vs {阴, 雨}
• 分组2：{阴} vs {晴, 雨}
• 分组3：{雨} vs {晴, 阴}

对于每个分组，计算基尼增益，选择最大的。

对于连续特征：

假设特征"温度"是连续值：{20, 22, 25, 28, 30}

需要尝试所有可能的阈值：

• 阈值1：温度 ≤ 21 vs 温度 > 21
• 阈值2：温度 ≤ 23.5 vs 温度 > 23.5
• 阈值3：温度 ≤ 26.5 vs 温度 > 26.5
• 阈值4：温度 ≤ 29 vs 温度 > 29

对于每个阈值，计算基尼增益，选择最大的。

3.5 基尼增益的计算步骤

步骤1： 计算数据集 $D$ 的基尼不纯度 $Gini(D)$

步骤2： 对于每个特征 $A$：

• 如果是离散特征：尝试所有可能的分组方式
• 如果是连续特征：尝试所有可能的阈值
• 对于每个分组/阈值：
  • 计算两个子集的基尼不纯度 $Gini(D_1)$ 和 $Gini(D_2)$
  • 计算条件基尼不纯度：$Gini(D|A) = \frac{|D_1|}{|D|} Gini(D_1) + \frac{|D_2|}{|D|} Gini(D_2)$
  • 计算基尼增益：$GiniGain(D, A) = Gini(D) - Gini(D|A)$

步骤3： 选择基尼增益最大的特征和分组/阈值

第四部分：CART算法原理

4.1 CART算法的基本思想

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

1. 从根节点开始，包含所有训练样本
2. 选择最优特征和分裂点：
   • 对于每个特征，找到最优的分组/阈值
   • 计算每个特征的基尼增益
   • 选择基尼增益最大的特征和分裂点
3. 分裂节点：根据选定的特征和分裂点，将数据分成两个子集
4. 递归构建：对每个子集递归执行步骤2-3
5. 停止条件：
   • 所有样本属于同一类别
   • 没有剩余特征可用
   • 基尼增益小于阈值
   • 样本数量小于阈值
   • 树的深度达到最大值
6. 剪枝：构建完成后进行剪枝，防止过拟合

4.2 CART算法的伪代码

函数 CART(数据集D, 特征集A, 深度):
    如果 深度 >= 最大深度:
        返回 叶节点(D中多数类)
    
    如果 D中所有样本属于同一类别:
        返回 叶节点(类别)
    
    如果 A为空 或 |D| < 最小样本数:
        返回 叶节点(D中多数类)
    
    最佳特征 = None
    最佳分裂点 = None
    最佳增益 = -∞
    
    对于每个特征 a ∈ A:
        如果 a是离散特征:
            对于 a的每个可能分组:
                计算基尼增益
                如果 基尼增益 > 最佳增益:
                    更新最佳特征、分裂点、增益
        否则 (a是连续特征):
            对于 a的每个可能阈值:
                计算基尼增益
                如果 基尼增益 > 最佳增益:
                    更新最佳特征、分裂点、增益
    
    如果 最佳增益 <= 0:
        返回 叶节点(D中多数类)
    
    创建节点，标记为特征 a* 和分裂点
    
    创建左分支: D_left = {样本 | 样本满足分裂条件}
    创建右分支: D_right = {样本 | 样本不满足分裂条件}
    
    左子树 = CART(D_left, A - {a*}, 深度+1)
    右子树 = CART(D_right, A - {a*}, 深度+1)
    
    返回 节点

函数 剪枝(树T):
    # 后剪枝：从叶节点向上，如果剪枝后性能不下降，则剪枝
    返回 剪枝后的树

4.3 CART算法的特点

优点：

• 二叉树结构简洁，易于理解和实现
• 可以处理分类和回归问题
• 可以处理连续特征（通过二分法）
• 计算效率高（基尼不纯度计算简单）
• 有完善的剪枝机制

缺点：

• 对于多值离散特征，需要尝试所有分组（计算量大）
• 可能产生较深的树
• 对噪声敏感（需要剪枝）

第五部分：完整实例演示

5.1 数据集描述

我们使用天气预测是否打网球的数据集：

数据集统计：

• 总样本数：14
• 特征：天气、温度、湿度、风力（4个特征）
• 类别：是否打网球（2个类别：是、否）
• "是"的数量：9
• "否"的数量：5

5.2 第一步：计算根节点的基尼不纯度

数据集 $D$ 的基尼不纯度：

$$
p(是) = \frac{9}{14} = 0.643
$$

$$
p(否) = \frac{5}{14} = 0.357
$$

$$
Gini(D) = 1 - [p(是)^2 + p(否)^2]
$$

$$
Gini(D) = 1 - [0.643^2 + 0.357^2]
$$

$$
Gini(D) = 1 - [0.414 + 0.127] = 1 - 0.541 = 0.459
$$

根节点基尼不纯度：$Gini(D) = 0.459$

5.3 第二步：计算各特征的基尼增益

5.3.1 特征"天气"的基尼增益

特征"天气"的取值： 晴、阴、雨

需要尝试所有可能的分组：

分组1：{晴} vs {阴, 雨}

计算基尼不纯度：

$$
Gini(D_{晴}) = 1 - \left[\left(\frac{2}{5}\right)^2 + \left(\frac{3}{5}\right)^2\right] = 1 - [0.16 + 0.36] = 0.480
$$

$$
Gini(D_{阴,雨}) = 1 - \left[\left(\frac{7}{9}\right)^2 + \left(\frac{2}{9}\right)^2\right] = 1 - [0.605 + 0.049] = 0.346
$$

计算条件基尼不纯度：

$$
Gini(D|天气={晴} vs {阴,雨}) = \frac{5}{14} \times 0.480 + \frac{9}{14} \times 0.346 = 0.171 + 0.222 = 0.393
$$

计算基尼增益：

$$
GiniGain(D, 天气={晴} vs {阴,雨}) = 0.459 - 0.393 = 0.066
$$

分组2：{阴} vs {晴, 雨}

计算基尼不纯度：

$$
Gini(D_{阴}) = 1 - \left[\left(\frac{4}{4}\right)^2 + \left(\frac{0}{4}\right)^2\right] = 0
$$

$$
Gini(D_{晴,雨}) = 1 - \left[\left(\frac{5}{10}\right)^2 + \left(\frac{5}{10}\right)^2\right] = 1 - [0.25 + 0.25] = 0.500
$$

计算条件基尼不纯度：

$$
Gini(D|天气={阴} vs {晴,雨}) = \frac{4}{14} \times 0 + \frac{10}{14} \times 0.500 = 0 + 0.357 = 0.357
$$

计算基尼增益：

$$
GiniGain(D, 天气={阴} vs {晴,雨}) = 0.459 - 0.357 = 0.102
$$

分组3：{雨} vs {晴, 阴}

计算基尼不纯度：

$$
Gini(D_{雨}) = 1 - \left[\left(\frac{3}{5}\right)^2 + \left(\frac{2}{5}\right)^2\right] = 1 - [0.36 + 0.16] = 0.480
$$

$$
Gini(D_{晴,阴}) = 1 - \left[\left(\frac{6}{9}\right)^2 + \left(\frac{3}{9}\right)^2\right] = 1 - [0.444 + 0.111] = 0.445
$$

计算条件基尼不纯度：

$$
Gini(D|天气={雨} vs {晴,阴}) = \frac{5}{14} \times 0.480 + \frac{9}{14} \times 0.445 = 0.171 + 0.286 = 0.457
$$

计算基尼增益：

$$
GiniGain(D, 天气={雨} vs {晴,阴}) = 0.459 - 0.457 = 0.002
$$

特征"天气"的最佳分组：

• 分组1：基尼增益 = 0.066
• 分组2：基尼增益 = 0.102（最大）
• 分组3：基尼增益 = 0.002

特征"天气"的最佳基尼增益：0.102（分组2：{阴} vs {晴, 雨}）

5.3.2 特征"温度"的基尼增益

特征"温度"的取值： 高、中、低

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

$$
Gini(D_{高}) = 1 - \left[\left(\frac{2}{4}\right)^2 + \left(\frac{2}{4}\right)^2\right] = 0.500
$$

$$
Gini(D_{中,低}) = 1 - \left[\left(\frac{7}{10}\right)^2 + \left(\frac{3}{10}\right)^2\right] = 1 - [0.49 + 0.09] = 0.420
$$

$$
Gini(D|温度={高} vs {中,低}) = \frac{4}{14} \times 0.500 + \frac{10}{14} \times 0.420 = 0.143 + 0.300 = 0.443
$$

$$
GiniGain(D, 温度={高} vs {中,低}) = 0.459 - 0.443 = 0.016
$$

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

$$
Gini(D_{中}) = 1 - \left[\left(\frac{3}{5}\right)^2 + \left(\frac{2}{5}\right)^2\right] = 1 - [0.36 + 0.16] = 0.480
$$

$$
Gini(D_{高,低}) = 1 - \left[\left(\frac{6}{9}\right)^2 + \left(\frac{3}{9}\right)^2\right] = 1 - [0.444 + 0.111] = 0.445
$$

$$
Gini(D|温度={中} vs {高,低}) = \frac{5}{14} \times 0.480 + \frac{9}{14} \times 0.445 = 0.171 + 0.286 = 0.457
$$

$$
GiniGain(D, 温度={中} vs {高,低}) = 0.459 - 0.457 = 0.002
$$

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

$$
Gini(D_{低}) = 1 - \left[\left(\frac{3}{4}\right)^2 + \left(\frac{1}{4}\right)^2\right] = 1 - [0.5625 + 0.0625] = 0.375
$$

$$
Gini(D_{高,中}) = 1 - \left[\left(\frac{6}{10}\right)^2 + \left(\frac{4}{10}\right)^2\right] = 1 - [0.36 + 0.16] = 0.480
$$

$$
Gini(D|温度={低} vs {高,中}) = \frac{4}{14} \times 0.375 + \frac{10}{14} \times 0.480 = 0.107 + 0.343 = 0.450
$$

$$
GiniGain(D, 温度={低} vs {高,中}) = 0.459 - 0.450 = 0.009
$$

特征"温度"的最佳基尼增益：0.016（分组1：{高} vs {中, 低}）

5.3.3 特征"湿度"的基尼增益

特征"湿度"的取值： 高、正常

只有一种分组方式：{高} vs {正常}

$$
Gini(D_{高}) = 1 - \left[\left(\frac{3}{7}\right)^2 + \left(\frac{4}{7}\right)^2\right] = 1 - [0.184 + 0.327] = 0.490
$$

$$
Gini(D_{正常}) = 1 - \left[\left(\frac{6}{7}\right)^2 + \left(\frac{1}{7}\right)^2\right] = 1 - [0.735 + 0.020] = 0.245
$$

$$
Gini(D|湿度={高} vs {正常}) = \frac{7}{14} \times 0.490 + \frac{7}{14} \times 0.245 = 0.245 + 0.123 = 0.368
$$

$$
GiniGain(D, 湿度={高} vs {正常}) = 0.459 - 0.368 = 0.091
$$

特征"湿度"的基尼增益：0.091

5.3.4 特征"风力"的基尼增益

特征"风力"的取值： 弱、强

只有一种分组方式：{弱} vs {强}

$$
Gini(D_{弱}) = 1 - \left[\left(\frac{6}{8}\right)^2 + \left(\frac{2}{8}\right)^2\right] = 1 - [0.5625 + 0.0625] = 0.375
$$

$$
Gini(D_{强}) = 1 - \left[\left(\frac{3}{6}\right)^2 + \left(\frac{3}{6}\right)^2\right] = 1 - [0.25 + 0.25] = 0.500
$$

$$
Gini(D|风力={弱} vs {强}) = \frac{8}{14} \times 0.375 + \frac{6}{14} \times 0.500 = 0.214 + 0.214 = 0.428
$$

$$
GiniGain(D, 风力={弱} vs {强}) = 0.459 - 0.428 = 0.031
$$

特征"风力"的基尼增益：0.031

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

各特征的基尼增益汇总：

结论： 特征"天气"的分组{阴} vs {晴,雨}的基尼增益最大（0.102），因此选择"天气"作为根节点的分裂特征，分裂条件为：天气 = 阴？

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

6.1 第一层分裂：根节点

根据"天气"特征进行分裂，分裂条件：天气 = 阴？

                    [根节点：D(14个样本)]
                    Gini(D) = 0.459
                           |
                    [特征：天气=阴?]
                    GiniGain = 0.102
                    /            \
            [是:4]            [否:10]
         Gini=0.000        Gini=0.500

子集划分：

• $D_{是}$（天气=阴，4个样本）：样本3,7,12,13

  • "是"：4个
  • "否"：0个
  • $Gini(D_{是}) = 0$（完全确定，已经是叶节点：是）

• $D_{否}$（天气≠阴，10个样本）：样本1,2,4,5,6,8,9,10,11,14

  • "是"：5个（样本4,5,9,10,11）
  • "否"：5个（样本1,2,6,8,14）
  • $Gini(D_{否}) = 0.500$

6.2 第二层分裂：处理"天气≠阴"分支

当前数据集： $D_{否}$（10个样本，天气为"晴"或"雨"）

计算基尼不纯度：

$$
Gini(D_{否}) = 1 - \left[\left(\frac{5}{10}\right)^2 + \left(\frac{5}{10}\right)^2\right] = 0.500
$$

计算各特征的基尼增益（在$D_{否}$上）：

6.2.1 特征"天气"的剩余分组

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

• 当前节点：天气≠阴（即天气∈{晴,雨}）
• 可以进一步分裂：{晴} vs {雨}

$$
Gini(D_{晴}) = 1 - \left[\left(\frac{2}{5}\right)^2 + \left(\frac{3}{5}\right)^2\right] = 0.480
$$

$$
Gini(D_{雨}) = 1 - \left[\left(\frac{3}{5}\right)^2 + \left(\frac{2}{5}\right)^2\right] = 0.480
$$

$$
Gini(D_{否}|天气={晴} vs {雨}) = \frac{5}{10} \times 0.480 + \frac{5}{10} \times 0.480 = 0.480
$$

$$
GiniGain(D_{否}, 天气={晴} vs {雨}) = 0.500 - 0.480 = 0.020
$$

6.2.2 特征"温度"的基尼增益

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

$$
Gini(D_{高}) = 1 - \left[\left(\frac{0}{2}\right)^2 + \left(\frac{2}{2}\right)^2\right] = 0
$$

$$
Gini(D_{中,低}) = 1 - \left[\left(\frac{5}{8}\right)^2 + \left(\frac{3}{8}\right)^2\right] = 1 - [0.391 + 0.141] = 0.469
$$

$$
Gini(D_{否}|温度={高} vs {中,低}) = \frac{2}{10} \times 0 + \frac{8}{10} \times 0.469 = 0.375
$$

$$
GiniGain(D_{否}, 温度={高} vs {中,低}) = 0.500 - 0.375 = 0.125
$$

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

$$
Gini(D_{中}) = 1 - \left[\left(\frac{3}{5}\right)^2 + \left(\frac{2}{5}\right)^2\right] = 0.480
$$

$$
Gini(D_{高,低}) = 1 - \left[\left(\frac{2}{5}\right)^2 + \left(\frac{3}{5}\right)^2\right] = 0.480
$$

$$
Gini(D_{否}|温度={中} vs {高,低}) = \frac{5}{10} \times 0.480 + \frac{5}{10} \times 0.480 = 0.480
$$

$$
GiniGain(D_{否}, 温度={中} vs {高,低}) = 0.500 - 0.480 = 0.020
$$

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

$$
Gini(D_{低}) = 1 - \left[\left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2\right] = 1 - [0.444 + 0.111] = 0.445
$$

$$
Gini(D_{高,中}) = 1 - \left[\left(\frac{3}{7}\right)^2 + \left(\frac{4}{7}\right)^2\right] = 1 - [0.184 + 0.327] = 0.490
$$

$$
Gini(D_{否}|温度={低} vs {高,中}) = \frac{3}{10} \times 0.445 + \frac{7}{10} \times 0.490 = 0.134 + 0.343 = 0.477
$$

$$
GiniGain(D_{否}, 温度={低} vs {高,中}) = 0.500 - 0.477 = 0.023
$$

特征"温度"的最佳基尼增益：0.125（分组1：{高} vs {中, 低}）

6.2.3 特征"湿度"的基尼增益

分组：{高} vs {正常}

$$
Gini(D_{高}) = 1 - \left[\left(\frac{1}{5}\right)^2 + \left(\frac{4}{5}\right)^2\right] = 1 - [0.04 + 0.64] = 0.320
$$

$$
Gini(D_{正常}) = 1 - \left[\left(\frac{4}{5}\right)^2 + \left(\frac{1}{5}\right)^2\right] = 1 - [0.64 + 0.04] = 0.320
$$

$$
Gini(D_{否}|湿度={高} vs {正常}) = \frac{5}{10} \times 0.320 + \frac{5}{10} \times 0.320 = 0.320
$$

$$
GiniGain(D_{否}, 湿度={高} vs {正常}) = 0.500 - 0.320 = 0.180
$$

特征"湿度"的基尼增益：0.180

6.2.4 特征"风力"的基尼增益

分组：{弱} vs {强}

$$
Gini(D_{弱}) = 1 - \left[\left(\frac{4}{6}\right)^2 + \left(\frac{2}{6}\right)^2\right] = 1 - [0.444 + 0.111] = 0.445
$$

$$
Gini(D_{强}) = 1 - \left[\left(\frac{1}{4}\right)^2 + \left(\frac{3}{4}\right)^2\right] = 1 - [0.0625 + 0.5625] = 0.375
$$

$$
Gini(D_{否}|风力={弱} vs {强}) = \frac{6}{10} \times 0.445 + \frac{4}{10} \times 0.375 = 0.267 + 0.150 = 0.417
$$

$$
GiniGain(D_{否}, 风力={弱} vs {强}) = 0.500 - 0.417 = 0.083
$$

特征"风力"的基尼增益：0.083

信息增益汇总：

结论： 选择"湿度"作为分裂特征，分裂条件：湿度 = 高？

分裂结果：

• $D_{否,高}$（湿度=高，5个样本）：样本1,2,4,8,14

  • "是"：1个（样本4）
  • "否"：4个（样本1,2,8,14）
  • $Gini = 0.320$

• $D_{否,正常}$（湿度=正常，5个样本）：样本5,6,9,10,11

  • "是"：4个（样本5,9,10,11）
  • "否"：1个（样本6）
  • $Gini = 0.320$

6.3 第三层分裂：处理"湿度=高"分支

当前数据集： $D_{否,高}$（5个样本）

计算基尼不纯度：

$$
Gini(D_{否,高}) = 1 - \left[\left(\frac{1}{5}\right)^2 + \left(\frac{4}{5}\right)^2\right] = 0.320
$$

计算各特征的基尼增益：

6.3.1 特征"天气"的基尼增益

当前节点：天气≠阴，可以进一步分裂为{晴} vs {雨}

$$
Gini(D_{晴}) = 1 - \left[\left(\frac{0}{3}\right)^2 + \left(\frac{3}{3}\right)^2\right] = 0
$$

$$
Gini(D_{雨}) = 1 - \left[\left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2\right] = 0.500
$$

$$
Gini(D_{否,高}|天气={晴} vs {雨}) = \frac{3}{5} \times 0 + \frac{2}{5} \times 0.500 = 0.200
$$

$$
GiniGain(D_{否,高}, 天气={晴} vs {雨}) = 0.320 - 0.200 = 0.120
$$

6.3.2 特征"温度"的基尼增益

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

$$
Gini(D_{高}) = 0
$$

$$
Gini(D_{中,低}) = 1 - \left[\left(\frac{1}{3}\right)^2 + \left(\frac{2}{3}\right)^2\right] = 1 - [0.111 + 0.444] = 0.445
$$

$$
Gini(D_{否,高}|温度={高} vs {中,低}) = \frac{2}{5} \times 0 + \frac{3}{5} \times 0.445 = 0.267
$$

$$
GiniGain(D_{否,高}, 温度={高} vs {中,低}) = 0.320 - 0.267 = 0.053
$$

分组2和3的计算类似，但基尼增益会更小。

特征"温度"的最佳基尼增益：0.053

6.3.3 特征"风力"的基尼增益

分组：{弱} vs {强}

$$
Gini(D_{弱}) = 1 - \left[\left(\frac{1}{3}\right)^2 + \left(\frac{2}{3}\right)^2\right] = 0.445
$$

$$
Gini(D_{强}) = 1 - \left[\left(\frac{0}{2}\right)^2 + \left(\frac{2}{2}\right)^2\right] = 0
$$

$$
Gini(D_{否,高}|风力={弱} vs {强}) = \frac{3}{5} \times 0.445 + \frac{2}{5} \times 0 = 0.267
$$

$$
GiniGain(D_{否,高}, 风力={弱} vs {强}) = 0.320 - 0.267 = 0.053
$$

特征"风力"的基尼增益：0.053

基尼增益汇总：

结论： 选择"天气"作为分裂特征，分裂条件：天气 = 晴？

分裂结果：

• $D_{否,高,晴}$（天气=晴，3个样本）：样本1,2,8

  • "是"：0个
  • "否"：3个
  • $Gini = 0$（完全确定，叶节点：否）

• $D_{否,高,雨}$（天气=雨，2个样本）：样本4,14

  • "是"：1个（样本4）
  • "否"：1个（样本14）
  • $Gini = 0.500$（需要继续分裂或使用多数类）

由于样本数量较少，我们可以选择多数类或继续分裂。这里选择多数类：否（因为两个样本中，如果无法确定，可以选择父节点的多数类）

6.4 第三层分裂：处理"湿度=正常"分支

当前数据集： $D_{否,正常}$（5个样本）

计算基尼不纯度：

$$
Gini(D_{否,正常}) = 1 - \left[\left(\frac{4}{5}\right)^2 + \left(\frac{1}{5}\right)^2\right] = 0.320
$$

计算各特征的基尼增益：

6.4.1 特征"天气"的基尼增益

$$
Gini(D_{晴}) = 0
$$

$$
Gini(D_{雨}) = 1 - \left[\left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2\right] = 0.445
$$

$$
Gini(D_{否,正常}|天气={晴} vs {雨}) = \frac{2}{5} \times 0 + \frac{3}{5} \times 0.445 = 0.267
$$

$$
GiniGain(D_{否,正常}, 天气={晴} vs {雨}) = 0.320 - 0.267 = 0.053
$$

6.4.2 特征"温度"的基尼增益

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

由于{高}组为空，这个分组无效。

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

$$
Gini(D_{中}) = 0
$$

$$
Gini(D_{高,低}) = 1 - \left[\left(\frac{2}{3}\right)^2 + \left(\frac{1}{3}\right)^2\right] = 0.445
$$

$$
Gini(D_{否,正常}|温度={中} vs {高,低}) = \frac{2}{5} \times 0 + \frac{3}{5} \times 0.445 = 0.267
$$

$$
GiniGain(D_{否,正常}, 温度={中} vs {高,低}) = 0.320 - 0.267 = 0.053
$$

6.4.3 特征"风力"的基尼增益

分组：{弱} vs {强}

$$
Gini(D_{弱}) = 0
$$

$$
Gini(D_{强}) = 1 - \left[\left(\frac{1}{2}\right)^2 + \left(\frac{1}{2}\right)^2\right] = 0.500
$$

$$
Gini(D_{否,正常}|风力={弱} vs {强}) = \frac{3}{5} \times 0 + \frac{2}{5} \times 0.500 = 0.200
$$

$$
GiniGain(D_{否,正常}, 风力={弱} vs {强}) = 0.320 - 0.200 = 0.120
$$

基尼增益汇总：

结论： 选择"风力"作为分裂特征，分裂条件：风力 = 弱？

分裂结果：

• $D_{否,正常,弱}$（风力=弱，3个样本）：样本5,9,10

  • "是"：3个
  • "否"：0个
  • $Gini = 0$（完全确定，叶节点：是）

• $D_{否,正常,强}$（风力=强，2个样本）：样本6,11

  • "是"：1个（样本11）
  • "否"：1个（样本6）
  • $Gini = 0.500$（选择多数类或继续分裂）

由于样本数量较少，选择多数类：是（因为父节点中"是"更多）

6.5 完整的决策树结构

                        [根节点：D(14个样本)]
                        Gini(D) = 0.459
                                 |
                        [特征：天气=阴?]
                        GiniGain = 0.102
                        /            \
                  [是:4]          [否:10]
                Gini=0.000      Gini=0.500
                    |                |
            [叶节点:是]      [特征：湿度=高?]
                          GiniGain = 0.180
                          /            \
                    [是:5]          [否:5]
                  Gini=0.320      Gini=0.320
                      |                |
            [特征：天气=晴?]    [特征：风力=弱?]
            GiniGain=0.120      GiniGain=0.120
            /            \      /            \
      [是:3]        [否:2]  [是:3]      [否:2]
    Gini=0.000    Gini=0.5 Gini=0.000  Gini=0.5
        |              |        |            |
  [叶节点:否]  [叶节点:否] [叶节点:是] [叶节点:是]

6.6 决策树的文本表示

如果 天气 = 阴：
    返回 是
否则（天气 ≠ 阴）：
    如果 湿度 = 高：
        如果 天气 = 晴：
            返回 否
        否则（天气 = 雨）：
            返回 否
    否则（湿度 = 正常）：
        如果 风力 = 弱：
            返回 是
        否则（风力 = 强）：
            返回 是

6.7 决策树的ASCII图示

                    ┌─────────────────┐
                    │  根节点(14样本) │
                    │ Gini(D) = 0.459 │
                    └────────┬────────┘
                             │
                    ┌────────▼────────┐
                    │  特征：天气=阴? │
                    │ GiniGain=0.102 │
                    └───┬────────────┘
                        │
            ┌───────────┴───────────┐
            │                       │
    ┌───────▼──────┐       ┌───────▼──────┐
    │ 是 (4样本)   │       │ 否 (10样本)  │
    │ Gini=0.000   │       │ Gini=0.500   │
    └───────┬──────┘       └───────┬──────┘
            │                      │
    ┌───────▼──────┐       ┌───────▼────────┐
    │ 叶节点:是    │       │ 特征：湿度=高? │
    └──────────────┘       │ GiniGain=0.180 │
                           └───┬────────────┘
                               │
                   ┌───────────┴───────────┐
                   │                       │
           ┌───────▼──────┐       ┌───────▼──────┐
           │ 是 (5样本)   │       │ 否 (5样本)   │
           │ Gini=0.320   │       │ Gini=0.320   │
           └───────┬──────┘       └───────┬──────┘
                   │                      │
       ┌───────────▼────────┐   ┌────────▼────────┐
       │ 特征：天气=晴?     │   │ 特征：风力=弱?  │
       │ GiniGain=0.120     │   │ GiniGain=0.120  │
       └───┬────────────┘   │   └───┬────────────┘
           │                 │       │
   ┌───────┴───────┐   ┌────┴────┐ ┌────┴────┐
   │              │   │         │ │        │
┌──▼──┐      ┌───▼──┐ ┌──▼──┐ ┌─▼──┐ ┌──▼──┐ ┌─▼──┐
│是:3 │      │否:2  │ │是:3 │ │否:2│ │是:3 │ │否:2│
│G=0  │      │G=0.5 │ │G=0  │ │G=0.5│ │G=0  │ │G=0.5│
└──┬──┘      └───┬──┘ └──┬──┘ └─┬──┘ └──┬──┘ └─┬──┘
   │             │       │      │      │      │
┌──▼──┐      ┌───▼──┐ ┌──▼──┐ ┌─▼──┐ ┌──▼──┐ ┌─▼──┐
│叶:否│      │叶:否 │ │叶:是│ │叶:是│ │叶:是│ │叶:是│
└─────┘      └──────┘ └─────┘ └────┘ └─────┘ └────┘

6.8 验证决策树

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

样本3： 天气=阴, 温度=高, 湿度=高, 风力=弱

• 路径：天气=阴？是 → 是 ✓（实际：是）

样本1： 天气=晴, 温度=高, 湿度=高, 风力=弱

• 路径：天气=阴？否 → 湿度=高？是 → 天气=晴？是 → 否 ✓（实际：否）

样本5： 天气=雨, 温度=低, 湿度=正常, 风力=弱

• 路径：天气=阴？否 → 湿度=高？否 → 风力=弱？是 → 是 ✓（实际：是）

样本6： 天气=雨, 温度=低, 湿度=正常, 风力=强

• 路径：天气=阴？否 → 湿度=高？否 → 风力=弱？否 → 是 ✓（实际：否）

注意：样本6的预测结果与实际不符，这是因为在构建过程中，某些节点样本数量较少，我们选择了多数类。在实际应用中，可以通过剪枝或调整停止条件来改善。

第七部分：CART算法的优缺点

7.1 优点

1. 二叉树结构简洁

   • 每个节点只有两个分支，易于理解和实现
   • 比多叉树更简洁

2. 计算效率高

   • 基尼不纯度计算简单（不需要对数运算）
   • 比信息熵计算更快

3. 可以处理连续特征

   • 通过二分法自然处理连续特征
   • 选择最优阈值进行分裂

4. 统一框架

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

5. 剪枝机制完善

   • 有完善的剪枝策略
   • 可以有效防止过拟合

7.2 缺点

1. 离散特征分组计算量大

   • 对于多值离散特征，需要尝试所有分组方式
   • 计算复杂度较高

2. 可能产生较深的树

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

3. 对噪声敏感

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

4. 不稳定

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

7.3 与其他算法的对比

总结与回顾

核心概念回顾

1. 基尼不纯度 $Gini(D)$

   • 衡量数据集的不纯度
   • 公式：$Gini(D) = 1 - \sum_{k=1}^{K} p_k^2$
   • 值域：[0, 0.5]（二分类）

2. 条件基尼不纯度 $Gini(D|A)$

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

3. 基尼增益 $GiniGain(D, A)$

   • 使用特征 $A$ 后，基尼不纯度的减少量
   • 公式：$GiniGain(D, A) = Gini(D) - Gini(D|A)$
   • 基尼增益越大，特征越重要

4. CART算法流程

   • 计算数据集的基尼不纯度
   • 对每个特征尝试所有可能的分组/阈值
   • 选择基尼增益最大的特征和分裂点
   • 递归构建二叉树
   • 直到满足停止条件

关键公式汇总

基尼不纯度：
$$
Gini(D) = 1 - \sum_{k=1}^{K} p_k^2 = 1 - \sum_{k=1}^{K} \left(\frac{|C_k|}{|D|}\right)^2
$$

条件基尼不纯度：
$$
Gini(D|A) = \sum_{v=1}^{V} \frac{|D_v|}{|D|} Gini(D_v)
$$

基尼增益：
$$
GiniGain(D, A) = Gini(D) - Gini(D|A)
$$

其中：

• $D$：数据集
• $C_k$：第 $k$ 个类别的样本集合
• $A$：特征
• $D_v$：特征 $A$ 取值为 $v$ 的样本子集
• $K$：类别数量
• $V$：特征 $A$ 的取值数量（对于CART，通常是2）

基尼不纯度 vs 信息熵

学习要点

1. 理解基尼不纯度的物理意义：衡量分类错误的概率
2. 掌握基尼增益的计算：这是CART算法的核心
3. 理解二叉树分裂方式：对于离散特征需要尝试所有分组
4. 注意停止条件：避免无限递归和过拟合

实际应用建议

1. 特征选择：CART会自动选择重要特征
2. 连续特征处理：CART通过二分法自然处理连续特征
3. 剪枝：使用剪枝防止过拟合
4. 集成方法：可以使用随机森林等集成方法提高稳定性

延伸学习

• CART剪枝技术：如何剪枝防止过拟合
• CART回归：如何使用CART处理回归问题
• 随机森林：集成多个CART树
• 梯度提升树：使用梯度提升方法优化CART