机器学习笔记之决策树算法（下）

阅读文本大概需要 7 分钟。

赶着这礼拜最后一天的末班车发出来了，这次是接着上次的决策树算法。

连续与缺失值

连续值处理

前面谈到的都是一些离散的特征属性，现实学习任务常会遇到连续属性，所有要解决连续属性在决策树学习中的问题。

连续属性没有可划分的结点，这个时候要用到连续属性离散化技术，最简单的策略就是采用二分法 ( bi-partition)对连续属性进行处理，C4.5 决策树算法采用的就是这种机制。在样本集 D 中有v个连续样本属性，将这些值从小到大排序，记为 {a1,a2,a3…aV}。基于划分点 t 将 D 分为子集 则包含属性 a 大于划分点 t 的样本，则包含属性 a 小于划分点 t 的样本。

这个划分点 t 是如何得来的呢。在两个数据之间就可以存在一个划分点，所以每两个数的中位数都可以作为一个划分点，当然只要是位于两个数之间的任意值划分结果都相同。这样就有一个候选划分点集合

这里的划分点就是用区间的中位点作为候选划分点。然后就可以像离散属性一样考察这些划分点，选取最优的划分点作为样本集合的划分，信息增益公式则可改造成：

在西瓜样本集上稍加改造，添加了密度和含糖率连续值。

在属性“密度”上，17 个训练集样本的取值均不相同。根据候选点划分集合公式，包含 16 个候选点集合 T密度= {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}。过程即是先把密度取值从小到大排序，再分别计算第一个、第二个的中位数，第二个、第三个，直到第十六个、第十七个，最后得到这个候选划分点集合。计算出“密度”的信息增益为0.262，对应的划分点为0.381。

列举部分计算过程：

由于当“密度”为0.381时的信息增益最大，所以划分点选为0.381。

在属性“含糖率”也是同样的计算过程，候选值为 T含糖率={0.049,0.074,0.095,0.101,0.126,0.155,0.179,0.204,0.213,0.226,0.250,0.265,0.292,0.344,0.373,0.418}。计算出其信息增益为 0.349 ，对应于划分点为0.126。

所有属性的信息增益则是：

于是“纹理”属性被选作根结点划分属性，此后的结点划分过程递归执行。

缺失值处理

可能会遇到连续值，同样也可能遇到不完整的样本，即样本的某些属性缺失。那又如何不放弃不完整的样本让决策树学习呢。下面的西瓜样本集包含不完整样本，如果放弃不完整样本，仅有编号 {4,7,14,16 }的4个样本能被使用，所以要考虑利用有缺失属性值的训练样例来进行学习。

要解决两个问题：( 1 )如何在属性值缺失的情况下进行划分属性选择？( 2 )给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

先来解决第一个问题。给定训练集 D 和属性 a ，令表示 D 中属性 a 上没有缺失值的样本子集。根据来判断属性 a 的优劣。假设属性 a 有 V 个可取值 {a1,a2,a3…aV},令表示中在属性 a 上取值为aV的样本子集，表示中属于第 k 类(k = 1,2,3…|y| )的样本子集。在西瓜数据集中 k 仅有两个值：好瓜和坏瓜。假定为每个样本x赋予一个权重wx，并定义

表示无缺失值样本所占的比例，表示无缺失值样本中第k类所占的比例，则表示无缺失值样本中在属性 a 上取值的样本所占比例。所以信息增益计算式可以推广为

第二个问题，若样本在划分属性 a 上已知则直接划入与其值对应的子结点，且样本权值在子结点保持为 。若样本属性在划分属性 a 上未知，则将样本同时划入所有子结点，且样本权值在与属性值 对应的子结点中调整为·，意思就是让同一个样本以不同概率划入不同的子结点。

多变量决策树

引入连续值的决策树在坐标系中可以很直观的看出来，每一个分类边界都是轴平行的，因为他的判断标准是一个常数，这样的决策树会相当复杂，多变量决策树用简单的线性划分属性，使决策树模型大为简化。在多变量决策树中，非叶结点不再是针对一个属性，而是对属性的线性组合进行测试。在多变量决策树的学习过程中，不再是为每个叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

总结

在连续值处理的问题上，可以用连续属性离散化技术进行处理，计算出候选点划分集合再选取最优的划分点，缺点就是运算量比较大。如果样本不完整的话利用没有缺失值的属性来进行属性划分，在该属性上有缺失值则以不同概率划分到子结点中。