上一篇我们通过银行贷款案例，理解了决策树 “像流程图一样判断” 的直观形态。但只知道 “怎么用” 还不够，入门阶段更要搞懂 “决策树是怎么建出来的”—— 比如为什么先判断 “房产” 而不是 “收入”？划分到什么时候停止？这篇就从基本流程、纯度评判、最优属性选择三个核心维度，结合经典的西瓜数据集，帮你彻底吃透决策树的构建逻辑。

一、先想清楚：决策树构建的核心问题

在正式讲流程前，我们先明确一个关键问题：构建决策树的本质，是 **“递归地选择最优属性划分样本，直到满足停止条件”**。这里有两个需要解决的核心点：

1. 怎么选 “最优属性”？比如西瓜数据集中，“色泽”“根蒂”“纹理” 哪个先作为根节点判断？
2. 什么时候停止划分？比如分到某个节点时，样本全是 “好瓜”，还用继续分吗？

这两个问题贯穿决策树构建的全程，也是我们接下来要重点拆解的内容。

二、决策树的基本流程：递归函数 TreeGenerate 详解

决策树的构建是一个 “自顶向下” 的递归过程，核心是一个叫TreeGenerate的函数 —— 输入训练数据和可选属性，输出一棵决策树。我们先明确流程的输入输出，再逐行拆解函数逻辑，全程无复杂代码，纯逻辑理解。

1. 流程的输入与输出

• 输入：
• 输出：以当前节点为根的一棵决策树（可能是完整树，也可能是某个分支的子树）。

2. 递归函数 TreeGenerate 逐步拆解

我们把函数的逻辑拆成 “初始化→终止条件→选最优属性→递归划分” 四步，用通俗的语言解释每一步的作用：

步骤 1：初始化节点

1: 生成结点node;

先创建一个空节点（可能是根节点、内部节点，也可能是叶节点），后续根据样本和属性的情况给它 “贴标签”。

步骤 2：判断终止条件（核心！避免无限递归）

这一步是递归的 “出口”—— 当满足以下两个条件之一时，当前节点不再划分，直接标记为叶节点（输出类别）：

条件 1：样本全属于同一类别

2: if D中样本全属于同一类别C then 
3:   将node标记为C类叶结点，return; 
4: end if

比如某个节点的样本全是 “好瓜”，再划分已经没有意义，直接把这个节点标为 “好瓜” 叶节点，结束当前分支的递归。

条件 2：无属性可选，或样本在所有属性上取值相同

5: if A=∅ OR D中样本在A上取值相同 then 
6:   将node标记为叶结点，类别为D中样本数最多的类; return; 
7: end if

• 情况 1：属性集 A 为空（所有属性都用完了），但样本类别还不统一 —— 此时选 “样本数最多的类别” 作为结果（比如 10 个样本里 7 个好瓜、3 个坏瓜，就标为好瓜）。
• 情况 2：样本在所有属性上取值相同（比如所有样本都是 “青绿色、蜷缩根蒂”），但类别不同 —— 同样按 “多数表决” 标类别（避免无意义划分）。

步骤 3：选择最优划分属性

8: 从A中选择最优划分属性a*;

这是决策树构建的 “灵魂步骤”—— 比如从 “色泽、根蒂、敲声” 中选一个 “划分效果最好” 的属性（比如西瓜数据集中的 “纹理”）。

“最优” 怎么定义？核心是 “划分后样本的纯度更高”—— 比如原本混合的好瓜坏瓜，划分后每个分支的样本类别更集中（比如一个分支多是好瓜，另一个多是坏瓜）。

后续会用 “信息增益” 量化 “纯度提升”，这里先记住：最优属性是让 “纯度提升最大” 的属性。

步骤 4：按最优属性递归划分

