第五章决策树-EW帮帮网

5.1 决策树模型与学习

说起决策树来，它不是一般的树，而是有理想有抱负的树，那么为什么这么讲呐？

5.1.1 思维模式

人类有两大逻辑思维：归纳法和演绎法。决策树是为了实现某一个目标而构建的树形结构。

我想看一下情人节这一天，大家是怎么过的，以这个例子为例，建立一棵决策树：

由于是情人节，我们首先需要考虑的是是否是单身。

如果不是单身，那么当天的活动安排就要将对方考虑在内，如果对方需要陪伴，那么就是各种花式虐狗行为了；如果不需要陪伴，就要看你当天是否有任务，如果有任务，我们就安排去学习，没有任务的话，就安排一些娱乐活动了（比如：男生喜欢打游戏，女生则刷刷剧）。

如果是单身，可能会考虑提升自我，想提升自我的小伙伴，可能会考虑内修还是外练，想要内在气质提升，就可能会去学习，想提升外在，就可能去运动；还有一些在情人节不想提升自己的小伙伴，可能会去娱乐。

以上就是一棵决策树，当然这是我们主观构造的决策树，现实生活中可能会更加复杂。kd树是二叉树，而决策树是多叉树。

现在我们看一个客观的例子，这是一个是否可以放贷款的例子：

5.1.2 模式结构

分类决策树模型是一种描述对实例进行分类的树形结构。

决策树由结点和有向边组成，结点又有内部结点和叶结点组成，其中，内部结点用圆圈表示，叶结点用方框表示。内部结点表示特征或属性，叶结点表示类别。

决策树是通过一系列规则（if-then）对数据进行分类的过程。其实从本质上来说，决策树就是从根节点到叶节点的过程。从根节点出发到叶节点所经过的称为路径，而这条路径就对应着一条规则，这条规则是用if-then组成的。

先判断是否是单身，如果不是的话，看对方是否需要陪伴；如果不需要陪伴，看你是否有任务；如果有任务的话就得到一个学习的活动安排。

我们现在看一下是不是每一个叶节点都对应着一个规则呢？是的，每一个叶节点都对应着一个规则，而且每一个叶节点所对应的规则都不一样。一个叶节点或一个类，它可能对应多条路径，但是每一个实例都对应着一条路径。

If-then规则是互斥且完备的。互斥是指这个属性所分的叉，它是互相之间没有交集；完备是指分完地叉合在一起是合集。

构建决策树的规则如下：

5.1.3 条件概率分布

对于决策树而言，表示给定特征条件下类的条件概率分布P(Y|X)，这就是说，决策树可以表示成在给定的特征条件下类的条件概率分布；而条件概率分布对应着特征空间的一个划分，如果我们有十个条件概率分布，对应着特征空间的十个划分，其实就相当于我们构建了十棵决策树，至于哪一棵决策树表现更好，就要看决策树学习了。

特征空间是由特征向量组成的，而特征向量用来表示输入的每一个实例，所以一般情况下我们可以认为输入空间与特征空间是相同的。比如说，下图中所表示的特征空间是： $\begin{Bmatrix} x=(x^{(1)},x^{(2)})^{T}|0\leq x^{(1)}\leq 1,0\leq x^{(2)}\leq 1 \end{Bmatrix}$ 。我们想要得到一个决策树，就需要将这个特征空间划分出来，划分完成后，就得到了一个完整的条件概率分布了。

在划分时，我们所得到的单元或区域是互不相交的，而且这些单元或者区域合在一起就是我们的整个特征空间。我们在讲决策树的规则时，是这样解释路径的互斥和完备的，而且恰好这里的每一个单元其实就是对应着我们之前讲的if-then规则的集合所组成的一条路径，一个单元对应着一条路径。

假如说，我们现在已经完成了对特征空间的划分，将其划分为一个又一个的小单元或小区域可是每个单元或者区域，它所对应的类别是怎么确定的呐？比如说，某个单元c的条件概率满足 $P(Y=+1|X=c)> 0.5$ 时，认为该单元属于正类;某个单元c的条件概率满足 $P(Y=-1|X=c)> 0.5$ 时，认为该单元属于负类。

我们现在由刚才看到的一个平面图变换成一个立体图形来看：

这个立体图形中包含了y=+1的条件概率，我们看一下对于用红色记号标记的区域而言，y=+1的条件概率是大于0.5，这个区域就是正类；对于用蓝色记号标记的区域而言，y=+1的条件概率是小于0.5，这个区域就是负类；对于黑色记号标记的区域而言，y=+1的条件概率是大于0.5，这个区域就是正类。

现在我们一直讲的是两个类别的分类，所以只需要与0.5比大小就可以了；如果我们分了多个类，我们只需呀看一下它们分别的条件概率，，哪一个类的条件概率大，那么就属于哪一个类。

假如，我们将特征空间划分成四个单元，这四个单元命名如下：

这四个单元在决策树中如下：

这就说明，对于决策树而言，特征空间中所划分的每一个单元都对应着决策树中的一条路径；决策树的条件概率分布由各个单元给定条件下类的条件概率分布组成。

5.1.4 决策树学习

已知：训练集 $T=\begin{Bmatrix} (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{N},y_{N}) \end{Bmatrix}$ ，其中 $x_{i}=(x_{i}^{(1)},x_{i}^{(2)},...,x_{i}^{(n)})^{T}$ ， $y_{i}\in \begin{Bmatrix} 1,2,...,k \end{Bmatrix}$ ，i=1,2,...,N

目的：构造决策树，并对实例正确分类

我们看一个贷款申请的例子：

在这个例子中，我们发现有三个特征（n=3，年收入、房产、婚姻状况），两种类别（k=2，可以偿还、无法偿还）。假如我们现在已经根据数据集T得到了这棵决策树，现在我们判一下实例：年收入 $x^{(1)}$ 为75万， $x^{(2)}$ 为无房产，婚姻状况 $x^{(3)}$ 为单身。对于这个实例而言，我们根据决策树可以得到的类别是无法偿还。

构造决策树过程中，产生的问题有：

1.我们根据同一个训练数据集可以构造出几种决策树？

2.在构造决策树过程中，以首选哪一个特征进行分类？第二个、第三个特征又是怎么确定的？

3.如果我们有一个复杂的决策树，我们应该怎么办？

决策树的本质就是从训练数据集T中归纳出一组分类规则，这组规则要与训练数据集不相矛盾。我们可能能训练出无穷多个条件概率模型，一棵好的决策树与训练数据矛盾较小（对已知数据的拟合能力强），同时具有很好的泛化能力（对未知数据的预测能力）。

我们怎样训练出一个模型呐？它的策略就是通过最小化损失函数来实现，而有可能是有无穷多个决策树，决策树树与决策树之间是有区别的，也就是每次选择的特征可能不一样。如何选择最优特征，就是特征选择（递归选择最优特征）将要面临的问题。当对应特征空间有了基本划分，直到所有的训练子集被基本正确划分类就停止我们的算法，之所以这里强调“基本正确分类”而不是“全部正确分类”其实就是为了避免过拟合，为了平衡拟合能力和泛化能力。如果决策树过于枝繁叶茂，为了避免过拟合，具有更好的泛化能力就需要剪枝。

