This note is currently available in Chinese. The original wording, formulas and diagrams are preserved to avoid an unverified technical translation.

描述：本节整理决策树的递归生成过程、信息熵与信息增益、增益率、基尼指数、预剪枝与后剪枝，以及属性缺失时的加权划分方法。

4.1 决策树模型

决策树基于树结构进行决策。
每个内部结点对应某个属性上的测试或判断。
每条分支对应一次测试的某个结果，即该属性的某个取值。
每个叶结点对应一个预测结果。
决策路径同时给出预测结果和形成该结果的判断过程，因此决策树直观、可视化且便于追溯。

学习与预测是两个过程：

学习阶段分析训练样本，确定每个内部结点使用的划分属性。
预测阶段从根结点开始，把待测样本依次代入各属性测试，沿分支下行直到叶结点。

4.2 递归划分过程

决策树采用“分而治之”的策略，自根向叶递归生成。

给定训练集

$$ D={(\boldsymbol{x}_1,y_1),\ldots,(\boldsymbol{x}_m,y_m)} $$

和属性集

$$ A={a_1,a_2,\ldots,a_d}, $$

下面先给出离散属性按取值多路划分的 ID3/C4.5 式基本过程：

生成当前结点。
若 $D$ 中样本全属于同一类别 $C$，把结点标记为类别 $C$ 的叶结点。
若 $A$ 为空，或 $D$ 中所有样本在 $A$ 上取值完全相同，把结点标记为叶结点，类别取 $D$ 中样本数最多的类别。
从 $A$ 中选择最优划分属性 $a_*$。
对 $a_$ 的每个取值 $a_^v$ 建立一个分支，令

$$ D_v={\boldsymbol{x}\in D\mid a_(\boldsymbol{x})=a_^v}. $$

若 $D_v$ 为空，把该分支直接标记为叶结点，类别取父结点数据 $D$ 中的多数类。
否则用 $D_v$ 和 $A\setminus{a_*}$ 递归生成子树。

上述“每个取值一条分支并删除已用属性”只适用于这种离散多路划分。连续属性通常选择阈值做二元切分，同一连续属性可在后代结点再次选择；CART 对离散属性也寻找二元子集划分，不能无条件套用步骤 5-7。

三类停止条件是：

当前结点所有样本属于同一类，不必继续划分。
属性集已空，或剩余样本在所有可用属性上取值相同，已无法划分。
某个分支对应的样本集合为空，没有数据可继续划分。
树太浅可能欠拟合，树过深又容易过拟合；最大深度、最小叶结点样本数等都可作为复杂度控制条件。

4.3 信息熵

信息熵用于度量样本集合的纯度或不确定性。

假设数据集 $D$ 含 $|\mathcal Y|$ 个类别，第 $k$ 类样本比例为 $p_k$，则

$$ \operatorname{Ent}(D) =-\sum_{k=1}^{|\mathcal Y|} p_k\log_2p_k. $$

信息熵越大，各类别越接近均匀分布，不确定性越高。
信息熵越小，样本越集中于少数类别，纯度越高。
当所有样本同属一类时，某个 $p_k=1$，其余为 $0$，有

$$ \operatorname{Ent}(D)=0. $$

对 $p_k=0$ 的项约定 $0\log_20=0$。
直观上，熵回答“还需要多少信息才能说明该样本属于哪一类”。

4.4 信息增益与 ID3

若离散属性 $a$ 有 $V$ 个可能取值

$$ {a^1,a^2,\ldots,a^V}, $$

令 $D^v$ 为 $D$ 中属性 $a$ 取值为 $a^v$ 的样本子集，则属性 $a$ 的信息增益为

$$ \operatorname{Gain}(D,a) =\operatorname{Ent}(D) -\sum_{v=1}^{V} \frac{|D^v|}{|D|} \operatorname{Ent}(D^v). $$

第一项是划分前的熵。
第二项是划分后各子结点熵的加权和，样本越多的分支权重越大。
信息增益越大，说明本次划分带来的纯度提升越大。
ID3 在候选属性中选择信息增益最大的属性，主要用于分类任务。

4.4.1 源资料中的西瓜数据示例