9: for a*的每一个值a*_v do  // 遍历最优属性的所有取值（如纹理的“清晰、稍糊、模糊”）
10:  为node生成一个分支；令D_v表示D中在a*上取值为a*_v的样本子集;
11:  if D_v为空 then  // 该取值没有样本（如“纹理=透明”，训练集中没有）
12:    将分支结点标记为叶结点，类别为D中样本最多的类; return;
13:  else  // 有样本，递归构建子树
14:    以TreeGenerate(D_v, A\{a*})为分支结点  // A\{a*}：去掉已用的属性
15:  end if
16: end for

比如最优属性是 “纹理”，它有 3 个取值：清晰、稍糊、模糊：

• 为每个取值建一个分支，把训练集分成 3 个子集（D_清晰、D_稍糊、D_模糊）；
• 对每个子集，用 “去掉纹理后的属性集”（色泽、根蒂、敲声等）递归调用TreeGenerate，继续构建子树；
• 如果某个子集为空（比如没有样本的纹理是 “透明”），就按 “多数表决” 标类别（避免空节点）。

三、先搞懂 “纯度”：划分效果的评判标准

要选 “最优属性”，首先得量化 “纯度”—— 样本集合的类别越集中，纯度越高。比如：

• 10 个样本全是好瓜：纯度 100%（最高）；
• 5 个好瓜、5 个坏瓜：纯度 50%（最低）；
• 8 个好瓜、2 个坏瓜：纯度 80%（中等）。

常用的纯度量化指标有 3 个：熵（Entropy）、Gini 系数、错误率，入门阶段重点掌握 “熵” 即可（信息增益基于熵计算）。

1. 熵（Entropy）：最常用的纯度指标

熵的本质是 “衡量样本集合的不确定性”—— 不确定性越低（类别越集中），熵越小；不确定性越高（类别越混合），熵越大。

2. 其他纯度指标（简单了解）

除了熵，还有两个常用指标，公式更简单，逻辑类似：

入门阶段先聚焦 “熵”，因为后续 “信息增益” 是基于熵的最优属性选择方法。

四、信息熵与信息增益：选最优划分属性的核心

有了 “熵” 来衡量纯度，接下来的问题是：用某个属性划分后，纯度提升了多少？ 这个提升量就是 “信息增益（Information Gain）”—— 信息增益越大，说明该属性的划分效果越好，就是 “最优属性”。

1. 信息增益的定义与公式

2. 实战：用西瓜数据集算信息增益

我们用 “西瓜数据集 2.0”（17 个样本，好瓜 8 个、坏瓜 9 个）为例，一步步计算 “色泽” 属性的信息增益，再对比其他属性，找到最优根属性。

步骤 1：计算根节点（整个样本集 D）的熵

步骤 2：计算 “色泽” 属性的信息增益

色泽有 3 个取值：青绿（D1）、乌黑（D2）、浅白（D3），先算每个子集的熵：

步骤 3：对比所有属性的信息增益，选最优

用同样的方法计算其他属性的信息增益（结果如下）：

根据 “信息增益最大” 原则，“纹理” 是根节点的最优划分属性—— 这就是为什么决策树的根节点会先判断 “纹理”，而不是其他属性。

五、继续构建：从 “纹理” 分支到子树

选好根属性 “纹理” 后，我们按 “纹理 = 清晰、稍糊、模糊” 分成 3 个分支，再对每个分支递归构建子树（以 “纹理 = 清晰” 为例）。

1. 处理 “纹理 = 清晰” 的分支（D1 子集）

• D1 包含 9 个样本（编号 1,2,3,4,5,6,8,10,15），类别：好瓜 6 个、坏瓜 3 个；
• 可选属性集：去掉 “纹理”，剩下 {色泽、根蒂、敲声、脐部、触感}；
• 计算这些属性在 D1 上的信息增益（结果如下）：

这里 “根蒂、脐部、触感” 的信息增益相同，任选一个即可（比如选 “根蒂”）。

2. 按 “根蒂” 划分 “纹理 = 清晰” 的子分支

根蒂有 3 个取值：蜷缩、稍蜷、硬挺：