剪枝可以分为预剪枝和后剪枝。预剪枝：比如我们要经营一片果园，我们的目的是想结果，所以果农通常需要修剪果树，使果树不要过高。这样既利于果子得到充足的营养，又避免果树过高而难以采摘，这是在树成长前剪枝。后剪枝：园艺工人为大树修剪特定的形状，这是在树成长后进行剪枝。

5.2 特征选择

我们为什么要对决策树进行特征选择？我们怎样选择出最优的特征？

5.2.1 特征选择问题

我们来看一个例子：这是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的4个特征：第1个特征是年龄，有3个可能值：青年，中年，老年；第2个特征是有工作，有2个可能值：是，否；第3个特征是有自己的房子，有两个可能值：是，否；第4个特征是信贷情况，有两个可能值：非常好，好，一般。有两个类别，可能值为：是，否。

希望通过对所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类，即当新的客户提出贷款申请时，根据申请人的特征利用决策树决定是否批准贷款申请。

如果我们第一个特征选择年龄的话，可以得到下面这样的决策树：

如果以有无工作这个特征作为第一个特征构建决策树，绘制出来的决策树如下：

根据上面这两个决策树我们发现，当我们逊选择不同的特征作为决策树的第一个特征进行构建，所构建出来的决策树是不一样的。当选择年龄作为决策树的一个个特征，我们发现决策树比较复杂；当选择有无工作作为决策树的第一个特征，我们发现构建的决策树比较简单。那么我们该如何选择最优特征呐？

5.2.2 信息增益

信息增益由熵构建而成，熵用来表示随机变量的不确定性。如果随机变量有n个取值的话，每个取值所对应的概率是 $p_{i}$ ，那么这个随机变量x的熵 $H(x)=-\sum_{i=1}^{n}p_{i}logp_{i}$ ，由于此处的熵是和随机变量x的分布有关系，所以也可以表示成 $H(p)=-\sum_{i=1}^{n}p_{i}logp_{i}$ ，这个p就对应着随机变量的分布。

当随机变量的取值等概率分布的时候，相应的熵最大。为什么随机变量的取值等概率分布的时候最大呐？我们通过一个简答的例子计算一下。

假如我们此处的随机变量只有两个取值，一个是1，一个是0，x取1的概率是p，取0的概率是q=1-p，这个随机变量x所对应的熵 $H(x)=-plog_{2}p-(1-p)\cdot log_{2}(1-p)$ ，绘制p和H(p)的图形如下：

当p=0.5时，熵取最大值H(p)=1，除了通过图像的方式知道最大值，还可以通过求导的方式得到最大值。当是凹函数时，可以用求导的方式取得最大值；当时凸函数时，可以用求导的方式得到最小值。

条件熵： $H(Y|X)=-\sum_{i=1}^{n}p_{i}H(Y|X=x_{i})$ 。当熵和条件熵中的概率是由数据估计得到时，则为经验熵和经验条件熵；当熵和条件熵中的概率对应着真是分布的时候，那就是理性熵和真是条件熵。信息增益就是熵减去条件熵，而熵和条件熵都是根据训练数据集计算出来的经验熵和经验条件熵，即 $g(D,A)=H(D)-H(D|A)$ 。

为什么用这样一个差值代表信息增益？上式所对应的D就是训练数据集，H(D)是我们在不知道任何信息的情况下得到的熵，假如我们知道x的某个特征信息A，在已知特征信息的情况下，训练数据集有了一个重新的分类，此时所对应的熵就是根据这个特征信息A而发生的变化。变化越大，就说明由于增加了A特征而更加确定。因此，哪一个特征所带来的信息增益越大，就应该选择哪一个特征作为最优特征。这就是信息增益的作用。

我们具体看一下怎样对信息增益进行求解：

我们现在知道训练数据集D和特征A，期望得到特征A关于D的信息增益g(D,A)。首先计算经验熵，再计算经验条件熵，信息增益就是经验熵减去经验条件熵。

现在通过例题看一下信息增益的计算，继续以贷款例子为例：

经验熵公式为： $H(D)=-\sum_{k=1}^{K}\frac{\left | C_{k} \right |}{\left | D \right |}log_{2}\frac{\left | C_{k} \right |}{\left | D \right |}$

我们把这个训练集记作D，其中包含15个样本，如果不加任何特征的话，我们最终想分为两个类别（不同意贷款，同意贷款），所以类别 K=2， $C_{k}$ 对应不附加任何特征的情况下，它所分的类别。假如 $C_{1}$ 对应不同意贷款，我们发现其中包含了6个样本； $C_{2}$ 对应着同意贷款，包含9个样本。这里的经验熵是根据训练数据集计算出来的，也就是说这个概率是根据D得到的。根据这个训练集得到的不同意贷款的概率是 $\frac{6}{15}$ ，同意贷款的概率是 $\frac{9}{15}$ ，所以此处的经验熵 $H(D)=-\frac{6}{15}log_{2}\frac{6}{15}-\frac{9}{15}log_{2}\frac{9}{15}=0.971$ ，这是不加任何特征的情况下所得到的训练数据集的熵。

接下来我们分别看一下，当我们加上特征的时候所得到的经验熵是多少，这时候计算的就是经验条件熵 $H(D|A)=\sum_{i=1}^{n}\frac{\left | D_{i} \right |}{\left | D \right |}H(D_{i})=-\sum_{i=1}^{n}\frac{\left | D_{i} \right |}{\left | D\right |}\sum_{k=1}^{K}\frac{\left | D_{ik} \right |}{\left | D \right |}log_{2}\frac{\left | D_{ik} \right |}{\left | D \right |}$ 。假如说我们现在加入年龄这一个特征，我们发现根据年龄这一个特征，可以将原本的训练数据集D划分为3个子集：有5个青年子集 $D_{1}$ ，其中有3个样本是不同意贷款，2个样本是同意贷款；5个中年子集 $D_{2}$ ，其中有2个样本是不同意贷款，3个样本是同意贷款；5个老年子集 $D_{3}$ ，其中有1个样本是不同意贷款，4个样本是同意贷款。具体如下表：

下面，我们就可以计算经验条件熵了。经验条件熵就是在给定特征A后所得到的n个子集，每个子集计算它的熵，然后进行加权求和。那么我们在给定年龄这个特征的时候，它划分出3个子集，所以n=3，每个权重就是 $D_{i}$ 中所包含的样本个数与训练数据集D中样本个数的比例。

$H(D|A_{1})=\frac{5}{15}H(D_{1})+\frac{5}{15}H(D_{2})+\frac{5}{15}H(D_{3})=\frac{5}{15}(-\frac{3}{5}log_{2}\frac{3}{5}-\frac{2}{5}log_{2}\frac{2}{5})+\frac{5}{15}(-\frac{2}{5}log_{2}\frac{2}{5}-\frac{3}{5}log_{2}\frac{3}{5})+\frac{5}{15}(-\frac{1}{5}log_{2}\frac{1}{5}-\frac{4}{5}log_{2}\frac{4}{5})=0.888$

下面我们看一下“有工作”这一个特征。我们可以将训练数据集分成2个子集：

$D_{1}$ 对应有工作，有5个样本个数； $D_{2}$ 对应无工作，有10个样本个数。

$H(D|A_{2})=\frac{5}{15}\cdot H(D_{1})+\frac{10}{15}\cdot H(D_{2})=\frac{5}{15}\cdot (-0log_{2}0-\frac{5}{5}log_{2}\frac{5}{5})+\frac{10}{15}\cdot (-\frac{6}{10}log_{2}\frac{6}{10}-\frac{4}{10}log_{2}\frac{4}{10})=0.647$