以属性“色泽”划分，三个分支的样本数分别为 $6,6,5$，对应熵为

$$ \operatorname{Ent}(D^1)=1.000, \qquad \operatorname{Ent}(D^2)=0.918, \qquad \operatorname{Ent}(D^3)=0.722. $$

根结点熵为 $0.998$，因此

$$ \begin{aligned} \operatorname{Gain}(D,\text{色泽}) &=0.998 -\left( \frac{6}{17}\times1.000 +\frac{6}{17}\times0.918 +\frac{5}{17}\times0.722 \right)\ &=0.109. \end{aligned} $$

对所有属性作同样计算，若“纹理”的信息增益最大，就选“纹理”作为根结点划分属性。

4.5 增益率与 C4.5

4.5.1 信息增益的多取值偏好

若把每个样本的唯一“编号”也作为候选属性，编号会产生 $17$ 个分支，每个分支只有一个样本，信息增益可达 $0.998$。
这种划分在训练集上纯度最高，却无法预测新编号，泛化能力很差。
因而信息增益天然偏好可取值数目较多的属性。

4.5.2 固有值与增益率

属性 $a$ 的固有值为

$$ \operatorname{IV}(a) =-\sum_{v=1}^{V} \frac{|D^v|}{|D|} \log_2\frac{|D^v|}{|D|}. $$

增益率定义为

$$ \operatorname{Gain_ratio}(D,a) =\frac{\operatorname{Gain}(D,a)} {\operatorname{IV}(a)}. $$

属性取值越多，$\operatorname{IV}(a)$ 通常越大，可抑制信息增益对多取值属性的偏好。
增益率本身又可能偏好取值较少的属性。
C4.5 采用启发式选择：先找出信息增益高于平均水平的候选属性，再从中选择增益率最高者。

4.6 基尼指数与 CART

数据集 $D$ 的基尼值为

$$ \operatorname{Gini}(D) =\sum_{k=1}^{|\mathcal Y|} \sum_{k'\neq k}p_kp_{k'} =1-\sum_{k=1}^{|\mathcal Y|}p_k^2. $$

直观上，它表示按照 $D$ 的经验类别分布独立、有放回地抽取两次时，两次类别标记不一致的概率；若从有限样本无放回抽取，概率会有修正。
$\operatorname{Gini}(D)$ 越小，数据集纯度越高。
二分类中，若两类概率为 $p$ 和 $1-p$，则

$$ \operatorname{Gini}(D) =1-p^2-(1-p)^2 =2p(1-p). $$

对一个候选二元切分 $s$，设它把 $D$ 分成 $D_1,D_2$，CART 使用的加权基尼指数为

$$ \operatorname{Gini_index}(D,s) =\frac{|D_1|}{|D|}\operatorname{Gini}(D_1) +\frac{|D_2|}{|D|}\operatorname{Gini}(D_2). $$

连续属性的候选 $s$ 通常是阈值；离散属性的候选 $s$ 是把取值集合分成两个子集。CART 比较候选二元切分并选择加权基尼指数最小者，而不是直接建立通用多路分支。

4.7 剪枝

为了尽量正确分类训练样本，结点划分可能不断进行，形成过多分支，把训练集偶然特征当作一般规律。
剪枝是决策树降低过拟合风险的主要手段。
源资料指出，划分准则对树尺寸影响较大，但剪枝方式和程度对泛化性能往往更关键；带噪数据上的影响尤其明显。

4.7.1 预剪枝

在生成树时，每次划分前先估计划分能否提高泛化性能。
若不能提升，就停止划分，把当前结点标记为叶结点。
优点是训练开销小、树较紧凑；缺点是可能过早停止，产生欠拟合。

4.7.2 后剪枝

先生成一棵较完整的决策树。
再自底向上考察非叶结点；若把对应子树替换为叶结点能提高验证性能，就进行替换。
后剪枝通常比预剪枝保留更多分支，训练成本也更高。
单棵决策树通常需要剪枝。源资料补充：部分集成学习方法会保留较深或未剪枝的基学习器，再通过集成降低方差；不能把这一经验机械推广到所有集成算法。
源 PDF 中多处写成“剪纸”，正确术语应为“剪枝”。

