第四章决策树

作者: 乘瓠散人 | 来源:发表于2022-01-20 18:53 被阅读0次

机器学习（4）
第四章决策树
《机器学习》西瓜书学习笔记（三）
机器学习西瓜书 Day04 决策树
机器学习6-决策树
决策树
决策树
决策树算法总结
机器学习 - 决策树算法[一]
机器学习系列（三十六）——回归决策树与决策树总结

基本流程

决策树是基于树结构来进行决策的，这恰是人类在面临问题时一种很自然的处理机制。

一般的，一棵决策树包含一个根结点、若干个内部结点和若干个叶结点。叶结点对应于决策结果，其他每个结点则对应于一个属性测试，从根结点到每个叶结点的路径对应了一个判定序列。

决策树学习的目的是产生一个泛化能力强，即处理未见示例能力强的决策树。

划分选择

决策树构建的关键是如何选择要划分的属性。一般来说，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的纯度越来越高。

信息增益

信息熵是度量样本集合纯度最常用的一种指标。假设当前样本集合 $D$ 中第 $k$ 类样本所占的比例为 $p_k$ ，则 $D$ 的信息熵为：
$Ent(D) = -\sum_{k=1}^{K}p_k log_2 p_k$
信息熵 $Ent(D)$ 值越小，则 $D$ 的纯度越高。

假设离散属性 $a$ 有 $V$ 个可能的取值，若使用属性 $a$ 来对样本集 $D$ 进行划分，则会产生 $V$ 个分支结点，每个分支结点所包含的样本在属性 $a$ 上取值相同，第 $v$ 个分支结点所包含的样本集合记为 $D^v$ 。考虑到不同的分支结点所包含的样本数不同，给分支结点赋予权重 $|D^v|/|D|$ ，即样本数越多的分支结点影响越大。
因此可计算出利用属性 $a$ 对样本集 $D$ 进行划分的信息增益为：
$Gain(D,a) = Ent(D) - \sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$
一般而言，信息增益越大，说明用该属性进行划分所获得的纯度提升越大。因此，我们可用信息增益来进行决策树的划分属性选择。

增益率

信息增益对可取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响，著名的C4.5决策树算法提出使用增益率来选择最优划分属性。增益率定义为：
$Gain\_ratio(D, a) = \frac{Gain(D, a)}{IV(a)}$
$IV(a) = - \sum_{v=1}^V\frac{|D^v|}{|D|}log_2\frac{|D^v|}{|D|}$

$IV(a)$ 称为属性 $a$ 的固有值，属性 $a$ 的可能取值数目越多(即 $V$ 越大)，则 $IV(a)$ 的值通常会越大。

然而，增益率对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。

基尼指数

CART(Classification and Regression Tree)决策树使用基尼指数来选择划分属性，数据集 $D$ 的纯度可用基尼值来度量：
$Gini(D) = \sum_{k=1}^{K}\sum_{k'\neq k} p_k p_{k'} = 1 - \sum_{k=1}^K {p_k}^2$

直观来说， $Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。因此基尼值 $Gini(D)$ 越小，则数据集 $D$ 的纯度越高。

属性 $a$ 的基尼指数定义为：
$Gini\_index(D, a) = \sum_{v=1}^V\frac{|D^v|}{|D|} Gini(D^v)$
在候选属性集合中，选择使得划分后基尼指数最小的属性作为最优划分属性。

剪枝处理

剪枝是决策树算法应对过拟合的主要手段。在决策树学习过程中，为了尽可能正确分类训练样本，结点划分过程不断重复，有时会造成决策树分支过多，导致过拟合。

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

预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点；
预剪枝使得决策树的很多分支没有展开，不仅降低了过拟合的风险，而且显著减少了训练和测试时间开销，但是带来了欠拟合的风险。
后剪枝是指先从训练集生成一棵完整的决策树，然后自底向上地对非叶子结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点。
后剪枝通常比预剪枝保留了更多的分支，欠拟合风险小，但是由于其是在完成生成决策树后进行的，训练时间开销大很多。

