手记

【机器学习】决策树——属性连续值与缺失值处理(二)【转】

转载自:https://blog.csdn.net/u012328159/article/details/79396893
**注:本博客为周志华《机器学习》读书笔记,虽然有一些自己的理解,但是其中仍然有大量文字摘自周老师的《机器学习》书。
前面一篇博客分别介绍了如何构造决策树(根据信息增益,信息增益率,基尼指数等)和如何对决策树进行剪枝(预剪枝和后剪枝),但是前面两篇博客主要都是基于离散变量的,然而我们现实的机器学习任务中会遇到连续属性,这篇博客主要介绍决策树如何处理连续值。

【连续值处理】

因为连续属性的可取值数目不再有限,因此不能像前面处理离散属性枚举离散属性取值来对结点进行划分。因此需要连续属性离散化,常用的离散化策略是二分法,这个技术也是C4.5中采用的策略。下面来具体介绍下,如何采用二分法对连续属性离散化:

下面举个具体的例子,来看看到底是怎样划分的。给定数据集如下(数据集来自周志华《机器学习》,我已经把数据集放到github上了,地址为:西瓜数据集3.0):

对于数据集中的属性“密度”,决策树开始学习时,根节点包含的17个训练样本在该属性上取值均不同。我们先把“密度”这些值从小到大排序:

根据上面计算 的公式,可得:

下面开始计算t 取不同值时的信息增益:

对属性“含糖率”,同样的计算,能够计算出:

再由第一篇博客中决策树(一)计算得到的各属性的信息增益值:

比较能够知道纹理的信息增益值最大,因此,“纹理”被选作根节点划分属性,下面只要重复上述过程递归的进行,就能构造出一颗决策树:

有一点需要注意的是 :与离散属性不同,若当前结点划分属性为连续属性,该属性还可作为其后代结点的划分属性。**如下图所示的一颗决策树,“含糖率”这个属性在根节点用了一次,后代结点也用了一次,只是两次划分点取值不同。

【缺失值处理】

现实生活中的数据集中的样本通常在某系属性上是缺失的,如果属性值缺失的样本数量比较少,我们可以直接简单粗暴的把不完备的样本删除掉,但是如果有大量的样本都有属性值的缺失,那么就不能简单地删除,因为这样删除了大量的样本,对于机器学习模型而言损失了大量有用的信息,训练出来的模型性能会受到影响。这篇博客就来介绍在决策树中是如何处理属性值有缺失的样本的,本篇博客使用的数据集如下(数据集来自周志华《机器学习》):

在决策树中处理含有缺失值的样本的时候,需要解决两个问题:

  • 如何在属性值缺失的情况下进行划分属性的选择?(比如“色泽”这个属性有的样本在该属性上的值是缺失的,那么该如何计算“色泽”的信息增益?)
  • 给定划分属性,若样本在该属性上的值是缺失的,那么该如何对这个样本进行划分?(即到底把这个样本划分到哪个结点里?)

下面就来介绍如何解决这两个问题:

比较发现,“纹理”在所有属性中的信息增益值最大,因此,“纹理”被选为划分属性,用于对根节点进行划分。划分结果为:“纹理=稍糊”分支:{7,9,13,14,17},“纹理=清晰”分支:{1,2,3,4,5,6,15},“纹理=模糊”分支:{11,12,16}。如下图所示:

那么问题来了,编号为{8,10}的样本在“纹理”这个属性上是缺失的,该被划分到哪个分支里?前面讲过了,这两个样本会同时进入到三个分支里,只不过进入到每个分支后权重会被调整(前面也说过,在刚开始时每个样本的权重都初始化为1)。编号为8的样本进入到三个分支里后,权重分别调整为5/15,7/15 和 3/15;编号为10的样本同样的操作和权重。因此,经过第一次划分后的决策树如下图所示:

我们都知道构造决策树的过程是一个递归过程,原来不打算继续介绍递归过程了,但是因为权重发生了变化,所以继续介绍下递归过程。接下来,递归执行“纹理=稍糊”这个分支,样本集D = {7,8,9,10,13,14,17},共7个样本。如下图所示:

下面来看具体的计算过程:

对比能够发现属性“敲声”的星系增益值最大,因此选择“敲声”作为划分属性,划分后的决策树如下图所示:

接下来对分支{敲声 = 沉闷}即结点{9,14,17}进行划分,根据博客决策树(一)介绍的三种递归返回情形,结点{9,14,17}因为包含的样本全部属于同一类别,因此无需划分,直接把结点{9,14,17}标记为叶结点,如下图所示:

根据递归过程,接下来对分支“敲声 = 浊响”即结点{7,8,13}进行划分,计算过程和上面一样,虽然我也算过了,但是不再贴出来了,需要注意的是样本的权重是1/3。计算完比较能够知道属性“脐部”的信息增益值最大,因此选择“脐部”作为划分属性,划分完的决策树如下图所示:

接下来,继续,对于结点{13},因为就一个样本了,直接把该结点标记为叶结点,类别为“坏瓜”;递归到结点{7,8},因为样本类别相同,所以也标记为叶结点,类别为“好瓜”;递归到结点“脐部=平坦”,因为这个结点不包含任何样本为空集,因此,把该结点标记为叶结点,类别设置为父节点中多数类的类别,即为“好瓜”。因此“纹理=稍糊”这颗子树构造完毕,如下图所示:

接下来,只需递归的重复上述过程即可,即能训练出一颗完整的决策树,最终的决策树如下图所示(该图片来自西瓜书):

遗留问题:
为什么是:
Gain(D,a)=ρ×Gain(D^,a)=ρ×(Ent(D^)v=1Vrv^Ent(D^v))Gain(D,a)=\rho \times Gain(\hat{D},a)=\rho \times \left(Ent(\hat{D})-\sum_{v=1}^{V}\hat{r_v}Ent(\hat{D}^v)\right)

有些不是很懂,希望懂的给解释一下,谢谢大佬了

1人推荐
随时随地看视频
慕课网APP