4.8 缺失值处理

现实数据常有属性缺失。仅丢弃所有含缺失值的样本会浪费数据，需要解决两个问题：

如何在含缺失值时选择划分属性？
已选定划分属性后，属性值缺失的样本应进入哪个分支？

核心方法是“样本加权、按比例分配”。

4.8.1 选择划分属性

对属性 $a$，令 $\tilde D$ 表示在 $a$ 上没有缺失值的样本集合。若样本权重为 $w_{\boldsymbol{x}}$，定义无缺失样本所占权重比例

$$ \rho

\frac{ \sum_{\boldsymbol{x}\in\tilde D}w_{\boldsymbol{x}} }{ \sum_{\boldsymbol{x}\in D}w_{\boldsymbol{x}} }. $$

先在 $\tilde D$ 上计算普通信息增益，再乘 $\rho$：

$$ \operatorname{Gain}(D,a) =\rho, \operatorname{Gain}(\tilde D,a). $$

源资料的缺失值示例中，“色泽”有 $14$ 个无缺失样本：

$$ \operatorname{Gain}(\tilde D,\text{色泽})=0.306, $$

所以

$$ \operatorname{Gain}(D,\text{色泽}) =\frac{14}{17}\times0.306 =0.252. $$

各属性加权信息增益为：

属性	信息增益
色泽	$0.252$
根蒂	$0.171$
敲声	$0.145$
纹理	$0.424$
脐部	$0.289$
触感	$0.006$

因此仍选择“纹理”。

4.8.2 把缺失样本分给各分支

若 $\tilde D^v$ 是在属性 $a$ 上无缺失且取值为 $a^v$ 的样本，定义该分支的权重比例

$$ \tilde r_v

\frac{ \sum_{\boldsymbol{x}\in\tilde D^v}w_{\boldsymbol{x}} }{ \sum_{\boldsymbol{x}\in\tilde D}w_{\boldsymbol{x}} }. $$

属性值不缺失的样本只进入对应分支，权重保持不变。
属性值缺失的样本同时进入所有分支，在第 $v$ 个分支中的新权重为 $\tilde r_vw_{\boldsymbol{x}}$。
源资料示例中，样本 8、10 在“纹理”上缺失，同时进入“清晰、稍糊、模糊”三个分支，权重分别为

$$ \frac{7}{15},\qquad \frac{5}{15},\qquad \frac{3}{15}. $$

4.9 易错点

结点样本无法继续划分时，通常标记为多数类叶结点，不是随意选择类别。
信息增益是“父结点熵减去子结点熵的加权和”，不能漏掉权重 $|D^v|/|D|$。
信息增益越大越好；基尼指数越小越好。
ID3 使用信息增益，C4.5 使用增益率启发式，CART 常用基尼指数。
增益率不是简单“归一化到 $0$ 到 $1$”，而是信息增益除以属性固有值。
剪枝才是术语；预剪枝在划分前停止，后剪枝先生成完整树再自底向上合并。
缺失属性的样本不是简单复制到所有分支；它进入所有分支时必须按分支概率重新分配权重。
缺失值示例的 $0.109$ 与 $0.252$ 来自不同计算条件：前者是完整的初始信息增益示例，后者是按无缺失比例修正后的缺失值示例，不能混用。

4.10 本节复盘

决策树把属性测试放在内部结点，把预测结果放在叶结点，采用分而治之递归生成。
离散多路划分在样本同类、可用属性耗尽或分支样本为空时停止；连续属性和 CART 的候选切分与属性复用规则需另行处理，不能无条件删除已用属性。
信息熵越小纯度越高；ID3 选择信息增益最大的属性。
信息增益偏好多取值属性，C4.5 先筛选高信息增益属性，再选增益率最高者。
CART 常选择加权基尼指数最小的二元切分；连续属性比较阈值，离散属性比较取值集合的二分。
剪枝通过限制或删除分支缓解过拟合，分为预剪枝和后剪枝。
属性缺失时，先用无缺失样本估计划分质量，再按各分支权重把缺失样本同时分配到多个分支。

Lecture 4：决策树