决策树学习

决策树学习的适用问题

通常决策树学习最适合具有以下特征的问题：

• 实例是由“属性-值”对（pair）表示的。实例是用一系列固定的属性（例如，Temperature）和它们的值（例如，Hot）来描述的。最简单的决策树学习中，每一个属性取少数的分离的值（例如，Hot、Mild、Cold）。然而，扩展的算法也运行处理值域为实数的属性（利润，数字表示的温度）。
• 目标函数具有离散的输出值。决策树给每个实例赋予一个布尔型的分类（例如，yes或no）。决策树方法很容易扩展到学习有两个以上输出值的函数。一种更强有力的扩展算法运行学习具有实数值输出的函数，尽管决策树在这种情况下的应用不太常见。
• 可能需要析取的描述，决策树很自然代表了析取表达式。
• 训练数据可以包含错误。决策树学习对错误有很好的鲁棒性，无论是训练样例所属的分类错误还是描述这些样例的属性值错误。
• 训练数据可以包含缺少属性值的实例。决策树学习甚至可以在未知属性值的训练样例中使用（仅有一部分训练样例知道当天的湿度）。

基本的决策树学习算法

ID3算法，通过自顶向下构造决策树来进行学习。构造过程是从“哪一个属性将在树的根节点被测试？”这个问题开始的。为了回答这个问题，使用统计测试来确定每一个实例属性单独分类训练样例的能力。分类能力最好的属性被选作为树的根节点的测试。然后为根节点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支之下。然后重复整个过程，用每个分支节点关联的训练样例来选取在该点呗测试的最佳 属性。这形成了对合格决策树的贪婪搜索，也就是算法从不回溯重新考虑以前的选择。

ID3算法的核心问题是选取在树的每个节点要测试的属性。我们希望选择的是最有助于分类实例的属性。那么衡量属性价值的一个好的定量标准是什么呢？这里将定义一个统计属性，称为“信息增益”，用来衡量给定的属性区分训练样例的能力。ID3算法在增长树的每一步使用这个信息增益标准从候选属性中选择属性。

用** “熵” **度量样例的均一性，它刻画了任意样例的纯度（purity），熵介于0~1之间。在信息论中，熵被用来衡量一个随机变量出现的期望值。

与其它的归纳学习算法一样，ID3算法可以被描述为从一个假设空间搜索一个拟合训练样例的假设。被ID3算法搜索的假设空间就是可能的决策树的集合。ID3算法以一种简单到复杂的爬山算法遍历这个假设空间，从空的树开始，然后逐步考虑更加复杂的假设，目的是搜索到一个正确分类训练数据的决策树。引导这种爬山搜索的评估函数是信息增益度。

决策树学习的常见问题
决策树学习的实际问题包括确定决策树增长的深度；处理连续值的属性；选择一个适当的属性筛选度量标准；处理属性值不完整的训练数据；处理不同代价的属性；以及提高计算效率。

过度拟合：给定一个假设空间 H，一个假设h∈H，如果存在其他的假设h´∈H，使得在训练样例上h 的错误率比h´小，但在整个实例分布上h´的错误率比h 小，那么就说假设h 过度拟合（overfit）训练数据。