当前位置：首页 > news >正文

机器学习（西瓜书）第四章决策树

news 2025/7/10 12:50:24

作者前言：本章内容是作者阅读《机器学习》（周志华）（网友戏称“西瓜书”，因为本书作者从第一章开始便通过如何辨别好的西瓜的例子来剖析机器学习的实质。）及相关资料写的。笔者在写此博客前，也看到了网上发布了大量相关此书的读书笔记，但翻来看去发现存在公式放的较多、大量拍摄书上的内容照片直接贴图等情况，不太适合新手阅读。故，作者写下此篇博客。笔者尽可能简化公式或者不放公式，读者在阅读。过程中不要过于纠结看懂里面的数学公式，只需搞懂里面各种的作用，内在大致的缘由即可。

PS：本章是书上的第四章，全书共有11种模型的讲解，含有线性模型、决策树、神经网络、支持向量机（SVM）、贝叶斯分类器、集成学习、聚类、半监督学习、概率图模型、规则学习、强化学习。下一章将更新神经网络!!! 请持续关注作者!!!

由于撰写此篇博客的网页编辑器编写上小标不方便，故内容中涉及到大量上下标的情况下采用截取笔者的阅读笔记，还请各位读者谅解！笔者也尽可能想办法提高读者的阅读体验！

一、基本流程

二、划分选择

1、信息增益

2、增益率

3、基尼指数

三、剪枝处理

四、连续与缺失值

1、连续值处理

2、缺失值处理

五、多变量决策树

一、基本流程

决策树是基于树结构来进行决策的，例如：我们要对”这是好瓜吗？“这样的问题进行决策时，如果是”青绿色“，则再看”它的根蒂是什么形态？“，如果是”蜷缩“，我们再判断”它敲起来是什么声音？“，最后，得出最终决策：这是个好瓜，决策过程如下图：

一般的，一颗决策树包含一个根结点、若干个内部结点和若干个叶结点；叶结点对应于决策结果，其他每个结点则对应于一个属性测试。每个结点包含的样本集合根据属性测试的结果被划分到子结点中；根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列，决策树学习的目的是为了产生一颗泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的“分而治之”策略。

注：一颗仅有一层划分的决策树，称为“决策树桩”。

         显然，决策树生成是一个递归过程。在决策树基本算法中，有三种情形会导致递归返回。

        (1)当前结点包含的样本全属于同一类别，无需划分

        (2)当前属性集为空，或是所有样本在所有属性上取值相同，无法划分

        (3)当前结点包含的样本集合为空，不能划分

        在(2)的情形下，把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在(3)的情形下，同样把当前结点标记为叶结点，但将其类别设定为其父节点所含样本最多的类别。注意这两种情形的处理实质不同：情形(2)是在利用当前结点的后验分布，而情形(3)则是把父节点的样本分布作为当前结点的先验分布。

二、划分选择

从上述学习基本算法的关键是第8行，即如何选择最优划分属性。一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本尽可能属于同一类别（即结点的“纯度”越来越高）。

1、信息增益

“信息熵”是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为 $p_{k}$ (k=1,2,...,|y|)，则D的信息熵定义为：

Ent(D)的值越小，则D的纯度越高。

一般而言，信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，可用信息增益来进行决策树的划分属性选择。（故最优划分属性就是通过寻找最大信息增益的属性：a*=arg maxGain(D,a)(a∈A)）.著名的ID3（迭代二分器）决策树学习算法就是以信息增益为准则来选择划分属性。

2、增益率

实际上，信息增益准则对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法不直接使用信息增益，而是使用“增益率”来选择最优划分属性。

其中：

称为属性a的“固有值”。属性a的可能取值数目越大(即V越大)，则IV(a)的值通常会越大。需要注意，增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选取增益率最大的候选划分属性，而是使用了一个启发式：先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

3、基尼指数

CART决策树使用“基尼指数”来选择划分属性，数据集D的纯度可用基尼值来度量：

