《西瓜书》第四章 决策树 笔记

2024-09-04 00:08

本文主要是介绍《西瓜书》第四章 决策树 笔记,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

    • 4.1 基本流程
      • 4.1.1 组成
      • 4.1.2 目的
      • 4.1.3 策略
      • 4.1.4 算法
    • 4.2 划分选择
      • 4.2.1信息增益-ID3决策树
        • 4.2.1.1 信息熵
        • 4.2.1.1 信息增益
      • 4.2.2 增益率-C4.5决策树
      • 4.2.3 基尼指数-CART决策树
        • 4.2.3.1 基尼值
        • 4.2.3.2 基尼指数
    • 4.3 剪枝处理
      • 4.3.1 预剪枝
      • 4.3.2 后剪枝
    • 4.4 连续与缺失值
      • 4.4.1 连续值处理
      • 4.4.2 缺失值处理
    • 4.5 多变量决策树
    • 4.6 总结
    • 4.7 参考资料

4.1 基本流程

4.1.1 组成

一颗决策树包含一个根结点、若干个子结点和若干个叶结点。
根结点:包含样本全集;
子结点:对应属性划分,包含划分样本;
叶结点:对应决策结果,包含决策样本。
从根结点到每个叶结点的路径:对应一个判定测试序列(系列子决策)。

4.1.2 目的

产生一棵泛化能力强,处理未见示例能力强的决策树。

4.1.3 策略

决策树采用分而治之(Divide and Conquer)策略,以一系列的子决策决定分类结果。

4.1.4 算法

frank yogan
上图算法中最关键的是第8行,即如何选择最优划分属性。

决策树的生成是一个递归过程。核心是最优划分属性的选择,有三种情形导致递归返回
(1) 当前结点包含的样本全属于同一类别,无需划分,该结点类别确定。
(2) 所有样本在所有属性值相同,或属性集为空,无法划分,该结点类别设定为所含样本最多的类别(利用当前结点的后验分布)。
(3) 当前结点包含的样本集合为空,不能划分。父结点类别确定(利用当前结点的先验分布)。

4.2 划分选择

判断最优划分属性的的依据是随着划分过程不断进行的,我们希望分支结点所包含的样本尽可能属于同一类,即结点的纯度(purity)越来越高。简单的说就是每一次根据某个条件分类之后,尽可能使样本都符合这个条件,说明我们的分类条件是极具区分意义的,能够明显的将样本分开。

4.2.1信息增益-ID3决策树

4.2.1.1 信息熵

信息熵的定义

信息熵(Information Entropy)用来描述信源的不确定度,一件事情发生的概率越小,事件发生后所包含的信息量越大,信息熵越高。首先我们用信息熵来度量样本集合的纯度(purity),一个样本集合的信息熵越低,则其纯度越高。

信息熵的公式定义
在这里插入图片描述
其中,D 指样本集;y 指样本总共有多少类;k 指第k类样本;pk 指第k类样本在D中的比例。

Ent(D)最小值为0,最大值为log2∣y∣.

信息熵的三个性质

  1. 单调性:发生概率越高的事件,其携带的信息量越低;
  2. 非负性:信息熵可以看作为一种广度量,非负性是一种合理的必然;
  3. 累加性:即多随机事件同时发生存在的总不确定性的量度是可以表示为各事件不确定性的量度的和,这也是广度量的一种体现。
4.2.1.1 信息增益

ID3决策树算法 使用信息增益(Information Gain)选择划分属性。
偏好:信息增益对可取数目较多的属性有所偏好。

属性a的信息增益公式定义为:
在这里插入图片描述
其中,D指样本集;a指属性;v 和V指a所有可能的取值;Dv指属性值为v vv时划分得到的子集。

信息增益最优属性
信息增益越大,意味着由这个属性来进行划分对纯度的提升越大,即对决策的帮助越大。所以对每个属性均求出信息增益,再取最大的那个,就是最优划分属性。

信息增益最优属性公式定义
在这里插入图片描述

4.2.2 增益率-C4.5决策树

