当样本中有连续属性时，连续属性的可取值是无限的，但$D$是有限的，如何处理？
当样本中的属性值缺失时，总不能空着吧，如何处理？

连续值的处理

连续属性$a$的可取值是无限的，但$D$是有限的，即$a$在$D$中出现的值是有限的，将这有限个$a$值从小到大排序设为 { a 1 , a 2 , ⋯   , a n } \{a^1,a^2,\cdots,a^n\} {a1,a2,⋯,an}（这里的上标不是指方幂，而是表示序号，通常把下标留给样本编号，故这里用上标），显然，对每一个$a^i$，可得到$D$的一个划分：（$D_{a^i}^{-}:由D中(a⩽a^i)$）与（$D_{a^i}^{+}:由D中(a>a^i)$），这里$D$的上标“+”与“-”是指连续属性值“大于”与“小于”分界点，而不是指样本的“正例”与“反例”。

又$i=n$时，$D_{a^n}^{+}=\varnothing$，即此时$D$无划分，故当有划分时，$i=1,2,\cdots ,n-1$。

当然，可以取更一般的$t^i\in [a^i,a^{i+1})$，在$t^i$处截断形成划分$D_{t^i}^{-}$和$D_{t^i}^{+}$，较常用中点：$$t^i=\frac{a^i+a^{i+1}}{2},i=1,2,\cdots ,(n-1)$$

这时，候选划分点集合为：
T a = { t 1 , t 2 , ⋯   , t n − 1 } T_a=\{t^1,t^2,\cdots,t^{n-1}\} Ta​={t1,t2,⋯,tn−1}

这样，对一个属性$a$（连续的）派生出多个属性（离散的），形成属性集$T_a$，由此定义
$$\begin{array}{rl}\mathrm{Gain}(D,a)& ={\max }_{t\in T_a}\mathrm{Gain}(D,a,t)\\ & ={\max }_{t\in T_a}\mathrm{Ent}(D)-\frac{|D_t^{+}|}{|D|}\mathrm{Ent}(D_t^{+})-\frac{|D_t^{-}|}{|D|}\mathrm{Ent}(D_t^{-})\end{array}\text{\hspace{1em}(4.15)}$$
式(4.15)即【西瓜书式(4.8)】。 求式(4.15)最大值时，也获得了对应的$t_{\ast }$
$$\begin{array}{r}{t}_{\ast }={\mathrm{argmax}}_{t\in T_a}\mathrm{Gain}(D,a,t)\end{array}\text{\hspace{1em}(4.16)}$$

连续属性$a$处的决策分为两步：

（1）由式(4.15)计算连续属性$a$的$\mathrm{Gain}$，它与其他属性的$\mathrm{Gain}$比较，确定连续属性$a$是否为本次划分属性。

（2）若它是本次划分属性，则再由式(4.16)在$T_a$中取最优的$t_{\ast }$进行划分。

而该处的划分是二叉的（二分），即划分为$D_{t^{\ast }}^{-}$和$D_{t^{\ast }}^{+}$，示例【西瓜书图4.8左下角】。

值得注意的是：该决策产生的划分并没有完全消除连续属性$a$，但消除了一个离散属性$t_{\ast }$，划分的子集中仍有$T_a$中的其他离散属性，需要在后续结点中消除：由于该划分将$T_a$一分为二，故后续节点中的$T_a$逐步变小，而后续节点中的$D$也是指划分后落入该结点的子集，即后续结点必须用划分到该结点处的$T_a$和$D$计算式(4.15)和式(4.16)。

示例【西瓜书图4.10】表明：1）连续属性的划分为二叉的；连续属性需要多次划分才能消除（每次消集$T_a$中的一个）。 2）离散属性是划分时使用多叉一次性地消除，分叉宽度为该属性的可取值个数。

决策树的基本算法【西瓜书图4.2】并没有包含连续属性，可以在其中增加对连续属性处理的分支。

缺失值的处理

当样本中的属性值缺失时，需要进行处理。

1.样本中处理：将缺失值化为非缺失值

（1）删除法：删除有缺失值（或有较多缺失）的样本；

（2）填补法：依某规则（如，概率）填补；

（3）增加值或维：如“性别”的缺失，将其取值由“男、女”增加成“男、女、未知”；或将“性别”的多值属性拆分为多个二值属性，并增加一维“未知”，这样，属性“性别”为变三个属性“男”、“女”、“未知”，每个属性取值范围为“是、否”。

2.算法中处理：即从算法的角度考虑缺失值，【西瓜书图4.2】所示的基本算法中与缺失值相关的有：属性选择与划分。

我们以信息增益准则为例，考虑在有缺失值的情况下算法中的变化。

（1）影响划分属性的选择

设$D$中有缺失属性$a$的样本，不缺失$a$的子集记为$\tilde{D}$，由【西瓜书式(4.1)(4.2)】可求得
$$\begin{array}{r}\mathrm{Gain}(\tilde{D},a)=\mathrm{Ent}(\tilde{D})-\sum _{v=1}^V\frac{|{\tilde{D}}^v|}{|\tilde{D}|}\mathrm{Ent}({\tilde{D}}^v)\end{array}\text{\hspace{1em}(4.17)}$$

假定在划分选择时对无缺失值的属性有偏好，即若$\mathrm{Gain}(\tilde{D},a)=\mathrm{Gain}(D,b)$，而属性$a$有缺失样本，$b$无缺失，则选择$b$作为划分属性。

若缺失属性$a$的样本占比小，则可视为$\mathrm{Gain}(D,a)\approx \mathrm{Gain}(\tilde{D},a)$。 此时，$\mathrm{Gain}(D,a)$应定义为略小于$\mathrm{Gain}(\tilde{D},a)$，使$\mathrm{Gain}(D,a)<\mathrm{Gain}(D,b)$，以便决策时满足上述偏好。

由此易找到一个合理的定义：
$$\begin{array}{r}\mathrm{Gain}(D,a)=\frac{|\tilde{D}|}{|D|}\mathrm{Gain}(\tilde{D},a)\end{array}\text{\hspace{1em}(4.18 )}$$

引入比重记号
$$\begin{array}{rl}\rho & =\frac{|\tilde{D}|}{|D|}\\ r_v& =\frac{|{\tilde{D}}^v|}{|\tilde{D}|}(v=1,2,\cdots ,V)\end{array}$$
则由式(4.17)、式(4.18)有限个时，有
$$\begin{array}{r}\mathrm{Gain}(D,a)=\rho [\mathrm{Ent}(\tilde{D})-\sum _{v=1}^V{r}_v\mathrm{Ent}({\tilde{D}}^v)]\end{array}\text{\hspace{1em}(4.19 )}$$

进一步地，假定$D$中样本各有不同的重要性，则对样本$\mathbf{x}$可赋予权重（反映其重要程度）$w_{\mathbf{x}}$，这时比重变为
$$\begin{array}{rl}\rho & =\frac{{\sum }_{\mathbf{x}\in \tilde{D}}{w}_{\mathbf{x}}}{{\sum }_{\mathbf{x}\in D}{w}_{\mathbf{x}}}\\ r_v& =\frac{{\sum }_{\mathbf{x}\in {\tilde{D}}^v}{w}_{\mathbf{x}}}{{\sum }_{\mathbf{x}\in \tilde{D}}{w}_{\mathbf{x}}}(v=1,2,\cdots ,V)\end{array}\text{\hspace{1em}(4.20 )(4.21 )}$$

同样，在权重下，类别$k$的频率（概率）变为
$$\begin{array}{rl}{\tilde{p}}_k& =\frac{{\sum }_{\mathbf{x}\in {\tilde{D}}_k}{w}_{\mathbf{x}}}{{\sum }_{\mathbf{x}\in \tilde{D}}{w}_{\mathbf{x}}}\\ {\tilde{p}}_k^v& =\frac{{\sum }_{\mathbf{x}\in {\tilde{D}}_k^v}{w}_{\mathbf{x}}}{{\sum }_{\mathbf{x}\in {\tilde{D}}^v}{w}_{\mathbf{x}}}(v=1,2,\cdots ,V)\end{array}\text{\hspace{1em}(4.22 )(4.23 )}$$

由式(4.22)、式(4.23)对应的信息熵变为
$$\begin{array}{rl}\mathrm{Ent}(\tilde{D})& =-\sum _{k=1}^{|\mathcal{Y}|}{\tilde{p}}_k{\log }_2{\tilde{p}}_k\\ \mathrm{Ent}({\tilde{D}}^v)& =-\sum _{k=1}^{|\mathcal{Y}|}{\tilde{p}}_k^v{\log }_2{\tilde{p}}_k^v(v=1,2,\cdots ,V)\end{array}\text{\hspace{1em}(4.24 )(4.25)}$$

由式(4.19)至式(4.25)即可计算带权重的$\mathrm{Gain}(D,a)$。

计算$\mathrm{Gain}(D,a)$后，$a$即可参与划分决策了，若选中有缺失属性$a$作为划分属性时，对于该属性的不缺失的样本，直接划入它所属于的分支的子集中，而对于缺失该属性的每个样本$\mathbf{x}$都分裂（一变多：将整体“一”打碎成多份）到生长出的各分支中，其在各分支所占的比重等于该分支中不缺失该属性$a$的样本的比重，即划分结点该样本$\mathbf{x}$的权重$w_{\mathbf{x}}$被按比重$r_v$分解到各分支中，相应的权重为$r_v\times w_{\mathbf{x}}(v=1,2,\cdots ,V)$。 例如【西瓜书p.88】依“纹理”划分后，编号为{8}的样本缺失该属性，划分到三个子结结点后，它的权重分别变为$\frac{7}{15}$、$\frac{7}{5}$和$\frac{3}{15}$。

上述讨论了有缺失值情况下的信息熵，也可以类似地讨论有缺失值情况下的基尼指数：上篇博客中式(4.12)中定义了基尼指数$Gini\_index(D,a)$最优划分属性准则，参照式(4.19)至式(4.25)对缺失值情况的讨论，可定义有缺失值情况下的基尼指数如下：
$$\begin{gathered} Gini\_index(D,a)=\frac{1}{\rho }Gini\_index(\tilde{D},a) \\ \text{其中，}\rho =\frac{|\tilde{D}|}{|D|}\text{\hspace{1em}(4.26 )} \end{gathered}$$

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：4.2 划分选择与剪枝（此事“信息量好大”，暗指该事件不平常）
下一篇：4.4 连续变量的决策树（以属性为轴的坐标系）