直观来说，Gini(D)反映了从数据集D中随机抽取两个两本，其类别标记不一致的概率。因此，Gini(D)越小，则数据集D的纯度越高。属性a的基尼指数定义为：于是，在候选属性集合A中，选择那个使得划分后基尼指数最小的属性作为最优划分属性。即a*=arg minGini_index(D,a)(a∈A)。

三、剪枝处理

剪枝是决策树学习算法对付“过拟合”的主要手段。在决策树学习中，为尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多这时就可能产生“过拟合”。因此，需要剪去一些分支来降低过拟合风险。

决策树剪枝的基本策略有：“预剪枝”和“后剪枝”。

预剪枝是在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点（预剪枝基于“贪心”本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险）

后剪枝是从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考虑，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点

那如何判断决策树泛化性能是否能提升？这里就看第二章介绍的性能评估。

注：后剪枝决策树通常比预剪枝决策树保留了更多的分支。一般情形下，后剪枝决策树的欠拟合风险很小，泛化性能往往优于预剪枝决策树。但后剪枝过程是在生成完全决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。

四、连续与缺失值

1、连续值处理

讨论如何在决策树学习中使用连续属性。由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结点进行划分。此时，需要用到连续属性离散化技术。最简单的策略是采用二分法对连续属性进行预处理，这也是C4.5决策树算法中采用的机制。

2、缺失值处理

        讨论样本的某些属性值缺失该如何处理。若存在少量的缺失值可以考虑去除缺失值，仅未缺失值的数据进行决策树训练。但若存在缺失值大量缺失，则会丢失大量信息，这个是需要解决的。此问题需要解决两个问题：

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

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

给定训练集D和属性a，令D'表示D中在属性a上没有缺失值的样本子集。

注：由于下面存在大量的公式和上下标，此文章的网页编辑器编写起来太过于麻烦，故贴上笔者在阅读过程中的笔记。敬请读者谅解！

五、多变量决策树

若把每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类就意味着在这个坐标空间中寻找不同样本之间的分类边界。决策树所形成的分类边界有一个明显的特点：轴平行，即它的分类边界由若干个与坐标轴平行的分段组成。这样的分类边界使得学习结果有较好的可解释性，因为每一段划分都直接对应了某个属性取值，如下图所示，分类边界的每一段都是与坐标轴平行的。

但在学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似，如下图所示，此时的决策树会相当复杂，由于要进行大量的属性测试，预测时间开销会很大。

若使用斜的划分边界（图4.12的红色线段所示），则决策树模型将大为简化。"多变量决策树"（亦称“斜决策树”）就是能实现这样的“斜划分”甚至更复杂划分的决策树。以实现斜划分的多变量决策树为例，在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试；换言之，每个非叶结点是一个形如： $\sum _{i=1}^{d}w_{i}a_{i}=t$ 的线性分类器，其中 $w_{i}$ 是属性 $a_{i}$ 的权重， $w_{i}$ 和t可在该结点所含的样本集和属性集上学的。

故，与传统的“单变量决策树”不同，在多变量决策树的学习过程中，不是为每个非叶结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。如下图所示：

注：有一些决策树学习算法可进行“增量学习”，即在接收到新样本后可对已学得的模型进行调整，而不用完全重新学习。主要机制是通过调整分支路径上的划分属性次序来对树进行部分重构，代表算法有ID4、ITI等。增量学习可有效地降低每次接收到新样本后的训练时间开销，但多步增量学习后的模型会基于全部数据训练而得的模型有较大差别。

PS：好的，如果你能看到这里，说明读者非常有毅力！恭喜你，你做什么事都会成功的。机器学习里面含有大量数学公式作为基础，对于数学不好的读者来说，理解起来难如登天。笔者希望可以尽可能简化这些公式来讲解机器学习！（我会持续更新下去，您的点赞+收藏是我更新的动力！）

不问前路几多险，只凭一腔热血与坚定的步伐。

查看全文

http://www.lryc.cn/news/583368.html