《机器学习》周志华西瓜书学习笔记（四）：决策树

【机器学习】《机器学习》周志华西瓜书 笔记/习题答案 总目录

• https://blog.csdn.net/TeFuirnever/article/details/96178919

——————————————————————————————————————————————————————

• 【机器学习】《机器学习》周志华西瓜书习题参考答案：第4章 - 决策树
• 【机器学习】《机器学习实战》读书笔记及代码：第3章 - 决策树

决策树

决策树（decision tree）是一类常见的机器学习方法，既可以做分类也可以做回归的模型。

这一章的内容大致如下：

• 基本流程：决策树是如何决策的？决策树学习的目的是什么？如何生成一棵决策树？

• 划分选择：怎样选择最优划分属性？有哪些判断指标？具体是怎样运作的？

• 剪枝处理：为什么要剪枝？如何判断剪枝后决策树模型的泛化性能是否提升？预剪枝和后剪枝是怎样工作的？有什么优缺点？

• 连续与缺失值：如何把连续属性离散化？如何基于离散化后的属性进行划分？和离散属性有何不同？如何在属性值缺失的情况下选择最优划分属性？给定划分属性，如何划分缺失该属性值的样本？

• 多变量决策树：决策树模型的分类边界的特点是怎样的？多变量决策数是如何定义的？又是如何工作的？

基本流程

顾名思义，决策树（decision tree） 是基于树结构来进行决策的，这恰是人类在面临决策问题时一种很自然的处理机制。例如，我们要对"这是好瓜吗？“这样的问题进行决策时，通常会进行一系列的判断或"子决策”：我们先看"它是什么颜色？"，如果是"青绿色"，则我们再看"它的根蒂是什么形态？"，如果是"蜷缩"，我们再判断"它敲起来是什么声音？"，最后，我们得出 最终决策：这是个好瓜。这个决策过程如图所示：

显然，决策过程的最终结论对应了我们所希望的判定结果，例如 “是” 或 “不是” 好瓜；决策过程中提出的每个判定问题都是对某个属性的 “测试”，例如 “色泽=?” “根蒂=?”；每个测试的结果或是导出最终结论，或是导出进一步的判定问题，其考虑范国是在上次决策结果的限定范围之内，例如若在 “色泽=青绿” 之后再判断 “根蒂=?”，则仅在考虑青绿色瓜的根蒂。

一般地，一棵决策树可以分成三个部分：一个 根结点、若干个 内部结点 和若干个 叶结点。叶结点 对应于 决策结果，其他每个 结点 则对应于一个 属性测试；每个 结点 包含的样本集合根据属性测试的结果被划分到子结点中；根结点 包含 样本全集。从根结点到每个叶结点的路径对应了一个 判定测试序列。

决策就是从根节点开始走到叶节点的过程。每经过一个节点的判定，数据集就按照答案（属性值）划分为若干子集，在子节点做判定时只需要考虑对应的数据子集就可以了。

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

决策树生成是一个 递归过程，遵循简单且直观的“分而治之”（divide-and-conquer）策略：

在决策树基本算法中，有三种情形会导致递归返回：

(1) 当前结点包含的样本全属于同一类别，无需划分；
(2) 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分；
(3) 当前结点包含的样本集合为空，不能划分。

在第(2)种情形下，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在第(3)种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别。

注意：这两种情形的处理实质不同：情形(2)是在利用当前结点的 后验分布，而情形(3)则是把父结点的样本分布作为当前结点的 先验分布。

划分选择

在决策树模型中，我们不断进行判定的初衷是希望 划分后需要考虑的可能更少，准确地说，是希望所得子节点的 纯度（purity） 更高（也可以说是混乱程度更低）。

信息熵（information entropy） 是一种衡量样本集合纯度的常用指标：

$Ent(D) = -sum_{k=1}^{|mathcal{Y}|}p_klog_2p_k$

解析：




南瓜书——https://datawhalechina.github.io/pumpkin-book/#/

一定要记得最前面的负号！！！ 其中 $|mathcal{Y}|$ 为类别集合，$p_k$ 为该类样本占样本总数的比例。

Ent(D)值越大，信息熵越大，表示样本集的混乱程度越高，纯度越低。$Ent(D)$ 的最小值为0，最大值为$log_2|mathcal{Y}|$。

信息增益

信息增益（information gain） 是 ID3算法 采用的选择准则，定义如下：

$Gain(D,a) = Ent(D) - sum_{v=1}^{V}frac{|D^v|}{|D|}Ent(D^v)$

解析：

南瓜书——https://datawhalechina.github.io/pumpkin-book/#/

它描述的是按某种属性划分后纯度的提升，一般而言，信息增益越大，代表用属性a进行划分所获得的纯度提升越大。

其中 $V$ 表示属性 $a$ 的属性值集合，$D^v$ 表示属性值为 $v$ 的数据子集。求和项也称为条件熵，我们可以理解为它是先求出每个数据子集的信息熵，然后按每个数据子集占原数据集的比例来赋予权重，比例越大，对提升纯度的帮助就越大。

多个属性都取得最大的信息增益时，任选一个即可。

信息增益又称为 互信息（Mutual information）。

• 一个连续变量$X$的不确定性，用方差$Var(X)$来度量
• 一个离散变量$X$的不确定性，用熵$H(X)$来度量
• 两个连续变量$X$和$Y$的相关度，用协方差或相关系数来度量
• 两个离散变量$X$和$Y$的相关度，用互信息$I(X;Y)$来度量(直观地，$X$和$Y$的相关度越高，$X$对分类的作用就越大)

（信息）增益率

增益率（gain ratio） 是 C4.5算法 采用的选择准则，定义如下：

$Gain\_ratio(D,a) = frac{Gain(D,a)}{IV(a)}$

其中，

$IV(a) = -sum_{v=1}^Vfrac{|D^v|}{|D|}log_2frac{|D^v|}{|D|}$

一定要记得最前面的负号！！！ $IV$称为属性的 固有值（intrinsic value），它的定义和信息熵是类似的，信息熵衡量的是样本集在类别上的混乱程度，而 固有值衡量的是样本集在某个属性上的混乱程度。固有值越大，则该属性混乱程度越高，可能的取值越多。

之所以要定义增益率是为了避免模型过份偏好用取值多的属性作划分。这是使用信息增益作准则非常容易陷入的误区，比方说每个样本都有一个“编号”属性，这个属性的条件熵肯定是最小的，但如果选择了该属性作为根节点，那么构建出的决策树就没有任何意义了，因为这个模型根本不具备泛化性能。

注意了，C4.5并非直接选择增益率最高的属性，它使用了一个 启发式：先从候选划分属性集中找到信息增益高于平均水平的属性，然后再比较这些候选属性的增益率，从中选择增益率最高的。

基尼指数

基尼指数（Gini index） 是 CART算法 采用的选择准则，定义如下：

CART 是 Classification and Regression Tree 的简称，这是一种著名的决策树学习算法，分类和回归任务都可用。

数据集 $D$ 的纯度可用基尼值来度量：

$Gini(D) = sum_{k=1}^{|mathcal{Y}|}sum_{k' eq k}p_kp_{k'}\ =1-sum_{k=1}^{|mathcal{Y}|}p_k^2$

解析：

南瓜书——https://datawhalechina.github.io/pumpkin-book/#/

基尼值是另一种衡量样本集纯度的指标。直观来说， Gini(D) 反映了从数据集D 中随机抽取两个样本，其类别标记不一致的概率。因此，Gini(D) 越小，基尼值越小，则数据集D 的纯度越高。属性α 的基尼指数定义：

$Gini\_index(D,a) = sum_{v=1}^{V}frac{|D^v|}{|D|}Gini(D^v)$

由基尼值引伸开来的就是基尼指数这种准则了，基尼指数越小，表示使用属性 $a$ 划分后纯度的提升越大。

剪枝处理

剪枝（pruning） 是决策树学习算法应对 过拟合 的主要手段。在决策树学习中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，这时就可能因训练样本学得 “太好” 了，以致于把训练集自身的一些特点当作所有数据都具有的一般性质而导致 过拟合。因此，可通过 主动去掉一些分支 来降低过拟合的风险。

怎么判断剪枝有没有用呢？具体来说就是 判断剪枝后模型的泛化性能有没有提升？这就涉及到【机器学习】《机器学习》周志华西瓜书读书笔记：第2章 - 模型评估与选择 的内容了。不过这里不用做比较检验，我们需要做的首先是 选定一种评估方法划分训练集和测试集，然后 选定一种性能度量 用来衡量剪枝前后的模型在测试集上的效果。

预剪枝

预剪枝（prepruning） 是在决策树生成的过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升（比方说，划分后在测试集上错得更多了 / 划分前后在测试集上效果相同），就停止划分并将当前节点标记为叶节点。

后剪枝

后剪枝（postpruning） 是先从训练集生成一颗完整的决策树，然后自底向上地逐个考察非叶节点，若将该节点对应的子树替换为叶节点能带来决策树泛化性能的提升，则将该子树替换为叶节点。实际任务中，即使没有提升，只要不是性能下降，一般也会剪枝，因为根据奥卡姆剃刀准则，简单的模型更好。

特别地，只有一层划分（即只有根节点一个非叶节点）的决策树称为 决策树桩（decision stump）。

优缺点

• 预剪枝是一种贪心策略，因为它在决策树生成时就杜绝了很多分支展开的机会，所以不但 降低了过拟合的风险，同时也 显著减少了模型的训练时间开销和测试时间开销。但是！这种贪心策略有可能导致 欠拟合，因为有可能当前划分不能提升模型的泛化性能，但其展开的后续划分却会显著提升泛化性能。在预剪枝中这种可能被杜绝了。

• 后剪枝是种比较保守的策略，欠拟合的风险很小，泛化性能往往优于预剪枝的决策树。但是由于后剪枝是在生成了完整决策树后，自底向上对所有非叶节点进行考察，所以 训练时间开销要比未剪枝决策树和预剪枝决策树都大得多。

连续与缺失值

连续值

前面线性模型已经谈到了离散属性连续化，而决策树模型需要的则是 连续属性离散化，因为决策树 每次判定只能做有限次划分。最简单的一种离散化策略是C4.5算法采用的 二分法（bi-partition）。

给定一个包含连续属性 $a$ 的数据集，并且 $a$ 在数据集中有 $n$ 个不同取值，我们先把属性 $a$ 的 $n$ 个属性值 从小到大进行排序。所谓“二分”是指将这些属性值分为两个类别。这就产生了一个新问题，怎么找到合适的划分点呢？

在对连续属性值排序完之后，由于有 $n$ 个不同取值，取 每两个取值的平均值作为划分点 的话，就有 $n-1$ 个候选划分点。我们需要做得就是按照准则（比方说 用ID3算法的话就是信息增益）进行 $n-1$ 次判断。每次拿出一个候选划分点，把连续属性分为两类，转换为离散属性。然后基于这个基础计算准则，最终选出一个最优的属性值划分点。

注意！和离散属性不同，连续属性用于当前节点的划分后，其 后代节点依然可以使用该连续属性进一步划分。

缺失值

缺失值在实际任务中是非常常见的，如果直接丢弃包含缺失值的样本会造成极大的浪费。具体来说缺失值的处理分以下两个部分：

• 如何在属性值缺失的情况F进行划分属性选择？

假设数据集为 $D$，有缺失值的属性为 $a$，令 $ilde{D}$ 表示 $D$ 中没有缺失属性 $a$ 的样本子集。我们只能基于 $ilde{D}$ 来判断属性 $a$ 的优劣。但是我们又希望包含缺失值的样本也能在建模过程体现出一定的影响，因此要重新定义准则。在那之前，先定义几个新定义用到的变量：

$ho = frac{sum_{mathbf{x} in ilde{D}}w_mathbf{x}}{sum_{mathbf{x} in D}w_mathbf{x}}$

