周志华《机器学习—西瓜书》四

四、决策树

4-1、决策树基本流程

决策树基于“树”结构进行决策

• 每个“内部结点”对应于某个属性上的“测试”(test)
• 每个分支对应于该测试的一种可能结果（即该属性的某个取值）
• 每个“叶结点”对应于一个“预测结果”

学习过程

通过对训练样本的分析来确定“划分属性”（即内部结点所对应的属性）

预测过程

将测试示例从根结点开始，沿着划分属性所构成的“判定测试序列”下行，直到叶结点

策略： “ 分而治之 ” (divide-and-conquer)

自根至叶的递归过程， 在每个中间结点寻找一个“划分”(split or test)属性

三种停止条件：

1. 当前结点包含的样本全属于同一类别，无需划分；
2. 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
3. 当前结点包含的样本集合为空，不能划分

基本算法

说明：

• 步骤 2-4 为递归返回情形 (1) ：样本全属于同一类别，直接标记为叶结点。
• 步骤 5-7 为递归返回情形 (2) ：无属性可分或样本在剩余属性上取值相同，标记为叶结点（类别取样本数最多的类）。
• 步骤 11-14 为递归返回情形 (3) ：若某分支无样本，标记为叶结点（类别取父结点样本最多的类）。
• 步骤 8 是决策树算法的核心：选择最优划分属性，决定了树的生长质量。

‍

4-2、信息增益(Information Gain)

• 信息熵 (entropy) 是度量样本集合“纯度”最常用的一种指标。

• 假定当前样本集合$(D)$ 中第$(k)$ 类样本所占的比例为$(p_k)$，则 ( D ) 的信息熵定义为：

  $$\text{Ent}(D)=-\sum _{k=1}^{|\mathcal{Y}|}{p}_k{\log }_2{p}_k$$

  • 计算信息熵时必须约定：若 $(p=0)$，则$(p{\log }_{2}p=0)$。
  • $(\text{Ent}(D))$的最小值为 $0$，最大值为 ${\log }_2|\mathcal{Y}|$。
  • $(\text{Ent}(D))$ 的值越小，则 $D$ 的纯度越高。

• 信息增益直接以信息熵为基础，计算当前划分对信息熵所造成的变化。

• 离散属性 a 的取值： {a1,a2,…,aV}\{a^1, a^2, \dots, a^V\}{a1,a2,…,aV}

• $D^v$ ：D 中在 a 上取值 $=a^v$ 的样本集合

• 以属性 a 对数据集 D 进行划分所获得的信息增益为：

  $$\text{Gain}(D,a)=\underset{\text{划分前的信息熵}}{\underbrace{\text{Ent}(D)}}-\sum _{v=1}^V\underset{\text{第 }v\text{ 个分支的权重，样本越多越重要}}{\underbrace{\frac{|D^v|}{|D|}}}\underset{\text{划分后的信息熵}}{\underbrace{\text{Ent}(D^v)}}$$

• 该方法在 " ID3算法 "中使用

举例：

步骤1：计算根结点的信息熵

已知数据集 ( D ) 包含17个样本，正例（好瓜=是）有8个，反例（好瓜=否）有9个。
根据信息熵公式：

$$\text{Ent}(D)=-\sum _{k=1}^2{p}_k{\log }_2{p}_k$$

其中$(p_1=\frac{8}{17})，(p_2=\frac{9}{17})$，代入得：

$$\text{Ent}(D)=-\left(\frac{8}{17}{\log }_2\frac{8}{17}+\frac{9}{17}{\log }_2\frac{9}{17}\right)\approx 0.998<br/>$$

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

“色泽”有3个取值：青绿、乌黑、浅白，对应子集 $D^1,D^2,D^3$

• 子集 ( D^1 )（色泽=青绿） ：共6个样本，正例3个，反例3个。
  信息熵：

  $$\text{Ent}(D^1)=-\left(\frac{3}{6}{\log }_2\frac{3}{6}+\frac{3}{6}{\log }_2\frac{3}{6}\right)=1.000<br/>$$

• 子集 ( D^2 )（色泽=乌黑） ：共6个样本，正例4个，反例2个。
  信息熵：

  $$\text{Ent}(D^2)=-\left(\frac{4}{6}{\log }_2\frac{4}{6}+\frac{2}{6}{\log }_2\frac{2}{6}\right)\approx 0.918<br/>$$

