【机器学习基础】第十四课:决策树中的连续与缺失值

连续值处理,缺失值处理

Posted by x-jeff on June 11, 2020

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.连续值处理

到目前为止我们仅讨论了基于离散属性来生成决策树。本节我们来讨论在决策树学习中如何使用连续属性。

可将连续属性离散化,最简单的策略是二分法(C4.5决策树算法中采用的机制)。

给定样本集D和连续属性a,假定a在D上出现了n个不同的取值,将这些值从小到大进行排序,记为$\{a^1,a^2,…,a^n \}$。基于划分点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个元素的候选划分点集合:

\[T_a=\{ \frac{a^i+a^{i+1}}{2} | 1 \leqslant i \leqslant n-1 \} \tag{1.1}\]

即把区间$[a^i,a^{i+1})$的中位点$\frac{a^i+a^{i+1}}{2}$作为候选划分点。

信息增益的公式加以改造:

\[\begin{align} Gain(D,a) &=\max \limits_{t\in T_a} Gain(D,a,t) \\&= \max \limits_{t\in T_a} Ent(D) - \sum \limits_{\lambda \in \{-,+\}} \frac{\mid D_t^{\lambda} \mid}{ \mid D \mid } Ent(D_t^{\lambda}) \end{align} \tag{1.2}\]

举个例子,假设我们有如下西瓜数据集:

以连续属性“密度”为例,将17个属性值从小到大排列:0.243、0.245、0.343、0.360、0.403、0.437、0.481、0.556、0.593、0.608、0.634、0.639、0.657、0.666、0.697、0.719、0.774。根据式1.1,得到该属性的16个候选划分点:0.244、0.294、0.351、0.381、0.420、0.459、0.518、0.574、0.600、0.621、0.636、0.648、0.661、0.681、0.708、0.746。计算每个候选分割点的信息增益:

t $D_t^-$ $D_t^+$ Gain
0.244 10 1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17 0.056
0.294 10,11 1,2,3,4,5,6,7,8,9,12,13,14,15,16,17 0.118
0.351 10,11,12 1,2,3,4,5,6,7,8,9,13,14,15,16,17 0.186
0.381 10,11,12,15 1,2,3,4,5,6,7,8,9,13,14,16,17 0.262
0.420 6,10,11,12,15 1,2,3,4,5,7,8,9,13,14,16,17 0.093
0.459 6,8,10,11,12,15 1,2,3,4,5,7,9,13,14,16,17 0.030
0.518 6,7,8,10,11,12,15 1,2,3,4,5,9,13,14,16,17 0.004
0.574 5,6,7,8,10,11,12,15 1,2,3,4,9,13,14,16,17 0.002
0.600 5,6,7,8,10,11,12,15,16 1,2,3,4,9,13,14,17 0.002
0.621 4,5,6,7,8,10,11,12,15,16 1,2,3,9,13,14,17 0.004
0.636 3,4,5,6,7,8,10,11,12,15,16 1,2,9,13,14,17 0.030
0.648 3,4,5,6,7,8,10,11,12,13,15,16 1,2,9,14,17 0.006
0.661 3,4,5,6,7,8,10,11,12,13,14,15,16 1,2,9,17 0.001
0.681 3,4,5,6,7,8,9,10,11,12,13,14,15,16 1,2,17 0.024
0.708 1,3,4,5,6,7,8,9,10,11,12,13,14,15,16 2,17 0.000
0.746 1,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17 2 0.067

根据式1.2取信息增益的最大值0.262,对应于划分点0.381。同理,可得连续属性“含糖率”的信息增益为0.349,对应于划分点0.126。

⚠️与离散属性不同,若当前结点划分属性为连续属性,该属性还可作为其后代结点的划分属性。例如在父结点上使用了“密度$\leqslant$0.381”,不会禁止在子结点上使用“密度$\leqslant$0.294”。

2.缺失值处理

假设我们有含缺失值的西瓜数据集见下:

如果直接舍弃含有缺失值的数据,那么仅有4、7、14、16四个样本可用,显然是对数据信息极大的浪费。

我们需解决两个问题:

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

👉解决问题1:

给定训练集D和属性a,令$\tilde{D}$表示D中在属性a上没有缺失值的样本子集。我们可仅根据$\tilde{D}$来判断属性a的优劣。假定属性a有V个可取值$\{ a^1,a^2,…,a^V \}$,令$\tilde{D}^v$表示$\tilde{D}$中在属性a上取值为$a^v$的样本子集,$\tilde{D}_k$表示$\tilde{D}$中属于第k类$(k=1,2,…,\mid y \mid)$的样本子集,则显然有$\tilde{D}=\cup^{\mid y \mid}_{k=1} \tilde{D}_k$,$\tilde{D}=\cup^V_{v=1} \tilde{D}^v$。假定我们为每个样本x赋予一个权重$w_x$,并定义:

\[\rho=\frac{\sum_{x\in \tilde{D}} w_x}{\sum_{x\in D} w_x}\] \[\tilde{p}_k=\frac{\sum_{x\in \tilde{D}_k} w_x}{\sum_{x\in \tilde{D}} w_x} (1\leqslant k \leqslant \mid y \mid)\] \[\tilde{r}_v=\frac{\sum_{x\in \tilde{D}^v} w_x}{\sum_{x\in \tilde{D}} w_x} (1\leqslant v \leqslant V)\]

在决策树学习开始阶段,根结点中各样本的权重初始化为1。

直观地看,对属性a,$\rho$表示无缺失值样本所占的比例,$\tilde{p}_k$表示无缺失值样本中第k类所占的比例,$\tilde{r}_v$则表示无缺失值样本中在属性a上取值$a^v$的样本所占的比例。显然,$\sum^{\mid y \mid}_{k=1} \tilde{p}_k=1,\sum^V_{v=1} \tilde{r}_v=1$。

根据上述定义,将信息增益推广为:

\[\begin{align} Gain(D,a) &= \rho \times Gain(\tilde{D},a) \\&= \rho \times ( Ent(\tilde{D}) - \sum^V_{v=1} \tilde{r}_v Ent(\tilde{D}^v) ) \end{align}\]

其中,

\[Ent(\tilde{D})=-\sum^{\mid y \mid}_{k=1} \tilde{p}_k \log_2 \tilde{p}_k\]

👉解决问题2:

若样本x在划分属性a上的取值已知,则将x划入与其取值对应的子结点,且样本权值在子结点中保持为$w_x$。若样本x在划分属性a上的取值未知,则将x同时划入所有子结点,且样本权值在与属性值$a^v$对应的子结点中调整为$\tilde{r}_v \cdot w_x$。

C4.5算法使用了上述解决方案。

以上述含缺失值的西瓜数据集为例。该数据集一共包含17个样例,各样例的权值均为1。以属性“色泽”为例,有14个样例无缺失值,$\tilde{D}$的信息熵为:

\[\begin{align} Ent(\tilde{D}) &= -\sum^2_{k=1} \tilde{p}_k \log_2 \tilde{p}_k \\&= -(\frac{6}{14}\log_2 \frac{6}{14} + \frac{8}{14}\log_2 \frac{8}{14} ) =0.985 \end{align}\]

令$\tilde{D}^1,\tilde{D}^2,\tilde{D}^3$分别表示在属性“色泽”上取值为“青绿”“乌黑”以及“浅白”的样本子集,有:

\[Ent(\tilde{D}^1)=-(\frac{2}{4} \log_2 \frac{2}{4} + \frac{2}{4} \log_2 \frac{2}{4})=1.000\] \[Ent(\tilde{D}^2)=-(\frac{4}{6} \log_2 \frac{4}{6} + \frac{2}{6} \log_2 \frac{2}{6})=0.918\] \[Ent(\tilde{D}^3)=-(\frac{0}{4} \log_2 \frac{0}{4} + \frac{4}{4} \log_2 \frac{4}{4})=0.000\]

因此,样本子集$\tilde{D}$上属性“色泽”的信息增益为:

\[Gain(\tilde{D},色泽)=0.985-(\frac{4}{14} \times 1.000 + \frac{6}{14} \times 0.918 + \frac{4}{14}\times 0.000)=0.306\]

于是,样本集D上属性“色泽”的信息增益为:

\[Gain(D,色泽)=\rho \times Gain(\tilde{D},色泽) = \frac{14}{17} \times 0.306 = 0.252\]

同理可计算出所有属性在D上的信息增益:

  • $Gain(D,色泽)=0.252$
  • $Gain(D,根蒂)=0.171$
  • $Gain(D,敲声)=0.145$
  • $Gain(D,纹理)=0.424$
  • $Gain(D,脐部)=0.289$
  • $Gain(D,触感)=0.006$

因此,选择属性“纹理”对根结点进行划分。样例1,2,3,4,5,6,15进入“纹理=清晰”分支,样例7,9,13,14,17进入“纹理=稍糊”分支,样例11,12,16进入“纹理=模糊”分支,且样本在各子结点中的权重依旧保持为1。

⚠️样例8在属性“纹理”上出现了缺失值,因此它将同时进入三个分支,但权重在三个子结点中分别调整为$\frac{7}{15},\frac{5}{15},\frac{3}{15}$。

最终生成的决策树见下: