决策树缺失值处理

实际决策树任务中，往往会遇到含有缺失值的数据，不能删除这些样本或属性，那么决策树应该怎么应对这样的数据集呢？

对于缺失值的处理，需要解决两个问题

1. 训练阶段：如何在属性值缺失的情况下进行划分属性选择
2. 验证阶段及测试阶段：给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分

首先我们做如下定义来针对含缺失值的数据集

给定训练集 和属性 ， 表示 中在属性 上没有缺失值的样本子集。属性 可取值 ，令 表示 在属性 取值为 的样本子集，令 表示 中属于 类（）的样本子集。我们为每一个样本 赋予一个权重 ( 初始化为 1），并定义

表示 的样本所占的比例

表示 的样本中第 类所占的比例

表示 的样本中取值为 的样本所占的比例。

对于问题 （1），我们可基于上述定义将信息增益推广为

其中

对于问题 （2），给定划分属性划分样本。

1. 若样本 在划分属性 上的取值已知，则将 划入与其取值对应的子节点，且样本权值在子节点中保持 不变
2. 若样本 在属性 上取值缺失 ，则将 同时划入所有子节点，且样本权值在属性值 对应的字节点中调整为 ，相当于将一个样本以不同的概率划入到不同的子节点中。