学习笔记十五：连续与缺失值 - 详解

1. 基本概念

1.1 连续值处理挑战

问题背景：

基于离散属性来进行的。然而，现实学习任务中常会遇到连续属性，因此有必要讨论如何在决策树学习中应用连续属性。就是我们之前讨论的决策树生成都

核心挑战：

连续属性的可取值数目不再有限，因此不能直接根据连续属性的可取值来对结点进行划分。

解决方案：

需要使用连续属性离散化技巧。最简单的策略是二分法（bi-partition），这正是C4.5决策树学习算法所采用的机制。

1.2 缺失值处理问题

问题背景：

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。例如在医疗诊断中，某些检查项目可能因为测试成本、隐私保护等因素而缺失。

核心挑战：

• 当属性数目较多时，往往会有大量样本出现缺失值
• 对数据信息极大的浪费就是要是简单地放弃不完整样本，仅使用无缺失值的样本进行学习，显然

需要解决的问题：

1. 如何在属性值缺失的情况下进行划分属性选择？
2. 给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

2. 连续值处理方法

2.1 二分法

基本思路：

给定样本集 D 和连续属性 a，假定 a 在 D 上出现了 n 个不同的取值，将这些值从小到大进行排序，记为 {a¹, a², ..., aⁿ}。

划分方式：

基于划分点 t 可将 D 分为子集 $D_t^{-}$ 和 $D_t^{+}$，其中：

• $D_t^{-}$ 包含那些在属性 a 上取值不大于 t 的样本
• $D_t^{+}$包含那些在属性 a 上取值大于 t 的样本

候选划分点：

对相邻的属性取值$a^i$ 和 $a^{i+1}$ 来说，t 在区间 [$a^i$, $a^{i+1}$) 中取任意值所产生的划分结果相同。因此，对连续属性 a，可考察 n-1 个候选划分点。

候选划分点集合：

通常将区间 [$a^i$, $a^{i+1}$)的中位点 $\frac{a^i+a^{i+1}}{2}$作为候选划分点。这样，候选划分点集合为：

$$T_a=\left\{\frac{a^i+a^{i+1}}{2}\mid 1\le i\le n-1\right\}$$

信息增益计算：

可像离散属性值一样来考察这些划分点，选择最优的划分点进行样本集合的划分。信息增益的计算公式需要稍作修改：

$$Gain(D,a)=\underset{t\in T_a}{\max }Gain(D,a,t)$$

其中 Gain(D, a, t) 是样本集 D 基于划分点 t 二分后的信息增益。选择使 Gain(D, a, t) 最大化的划分点。

2.2 连续属性的特点

与离散属性的区别：

与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

3. 缺失值处理方法

3.1 基本思路

权重表示：

为每个样本 x 赋予一个权重 $w_x$，并初始化为1。

符号定义：

• D：训练集
• a：属性
• Ď：表示在属性 a 上没有缺失值的样本子集
• Ďᵛ：表示在属性 a 上取值为 aᵛ 的样本子集
• Dₖ：表示属于第 k 类的样本子集

比例计算：

• ρ：无缺失值样本所占的比例
• p̃ₖ：无缺失值样本中第 k 类所占的比例
• r̃ᵥ：无缺失值样本中在属性 a 上取值 aᵛ 的样本所占的比例

3.2 疑问（1）的解决：划分属性选择

方法：

对于问题（1），可根据 Ď 来判断属性 a 的优劣。信息增益的计算可推广为：

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

其中 $Gain(\tilde{D},a)$ 是基于无缺失值样本子集 Ď 计算的信息增益。

直观理解：

• ρ 表示无缺失值样本所占的比例
• p̃ₖ 表示无缺失值样本中第 k 类所占的比例
• r̃ᵥ 表示无缺失值样本中在属性 a 上取值 aᵛ 的样本所占的比例

3.3 问题（2）的解决：样本划分

已知属性值的情况：

若样本 x 在划分属性 a 上的取值已知，则将 x 划入与其取值对应的子结点，且样本权值在子结点中保持为 wₓ。

缺失属性值的情况：

若样本 x 在划分属性 a 上的取值未知，则将 x 同时划入所有子结点，且样本权值在与属性值 aᵛ 对应的子结点中调整为 r̃ᵥ × wₓ。

直观理解：

这就是让同一个样本以不同的概率划入到不同的子结点中去。样本权重会根据无缺失值样本中各个属性值的分布比例进行调整。

C4.5算法：

C4.5算法利用了上述解决方案来处理缺失值。

3.4 处理示例

初始状态：

在学习开始时，根结点包含样本集 D 中全部样本，各样例的权值均为1。

属性选择：

以属性"色泽"为例，该属性上无缺失值的样例子集 Ď 包含14个样例。根据 Ď 计算信息熵和信息增益，然后乘以 ρ 得到该属性在整个数据集上的信息增益。

样本划分：

• 对于属性值已知的样本，直接划入对应的子结点，权重保持为1
• 对于属性值缺失的样本，同时划入所有子结点，权重在各子结点中按比例调整

递归过程：

上述结点划分过程递归执行，最终生成完整的决策树。

4. 总结

连续值处理：

现实学习任务中常会遇到连续属性。二分法是处理连续属性的基本策略，利用选择候选划分点，将连续属性离散化。C4.5算法采用二分法，选择使信息增益最大化的划分点。与离散属性不同，连续属性可以作为其后代结点的划分属性。

缺失值处理：

现实任务中常会遇到不完整样本。C4.5算法通过样本权重机制来处理缺失值：

• 对于划分属性选择，基于无缺失值样本子集计算信息增益，然后乘以无缺失值样本的比例
• 对于样本划分，属性值已知的样本直接划入对应子结点，属性值缺失的样本同时划入所有子结点，权重按比例调整

决策树学习中的重要技术。就是此种方法能够充分利用含有缺失值的样本，避免信息浪费，