第四章：决策树

4.1 基本流程4.1.1 决策树的结构4.1.2 决策树学习基本算法 4.2 划分选择4.2.1 决策树学习的关键4.2.2 信息增益(information gain)信息熵属性a的信息增益$Gain(D,a)$ 4.2.3 增益率(gain ratio)4.2.4 基尼指数(Gini index)基尼值基尼指数(Gini index) 4.3 剪枝处理（决策树对付过拟合的主要手段）4.3.1 预剪枝(prepruning)4.3.2 后剪枝(postpruning) 4.4 连续与缺失值4.4.1 连续值处理4.4.2 缺失值处理4.4.2.1 如何在属性值缺失的情况下进行划分属性选择？4.4.2.2 样本在划分属性上缺失值，如何对样本进行划分 4.5 多变量决策树4.6 阅读材料

4.1 基本流程

4.1.1 决策树的结构

一般的，决策树包含一个根结点，多个内部结点和多个叶结点叶结点表示决策结果（好瓜，坏瓜）：根据叶结点里面的的样本集合判定该叶结点的决策结果内部结点和根结点对应属性测试（attr=?）：将结点内的样本集合根据属性测试的结果划分到各个子结点；根结点包含样本全集从根结点到每个叶结点的路径即对应着一个判定测试序列仅有一层划分的决策树，也称“决策树桩”(decision stump)

4.1.2 决策树学习基本算法

决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树，其基本流程遵循简单且直观的分而治之（divide-and-conquer）策略。 可见，决策树的生成是一个递归过程。在决策树的基本算法中，有三种情形会导致递归返回： (1)当前结点包含的样本全属于同一类，无需划分 (2)当前属性集为空，或所有样本在所有属性上取值相同，无法划分 (3)当前结点包含的样本为空，不能划分

对各种情形的处理方式：

\quad 情形(2)：属性集为空或所有样本属性上取值相同

把当前结点标记为叶结点，其类别设定为该结点样本集合中最多的类别；此为利用当前结点的后验分布

\quad 情形(3)：样本为空

把当前结点标记为叶结点，其类别设定为父结点样本集合中最多的类别把父结点的样本分布作为当前结点的先验分布

4.2 划分选择

4.2.1 决策树学习的关键

决策树学习的关键是如何选择最优划分属性 一般而言，随着划分过程的不断进行，我们希望决策树的分直接点所包含的样本尽可能属于同一类别，即结点的纯度(purity)越来越高。（也即信息熵越低）

4.2.2 信息增益(information gain)

信息熵

度量样本集合纯度最常用的一种指标是信息熵(information entropy) 样本集合$D$中第$k$类样本所占比例为$p_k$(k=1,2,…,$|\gamma |$)，则集合$D$的信息熵定义为： $$Ent(D)=-\sum _{k=1}^{|\gamma |}{p}_k{\log }_2{p}_k\text{\hspace{1em}(4.1)}$$ $Ent(D)$的值越小，则$D$的纯度越高。 注1：信息熵可以理解为信息的不确定性，《数学之美》第6章有很形象的例子介绍。 注2：信息熵最小值为0，最大值为${\log }_2|\gamma |$ 最小值为0：:在中越法中猜世界杯冠军 最大值为${\log }_2|\gamma |$：样本$D$中$|\gamma |$类样本均匀分布（信息不确定性最大），即$p_k=\frac{1}{|\gamma |}$，代入式(4.1)可得$Ent(D)={\log }_2|\gamma |$

属性a的信息增益$Gain(D,a)$

属性$a$的$V$个可能的取值：$\left\{a^1,a^2,\dots ,a^V\right\}$ 第$v$个结点包含的$D$中所有属性$a$取值为$a^v$的样本：$D^v$ 每个分支节点的权重：$\frac{|D^v|}{|D|}$，即样本数越多的结点影响越大 \quad 用属性$a$对样本集$D$进行划分所获得的信息增益为： $$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)\text{\hspace{1em}(4.2)}$$ 一般而言，信息增益越大，表示用属性$a$作为划分属性所获得的==“纯度提升”越大== 注：著名的ID3决策树学习算法就是用信息增益来选择划分属性

信息增益的示例在西瓜书P75

4.2.3 增益率(gain ratio)

信息增益准则对可取值较多的属性有所偏好（分支越多，每个分支结点的样本就越少，则每个分支结点纯度就越大；极端情形为每个分支节点只有一个样本）

C4.5决策树算法使用增益率来选择最优划分属性，增益率定义为： $$Gain\_ratio(D,a)=\frac{Gain(D,a)}{IV(a)}\text{\hspace{1em}(4.3)}$$ 其中， $$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}{\log }_2\frac{|D^v|}{|D|}\text{\hspace{1em}(4.4)}$$ 称为属性$a$的固有值(intrinsic value)

属性$a$的可能取值越多（即V越大），则$IV(a)$的值通常会越大（以此调整也越大的信息增益）

\qquad 需注意，信息增益率对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接根据增益率选择最优划分属性，而是使用了一个启发式：

先从候选划分属性中选择出信息增益高于平均水平的几个属性再从选择出的属性中选择增益率最高的属性作为划分属性

即C4.5选择的最优划分属性是信息增益高于平均水平且信息增益率最大的属性

4.2.4 基尼指数(Gini index)

CART是Classfication and Regression Tree的简称，这是一种著名的决策树学习算法，分类和回归任务都可用 CART决策树使用基尼指数来选择最优划分属性

基尼值

数据集$D$的纯度可用基尼值来度量： $$Gini(D)=\sum _{k=1}^{|\gamma |}\sum _{k̸=k^{{}^{\prime }}}{p}_k{p}_{k^{{}^{\prime }}},$$$$=1-\sum _{k=1}^{|\gamma |}{p}_k^2\text{\hspace{1em}(4.5)}$$ 直观来说，$Gini(D)$反映了从数据集$D$中随机抽取两个样本，其类别标记不同的概率 因此，$Gini(D)$越小，数据集$D$的纯度越高

注：基尼值与信息熵都是越小则说明纯度越高；

基尼指数(Gini index)

属性$a$的基尼指数定义为： $$Gini\_index(D,a)=\sum _{v=1}^V\frac{|D^v|}{|D|}Gini(D^v)\text{\hspace{1em}(4.6)}$$ 于是，我们在候选属性中选择使得划分后基尼指数最小的属性作为最优划分属性

4.3 剪枝处理（决策树对付过拟合的主要手段）

剪枝(pruning)是决策树学习算法对付“过拟合”的主要手段。决策树分支过多，可能把训练集中的一些特性当作所有数据都具有的一般性质而导致过拟合。

因此，可主动剪枝降低过拟合的风险。 剪枝的基本策略有预剪枝和后剪枝，剪枝与否则要看剪枝前后决策树的泛化性能的变化情况。

决策树泛化性能的评估：这里采用留出法，预留一部分数据做测试集，用测试集的样本在决策树中的判断准确率来作为泛化性能的近似

留出法在西瓜书P25

4.3.1 预剪枝(prepruning)

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

留出法要求训练集和测试集的数据分布一致，类别比例相似，即采用分层采样。

预剪枝步骤： \quad 第一步：将数据集按留出法要求划分为训练集和测试集 \quad 第二步：对训练集的所有样本基于某种指标（西瓜书的示例以信息增益为准则）选出最优划分属性，根据该结点划分前后的泛化性能差异判断该结点是否要根据该最优划分属性划分结点。 \quad 第三步：若划分了若干个结点，则继续对各个分支结点重复第二步的操作（第二步的“所有样本”转变成划分到该分支结点的样本子集，之后的计算都是基于对应的子集进行的），同时根据前面的三种情形做叶结点的判断，最终生成一棵决策树。 对比图4.6和图4.5可以看出，预剪枝使得决策树的很多分支都没有展开，优缺点是：

预剪枝决策树优点：

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

预剪枝决策树缺点： 需要注意的是，虽然有些分支的当前划分不能提升泛化性能，甚至可能导致泛化性能下降，但在其基础上进行的后续划分却有可能显著提升决策树的泛化性能！ 预剪枝基于贪心的本质禁止这些分支展开，给预剪枝决策树带来了欠拟合的风险。

4.3.2 后剪枝(postpruning)

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

后剪枝步骤： \quad 第一步：将数据集按留出法要求划分为训练集和测试集 \quad 第二步：对训练集的所有样本基于某种指标（西瓜书的示例以信息增益为准则）选择最优划分属性，划分每一个可以划分的结点（先不比较泛化性能），生成一棵完整的未剪枝决策树（此时已经可以根据验证集得到该棵决策树的验证集精度） \quad 第三步：从下而上对各个分支结点逐个进行如下操作：若该分支结点不展开，计算此时决策树的验证集精度，若验证集精度提高或不变，则剪枝不展开该结点。

注：若验证集精度保持不变，根据奥卡姆剃刀准则，还是要进行剪枝，实际的决策树算法在此种情况下会进行剪枝。

对比图4.7和图4.6可看出，后剪枝决策树通常比预剪枝决策树保留了更多的分支，优缺点如下：

后剪枝决策树优点：

保留更多分支，使得欠拟合风险很小泛化性能往往优于预剪枝决策树

后剪枝决策树缺点：

后剪枝是在生成决策树后进行的，并且还要自底向上对书中每个非叶结点逐一考察，因此训练时间开销大

4.4 连续与缺失值

4.4.1 连续值处理

\quad 之前讨论的都是基于离散属性来生成决策树，但现实任务中常会遇到连续属性，以下则讨论决策树生成过程中如何处理连续属性。

最简单的策略是采用二分法（这也是C4.5决策树算法采用的机制），这就相当于该连续属性是每次都只有两个取值（小于等于 t 和大于 t）的离散属性，以此来划分样本。

给定样本集$D$和连续属性$a$，$a$在$D$上出现了n个不同的取值，将这些值从小到大排序，记为$\{a^1,a^2,...,a^n\}$基于划分点 t 可将$D$划分为子集$D_t^{-}$和$D_t^{+}$（即划分为在属性a上取值小于等于 t 的子集和大于 t 的子集）t 的取值在区间$[a^i,a^{i+1})$，实际上即为不大于该区间的中位点$\frac{a^i+a^{i+1}}{2}$的最大值，从而使得最终决策树使用的划分点都在训练集中出现过因此，对于出现n个值的连续属性$a$，我们可考察包含$n-1$个元素的候选划分点集合 $$T_a=\{\frac{a^i+a^{i+1}}{2}|1\le i\le n-1\}$$

于是，根据这些划分点我们就可以像处理离散值一样考察这些划分点，选取最优的划分点进行样本集合的划分。（划分点 就相当于 划分属性）

示例在西瓜书P85

4.4.2 缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。 在此背景下，我们需要解决的两个问题：

如何在属性值缺失的情况下进行划分属性选择？给定了划分属性，若样本在该属性上的值缺失，如何对样本进行划分

给定样本集$D$和连续属性$a$，$\tilde{D}$表示$D$中在属性$a$上没有缺失值的样本子集。

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

对于问题(1)，显然我们仅可根据$\tilde{D}$来判断属性$a$的优劣为了不浪费数据，将总样本分布视为无缺失分布，我们用无缺失值的样本所占比例 $p$ 来修正计算出的无缺失样本集的信息增益Gain$(\tilde{D},a)$，以此来近似为全部样本的信息增益Gain$(D,a)$（详见公式(4.12)）

对于属性$a$，

