4 处理连续值和缺失值

处理连续值

有的属性取值不是离散的，比如西瓜的密度。此时想要做划分可能需要选一个 magic number 作为划分标度。

• C4.5 算法采用二分法对连续数值进行划分，是一种简单粗暴的划分方法

下面说的是一种一般的方法：

对于 $D$ 的某个属性 $a$，其取值按从小到大的顺序排列为 $a^1,a^2,...,a^V$，可以相应地得到一串平均数列 $\displaystyle \frac{a^1+a^2}{2},\frac{a^2+a^3}{2},...,\frac{a^{V-1}+a^V}{2}$，我们要选的划分点 $t$ 就从这之中产生。

相应地，$D$ 被这种划分划分为 $D_t^-\dot\cup D_t^+$（$D_t^-$ 表示 $D$ 中在 $a$ 属性取值上不大于 $t$ 的那些样本，$D_t^+$ 同理）。

遍历这些划分点，计算其信息增益： $$ \begin{aligned} Gain(D,a)&=\max_{t\in T_a}Gain(D,a,t)\newline &=\max_{t\in T_a}\left[Ent(D)-\sum_{\lambda\in{-,+}}\frac{|D^\lambda_t|}{|D|}Ent(D^\lambda_t)\right] \end{aligned} $$ 选择的划分点就是 $t_*=\arg\max_{t\in T_a} Gain(D,a,t)$。

处理缺失值

即样本的某些属性缺失。

给定数据集 $D$ 和属性 $a$，先看看以下定义。

记号	含义
$\tilde{D}$	$D$ 的在 $a$ 上无缺失的数据子集
$V$	属性 $a$ 的可取值数，分别记为 $a^1,...,a^V$
$\tilde{D}^v$	$\tilde{D}$ 中 $a$ 属性取值为 $a^v$ 的数据子集
$\mathcal{Y}$	$\tilde D$ 的类别标记组成的集合，$
$\tilde D_k$	$\tilde D$ 中属于第 $k$ 类的数据子集

也就是说从两个方面来看，有 $\tilde D=\cup_v \tilde{D}^v=\cup_k\tilde D_k$。

如何在属性值缺失的情况下进行划分属性的选择？

假定我们为每个样本 $x$ 赋予一个权重 $w_x$（在开始时全为 1），并对属性 $a$ 作如下定义：

定义	含义
$\displaystyle\rho=\frac{\sum_{x\in \tilde{D}}w_x}{\sum_{x\in {D}}w_x}$	无缺失值样本占所有样本的比例
$\displaystyle\tilde{p}_k=\frac{\sum_{x\in \tilde{D}_k}w_x}{\sum_{x\in \tilde{D}}w_x}$	无缺失值样本中第 $k$ 类所占的比例
$\displaystyle\tilde{r}_v=\frac{\sum_{x\in \tilde{D}^v}w_x}{\sum_{x\in \tilde{D}}w_x}$	无缺失值样本中在 $a$ 上取值为 $a^v$ 的所占比例

用上述定义去计算信息增益，相关式子应推广如下： $$ Ent(\tilde{D})=-\sum_{k=1}^{|\mathcal{Y}|}\tilde{p}_k\log_2\tilde{p}_k $$

$$\begin{aligned} Gain(D,a)&=\rho\times Gain(\tilde{D},a)\newline &=\rho\times\left[Ent(\tilde{D})-\sum_{k=1}^V\tilde{r}_vEnt(\tilde{D}^v)\right] \end{aligned}$$

按原来的思想使用信息增益即可。

给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

在划分时，有两种情况。

• 如果某个样本 $x$ 在 $a$ 上不缺失，则将 $x$ 划分进对应子节点，并保持 $w_x$ 在子节点中不变
• 如果某个样本 $x$ 在 $a$ 上缺失值，则同时将 $x$ 划分进所有子节点，并在 $a^v$ 对应的子节点中的权重调整为 $\tilde{r}^vw_x$

直观的看，这种方法就是让同一个样本以不同的概率划入不同的子节点中。

本文阅读量