如果一个属性对每个样本的取值都是不同的,那么针对这个属性的每个取值只包含一个样本并且分支结点的纯度已达最大,这样的决策树显然没有泛化能力,无法对新样本进行预测。因为新的样本在这个属性的值与决策树所学习的均不相同。因为信息增益准则对可取值数目较多的属性有偏好。所以增益率要对信息增益进行优化。

增益率公式定义
在这里插入图片描述
IV(a)称为属性a的固有值(intrinsic value),属性a的可能取值数目越多,IV(a)的值越大,增益率就越小。所以我们在应用增益率准则的时候,先从划分属性中选择信息增益高于平均水平的属性,再进行二次选择,选择增益率最高的作为最终的最优化分属性。

4.2.3 基尼指数-CART决策树

4.2.3.1 基尼值

基尼值是另一种度量数据集纯度的指标,与信息熵性质一样。其反映了从数据集中随机抽取两个样本,其类别不一致的概率。因此,基尼值越小,则数据集的纯度越高。

基尼值公式定义
在这里插入图片描述

4.2.3.2 基尼指数

属性a的基尼指数公式定义为:
在这里插入图片描述
最优化分属性
选基尼指数最小的那个属性作为最优化分属性:
在这里插入图片描述

4.3 剪枝处理

4.3.1 预剪枝

预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点。

#仅有一层划分的决策树称为“决策树桩
预剪枝基于贪心策略,预划分当前结点,减少了决策树的分支。

优点:

  1. 显著减少了决策树的训练时间开销和测试时间开销;
  2. 降低了过拟合的风险;

缺点:

  1. 数据集可能存在当前划分验证集精度低,但后续划分显著提高的情形,无法得到最优决策树;
  2. 增加了欠拟合的风险;

4.3.2 后剪枝

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

后剪枝相对预剪枝保留了更多的分支。

优点:

  1. 保留了更多分支,泛化性能往往优于预剪枝决策树;
  2. 降低了欠拟合的风险;

缺点:

  1. 先从训练集生成一颗完整的决策树,训练时间开销和测试时间开销比未剪枝决策树和预剪枝决策树要大得多;

4.4 连续与缺失值

4.4.1 连续值处理

之前基于离散属性生成决策树,现在考虑使用连续属性。由于连续属性可取值数目无限,使用连续属性离散化技术。最简单的策略采用二分法(bi-partition),将给定连续属性的区间的中位点作为候选划分点。
在这里插入图片描述
计算纯度的方式跟之前一致,但是将中位点值替换为划分属性值。同时输入可以变成范围值,泛化能力增强。

C4.5:Information Gain (Ratio) based Threshold
CART:遍历所有输入变量j 和切分点s,根据最小化平方误差准则选取;

4.4.2 缺失值处理

缺失值面临的两个问题:

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

对于第一个问题,若取值未知,则根据其他样本的取值来计算划分点。
对于第二个问题,若取值未知,则将该样本同时划入所有子结点,且设置一个样本权值用于计算loss。

缺失值处理方法:
4. 插值法(Imputation): QUEST, CRUISE
5. 替代法(Alternate/Surrogate Splits):CART, CRUISE
6. 缺失值单独分支(Missing value branch):CHAID, GUIDE
7. 概率权重(Probability weights): C4.5

4.5 多变量决策树

多变量决策树是用属性的线性组合(对应多变量)划分结点。

将样本集合对应多维空间,每个属性对应一个维度,分类就是在不同类空间寻找边界。单变量决策树的分类边界是由若干个与坐标轴平行的分段组成。
在这里插入图片描述
多变量决策树的分类边界是由若干个折线分段组成。
在这里插入图片描述

4.6 总结

  1. 决策树采用的是一种简单且直观的“分而治之”(divide-and-conquer)策略
  2. 决策树根据数据集的总体纯度来衡量不同属性划分的优劣
  3. 当属性选择过于频繁会导致模型过拟合,这时候就需要使用剪枝算法来进行处理
  4. 剪枝算法的判断标准是剪枝前后模型的性能指标是否提高
  5. 当遇到连续值的属性时,可以通过将其拆解成两块的方式将数据转换为离散值
  6. 当遇到缺失值属性时,可以通过在属性选择算法中加入缺失值数据的影响来适应
  7. 在处理真实分类边界比较复杂的学习任务时,我们可以使用属性的线性组合来对数据进行划分
    在这里插入图片描述

