周志华西瓜书学习笔记
2023.12 二周目补充版
加粗和高亮是重点和我自己的理解
二周目心得:不好好学习贪图一时享乐欠下的债以后都是要还的
基本流程
一棵决策树包含一个根节点、若干个内部结点和若干个叶结点;叶结点对应于决策结果,其他每个结点则对应于一个属性测试;每个结点包含的样本集合根据属性测试的结果被划分到子结点中;根结点包含样本全集。从根结点到每个叶结点的路径对应了一个判定测试序列。示意图如下

生成是一个递归过程,四种情况会导致递归返回:
- 当前结点包含的样本全属于同一类别,无需划分 => 比如现在的样本类别都是好瓜
- 当前属性集为空,无法划分 => 没有属性 => 标记为叶结点,并将其类别设定为该结点所含样本最多的类别(当前结点的后验分布 )
- 所有样本在所有属性上取值相同,无法划分 => 当前node所包含的样本集在所有属性
上的值都相同,比如色泽、根蒂、敲声 三个属性值都一样 => 标记为叶结点,并将其类别设定为该结点所含样本最多的类别(当前结点的后验分布 ) - 当前结点包含的样本集合为空,不能划分 => 标记为叶结点,将其类别设定为其父结点所含样本最多的类别(把父节点的样本分布作为当前结点的先验分布)

划分选择
随着划分过程不断进行,我们希望决策树的分支结点所包含的样本尽可能属于同一类别,即结点的纯度越来越高。
本章节记录了几种选择最优化分属性
(纯度)的方法
信息增益 => ID3决策树
定义
用信息熵来衡量样本集合纯度。若当前样本集合
当每个类别出现的概率相等时,即
假设离散属性
为当前的每个划分离散值对应的样本子集信息熵,划分得到的信息熵和越小,划分后的纯度越大,原来的值减去新的划分和得到的值越大
取
举例
这是书上举的例子,很好理解且一定要理解:
增益率 => C4.5决策树
信息增益准则对可取值数目较多的属性有所偏好
增益率准则对可取值数目较少的属性有所偏好
增益率定义:
基尼指数 => CART决策树
纯度用基尼值来度量
基尼指数定义:
在候选属性集合A中,选择那个使得划分后基尼指数最小的属性作为最优划分属性
剪枝处理
为了应付过拟合,提升泛化能力。基本策略有 “预剪枝” (prepruning)和 “后剪枝” (postpruning)
预剪枝
在每次划分前验证划分后精度是否会下降,若会下降则不进行此次划分。
有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降,但在其基础上进行的后续划分却有可能导致性能显著提高;还可能会带来欠拟合的风险
后剪枝
先生成一颗完整的树再进行剪枝,能够保留更多的分支,欠拟合的风险比较小,泛化性能往往优于预剪枝决策树。
但存在的问题是要自顶向下生成一棵树,再自底向上进行剪枝,开销会特别大。
连续与缺失值
连续属性的可取值数目不再有限,不能直接根据连续属性的可取值来对结点进行划分 => 连续属性离散化技术
二分法 => C4.5决策树
定义
给定样本集
找出(一个个算)使得
举例
同样上个例子:
缺失值处理
定义
符号说明(看得明白):
表示 在属性 上 没有缺失值的样本子集,意思就是对于某个属性 我们把这一列没有缺失值的拿出来打包成一个集合- 属性
有 个取值, , 表示在属性a上取值为 的样本子集,属性a有6个取值,从小到大排序,第五个的值为3.78,把所有在a上取值为3.78的样本都取出来,这样的集合就叫做 ,它们在a上的取值都是 表示 中属于第 类 的样本子集,第一类是好瓜,第二类是坏瓜诸如此类 ,
从上面内容可以进行新的定义(注意各自的分母),对于每个样本
第
根据信息熵公式:
可以得到信息增益:
算出每个属性的信息增益,然后选择信息增益最大的属性作为划分属性
举例
同样上个例子
多变量决策树
把每个属性视为坐标空间中的一个坐标轴,则 d 个属性描述的样本就对应了 d 维空间中的一个数据点,对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界
多变量决策树希望做的事情是把平行的轴变成倾斜的轴,非叶结点不再是仅对某个属性,而是对属性的线性组合进行测试,每个非叶结点是一个形如