• 根蒂 = 蜷缩：D11 包含 5 个样本（编号 1,2,3,4,5），全是好瓜 → 满足终止条件，标为 “好瓜” 叶节点；
• 根蒂 = 稍蜷：D12 包含 3 个样本（编号 6,8,15），好瓜 1 个、坏瓜 2 个 → 继续用剩下的属性（色泽、敲声、脐部、触感）计算信息增益，比如选 “色泽”，再划分；
• 根蒂 = 硬挺：D13 包含 1 个样本（编号 10），是坏瓜 → 标为 “坏瓜” 叶节点。

以此类推，递归处理 “纹理 = 稍糊”“纹理 = 模糊” 的分支，直到所有节点都满足停止条件，最终得到完整的决策树（结构如下，简化版）：

根节点：纹理
├─ 清晰 → 子节点：根蒂
│  ├─ 蜷缩 → 叶节点：好瓜
│  ├─ 稍蜷 → 子节点：色泽
│  │  ├─ 青绿 → 叶节点：好瓜
│  │  ├─ 乌黑 → 子节点：触感 → 硬滑：好瓜，软粘：坏瓜
│  │  └─ 浅白 → 叶节点：好瓜
│  └─ 硬挺 → 叶节点：坏瓜
├─ 稍糊 → 子节点：触感
│  ├─ 硬滑 → 叶节点：好瓜
│  └─ 软粘 → 叶节点：坏瓜
└─ 模糊 → 叶节点：坏瓜

六、决策树的停止条件：何时该 “收手”？

递归构建决策树时，必须有明确的停止条件，否则会一直划分到 “每个叶节点只有一个样本”（过拟合，无法泛化到新数据）。常用的停止条件有两种：

1. 条件 1：子节点样本全属于同一类别

这是最直观的停止条件 —— 比如 “根蒂 = 蜷缩” 的子集中全是好瓜，再划分没有意义，直接标为叶节点。

2. 条件 2：样本数低于 “最小阈值”

如果子节点的样本数太少（比如少于 5 个），即使类别不统一，也停止划分 —— 因为样本太少时，划分结果的 “通用性” 差（比如 2 个样本 1 好 1 坏，再分也代表不了整体规律），此时按 “多数表决” 标类别（比如 3 个样本 2 好 1 坏，标为好瓜）。

七、避坑指南：为什么 “编号” 不能当划分属性？

假设我们把西瓜的 “编号” 也作为候选属性，计算它的信息增益会发现：Gain (D, 编号) = 0.998（几乎等于根节点的熵）—— 这是因为每个编号对应一个样本，划分后每个子节点只有 1 个样本（纯度 100%），信息增益最大。

但为什么不能用 “编号”？因为编号是 “唯一标识”，没有泛化能力：

• 训练集中每个编号只出现一次，划分后能完美分类训练集；
• 但新测试样本的编号是训练集中没有的（比如 “测 1” 没有编号），决策树无法判断，完全失去分类能力。

这告诉我们：划分属性必须是 “有实际意义的特征”（如色泽、根蒂），而不是 “唯一标识”（如编号、ID）—— 这是入门决策树时最容易踩的坑。

总结

决策树的基本流程是 “递归选最优属性划分样本，直到满足停止条件”，核心在于：

1. 用 “熵” 衡量纯度：熵越小，样本类别越集中；
2. 用 “信息增益” 选最优属性：信息增益越大，划分后纯度提升越多；
3. 用 “停止条件” 避免过拟合：样本全同类别或数量太少时，停止划分。

对入门学生来说，不用死记公式，而是要跟着西瓜数据集的案例 “手动计算一遍信息增益”—— 比如自己算 “根蒂” 的信息增益，再对比 “纹理”，就能真正理解 “为什么选这个属性”。

下一篇我们会讲决策树的 “剪枝”（解决过拟合问题），但当前阶段，先吃透 “基本流程和信息增益”，就是理解决策树的关键一步～