• 子集 ( D^3 )（色泽=浅白） ：共5个样本，正例1个，反例4个。
  信息熵：

  $$\text{Ent}(D^3)=-\left(\frac{1}{5}{\log }_2\frac{1}{5}+\frac{4}{5}{\log }_2\frac{4}{5}\right)\approx 0.722<br/>$$

根据信息增益公式：

$$\text{Gain}(D,\text{色泽})=\text{Ent}(D)-\sum _{v=1}3\frac{|Dv|}{|D|}\text{Ent}(Dv)]代入(|D1|=6)，(|D^2|=6)，(|D^3|=5)，(|D|=17)$$

得：

$$\text{Gain}(D,\text{色泽})=0.998-\left(\frac{6}{17}\times 1.000+\frac{6}{17}\times 0.918+\frac{5}{17}\times 0.722\right)\approx 0.109$$

步骤3：计算其他属性的信息增益（以“纹理”为例，最终选择信息增益最大的属性）

类似地，计算“根蒂”“敲声”“纹理”“脐部”“触感”的信息增益：

• $(\text{Gain}(D,\text{根蒂})\approx 0.143)$
• $(\text{Gain}(D,\text{敲声})\approx 0.141)$
• $(\text{Gain}(D,\text{纹理})\approx 0.381)$（最大，选为划分属性）
• $(\text{Gain}(D,\text{脐部})\approx 0.289)$
• $(\text{Gain}(D,\text{触感})\approx 0.006)$

综上，通过计算各属性的信息增益，选择“纹理”作为最优划分属性，后续可继续对其子集递归划分。

‍

4-3、其他属性划分准则

增益率 (Gain Ratio)

信息增益对可取值数目较多的属性存在偏好， 有明显的弱点（例如“编号”这类属性会因取值过多而获得高信息增益，但无实际分类意义）。

增益率是为解决这一问题提出的指标，用于C4.5算法中选择最优划分属性。

公式与解释

• 增益率公式：

  $$\text{Gain\_ratio}(D,a)=\frac{\text{Gain}(D,a)}{\text{IV}(a)}$$

• 其中，$\text{IV}(a)$ 是属性 $a$ 的固有值 (Intrinsic Value) ，计算公式为：

  $$\text{IV}(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}$$

  固有值的特点：属性 $a$ 的可能取值数目越多（即 $V$ 越大），$\text{IV}(a)$ 通常越大，从而抵消多取值属性在信息增益上的“优势”。

选择策略

采用**启发式方法**：先从候选划分属性中找出信息增益高于平均水平的，再从中选取增益率最高的属性。

‍

基尼指数 (Gini Index)

• 基尼指数用于度量数据集的“纯度”，公式为：

  $$\begin{array}{rl}\text{Gini}(D)& =\sum _{k=1}^{|\mathcal{Y}|}\sum _{k^{\prime }\ne k}{p}_k{p}_{k^{\prime }}\\ & =1-\sum _{k=1}^{|\mathcal{Y}|}{p}_k^2\end{array}$$

  其物理意义是：从数据集 ( D ) 中随机抽取两个样例，类别标记不一致的概率。

• 性质：$\text{Gini}(D)$ 越小，数据集 $D$ 的纯度越高。

属性的基尼指数

对于属性 ( a )，其基尼指数计算公式为：

$$\text{Gini\_index}(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}\text{Gini}(D^v)$$

中 $D^v$ 是数据集 D 中属性 a 取值为 $a^v$ 的样本子集。

应用与选择策略

在候选属性集合中，选取使划分后基尼指数​最小****的属性，该方法用于CART算法中。

‍

4-4、划分和剪枝

研究表明：划分选择的各种准则虽然对决策树的尺寸有较大影响，但对泛化性能的影响很有限

例如信息增益与基尼指数产生的结果，仅在约2%的情况下不同

剪枝方法和程度对决策树泛化性能的影响更为显著

在数据带噪时甚至可能将泛化性能提升25%

Why? 剪枝 (pruning) 是决策树对付“ 过拟合 ” 的主要手段！

剪枝：

为了尽可能正确分类训练样本，有可能造成分支过多 ------> 过拟合

可通过主动去掉一些分支来降低过拟合的风险

基本策略：

• 预剪枝(pre-pruning):提前终止某些分支的生长
• 后剪枝（post-pruning):生成一棵完全树，再“回头”剪枝

剪枝过程中需评估剪枝前后决策树的优劣 -------> 第二章 模型性能评估

4-5、缺失值的处理

缺失值：

• 现实应用中经常遇到属性值 “缺失”(missing) 的现象。如果仅使用无缺失的样例 ------------> 会造成对数据的极大浪费。

