一般情况下可以使用如下两类方法来减小决策树的规模:

一、在决策树完美分割学习样例之前，停止决策树的生长。这种提早停止树生长的方法，称为预剪枝方法。

二、与预剪枝方法尽量避免过度分割的思想不同，一般情况下即使决策树可能出现过度拟合现象，算法依然允许其充分生长。在决策树完全生长之后，通过特定标准去掉原决策树中的某些子树。通常称这种方法为后剪枝方法。

1、预剪枝方法

预剪枝方法实际上是对决策树停止标准的修改。在原始的ID3算法中，节点的分割一直到节点中的实例属于同一类别时才停止。对于包含较少实例的节点，可能被分割为单一实例节点。为了避免这种情况，我们给出一个停止阈值a。当由一个节点分割导致的最大的不纯度下降小于a时，就把该节点看作是一个叶子节点。在该方法中，阈值a的选择对决策树具有很大的影响。当阈值a选择过大时，节点在不纯度依然很高时就停止分割了。此时由于生长不足，导致决策树过小，分类的错误率过高。假设在一个两类问题中，根节点Root一共包含100个学习样例，其中正例和负例均为50。并且使用属性b可以将正例与负例完全分开，即决策树在学习样例上的分类精度R(T)=100%。由信息增益公式可知，使用属性b分割节点可以得到不纯度下降的最大值0.5。如果设a=0.7，因为Gain(Root，a)=0.5<0.7，所以根节点Root不需要分割。此时导致决策树在学习样例上的分类精度下降为R(T)=50%。当阈值a选择过小时，例如a近似为0，节点的分割过程近似等同于原始的分割过程。由此可见，预剪枝方法虽然原理简单，但是在实际应用中，阈值a的选择存在相当大的主观性。如何精确的给出适当的阈值a以获得适当规模的决策树是十分困难的。

2、后剪枝方法

决策树是一种树形结构。一棵树是一个或者多个节点的有限集合T，使得

1)、有一个特别指定的节点，叫做树的根节点;

2)、除根节点以外，剩余的节点被划分成m>=0个不相交的集合Tl，…，Tm，而且每一个集合也都是树。树Tl，…，Tm称为这个根节点的子树。根据上述树的定义，可以直观地将决策树的后剪枝看作是去掉某些子树中除根节点外所有节点的过程，如图1所示。移除子树后，还需要对新生成的叶子节点赋予一个类别标志，一般是叶子节点中所占比例最大的类别标志。

3、代价复杂度剪枝

代价复杂度剪枝过程分成两个阶段:第一阶段，首先由原决策树通过某种剪枝策略生成一系列决策树T0，Tl，…，Tk。其中T。是由决策树生成算法推导出来的属性决策树，Ti十1是依次删除Ti的一棵或者多棵后生成的。重复此过程，直到最后的决策树Tk只含有一个叶子结点。

第二阶段，我们对上一阶段得到的决策树进行评估，最终选择一棵最好的作为剪枝后的决策树。

考虑包含N个样例的训练集合，通过决策树生成算法，如ID3，我们可以推导出一棵属性决策树。假定这棵决策树会将其中的E个样例错误分类，再定义L(T)是决策树T中叶子结点的数目，L.Breiman等人定义决策树T的代价复杂度为

最后我们从所有子树中选择观察错误数不超过E’ se伍’)中最小的子树，作为剪枝后的子树。