下面我们看一下“有工房子”这一个特征。我们可以将训练数据集分成2个子集：

$D_{1}$ 对应有自己的房子，有6个样本个数； $D_{2}$ 对应没有自己的房子，有9个样本个数。

$H(D|A_{3})=\frac{6}{15}\cdot H(D_{1})+\frac{9}{15}\cdot H(D_{2})=\frac{6}{15}\cdot (-0log_{2}0-\frac{6}{6}log_{2}\frac{6}{6})+\frac{9}{15}\cdot (-\frac{3}{9}log_{2}\frac{3}{9}-\frac{6}{9}log_{2}\frac{6}{9})=0.551$

下面我们看一下“信贷情况”这一个特征。我们可以将训练数据集分成3个子集：

$D_{1}$ 对应信贷情况非常好，有4个样本个数； $D_{2}$ 对应信贷情况好，有6个样本个数； $D_{3}$ 对应信贷情况一般，有5个样本个数。

$H(D|A_{3})=\frac{4}{15}H(D_{1})+\frac{6}{15}H(D_{2})+\frac{5}{15}H(D_{3})=\frac{4}{15}\cdot (-0log_{2}0-\frac{4}{4}log_{2}\frac{4}{4})+\frac{6}{15}\cdot (-\frac{2}{6}log_{2}\frac{2}{6}-\frac{4}{6}log_{2}\frac{4}{6})+\frac{5}{15}\cdot (-\frac{4}{5}log_{2}\frac{4}{5}-\frac{1}{5}log_{2}\frac{4}{5})=0.608$

因此，相应的信息熵、信息经验熵、信息增益如下：

5.2.3 信息增益比

除了信息增益，还可以通过信息增益比来选择最优特征。为什么有了信息增益，还要定义一个信息增益比？这是因为信息增益有时候更倾向于选择具有更多取值的特征，比如说信贷情况有3个取值，有工作有两种取值，那么这时候信贷情况的取值个数是多于有工作的取值个数的。由于信贷情况的取值个数较多，有可能由于这个原因造成它的信息增益是大于有工作的。信息增益比就可以降低由于特征取值较多所造成影响。信息增益比就是在信息增益的基础上增加一个惩罚项。这个惩罚项就是训练数据集D关于特征A的熵的倒数，信息增益比是 $\frac{g(D,A)}{H_{A}(D)}$

$H_{A_{1}}(D)=-\frac{5}{15}log_{2}\frac{5}{15}-\frac{5}{15}log_{2}\frac{5}{15}-\frac{5}{15}log_{2}\frac{5}{15}=1.585$

$H_{A_{2}}(D)=-\frac{5}{15}log_{2}\frac{5}{15}-\frac{10}{15}log_{2}\frac{10}{15}=0.918$

$H_{A_{3}}(D)=-\frac{6}{15}log_{2}\frac{6}{15}-\frac{9}{15}log_{2}\frac{9}{15}=0.971$

$H_{A_{4}}(D)=-\frac{4}{15}log_{2}\frac{4}{15}-\frac{6}{15}log_{2}\frac{6}{15}-\frac{5}{15}log_{2}\frac{5}{15}=1.566$

算出的信息增益比如下：

对比“有工作”和“信贷情况” 这两个特征的信息增益，我们会选择信息增益较大的“信贷情况”作为最优特征，也就是选择信贷情况这个值可以带来更大的确定性；如果引入信息增益比来消除特征个数的不同所带来的影响，这时候选择“有工作”这个特征来作为最优特征。

对于信息增益和信息增益比，这两个孰优孰劣？信息增益的缺点是倾向于选择取值较多的特征；而信息增益比倾向于选择取值较少的特征。选择哪一个需要根据实际情况而定。

5.3 决策树的生成

5.3.1 ID3算法

ID3算法是使用信息增益进行特征选择。

ID3算法如下：

输入：训练数据集D、特征集A、阈值 $\epsilon$

输出：决策树T

（1）判断T是否需要选择特征生成决策树。

不需要进行特征选择：

①如果所有的实例点都属于同一个类，则T是单结点树，记录实例类别 $C_{k}$ ，以此作为该节点的类标记。例如现在有10天的天气数据，每一天的数据包含了湿度、温度、风力等特征，但是这10天都是晴天，也及时这些实例点都属于同一类。

②当特征集 $A=\varnothing$ 时，则T是单结点树，记录实例个数最多类别 $C_{k}$ ，以此作为该节点的类标记。假如现在有10天的天气数据，其中8天是晴天，2天不是晴天，除此之外，没有关于天气的任何特征数据。没有特征。自然就不需要特征选择了。

需要进行特征选择，就计算A中各特征的信息增益，并选择信息增益最大的特征 $A_{g}$ :

①若 $A_{g}$ 的信息增益小于 $\epsilon$ ，则说明 $A_{g}$ 这个特征并不会给分类带来更多的确定性，也就是说它并没有有助于分类。既然这个信息增益最大的特征对分类都没有很大的帮助，就更别说其他特征了。这时我们可以认为这棵决策树是一个单结点树，记录D中实例点个数最多类别 $C_{k}$ ，以此作为该结点的类标记。

②若 $A_{g}$ 的信息增益大于 $\epsilon$ ，我们可以将训练数据集D根据 $A_{g}$ 这个特征的所有可能取值 $a_{i}$ 划分为若干个非空子集 $D_{i}$ ，将 $D_{i}$ 中实例个数最多的类别作为标记，构建子节点

（2）第i个子节点，以 $D_{i}$ 为训练集， $A-A_{g}$ 为特征集合，递归地调用以上步骤，直到为单一结点后停止。

下面我们看一个例子：

这是一个贷款申请的数据集。这个数据集中包含了15个训练样本，其中有9个是同意贷款，6个是不同意贷款，这说明所有的实例点并不属于同一个类；这个训练样本集包含了4个特征，说明特征集A不是空集，因此，这并不是一个单节点的决策树，我们需要进行下一步的判断。

接下来，我们计算每一个特征所对应的信息增益：

我们发现这里的信息增益值是比较大的，也就是说，即使我们人为的给定一个阈值，比如 $\epsilon =0.001$ ，那么这里的四个信息增益值没有一个是小于阈值的，所以依然不可以认为这是一个单节点的决策树，我们需要选择信息增益最大的进行决策树的生成。

这里信息增益最大的特征是“有自己的房子”，我们现在就将根节点确定下来了。

当“有自己的房子”将整个训练集D划分为 $D_{1}$ 和 $D_{2}$ 时， $D_{1}$ 中的所有实例都是同意贷款的；而 $D_{2}$ 中有6个是同意贷款的，3个不同意贷款。

我们画一个这个决策树，如下：

根节点处就是有自己的房子，如果有自己的房子，那么所对应到的所有实例都是同意贷款，那么就得到一个叶子结点（同意贷款的类别）；但如果没有自己的房子，这时候所对应的 $D_{2}$ 既有同意贷款，又有不同意贷款，我们就需要根据特征选择来找到这个内部结点所对应的特征。

下面，我们就以 $D_{2}$ 作为新的训练数据集， $A_{1},A_{2},A_{4}$ 作为新的特征集来计算各个特征的信息增益。

计算 $g(D_{2},A_{1})$ 的信息增益。 $g(D_{2},A_{1})=H(D_{2})-H(D_{2}|A_{1})$ ，其中

经验熵 $H(D_{2})=-\frac{6}{9}log_{2}\frac{6}{9}-\frac{3}{9}log_{2}\frac{3}{9}=0.918$ ；

经验条件熵 $H(D_{2}|A_{1})=\frac{4}{9}(-\frac{1}{4}log_{2}\frac{1}{4}-\frac{3}{4}log_{2}\frac{3}{4})+\frac{3}{9}(-\frac{2}{3}log_{2}\frac{2}{3}-\frac{1}{3}log_{2}\frac{1}{3})=0.667$

信息增益为0.251

我们接下来算一下第二个特征，也就是对“有工作”这个特征而言：

经验条件熵 $H(D_{2}|A_{2})=\frac{3}{9}H(D_{21})+\frac{6}{9}H(D_{22})=0$

信息增益为0.918

接下来计算“信贷情况”这个特征的经验条件熵：

经验条件熵 $H(D_{2}|A_{4})=\frac{4}{9}(-\frac{2}{4}log_{2}\frac{2}{4}-\frac{2}{4}log_{2}\frac{2}{4})=0.444$

信息增益为0.474

现在我们整理一下：

我们发现“有工作”这个特征所对应的信息增益最大，所以我们接下来的内部节点就对应着“有工作”这个特征，相应的决策树如下：

我们发现，对于这个例题而言，整棵决策树只用了两个特征，这是因为我们在选择了第二个特征后所得到的两个小子集都是同属于同一类别的，所以就停止了。

5.3.2 C4.5算法

C4.5算法是使用信息增益比进行特征选择。C4.5算法是非常有名的算法。

C4.5算法就是将上述ID3算法的信息增益改成信息增益比。使用信息增益比来构建决策树，它可以克服之前信息增益选择特征时，可能会偏向取值较多的特征的问题；而且相较于ID3算法，C4.5算法不仅可以处理离散型的描述特征，还可以处理连续型的。所以说C4.5算法在继承ID3算法的一些优点外，还有自己的优点。不过C4.5算法也有一定的缺点：信息增益比的计算麻烦，尤其实是在处理连续型变量时。因此C4.5算法虽然解释起来比较容易，但是在决策树的生成过程中需要对数据进行多次的顺序扫描和排序，导致算法的低效性。也就是说，当我们的数据量非常大时，这个程序很难运行。

5.3 剪枝

想要知道剪枝，就要先了解什么样的决策树可以算是一个非常优秀的决策树。简单来说，决策树是有特定目的----做决策，所以评判它是否优秀，应该从下面几个方面考虑：

（1）这棵决策树能力强不强：具有很好的拟合能力和泛化能力。

（2）这棵决策树结构简不简单：深度小、叶节点数少

这里树的结构和拟合、泛化能力有什么关系呐？拟合能力和泛化能力可以通过训练误差和测试误差来度量。训练误差就是通过对训练数据集而言的误差；测试误差就是根据测试集计算出来的，反映对未知数据的预测能力。

如果我们训练出来的模型训练误差低，测试误差高，这就说明它对已知数据的拟合能力很强，但是对未知数据的预测能力非常差，这就是过拟合的现象。过拟合的现象往往是由于我们过度重视它对已知数据的拟合能力，这时候往往得到的模型结构是过于复杂的，反映到决策树中就说明如果得到的决策树树形结构非常复杂，就有可能出现过拟合情况。

欠拟合和过拟合是一个相反的情况：训练误差、测试误差高，也就是对已知数据的预测能力很差，对未知数据的预测能力也差。一般出现欠拟合的现象，是由于训练出来的模型，它所具有的结构是过于简单造成的。

决策树是根据训练数据集一步一步生成的，所以往往在生成过程中过于强调对于训练数据集的拟合能力，因此不容易出现欠拟合，而最容易出现过拟合现象。剪枝就是为了处理决策树过拟合问题。

关于决策树的剪枝，根据决策树发生的时间可以分为预剪枝和后剪枝。

预剪枝：例如，对于果树，我们是想要它结更多的果实，所以它的剪枝基本上是在它结果前，也就是成长过程中。大家可能会发现，果园里的果树都比较矮，这是因为我们为了让它结果，果农经常会抑制果树的生长高度，有时还会剪掉不结果的枝杈，尽量留下更多结果的枝杈。在决策树中，预剪枝就是在决策树的生长过程中，对每个结点划分前进行估计，若当前结点的划分不能提升泛化能力，则停止划分，记当前结点为叶节点。

后剪枝：在树木生长完毕后进行的修剪。后剪枝是在生成一棵完整的决策树之后，自底向上地对内部结点考察，若此内部结点变为叶节点，可以提升泛化能力，则做此替换。

5.3.1 预剪枝

预剪枝有三种最常用的方法：

①限定决策树的深度

②设定一个阈值

③设置某一个指标，比较结点划分前后的泛化能力

我们通过一个例子看一下这三种最常用的预剪枝方法：

这是一个挑西瓜的例子，这组数据一共有17个样本点，每个样本点有6个特征。通过信息增益可以形成下面这棵决策树模型：

5.3.1.1 限定决策树的深度

通过决策树的深度进行预剪枝。根结点是第0层，这棵决策树一共有4层。假如现在将深度限定为2，我们看一下能得到一棵什么样的决策树呢？

如果将深度限定为2，就不能有第3、4层了，而第3层是从“色泽”这个内部节点生长出来的，我们就要看一下如果在这个地方进行剪枝的话，应该写成什么？

如果在这17个样本中，选择纹理清晰的样本，并且根蒂是稍蜷缩的，我们可以得到3个样本：

这3个样本中，有2个好瓜，1个坏瓜，因此此处的类别分类为好瓜，这就确定了叶节点。通过深度预剪枝得到的决策树如下：

5.3.1.2 设定一个阈值

通过设定一个阈值进行预剪枝。这里我们看一下决策树生成算法，看看阈值在哪出现的：

这个阈值不仅可以判断整棵决策树是不是单节点树，还可以判断子树 $T_{i}$ 是不是单节点树。如果阈值设定的非常大，决策树就有可能非常简单。下面我们再看一看挑西瓜的例子：

如果我们设定阈值 $\epsilon =0.4$ ，我们计算出每一个特征的信息增益后选择特征。

这里算出的所有值都是小于0.4的，根据算法就可以判断这棵决策树是一个单节点树了。在数据集中，有8个样本是好瓜，9个是坏瓜， $8< 9$ 。如果将阈值设为0.4，所得到的单节点树就是这样的形式。

5.3.1.3 基于测试集误差率，比较结点划分前后的泛化能力

设置某一个指标，比较结点划分前后的泛化能力。泛化能力度量的是对未知数据集的一个预测能力，我们往往用测试集来代表未知数据。在这里使用的指标是：测试集上的误差率。

测试集上的误差率：测试集中错误分类的实例占比。

测试集上的准确率：测试集中正确分类的实例占比。

因为误差率是错误分类的实例占比，所以这个误差率越高，代表着它的泛化能力越弱；误差率越低，代表泛化能力越强。接下来，我们就用这个指标进行预剪枝。