4.7 参考资料

1. 机器学习(西瓜书) 第4章 决策树
2. 学习笔记Task2-决策树-80%
3. github - deyiwang89/WaterMelon-ML
4. 决策树处理连续值,缺失值

这篇关于《西瓜书》第四章 决策树 笔记的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1134437

相关文章

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络(1)sklearn

系列文章目录 监督学习:参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归(SAheart.csv) 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

论文阅读笔记: Segment Anything

文章目录 Segment Anything摘要引言任务模型数据引擎数据集负责任的人工智能 Segment Anything Model图像编码器提示编码器mask解码器解决歧义损失和训练 Segment Anything 论文地址: https://arxiv.org/abs/2304.02643 代码地址:https://github.com/facebookresear

数学建模笔记—— 非线性规划

数学建模笔记—— 非线性规划 非线性规划1. 模型原理1.1 非线性规划的标准型1.2 非线性规划求解的Matlab函数 2. 典型例题3. matlab代码求解3.1 例1 一个简单示例3.2 例2 选址问题1. 第一问 线性规划2. 第二问 非线性规划 非线性规划 非线性规划是一种求解目标函数或约束条件中有一个或几个非线性函数的最优化问题的方法。运筹学的一个重要分支。2

【C++学习笔记 20】C++中的智能指针

智能指针的功能 在上一篇笔记提到了在栈和堆上创建变量的区别,使用new关键字创建变量时,需要搭配delete关键字销毁变量。而智能指针的作用就是调用new分配内存时,不必自己去调用delete,甚至不用调用new。 智能指针实际上就是对原始指针的包装。 unique_ptr 最简单的智能指针,是一种作用域指针,意思是当指针超出该作用域时,会自动调用delete。它名为unique的原因是这个

查看提交历史 —— Git 学习笔记 11

查看提交历史 查看提交历史 不带任何选项的git log-p选项--stat 选项--pretty=oneline选项--pretty=format选项git log常用选项列表参考资料 在提交了若干更新,又或者克隆了某个项目之后,你也许想回顾下提交历史。 完成这个任务最简单而又有效的 工具是 git log 命令。 接下来的例子会用一个用于演示的 simplegit

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪(un-tracking)文件重新跟踪(re-tracking)文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法,现在我们已经有了一个仓库,并从这个仓

忽略某些文件 —— Git 学习笔记 05

忽略某些文件 忽略某些文件 通过.gitignore文件其他规则源如何选择规则源参考资料 对于某些文件,我们不希望把它们纳入 Git 的管理,也不希望它们总出现在未跟踪文件列表。通常它们都是些自动生成的文件,比如日志文件、编译过程中创建的临时文件等。 通过.gitignore文件 假设我们要忽略 lib.a 文件,那我们可以在 lib.a 所在目录下创建一个名为 .gi

取得 Git 仓库 —— Git 学习笔记 04

取得 Git 仓库 —— Git 学习笔记 04 我认为, Git 的学习分为两大块:一是工作区、索引、本地版本库之间的交互;二是本地版本库和远程版本库之间的交互。第一块是基础,第二块是难点。 下面,我们就围绕着第一部分内容来学习,先不考虑远程仓库,只考虑本地仓库。 怎样取得项目的 Git 仓库? 有两种取得 Git 项目仓库的方法。第一种是在本地创建一个新的仓库,第二种是把其他地方的某个

Git 的特点—— Git 学习笔记 02

文章目录 Git 简史Git 的特点直接记录快照,而非差异比较近乎所有操作都是本地执行保证完整性一般只添加数据 参考资料 Git 简史 众所周知,Linux 内核开源项目有着为数众多的参与者。这么多人在世界各地为 Linux 编写代码,那Linux 的代码是如何管理的呢?事实是在 2002 年以前,世界各地的开发者把源代码通过 diff 的方式发给 Linus,然后由 Linus