$ilde{p_k} = frac{sum_{mathbf{x} in ilde{D_k}}w_mathbf{x}}{sum_{mathbf{x} in ilde{D}}w_mathbf{x}},quad (1 leq k leq |mathcal{Y}|)$

$ilde{r_v} = frac{sum_{mathbf{x} in ilde{D^v}}w_mathbf{x}}{sum_{mathbf{x} in ilde{D}}w_mathbf{x}},quad (1 leq v leq V)$

$ho$ 表示 无缺失值样本所占的比例;

$ilde{p_k}$ 表示 无缺失值样本中第 $k$ 类所占的比例;

$ilde{r_v}$ 表示 无缺失值样本中在属性 $a$ 上取值 $a^v$ 的样本所占的比例 ;

注意，这里的 $w_mathbf{x}$ 表示样本的权值，它是 含缺失值样本参与建模的一种方式。在根节点处初始时，所有样本 $mathbf{x}$ 的权重都为1。

接下来重新定义信息熵和信息增益，推广到样本含缺失值的情况：

$Ent( ilde{D}) = -sum_{k=1}^{|mathcal{Y|}} ilde{p_k}log_2 ilde{p_k}$

$Gain(D,a) = ho imes Gain( ilde{D},a)\ = ho imes (Ent( ilde{D}) - sum_{v=1}^V ilde{r_v}Ent( ilde{D^v}))$

按照新的定义来计算包含缺失值的属性的信息增益，然后和其他属性的信息增益相比，选出最优的。

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

假设有一个包含缺失值的属性被计算出是最优划分属性，那么我们就要按该属性的不同取值划分数据集了。缺失该属性值的样本怎么划分呢？答案是 按概率划分，这样的样本会被 同时划入所有子节点，并且其 权重更新 为对应的 $ilde{r_v} dot w_mathbf{x}$。

可以把无缺失值的决策树建模想象为各样本权值恒为1的情形，它们 只对自己所属的属性值子集作贡献。而样本含缺失值时，它会 以不同的概率对所有属性值子集作贡献。C4.5 算法使用了上述解决方案。

多变量决策树

前面提到的决策树都是 单变量决策树（univariate decision tree）， 即在每个节点处做判定时都只用到一个属性。它有一个特点，就是形成的 分类边界都是轴平行（axis-parallel）的。

如果把属性都当作坐标空间中的坐标轴，由于我们建模时假设样本的各属性之间是没有关联的，所以 各坐标轴是相互垂直的。而决策数每次只取一个确定的属性值来划分，就等同于 画一个垂直于该属性坐标轴的超平面（只有两个属性时就是一条线），它 与其他坐标轴都是平行的，这就是轴平行。最终由多个与坐标轴平行的超平面组成分类边界。

这样有一个弊端就是，如果真实分类边界特别复杂，就需要画出很多超平面（线），在预测时就需要继续大量的属性测试（遍历决策树）才能得到结果，预测时间开销很大。

多变量决策树（multivariate decision tree），顾名思义，它不再是选择单个最优划分属性作为节点，而是试图寻找一个 最优的多属性的线性组合 作为节点，它的每个非叶节点都是一个形如 $sum_{i=1}^d w_ia_i = t$ 的线性分类器。多变量决策树的决策边界能够 斜着走，甚至 绕曲线走，从而用更少的分支更好地逼近复杂的真实边界。

决策树的优劣总结

根据sklearn官网 - 1.10.Decision Trees总结如下：

1. 优势（Advantages）：

   • 易理解，解释性好，易可视化；
   • 数据预处理少；
   • 复杂度O(logN)；
   • 支持标称变量+连续变量；
   • 支持多输出；
   • 白盒模型，布尔逻辑；
   • 模型好坏易验证；
   • 容忍先验知识错；

2. 劣势（Disadvantages）：

   • 决策树生成易太大、过拟合；（需要剪枝、设置树最大深度等后续操作。）
   • 模型生成不稳定，易受小错误样本影响；
   • 学习最优模型是N-P难题，贪心搜索易陷入局部最优；（可采用随机初始化生成多个模型。）
   • 不支持非线性逻辑，如XOR；
   • 数据不平衡时生成的树形差；