首先将数据集分成两部分，一部分作为训练集训练模型，训练集对训练出来的模型进行检测。

如果直接用训练数据集得到一个单节点的决策树可以得到什么呢？我们发现在训练数据集中有5个是好瓜，5个是坏瓜。由于好瓜和坏瓜的个数相同，所以这一棵单节点决策树既可以是好瓜，也可以是坏瓜。

由测试集判断可知：测试集中有3个是好瓜，4个是坏瓜。如果这棵单节点决策树是好瓜，那么测试集得误差率为 $\frac{4}{7}$ 。如果这个叶节点变成一个内部结点，选择信息增益最大的特征----脐部作为根节点，生长出一个具有两层的决策树：

我们发现得到这一棵决策树后，如果用它对测试集进行判断，此时的误差率为 $\frac{2}{7}$ ，这跟之前通过单节点决策树所得到的误差率 $\frac{4}{7}$ 相比明显减小了。这说明，如果将这个叶节点变成一个内部节点的话，可以使泛化能力得到一个提升，我们应该在这个节点处继续划分。

如果这棵单节点决策树是坏瓜，对于测试数据集的误差率是 $\frac{3}{7}$ ，这跟之前通过单节点决策树所得到的误差率 $\frac{4}{7}$ 相比也是明显减小了，说明泛化能力得到了一个提升。

无论这一棵单节点树是好瓜还是坏瓜，都支持接着划分这个节点。

首先看这第一个叶节点：根据之前的信息增益，我们选择的特征----色泽。如果在这个节点继续划分的话，就把它转化成一个内部节点了。

我们看看新得到的这棵决策树的误差率变成了多少。

在测试集中，脐部是凹陷的有3个样本。如果色泽是浅白的，则是好瓜，但决策树做出了坏瓜的判断；如果色泽是青绿色，决策树应该做出好瓜的判断，但实际上它是坏瓜。在脐部稍凹的中，有一个是坏瓜，但决策树却将其判断为好瓜，这也是一个误判样本。此时的误差为 $\frac{3}{7}$

刚才两层结构的决策树误差率是 $\frac{2}{7}$ ，而现在的三层结构决策树误差变为了 $\frac{3}{7}$ ，说明我们的误差率变大了，泛化能力下降，说明在第一个节点处不应该继续划分。

现在我们看一下第二个节点。我们也可以根据训练数据集中的样本得到一棵决策子树，这棵决策子树是否应该保留需要看一下它的误差率。

我们看一下测试集中的误差率。决策树把脐部凹陷的都判做好瓜，但测试集中有一个是坏瓜，出现了一个误判样本。脐部稍凹、根蒂蜷缩的有一个是好瓜、一个坏瓜，决策树判断是好瓜，出现了一个误判。这时候的误差率是 $\frac{2}{7}$ ，和之前两层决策树的误差率相同。出于奥卡姆剃刀原理，也就是模型在相同的效果下，越简单越好。此时不做继续划分。

对于第三个叶节点：脐部平坦都是坏瓜，就没必要继续划分了。

最后得到了一个两层结构的决策树：

5.3.2 后剪枝

预剪枝是一个自上而下的过程，而后剪枝是一个自下而上的过程。

目前来说，最常用的后剪枝一般有这几种：

①降低错误剪枝（REP）

②悲观错误剪枝（PEP）

③最小误差剪枝（MEP）

④基于错误剪枝（EBP）

⑤代价-复杂度剪枝（CCP）

5.3.2.1 降低错误剪枝

原理：自下而上，使用测试集来剪枝。对每个结点，计算剪枝前和剪枝后的误判个数，若是剪枝有利于减少误判（包括相等的情况），则剪掉该结点所在分枝。

此处的降低错误剪枝方法和之前的基于测试集上的误差率的预剪枝方法是非常相似的。我们来看一下这个后剪枝方法，依然选用挑西瓜的例子，10个训练集，7个测试集：

对训练集中样本的训练，我们可以得到一棵决策树：

这一棵决策树的深度是4，我们先看一下第4层是否需要剪枝。如果把下面紫框圈出的部分用一个叶子节点代替的话，应该是什么样的叶子节点。

对照训练集发现，脐部稍凹、根蒂稍蜷缩、色泽乌黑所对应的样本一个是好瓜、一个是坏瓜。我们不妨将这个叶子结点设为好瓜。现在我们就要看看是用这棵子树误判个数少，还是直接用“好瓜”这个叶子结点误判个数少。

这一棵子树在测试集中的误判个数为2个；如果我们现在将这一棵子树用叶子结点替换，此时误判个数为1。因此进行剪枝，也就是决策树从深度为4，变成深度为3。

我们继续看一下是否还可以对决策树进行剪枝操作，也就是能否把现在的3层决策树变成2层的决策树。那么我们就需要看下图紫框的子树是保留还是剪掉：

这时，我们先看一下训练集，发现脐部稍凹、根部稍蜷缩的样本有3个，其中2个好瓜，1个坏瓜。所以，如果选择一个叶子结点来替代这棵子树的话，应该选择“好瓜”作为叶子结点。

如果使用这棵子树的话，测试集中的误判个数是1个；使用“好瓜”作为叶节点的话，误判个数也是1个。根据奥卡姆剃刀原理，我们这时候可以进行剪枝。所以决策树从3层变成2层.

接下来，我们要判断2层的决策树能不能变成1层的决策树：

按照以上这样的步骤，看一下还能不能继续进行剪枝。最后得到一个1层决策树如下：

这个剪枝方法操作简单，容易理解。由于每次剪枝只需要判断每个节点剪枝前后的误判次数就可以了，所以只需要每个节点访问一次，因此整个计算的复杂度是线性的。

这种后剪枝方法也有缺点，比如上述我们得到的决策树有欠拟合的迹象。这是因为它受测试集的影响非常大，如果测试集比训练集小很多，会限制分类的精度。

5.3.2.2 悲观错误剪枝

原理：根据剪枝前后的错误率来决定是否剪枝。和降低错误剪枝（PEP）不同的是：PEP补单需要训练集，还需要验证集，错误率就是在验证集上计算出来的；悲观错误剪枝（PEP）只需要训练集即可，不需要验证集，错误率是在验证集上计算出来的，并且PEP是自上而下剪枝。

悲观错误剪枝方法的具体步骤如下：

（1）计算剪枝前目标子树每个叶节点的误差，并进行修正： $Error(Leaf_{i})=\frac{error(Leaf_{i})+0.5}{N(T)}$ ，其中分子的 $error(Leaf_{i})$ 表示第i个叶子结点上误判的样本个数，分母的 $N(T)$ 表示这棵目标子树包含的总样本个数。这样就计算出来了某一个叶子节点对应的误差率，但是这样计算出来的结果是离散的，为了进行连续的修正，我们在分子上又加了0.5

（2）每一个叶子结点的修正值计算完毕之后，计算剪枝前目标子树的修正误差，就是每个叶子结点误差率的一个和，即 $Error(T)=\sum_{i=1}^{L}Error(Leaf_{i})=\frac{\sum_{i=1}^{L}error(Leaf_{i})+0.5\cdot L}{N(T)}$

（3）计算剪枝前目标子树误判个数的期望值。对于二项分布而言，期望就是 $n\cdot p$ ，其中n是这棵目标子树所包含的总样本数。 $E(T)=N(T)\cdot Error(T)=\sum_{i=1}^{L}error(Leaf_{i})+0.5\cdot L$