$p$表示无缺失值样本所占的比例${\tilde{p}}_k$表示无缺失值样本中第k类所占的比例${\tilde{r}}_v$表示无缺失值样本在属性$a$上取值$a^v$的样本所占的比例 基于上述定义，有缺失值的样本的信息增益计算式为 $$Gain(D,a)=p\times Gain(\tilde{D},a)$$$$=p\times (Ent((\tilde{D})-{\tilde{r}}_v\sum _{v=1}^{V}Ent({\tilde{D}}^v))\text{\hspace{1em}(4.12)}$$ 其中，由式(4.1)有 $$Ent(\tilde{D})=-\sum _{k=1}^{|\gamma |}{\tilde{p}}_k{\log }_2{\tilde{p}}_k$$

4.4.2.2 样本在划分属性上缺失值，如何对样本进行划分

C4.5算法采用了以下的方案： 注：每个样本初始时都被赋予权重$w_x$，初始化为1

若样本$x$在划分属性$a$上的取值已知，则将$x$划入与其取值对应的子结点，且样本权值在子结点中保持为$w_x$若样本$x$在划分属性$a$上的取值未知，则将$x$同时划入所有子结点，且样本权值在与属性值$a^v$对应的子结点中调整为${\tilde{r}}_v\ast w_x$（即让同一样本以不同的概率划分到子结点中，即可看到许多子结点中有同一样本，只是带的权重大小不一样，由${\tilde{r}}_v$决定） 示例在西瓜书P87

4.5 多变量决策树

若将每个属性视为坐标空间中的一个坐标轴，则d个属性描述的样本就对应了d维空间中的一个数据点，对样本分类则意味着在这个坐标空间中寻找不同类样本的分类边界。决策树形成的分类边界由若干个与坐标轴平行的分段组成，这些分类边界使得学习结果有较好的可解释性，因为每一段划分都对应了一个属性的取值的划分。

但是，当学习任务的真实分类边界比较复杂时，就需要有很多的分段才能有较好的近似，此时的决策树会相当复杂，需进行大量属性测试，时间开销很大。 基于以上几点，我们想到若能使用斜的划分边界(如图4.12的红线所示)，则决策树模型将大为简化。

多变量决策树正是适合能实现这样的“斜划分”甚至更复杂划分的决策树。

在此类决策树中，非叶结点不再是仅对某个属性，而是对属性的线性组合进行测试，即每个非叶结点是一个形如${\sum }_{i=1}^d{w}_i{a}_i=t$的线性分类器，其中$w_i$是属性$a_i$的权重，$w_i$和 t 可在结点的样本集和属性集上学得。 注：线性分类器看第三章 多变量决策树与传统的单变量决策树(univariate decision tree)不同，多变量决策树在学习过程中不是为每个非叶结点寻找最优划分属性，而是试图建立一个合适的线性分类器。

4.6 阅读材料

决策树学习算法最著名的代表是ID3 , C4.5 , CART

C4.5Rule是一个将C4.5转化为符号规则的算法，最终规则集的泛化性能甚至可能优于原决策树

除了信息增益，增益率，基尼指数之外，还有许多其他准则用于决策树划分选择，要注意的是，虽然这些准则对决策树的尺寸有较大影响，但对泛化性能影响很有限

本质上，各种特征选择方法君可用于决策树的划分属性选择（见第11章）

信息增益和基尼指数仅在2%的情况下会有所不同

剪枝方法和程度对决策树的泛化性能的影响相当显著，在数据带有噪声时通过剪枝甚至可将决策树的泛化性能提高25%

多变量决策树算法主要有OC1和[Brodley and Utgoff,1995]提出的一系列算法

OC1先贪心地寻找每个属性的最优权值，在局部优化的基础上再对分类边界进行随机扰动以试图找到更好的边界

[Brodley and Utgoff,1995]直接引入线性分类器学习的最小二乘法

一些多变量决策树算法在决策树的叶结点上嵌入神经网络，以结合这两种学习机制的优势（如感知机树）

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