《机器学习》周志华读书笔记（四）决策树（下）

注：本文为https://blog.csdn.net/qq_38172282/article/details/91360640（文章）的下半部分，从4.4连续与缺失值开始讲起。

4.4连续与缺失值

4.4.1连续值处理

        如果学习任务中遇到连续属性，由于连续属性的可取值数目不再有限，若每个取值作为一个分支则显得不可行（总不能划分成无数个分支吧），因此需要进行离散化处理，常用的方法为二分法（bi-partition）。（连续属性离散化技术）

        定义：给定样本集 D 和连续属性 a，假定 a 在 D上有 n 个不同的取值，将这些值从小到大进行排序，记为  。基于划分点 t 可将 D 分为子集  和  ，其中  包含那些在属性 a 上取值不大于 t 的样本，而  则包含那些在属性 a 上取值大于 t的样本。对相邻的属性取值  与  来说，t 在区间  中取任意值所产生的划分结果相同。我们可以设

        则基于这种划分方法，划分点 t 共有 n-1 个候选点，该候选划分点集合为：

        我们假定通过信息增益进行划分选择，则对于连续属性来说，其信息增益计算如下：

       其中  是样本集 D 基于划分点 t 二分后的信息增益，这样就可以选择使  最大化的划分点。

       离散属性的划分中，作为当前结点划分依据的属性，在其分支结点将不再作为划分考虑。例如在判别西瓜的好坏分类中，我们第一个结点通过色泽分出了亮和暗，得出了亮和暗两个分支结点。那么接下来这两个分支结点将不再考虑西瓜的色泽属性了，因为在第一个结点已经明确划分出了哪些瓜是“亮”属性，哪些瓜是“暗“属性，离散属性的划分重点是判别”是什么“，所以不存在多次重复判别。

        连续属性与离散数学在划分时的一个区别：假设以二分法来离散化，划分重点不是”是什么“，而是”区间内属性值的大小关系“，这是可以多次划分多次比较的。例如在区间 0 到 1，第一个结点是以 t = 0.5 进行划分，得出两个分支结点 v1 , v2 。 在 v1中 0 到 0.5，我们可以再次选定一个划分点 t=0.25，再次划分出分支结点。

4.4.2缺失值处理

        现实中常会遇到不完整的样本，即某些属性值缺失（可能为测试成本，隐私保护等原因）。若简单采取剔除，则会造成大量的信息浪费，因此在属性值缺失的情况下需要解决两个问题：

（1）如何在属性值缺失的情况下进行划分属性选择？

（2）给定划分属性，若样本在该属性上的值缺失，如何对样本进行划分？

讨论问题一：

        我们给定训练集 和属性 ，令  表示  中在属性  上没有缺失值的样本集合，显然我们只能通过  来判断属性  的优劣。假定属性  有  个可取值  ，令  表示  在属性  上取值为  的样本子集， 表示  中属于第 k 类 的样本子集。假定我们为每个样本  赋予一个权重  ，初值为1。同时定义：

① ，表示对于属性 a，无缺失的样本比例，样本子集所占比例

②，表示无缺失样本中，第 k 类所占比例，样本子集每个类别的比例

③，表示无缺失样本在属性 a 上取值为的样本的比例，每个分支所含样本的比例

       一般的样本具有多个属性。不同属性的缺失值情况不同。直观来看：假如100个样本中，属性 a 的缺失值高达 99 份，属性 b 的缺失值只有 1 个，属性 c 的缺失值有 50 个。再假定他们在没有缺失值的情况下对于样本集合的纯度提升效果一样，那在存在前面缺失的情况下，哪个属性最可靠？

        我们可以直观的判断出最可靠的是属性b（缺失的值最少），其次是 c，再其次是 a 。由此可以考虑给不同属性增加一个系数  = 无缺失值总数 / 样本集合总数，例如此处举例  = 1/100， = 99/100，=50/100.

        基于上述推论，我们可以将信息增益的计算时推广为：

讨论问题二：

由于缺失值的样本终归不是理想样本，我们希望这样的非理想样本对于决策树的贡献减小。我们可以采用如下策略：

若样本  在划分属性  上的取值已知，则将  划入与其对应的分支结点，并保持样本权重  不变。若样本 在划分属性 上的取值未知，则将样本  划入所有分支结点，且样本权重调整为。

4.5多变量决策树

       若我们把样本的每个属性都视为坐标空间中的一个坐标轴，则由 d 个属性描述的样本就对应了 d 维空间中的一个数据点。对样本的分类就意味着在这个坐标空间中寻找不同类样本之间的分类边界。而我们前面提到的决策树在 d 维空间中形成的分类边界有一个特点：轴平行

       下左图中我们可以看出决策树上有4个分支节点，对应下右图则有4段关于轴平行的分类边界，（样本集的属性只包括两个连续属性（密度，含糖率），它的分类边界由若干个与坐标轴平行的分段组成的。）通过多段的分类边界去划分，显然时间开销是很大的，因此假如我们不局限于平行与轴的分类边界，考虑使用斜的划分边界，此时就引入了“多变量决策树”。

      “多变量决策树”与“普通决策树”相比，关键在于分支结点的属性测试的区别。“多变量决策树”的属性测试不再是单一的属性测试，而是对多个属性的线性组合进行测试。换句话说，对于分支结点的属性测试，我们不再是为每个结点寻找一个最优划分属性了，而是对每个分支结点建立一个合适的线性分类器。

决策树对复杂分类边界的分段近似：

按照上述的方法，应用于书上的例子，如下图所示，显然与“普通的决策树分类边界”相比，采用“多变量决策树”能够通过斜的划分边界取得较好的效果。