（4）计算剪枝前目标子树误判个数的标准差： $std(T)=\sqrt{N(T)\cdot Error(T)\cdot (1-Error(T))}$

（5）计算剪枝前误判上限（即悲观误差）： $E(T)+std(T)$

（6）剪枝后，原来的目标子树就变成了一个叶节点，计算剪枝后该叶子结点的修正误差：

$Error(Leaf)=\frac{error(Leaf)+0.5}{N(T)}$ ，分子的 $error(Leaf)$ 表示叶子结点上误判的样本个数，分母的 $N(T)$ 表示这个叶节点上包含的总样本个数。

（7）计算剪枝后该结点误判个数的期望值： $E(Leaf)=error(Leaf)+0.5$

（8）剪枝后的误判个数与剪枝前的误判上限进行比较。如果剪枝后的误判个数小于剪枝前的误判上限，进行剪枝，将原来的目标子树剪去，用一个叶子节点替换；否则，不剪枝

$E(Leaf)<E(T)+std(T)$

例子一：

我们想判断是否需要修剪这一棵子树，就要分别计算剪枝前的误判上限和剪枝后的误判个数的期望值。

图中的 $T_{4},T_{5},T_{6},T_{7},T_{8}$ 代表结点；+表示正类样本，-表示负类样本； $T_{4}$ 有30个样本，其中17个正类样本，13个负类样本，由 $T_{4}$ 得到一个叶结点 $T_{6}$ ，内部结点 $T_{5}$ ；在叶节点 $T_{6}$ 处，有7个正类，3个负类......

正类是用绿色+表示的；负类用红色-表示的。所以 $T_{6},T_{7}$ 叶结点对应正类， $T_{8}$ 对应负类。

在这3个叶节点上误判的个数是多少呢？在 $T_{6}$ 这个叶节点上误判的个数是3，在 $T_{7}$ 这个叶节点上误判的个数是2，在 $T_{8}$ 这个叶节点上误判的个数是1。所以剪枝前目标子树的修正误差为：

$Error(T)=\frac{3+2+1+0.5\cdot 3}{30}=\frac{7.5}{30}$

下面计算误判个数的期望值和误判个数的标准差。期望值 $E(T)=7.5$ ；标准差 $std(T)=\sqrt{30\cdot \frac{7.5}{30}\cdot (1-\frac{7.5}{30})}=2.37$

剪枝前的误判个数上限 $E(T)+std(T)=7.5+2.37=9.87$

下面我们看一下剪枝后的误判个数是多少？

如果我们在图中剪刀处进行剪枝，用一个叶结点代替，我们发现它一共包含了30个样本，其中17个是正类，13个负类，我们把这个叶子节点归为正类。

修正后的误差率 $Error(Leaf)=\frac{13+0.5}{30}$ ，因为如果我们把叶节点归为正类，有13个是误判的。

剪枝后误判个数的期望值 $E(Leaf)=13.5$

现在比较 $E(Leaf)$ 和 $E(T)+std(T)$ ， $13.5> 9.87$ 。剪枝后的误判个数期望值比剪枝前的误判上限大，因此不剪枝。

例子二：

剪枝前的修正错误率 $Error(T)=\frac{3+3+1+0.5\cdot 3}{27}=\frac{8.5}{27}$

计算剪枝前误判个数的期望值 $E(T)=8.5$ ；标准差 $std(T)=\sqrt{27\cdot \frac{8.5}{27}\cdot (1-\frac{8.5}{27})}=2.41$

剪枝前的误判上限 $E(T)+std(T)=8.5+2.41=10.91$

剪枝后得到一个叶结点，包括17个正类样本，10个负类样本，由于17＞10，我们将该叶节点归为正类

剪枝后的误差率 $Error(Leaf)=\frac{10+0.5}{27}=\frac{10.5}{27}$

剪枝后误判个数的期望值 $E(Leaf)=10.5$

在此，我们发现剪枝后误判个数期望值是小于剪枝前的误判上限。因此将这棵子树修剪。

看了两个这样的例子，大家可能觉得不太实际，因为我们只看到了一系列数字，下面我们就举一个大家非常熟悉的关于西瓜的数据集。

这是之前得到的西瓜数据集的决策树，对于这个数据集，最后分成两个类别：好瓜、坏瓜。标注每一个节点处的好瓜和坏瓜个数如下：

现在这棵树就非常清晰了。下面我们要判断下载根蒂这个节点是否要进行剪枝，我们就要计算下剪枝前和剪枝后的误判情况。

这棵目标子树有4个叶子结点

剪枝前的修正错误率 $Error(T)=\frac{1+0.5\cdot 4}{9}=\frac{1}{3}$

剪枝前误判个数的期望值 $E(T)=9\cdot \frac{1}{3}=3$ ；

标准差 $std(T)=\sqrt{9\cdot \frac{1}{3}\cdot (1-\frac{1}{3})}=1.414$

剪枝前的误判上限 $E(T)+std(T)=3+1.414=4.414$

剪枝后的叶节点为好瓜，此时的误差率 $Error(Leaf)=\frac{2+0.5}{9}=\frac{2.5}{9}$

剪枝后的误判个数期望值 $E(Leaf)=2.5$

因为剪枝后误判个数期望值是小于剪枝前的误判上限。因此将这棵子树修剪。

看完这3个例子，我想大家对悲观错误剪枝方法就非常了解了。最后我们看一下悲观错误剪枝方法的特点：

（1）我们之前说过降低错误剪枝方法需要验证集计算错误率，但是悲观错误剪枝方法不需要，所以它不需要分离剪枝数据集，有利于实例较少的问题；

（2）在悲观错误剪枝方法中，误差使用了连续修正值，使得适用性更强；

（3）由于自上而下的剪枝策略，比降低错误剪枝的效率更高；

（4）由于是自上而下的策略，可能会修剪掉不应剪掉的枝条。

5.3.2.3 最小误差剪枝

原理：根据剪枝前后的最小分类错误概率来决定是否剪枝。自下而上剪枝，只需要训练集即可。

假如我们现在想用决策树把样本分成K类：

①在结点T处，属于类别k的概率 $P_{k}(T)=\frac{n_{k}(T)+Pr_{k}(T)\cdot m}{N(T)+m}$ 。 $P_{k}(T)$ 中的P表示概率，k表示属于类别k，T表示处于结点T处。这个概率怎么计算呢？常规来了说就是 $\frac{n_{k}(T)}{N(T)}$ ，也就是在节点T处属于类别k的样本个数与节点T处的总样本个数之比。

现在我们要将先验概率考虑进去，也就是使用贝叶斯思维。先验概率是 $Pr_{k}(T)$ ，表示在结点T处属于类别k的先验概率，m表示先验概率对后验概率的影响。如果m取值非常小， $m\rightarrow 0$ ，后验概率 $P_{k}(T)\rightarrow \frac{n_{k}(T)}{N(T)}$ ，即直接通过训练数据集得到的概率值，说明此时先验概率对后验概率是没有影响的；如果 $m\rightarrow \infty$ ，后验概率 $P_{k}(T)\rightarrow Pr_{k}(T)$ ，也就是后验概率趋向于先验概率。从这两个极端概率，我们可以发现m的确表示了先验概率对后验概率的一个影响程度。