• 使用带缺失值的样例时，需解决两个问题:

  • Q1：如何进行划分属性选择？
  • Q2：给定划分属性，若样本在该属性上的值缺失，如何进行划分？

  基本思路：样本赋权，权重划分

• 举例：

  

  仅通过无缺失值的样例来判断划分属性的优劣

  这例子，展示了含缺失值时决策树划分属性选择（信息增益计算） 和缺失值样本划分（权重划分） 的过程，具体计算内容如下：

  一、划分属性选择：信息增益计算

  以“色泽”属性为例，步骤如下：

  1. 计算无缺失值子集​**$\tilde{D}$​的信息熵**
     无缺失值的样例数为14，其中“好瓜=是”有6个，“好瓜=否”有8个。
     信息熵公式：$\text{Ent}(\tilde{D})=-{\sum }_{k=1}^2{\tilde{p}}_k{\log }_2{\tilde{p}}_k$
     代入计算：
     $\text{Ent}(\tilde{D})=-\left(\frac{6}{14}{\log }_2\frac{6}{14}+\frac{8}{14}{\log }_2\frac{8}{14}\right)\approx 0.985$

  2. 计算各取值分支的信息熵
     令${\tilde{D}}^1$（青绿）、${\tilde{D}}^2$（乌黑）、${\tilde{D}}^3$（浅白）为“色泽”取值的子集：

     • ${\tilde{D}}^1$（4个样例，2是2否）：$\text{Ent}({\tilde{D}}^1)=-\left(\frac{2}{4}{\log }_2\frac{2}{4}+\frac{2}{4}{\log }_2\frac{2}{4}\right)=1.000$
     • ${\tilde{D}}^2$（6个样例，4是2否）：$\text{Ent}({\tilde{D}}^2)=-\left(\frac{4}{6}{\log }_2\frac{4}{6}+\frac{2}{6}{\log }_2\frac{2}{6}\right)\approx 0.918$
     • ${\tilde{D}}^3$（4个样例，0是4否）：$\text{Ent}({\tilde{D}}^3)=-\left(\frac{0}{4}{\log }_2\frac{0}{4}+\frac{4}{4}{\log }_2\frac{4}{4}\right)=0.000$

  3. 计算​**$\tilde{D}$​上“色泽”的信息增益**
     信息增益公式：$\text{Gain}(\tilde{D},\text{色泽})=\text{Ent}(\tilde{D})-{\sum }_{v=1}^3{\tilde{r}}_v\text{Ent}({\tilde{D}}^v)$
     其中${\tilde{r}}_v$是无缺失值样例中属性取$v$的占比（${\tilde{r}}_1=\frac{4}{14},{\tilde{r}}_2=\frac{6}{14},{\tilde{r}}_3=\frac{4}{14}$）。
     代入计算：
     $\text{Gain}(\tilde{D},\text{色泽})=0.985-\left(\frac{4}{14}\times 1.000+\frac{6}{14}\times 0.918+\frac{4}{14}\times 0.000\right)\approx 0.306$

  4. 计算整个样本集​**$D$​上“色泽”的信息增益**
     公式：$\text{Gain}(D,\text{色泽})=\rho \times \text{Gain}(\tilde{D},\text{色泽})$
     其中$\rho$是无缺失值样例占比（$\rho =\frac{14}{17}$）。
     代入计算：
     $\text{Gain}(D,\text{色泽})=\frac{14}{17}\times 0.306\approx 0.252$

  二、所有属性的信息增益对比

  类似计算其他属性后，得到：

  • $\text{Gain}(D,\text{色泽})=0.252$
  • $\text{Gain}(D,\text{根蒂})=0.171$
  • $\text{Gain}(D,\text{敲声})=0.145$
  • $\text{Gain}(D,\text{纹理})=0.424$（最大，因此选“纹理”作为划分属性）
  • $\text{Gain}(D,\text{脐部})=0.289$
  • $\text{Gain}(D,\text{触感})=0.006$

  三、缺失值样本的划分：权重划分

  以“纹理”属性（信息增益最大）为例，对缺失值样本（如样本8、10）的处理：

  • 样本8、10在“纹理”上缺失，需按权重划分到所有分支。
  • 权重分配：根据“纹理=清晰”“稍糊”“模糊”的样本占比，分别为$\frac{7}{15}$、$\frac{5}{15}$、$\frac{3}{15}$，即样本8、10同时进入三个分支，权重按此比例分配。

‍