参看书籍：Machine Learning(Tom Mitchell)
之前我们已经比较详细的介绍啦决策树的相关知识，如ID3（Machine Learning -- ID3算法）和C4.5（Machine learning -- C4.5算法详解及Python实现）.
本文章介绍决策树学习的实际问题包括确定决策树增长的深度；处理连续值的属性；选择一个适当的属性筛选度量标准；处理属性值不完整的训练数据；处理不同代价的属性；以及提高计算效率。下面我们讨论每一个问题，并针对这些问题扩展基本的ID3算法。事实上，为了解决其中多数的问题， ID3算法已经被扩展了，扩展后的系统被改名为C4.5（Quinlan 1993）.
1,避免过拟合问题
表1描述的算法增长树的每一个分支的深度，直到恰好能对训练样例完美地分类。然而这个策略并非总是行得通的，事实上，当数据中有噪声，或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，这个策略便会遇到困难。在以上任一种情况发生时，这个简单的算法产生的树会过度拟合训练样例。
表1 专用于学习布尔函数的ID3算法概要
ID3是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都使用过了。
对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布（也就是包含训练集合以外的实例）上表现的却更好时，我们说这个假设过度拟合（overfit）训练样例。
定义： 给定一个假设空间H，一个假设h∈H，如果存在其他的假设h´∈H，使得在训练样例上h的错误率比h´小，但在整个实例分布上h´的错误率比h小，那么就说假设h过度拟合（overfit）训练数据。
图1-1画出了在决策树学习的一个典型应用中过度拟合的影响。在这个例子中，ID3算法用来学习哪一个病人患有某种糖尿病。这幅图的横轴表示在决策树创建过程中树的结点总数，纵轴表示决策树作出的预测的精度。实线显示决策树在训练样例上的精度，虚线显示在一套独立的测试样例（没有被包括在训练样例中）上测量出的精度。可以看出，随着树的增长，在训练样例上的精度是单调上升的。然而，在独立的测试样例上测出的精度先上升后下降。如图所示，当树超过大约25个结点时，对树进一步精细化尽管可以提高它在训练数据上的精度，却降低了它在测试样例上的精度。
图1-1 决策树学习中的过度拟合。
随着ID3算法增加新的结点增长决策树，在训练样例上的精度是单调上升的。然而，在独立于训练样例的测试样例上，精度先上升，然后下降。实验这个图所需的软件和数据可以通过网址http://www.cs.cmu.edu/~tom/mlbook.html得到。
表2 目标概念PlayTennis的训练样例
是什么原因导致h比h′更好地拟合训练样例，但对于后来的实例却表现更差呢？这种情况发生的一种可能原因是训练样例含有随机错误或噪声。举例说明，考虑在表2的本来正确的样例中加入一条训练正例，但却被误标示为反例，如下：
<Outlook=Sunny，Temperature=Hot，Humidity=Normal，Wind=Strong，PlayTennis=No>
对于本来没有错误的数据，ID3生成图3-2表示的决策树。然而，增加这个不正确的样例导致ID3建立一个更复杂的树。确切地讲，新的样例会被排列到图3-2表示的树的左起第二个叶子结点，与以前的正例D9和D11排在一起。因为新的样例被标记为反例，所以ID3会在这个结点下面进一步搜索更多的细节。当然只要新的错误样例与原来这个结点的两个样例有任何差异，ID3会成功找到一个新的决策属性来把新的样例从以前的两个正例中分开。这样的结果是ID3会输出一个决策树(h)，它比图3-2中原来的树（h´）更复杂。当然，h会完美地拟合训练样例集，而较简单的h´不会。然而，由于新的决策结点只是拟合训练样例中噪声的结果，我们可以断定在取自同一实例分布的后续数据上，h´会胜过h。
图3-2 决策树
上面的例子演示了训练样例中的随机噪声如何导致过度拟合。事实上，当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子结点时。这种情况下，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。一旦这样的巧合的规律性存在，就有过度拟合的风险。
过度拟合对于决策树学习和其他很多学习算法是一个重要的实践困难。例如，在一次关于ID3算法的实验研究中（Mingers 1989b），对于5种带有噪声和不确定数据的不同学习任务，人们发现在多数问题中过度拟合使决策树的精度降低了10-25%。
有几种途径用来避免决策树学习中的过度拟合。它们可被分为两类：
