Loading...
墨滴

SuperMP

2021/04/21  阅读:123  主题:默认主题

机器学习 | 决策树:C4.5算法之处理缺失值

那天,我听到了种子破土的声音,又细微又坚定。

机器学习 | 决策树:C4.5算法之处理缺失值

具有缺失属性值的样本集,如何进行决策树学习?这就需要解决两个问题:

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

1 划分属性的选择(问题1)

在不具有缺失值的数据集中,对于某一个属性 a,算法一般使用其所有样本来判断属性的优劣。自然地,对于具有缺失值的数据集,在某一个属性 a 下,算法只能使用在属性 a 下不具有缺失值的样本子集(即下面的 )来判断属性 a 的优劣。那么,缺失样本所占的比例是否影响算法对属性的选择?

对于数据集 ,若其样本无缺失值,则以信息增益最大的属性作为最优划分属性;若其样本有缺失值,其信息增益就是:无缺失值样本的比例 乘以无缺失值样本子集 的信息增益。 PS:这表明,对于某一属性 a,若缺失比例越大,信息增益越不重要。

假设 表示在数据集 的属性 a 上,不具有缺失值的样本构成的样本子集; 表示在 的属性 a 上取值为 时构成的样本子集; 表示在 中属于第 类的样本子集。由此,可以确定以下变量(初始时 ):

其中, 表示无缺失值样本所占的比例; 表示无缺失值样本中第 类所占的比例; 表示无缺失值样本中在属性 a 上取值为 的样本所占的比例。

那么,具有缺失值的样本集的信息增益公式更新为

易知,在递归的过程中,若某一属性值包含的所有样本都不具有缺失值(自然有 ),那么在划分属性的选择时使用的就是标准的信息增益公式了(当然,这里的“所有样本”不应包含由属性值缺失划分过来的样本,因为这会导致这个样本的权重 ,那么 就不是基于“计数频率”来计算比例了)。

2 样本划分(问题2)

第一节解决了在属性值缺失的情况下,如何进行划分属性的选择。那么,在确定了结点的划分属性后,若样本在该属性上的值缺失,如何对样本进行划分(划分到哪个属性值分支下)?

因为我们不知道缺失值原本是什么,所以我们将该样本划分到所有属性分支下;但是,划分到不同分支后,该样本的权重 也不再相同——这个样本被划分到属性值为 的分支后的权重将被更新为

即根据“先验”来决定划分到不同分支的重要程度,这个样本在下一次划分属性的选择时,将以更新后的权重值参与 的再计算。同样地,对于在属性 a 上无缺失值的样本,被划分到子结点时的权重保持不变。

综上,问题 1 解决了划分属性的选择;问题 2 解决了对具有缺失值的样本进行划分的问题。至此,对每个分支递归地进行最优划分属性的选择和样本的划分即可完成(具有缺失值的数据集)决策树的构建

3 如何对具有缺失值的样本分类

在测试阶段,对于具有缺失属性值的测试样本,如何利用构建好的决策树对其进行分类?

如果在决策过程中进入某一个属性结点后,测试样本在该属性上的属性值未知,算法将探索所有可能的分类结果并把所有结果结合起来进行考虑,选择概率最大者作为标签。

对具有缺失值的样本分类示意图
对具有缺失值的样本分类示意图

参考资料:周志华《机器学习》,赵赵赵颖[1]

参考资料

[1]

赵赵赵颖: https://blog.csdn.net/leaf_zizi

SuperMP

2021/04/21  阅读:123  主题:默认主题

作者介绍

SuperMP