连续与缺失值

连续值处理

由于连续属性的可取值数目不再有限，因此，不能直接根据连续属性的可取值来对结点进行划分。此时，连续属性离散化技术可派上用场。最简单的策略是采用二分法对连续属性进行处理。

与离散属性不同，若当前结点划分属性为连续属性，该属性还可作为其后代结点的划分属性。

缺失值处理

1.如何在属性值缺失的情况下选择划分属性？

给定训练集 $D$ 和属性 $a$ ，令 $\tilde{D}$ 表示 $D$ 中在属性 $a$ 上没有缺失值的样本集合， $\rho$ 表示属性 $a$ 无缺失值的样本所占的比例，则 $Gain(D, a) = \rho \times Gain(\tilde{D}, a)$

2.若样本在划分属性上的值缺失，如何对样本进行划分？

若样本 $x$ 在划分属性 $a$ 上的取值未知，则将 $x$ 同时划入所有子节点，并赋予不同的权重。

多变量决策树

若我们把每个属性视为坐标空间中的一个坐标轴，则决策树所形成的的分类边界是轴平行(axis-parallel)的，即它的分类边界由若干个与坐标轴平行的分段组成。这样的分类边界使得学习结果具有较好的可解释性，因为每一段划分都直接对应了某个属性取值。

当学习任务的真实分类边界比较复杂时，必须使用很多段划分才能获得较好的近似，此时决策树可能非常复杂，由于要进行大量的属性测试，时间开销也会很大。若能使用斜的划分边界，则决策树模型将大为简化。

多变量决策树就是能实现斜划分甚至更复杂划分的决策树。在此类决策树中，非叶子节点不再是仅针对某个属性，而是对属性的线性组合进行测试，即每个非叶子结点对应一个线性分类器。在多变量决策树的学习过程中，不是为每个非叶子结点寻找一个最优划分属性，而是试图建立一个合适的线性分类器。

《西瓜书》
《南瓜书》

机器学习（4）
本章节是对我学习完机器学习（周志华）第四章所做出来的总结第四章决策树 4.1 基本流程一般的，一棵决策树包...
第四章决策树
第四章决策树 4.1 基本流程一颗决策树一个根结点，若干内部结点，若干叶结点。数据结构中结点是专用的。叶...
《机器学习》西瓜书学习笔记（三）
上一篇笔记在这里：《机器学习》西瓜书学习笔记（二）第四章决策树 4.1 基本流程决策树的生成是一个递归过程，...
机器学习西瓜书 Day04 决策树
p73 - p97 第四章决策树 4.1 基本流程一棵决策树包含一个根节点，若干个内部节点和若干个叶节点；叶节...
机器学习6-决策树
一. 决策树概述 1.1 什么是决策树决策树输入: 测试集决策树输出: 分类规则(决策树) 1.2 决策树算法概...
决策树
1、决策树决策树学习通常包括3个步骤：特征选择。决策树生成。决策树剪枝。决策树的学习目标是：根据给定的训...
决策树
决策树决策树模型与学习特征选择决策树的生成决策树的剪枝 CART 算法决策树模型呈树形结构，在分类问题中...
决策树算法总结
目录一、决策树算法思想二、决策树学习本质三、总结一、决策树（decision tree）算法思想：决策树...
机器学习 - 决策树算法[一]
1 决策树模型与学习 1.1 决策树模型决策树定义：分类决策树模型是一种描述对实例进行分类的树形结构。决策树由...
机器学习系列（三十六）——回归决策树与决策树总结
本篇主要内容：回归决策树原理、回归树学习曲线、决策树总结回归决策树原理回归决策树树是用于回归的决策树模型，回归...

第四章决策树

基本流程

划分选择

信息增益

增益率

基尼指数