②我们知道，在每个节点处，我们只将它归为一个类别，比如把它归为类别k，那么结点T处，预测错误率就是这个类别不属于类别k的概率，我们将它的最小概率值作为结点T的预测错误率，也就是： $Error(T)=min\begin{Bmatrix} 1-P_{k}(T) \end{Bmatrix}=min\begin{Bmatrix} \frac{N(T)-n_{k}(T)+m(1-Pr_{k}(T))}{N(T)+m} \end{Bmatrix}$ 。这就是为什么我们将这个方法称为最小误差剪枝方法了。

在公式 $\frac{N(T)-n_{k}(T)+m(1-Pr_{k}(T))}{N(T)+m}$ 中，分子的 $N(T)-n_{k}(T)$ 表示不属于类别k的样本个数； $m(1-Pr_{k}(T))$ 表示不属于类别k的先验概率乘以它的影响因子m。如果先验概率是确定的，训练样本集也是确定的，那么求 $\frac{N(T)-n_{k}(T)+m(1-Pr_{k}(T))}{N(T)+m}$ 的最小值就是找到一个合适的m对应于函数的最小值，换言之错误率其实就是m的函数，接下来就是以m为变量，找到这个函数的最小值就可以了。

下面为了方便给大家演示最小误差剪枝方法的具体步骤，我就直接给定m的取值。大家在实际操作中吗，一定要注意这个m是选出来的。

假设样本属于每一个类别的概率是相同的，先验概率就是 $Pr_{k}(T)=\frac{1}{K}$ ， $m=K$ ，这个预测错误率 $Error(T)=\frac{N(T)-n_{k}(T)+K-1}{N(T)+K}$ 。下面就用这个公式演示最小误差剪枝方法的具体步骤：

（1）计算剪枝前目标子树每个叶子结点的预测错误率： $Error(Leaf_{i})=\frac{N(Leaf_{i})-n_{k}(Leaf_{i})+K-1}{N(Leaf_{i})+K}$ 。 $N(Leaf_{i})$ 表示第i个叶节点处的样本总数， $N(Leaf_{i})-n_{k}(Leaf_{i})$ 表示不属于类别k的样本个数；

（2）通过加权求和的形式计算剪枝前目标子树的预测错误率。对每个叶子结点处的预测错误率都赋予一个权重 $w_{i}$ 。 $w_{i}$ 就是每个叶节点处的样本个数与目标子树拥有的的样本总数。

$\boldsymbol{Error(Leaf)=\sum_{i=1}^{L}w_{i}Error(Leaf_{i})=\sum_{i=1}^{L}\frac{N(Leaf_{i})}{N(T)}Error(Leaf_{i})}$

（3）将目标子树用一个叶节点代替，计算剪枝后目标子树的预测错误率：

$Error(T)=\frac{N(T)-n_{k}(T)+K-1}{N(T)+K}$

（4）比较剪枝前后的预测错误率，如果满足 $Error(T)< Error(Leaf)$ ，即剪枝后的错误率小于剪枝前的错误率，进行剪枝；否则，不剪枝。

下面看一个例子，我们想看一下在 $T_{5}$ 处是否需要剪枝：

（1）剪枝前 $T_{5}$ 目标子树有2个叶节点 $T_{7},T_{8}$ ，我们分别计算 $T_{7},T_{8}$ 的预测错误率。

$T_{7}$ 处的预测错误率 $Error(T_{7})=\frac{2+2-1}{11+2}\frac{3}{13}$ ； $T_{8}$ 处的预测错误率 $Error(T_{7})=\frac{1+2-1}{9+2}\frac{2}{11}$

（2）通过加权求和的形式计算剪枝前目标子树的预测错误率。 $T_{7}$ 叶节点处的权重是 $\frac{11}{20}$ ，因为 $T_{5}$ 这棵目标子树有20个样本，叶节点 $T_{7}$ 有11个样本；同理， $T_{8}$ 叶节点的权重是 $\frac{9}{20}$ 。因此剪枝前的预测错误率 $Error(Leaf)=\frac{11}{20}\cdot \frac{3}{13}+\frac{9}{20}\cdot \frac{2}{11}=0.2087$

（3）将 $T_{5}$ 这个节点化为叶节点，由于正类和负类样本个数均为10，不妨设叶节点为正类。

预测错误率： $Error(T)=\frac{10+2-1}{20+2}\frac{11}{22}=0.5$

（4）比较剪枝前后的预测错误率，剪枝后的预测错误率0.5大于剪枝前的预测错误率0.2087，因此不进行剪枝。

5.3.2.4 基于错误剪枝

原理：根据剪枝前后的误判个数来决定是否剪枝，自下而上，只需要训练集即可。这里的误判个数不仅仅是算出一个期望值，而是采用一个上界。

这个误判率上界是在一定的置信水平下计算得到的。假如我们有一个结点T，在这个节点处的样本总数为 $N(T)$ ，误判个数 $e(T)$ ，此时的误判率是 $\frac{e(T)+0.5}{N(T)}$ 。分子加上0.5是用于从二项分布到正态分布的连续性修正。现在我们要求误判率上界，需要把置信水平考虑在内，通过 $q_{\alpha }$ 来体现。现在，我们就有了置信水平 $\alpha$ 下每个节点的误判率上界： $\boldsymbol{U_{\alpha }(e(T),N(T))=\frac{e(T)+0.5+\frac{q_{\alpha }^{2}}{2}+q_{\alpha }\sqrt{\frac{(e(T)+0.5)(N(T)-e(T)-0.5)}{N(T)}+\frac{q_{\alpha }^{2}}{4}}}{N(T)+q_{\alpha }^{2}}}$

在这个公式中， $U_{\alpha }(e(T),N(T))$ 的U就是上界的意思； $\alpha$ 表示置信水平， $e$ 和 $N$ 分别表示误判个数和样本总个数。在 $\frac{e(T)+0.5+\frac{q_{\alpha }^{2}}{2}+q_{\alpha }\sqrt{\frac{(e(T)+0.5)(N(T)-e(T)-0.5)}{N(T)}+\frac{q_{\alpha }^{2}}{4}}}{N(T)+q_{\alpha }^{2}}$ 中， $\frac{e(T)+0.5}{N(T)}$ 就是本来的误判率；分子和分母加的部分是做的修正，得到的误判率上界。 $\frac{(e(T)+0.5)(N(T)-e(T)-0.5)}{N(T)}$ 就是二项分布里的方差，其中n是 $N(T)$ ，p是 $\frac{e(T)+0.5}{N(T)}$ ，q是 $\frac{N(T)-e(T)-0.5}{N(T)}$ ，开根号得到标准差。

式子中的 $q_{\alpha }$ 表示上分位数，也就是随机变量X≥ $q_{\alpha }$ 的概率为 $\alpha$ ，即 $P(X\geq q_{\alpha })=\alpha$ ，

当 $\alpha$ =25%，此时 $q_{\alpha }=0.6925$

我们知道了每个值后，就可以求出误判率上界。求出误判率上界后，就可以很容易得到误判个数上界，也就是样本总个数乘以误判率上界。

下面我们看一下基于错误剪枝方法的具体步骤：

（1）假如说剪枝前目标子树有L个叶节点，我们对每个叶节点计算误判率上界。

$\boldsymbol{U_{CF }(e(Leaf_{i}),N(Leaf_{i}))=\frac{e(Leaf_{i})+0.5+\frac{q_{\alpha }^{2}}{2}+q_{\alpha }\sqrt{\frac{(e(Leaf_{i})+0.5)(N(Leaf_{i})-e(Leaf_{i})-0.5)}{N(Leaf_{i})}+\frac{q_{\alpha }^{2}}{4}}}{N(Leaf_{i})+q_{\alpha }^{2}}}$

（2）计算剪枝前目标子树的误判个数上界： $\boldsymbol{E(Leaf)=\sum_{i=1}^{L}N(Leaf_{i})U_{CF }(e(Leaf_{i}),N(Leaf_{i}))}$

（3）将目标子树替换成叶节点后，计算剪枝后的误判率上界：

$\boldsymbol{U_{CF}(e(T),N(T))=\frac{e(T)+0.5+\frac{q_{\alpha }^{2}}{2}+q_{\alpha }\sqrt{\frac{(e(T)+0.5)(N(T)-e(T)-0.5)}{N(T)}+\frac{q_{\alpha }^{2}}{4}}}{N(T)+q_{\alpha }^{2}}}$

（4）计算剪枝后的误判个数上界： $\boldsymbol{E(T)=N(T)U_{CF }(e(T),N(T))}$

（5）比较剪枝前后的误判个数上界，如果满足 $E(T)< E(Leaf)$ 就剪枝；否则，不剪枝。

下面，看一个例子：

我们要判断是否需要在图中剪刀处进行剪枝。这棵目标子树有3个叶节点，默认置信水平为25%

（1）计算剪枝前的误判率上界。叶节点 $T_{6}$ 的误判率上界 $U_{CF}(0,6)=0.206$ ；叶节点 $T_{7}$ 的误判率上界 $U_{CF}(0,9)=0.143$ ；叶节点 $T_{8}$ 的误判率上界 $U_{CF}(0,1)=0.75$

（2）计算剪枝前误判个数上界。 $E(Leaf)=6\cdot 0.206+9\cdot 0.143+1\cdot 0.75=3.273$

（3）计算剪枝后的误判率上界。 $U_{CF}(1,16)=0.157$

（4）计算剪枝后的误判个数上界。 $E(T)=16\cdot 0.157=2.512$

（5）剪枝后的误判个数上界小于剪枝前的误判个数上界，所以进行剪枝。

5.3.2.5 代价-复杂度剪枝

原理：根据剪枝前后的损失函数来决定是否剪枝。这个损失函数是由代价和复杂度组成的。

损失函数 $C_{\alpha }=C(T)+\alpha \left | T \right |$ ， $C_{\alpha }$ 就是决策树T的损失函数； $C(T)$ 是决策树T在训练集中的预测误差，它体现模型T的拟合程度； $\left | T \right |$ 表示树T所包含的叶节点个数，树包含的叶节点越多，就说明树越复杂，因此这个参数反映的是这棵树T的复杂度，复杂度反映的是模型的泛化能力。

式子中的 $\alpha$ 是一个乘法分数，是一个非零值。如果 $\alpha =0$ ，这时候损失函数 $C_{\alpha }=C(T)$ ，此时我们只能通过预测误差来选择一棵决策树，也就是只从它的拟合程度进行选择；如果 $\alpha$ 越大，就说明复杂度这一项很重要，例如当 $\alpha \rightarrow \infty$ ，这时候 $C_{\alpha }=\alpha \left | T \right |$ ，此时损失函数由这棵树的复杂度决定，如果用这样的损失函数就倾向于选择一个更简单的模型。

$\alpha$ 是用来调节预测误差和模型复杂度之间的平衡。换而言之，就是平衡模型的拟合能力和泛化能力的。

正则化的一般形式为：

它对应结构性风险。包含预测误差部分和模型复杂度，这里的 $\lambda$ 和上述的 $\alpha$ 是类似的，用来调节拟合程度和模型复杂度的参数。因此上述所说的损失函数可以视作结构性风险函数在决策树中的一个特殊情况。

损失函数中的预测误差部分，t表示树T的叶节点，计算每一个叶节点的经验熵，即 $H_{t}(T)$ ；然后通过加权和形式计算出它的预测误差。此处介绍的经验熵的加权和，其实预测误差可以用基尼指数来表示。

现在有乐经验熵怎么进行加权求和？每一个叶节点处的样本可以用 $N_{t}$ ，这棵树有 $N$ 个样本，在每个叶节点处的权重 $w_{t}=\frac{N(T)}{N}$ ，那么加权和就是 $\sum_{}^{}\frac{N_{t}}{N}H_{t}(T)$ ，由于对于一个固定的训练集而言，N是固定的，所以可以写成 $\sum_{}^{}N_{t}H_{t}(T)$

现在我们看一下代价-复杂度剪枝方法的具体步骤：

（1）剪枝前的决策树记作 $T_{A}$ ，计算每个叶节点t的经验熵： $H_{t}(T)=-\sum_{k=1}^{K}\frac{N_{t}k}{N_{t}}log\frac{N_{t}k}{N_{t}}$

（2）剪枝前决策树的损失函数为： $C_{\alpha }(T_{A})=C(T_{A})+\alpha \left | T_{A} \right |$

（3）剪枝后的决策树记作 $T_{B}$ ，损失函数为： $C_{\alpha }(T_{B})=C(T_{B})+\alpha \left | T_{B} \right |$

（4）比较剪枝前后的损失函数，如果满足 $C_{\alpha }(T_{B})\leq C_{\alpha }(T_{A})$ 就剪枝；否则，不剪枝。

第五章决策树

5.1 决策树模型与学习

5.1.1 思维模式

5.1.2 模式结构

5.1.3 条件概率分布

5.1.4 决策树学习

5.2 特征选择

5.2.1 特征选择问题

5.2.2 信息增益

5.2.3 信息增益比

5.3 决策树的生成

5.3.1 ID3算法

5.3.2 C4.5算法

5.3 剪枝

5.3.1 预剪枝

5.3.1.1 限定决策树的深度

5.3.1.2 设定一个阈值

5.3.1.3 基于测试集误差率，比较结点划分前后的泛化能力

5.3.2 后剪枝

5.3.2.1 降低错误剪枝

5.3.2.2 悲观错误剪枝

5.3.2.3 最小误差剪枝

5.3.2.4 基于错误剪枝

5.3.2.5 代价-复杂度剪枝

网站公告

今日签到

热门文章

最新发布

第五章 决策树

5.1 决策树模型与学习

5.1.1 思维模式

5.1.2 模式结构

5.1.3 条件概率分布

5.1.4 决策树学习

5.2 特征选择

5.2.1 特征选择问题

5.2.2 信息增益

5.2.3 信息增益比

5.3 决策树的生成

5.3.1 ID3算法

5.3.2 C4.5算法

5.3 剪枝

5.3.1 预剪枝

5.3.1.1 限定决策树的深度

5.3.1.2 设定一个阈值

5.3.1.3 基于测试集误差率，比较结点划分前后的泛化能力

5.3.2 后剪枝

5.3.2.1 降低错误剪枝

5.3.2.2 悲观错误剪枝

5.3.2.3 最小误差剪枝

5.3.2.4 基于错误剪枝

5.3.2.5 代价-复杂度剪枝

网站公告

今日签到

热门文章

最新发布

第五章决策树