决策树学习

title: 决策树学习 tags:

• 机器学习

• 决策树学习

  categories:

• 机器学习

决策树学习

• 决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散值函数的方法，对噪声数据有很好的健壮性且能够学习析取表达式。

• 决策树学习方法搜索一个完整表示的假设空间，从而避免了受限假设空间的不足。

• 决策树学习的归纳偏置是优先选择较小的树。

• 基于树结构来进行决策

简介

决策树是一种逼近离散值目标函数的方法，在这种方法中学习到的函数被表示为一棵决策树。学习得到的决策树也能再被表示为多个if-then的规则，以提高可读性。

• 符号主义学习

• 以信息论为基础

• 以信息熵的最小化为目标

• 直接模拟了人类对概念进行判断的树形流程

决策树表示法

决策树通过把实例从根结点排列到某个叶子结点来分类实例，叶子结点即为实例所属的分类。树上的每一个结点指定了对实例的某个属性的测试，并且该结点的每一个后继分支对应该属性的一个可能值。分类实例的方法是从这棵树的根节点开始，测试这个节点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动。以此类推。

决策树学习的适用问题

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

• 实例是由“属性-值”对表示的

• 目标函数具有离散的输出值

• 可能需要析取的描述

• 训练数据可以包含错误

• 训练数据可以包含缺少属性值的实例

决策树解决问题的核心任务是要把样例分类到各可能的离散值对应的类别中，因此经常被称为分类问题。

决策树特点

优点

• 训练时间复杂度低

• 预测过程比较快速

• 模型容易展示

缺点

• 容易过拟合

基本的决策树学习算法

大多数已开发的决策树学习算法是一种核心算法的变体。该算法采用自顶向下的贪婪搜索遍历可能的决策树空间。这种方法是ID3算法和后继的C4.5算法的基础。

基本的ID3算法通过自顶向下构造决策树来进行学习。

使用统计测试来确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性被选作树的根节点的测试。

专用于学习布尔函数的ID3算法概要：

ID3($Example, Target\_attribute, Attributes$)

​ $Example$ 即训练样例集。$Target\_attribute$ 是这棵树要预测的目标属性。$Attributes$是除目标属性外供学习到的决策树测试的属性列表。返回一棵能正确分类给定 $Examples$ 的决策树。

• 创建树的 $Root$ 节点

• 如果 $Examples$ 都是正，那么返回 label = + 的单节点树$Root$

• 如果 $Examples$ 都是负，那么返回 label = - 的单节点树$Root$

• 如果 $Attributes$ 为空，那么返回单节点树 $Root$ ，label = $Examples$ 中最普遍的 $Target\_attribute$ 值

• 否则开始

  • $A \leftarrow Attributes$ 中分类 $Examples$ 能力最好的属性

  • $Root$ 的决策属性 $\leftarrow A$

  • 对于 A 的每个可能值 $v_i$

    • 在 $Root$ 下加一个新的分支对应测试 $A = v_i$

    • 令 $Examples_{v_i}$ 为 $Examples$ 中满足A属性值为 $v_i$ 的子集

    • 如果 $Examples_{v_i}$ 为空

      • 在这个新分支下加一个叶子结点，结点的label = $Examples$ 中最普遍的 $Target\_attribute$ 值

    • 否则在这个新分支下加一个树ID3($Examples_{v_i}, Target\_attribute, Attributes - \{A\}$)

• 结束

• 返回 $Root$

注：具有最高信息增益的属性是最好的属性。

哪个属性是最佳的分类属性

ID3算法在增长树的每一步使用信息增益标准从候选属性中选择属性。

用熵度量样例的均一性

在信息论中，熵刻画了任意样例集的纯度。给定包含关于某个目标概念的正反样例的样例集 $S$ ，那么 $S$ 相对于这个布尔型分类的熵为：

$Entropy(S) \equiv -p_\oplus log_2p_\oplus - p _\ominus log_2p_\ominus$

其中 $p_\oplus$ 是在 $S$ 中正例的比例，$p_\ominus$ 是在 $S$ 中反例的比例。有关熵的计算，我们定义 $0log0$ 为 0。

那么，如果 $S$ 的所有成员属于同一类，那么 $S$ 的熵为 0。

信息论中熵的一种解释是，熵确定了要编码集合 $S$ 中任意成员（即以均匀的概率随机抽出的一个成员）的分类所需要的最少二进制位数。

$S$ 相对于 $c$ 个状态(c-wise)的分类的熵定义为：

$Entropy(S) \equiv \sum \limits ^2 \limits _{i=1} - p_i log_2 p_i$

其中，$p_i$ 是 $S$ 中属于类别 $i$ 的比例。对数底数仍然为2，是因为熵是以二进制位的个数来度量编码长度的。目标属性具有 $c$ 个可能值，那么熵最大可能是 $log_2c$ 。

用信息增益度量期望的熵降低

一个属性的信息增益就是由于使用这个属性分隔样例而导致的期望熵降低。更精确地讲，一个属性 $A$ 相对样例集合 $S$ 的信息增益 $Gain(S, A)$ 被定义为：

$Gain(S,A) \equiv Entropy(S) - \sum \limits _{v \in Values(A)} \frac{|S_v|}{|S|} Entropy(S_v)$

其中，$Values(A)$ 是属性 $A$ 所有可能值的集合，$S_v$ 是 $S$ 中属性 $A$ 的值为 $v$ 的子集（也就是，$S_v = \{s \in S | A(s) = v\}$）。 上等式，第一项是原集合的熵，第二项是用 A 分类 S 后熵的期望值。第二项描述的期望熵就是每个子集的熵的加权和，权值为属于 $S_v$ 的样例占原始样例 $S$ 的比例 $\frac{S_v}{S}$ 。所以 $Gain(S,A)$ 是由于知道属性 A 的值而导致的期望熵减少。换句话讲，$Gain(S,A)$ 是由给定属性 A 的值而得到的关于目标函数值的信息。当对 $S$ 的一个任意成员的目标值编码时， $Gain(S,A)$ 的值是在知道属性 A 的值后可以节省的二进制位数。

信息增益是ID3算法增长树的每一步中选取最佳属性的度量标准。

决策树学习中的假设空间搜索

与其他的归纳学习算法一样，ID3算法可以被描述为从一个假设空间中搜索一个拟合训练样例的假设。

ID3算法的优势和不足：

• ID3算法中的假设空间包含所有的决策树，它是关于现有属性的有限离散函数值函数的一个完整空间。ID3算法避免了搜索不完整假设空间的一个主要风险：假设空间可能不包含目标函数。

• 当遍历决策树空间时，ID3仅维护单一的当前假设。ID3算法失去了表示所有一致假设所带来的优势。

• 基本的ID3算法在搜索中不进行回溯，它收敛到局部最优解，而不是全局最优解。ID3算法在搜索的每一步都使用当前的所有训练样例，以统计为基础决定怎样精化当前的假设。使用所有样例的统计属性的一个优点是大大降低了对个别训练样例错误的敏感度。可以被很容易地扩展到处理含有噪声的训练样例。

决策树的归纳偏置

较短的树比较长的树优先。那些信息增益高的属性更靠近根节点的树优先。

限定偏置和优选偏置

ID3的归纳偏置来自它的搜索策略，而候选消除算法的归纳偏置来自它对搜索空间的定义。

ID3的归纳偏置是对某种假设胜过其他假设的一种优选，它对最终可列举的假设没有硬性限制。这种类型的偏置通常被称为优选偏置或搜索偏置。相反，候选消除算法的偏置是对待考虑假设的一种限定。这种形式的偏置通常被称为限定偏执或语言偏执。

决策树中的常见问题

基本ID3算法有很多问题，扩展后的系统被改名为C4.5。

避免过度拟合数据

当数据中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，算法产生的树就会过度拟合训练样例。

对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合(overfit)训练样例。

定义：给定一个假设空间 $H$ ，一个假设 $h \in H$ ，如果存在其它的假设 $h' \in H$ ，使得在训练样例上 $h$ 的错误率比 $h'$ 小，但在整个实例分布上 $h'$ 的错误率比 $h$ 小，那么就说假设 $h$ 过度拟合训练数据。

避免过度拟合的两类方法：

• 及早停止树增长，在ID3算法完美分类训练数据之前就停止树增长

• 后修剪法，即允许树过度拟合数据，然后对这个树进行后修剪

关键问题是使用什么样的准则来确定最终正确树的规模。解决这个问题的方法包括：

• 使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修剪节点的效用

• 使用所有可用数据进行训练，但进行统计测试来估计扩展（后修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。

• 使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。这个方法基于一种启发式规则，被称为最小描述长度的准则。

第一种方法常被称为训练和验证集法，这种方法中可用数据被分成两个样例集合：一个训练集合用来形成学习到的假设，一个分离的验证集合用来评估这个假设在后续数据上的精度，确切地说是用来评估修剪这个假设的影响。验证集合可以用来对过度拟合训练集合中的虚假特征提供防护检验。当然，很重要的一点是验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。一种常见的做法是取出可用样例的三分之一用作验证集合，用另外三分之二作训练集合。

下面介绍第一种方法的两个主要变种。

错误率降低修剪

错误率降低修剪是考虑将树上的每一个节点作为修剪的候选对象。反复地修剪节点，每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点。继续修剪节点直到进一步的修剪是有害为止。

如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪是一个有效的方法。

规则后修剪

规则后修剪步骤：

• 从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生。

• 将决策树转化为等价的规则集合，方法是为从根节点到叶子结点的每一条路径创建一条规则

• 通过删除任何能导致估计精度提高的前件来修剪（泛化）每一条规则。

• 按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例。

在规则后修剪算法中，为树中的每个叶子结点产生一条规则。从根节点到叶子结点路径上的每一个属性的测试称为一个规则的先行词（即前件），叶子结点的分类称为规则的结论（即后件）。

接下来通过删除不会降低估计精度的先行词来修剪每一个规则。选择这些修剪步骤中使估计精度有最大提升的步骤。

估计规则精度的一种方法是使用与训练集合不相交的验证集合。另一种方法是基于训练集合本身评估性能，但使用一种保守估计来弥补训练数据有利于当前规则的估计偏置。C4.5通过以下方法计算保守估计：先计算规则在它应用的训练样例上的精度，然后假定此估计精度为二项分布，并计算它的标准差。对于一个给定的置信区间，采用下界估计作为规则性能的度量。

虽然这种启发式方法不是统计有效的，但是已经发现它在实践中是有效的。在数据有限的许多实际情形下，这种方法很有效。

把决策树转化为规则集的好处：

• 转化为规则集可以区分决策节点使用的不同上下文。

• 转化为规则集消除了根节点附件的属性测试和叶节点附件的属性测试的区别。

• 转化为规则以提高可读性。

合并连续值属性

把连续值属性的值域分割为离散的区间集合。

属性选择的其他度量标准

信息增益度量存在一个内在的偏置，它偏袒具有较多值的属性，这种属性相对于训练样例有非常高的信息增益，但对于未见实例可能是一个非常差的目标函数预测器。

避免这种不足的一种方法是用其他度量而不是信息增益来选择决策属性。一个可以选择的度量标准是增益比率。增益比率通过加入一个被称作分裂信息(split information)的项来衡量属性分裂数据的广度和均匀性：

$SplitInformation(S,A) \equiv - \sum \limits ^c \limits _{i=1} \frac{|S_i|}{|S|} log_2 \frac{|S_i|}{|S|}$

其中，$S_1$ 到 $S_c$ 是 $c$ 个值的属性 $A$ 分割 $S$ 而形成的 $c$ 个样例子集。分裂信息实际上就是 $S$ 关于属性 $A$ 的各值的熵。

增益比率度量是用前面的增益度量和这里的分裂信息度量来共同定义的，即：

$GainRatio(S,A) \equiv \frac{Gain(S,A)}{SplitInformation(S,A)}$

分裂信息项阻碍选择值为均匀分布的属性。

处理缺少属性值的训练样例

处理缺少属性值的一种策略是赋给它节点n的训练样例中该属性的最常见值，或者赋给它节点 n 的被分类为 $c(x)$ 的训练样例中该属性的最常见值。

第二种更复杂的策略是为 $A$ 的每个可能值赋予一个概率，而不是简单地将最常见的值赋给 $A(x)$。根据节点n的样例上A的不同值得出现频率，这些频率可以被再次估计。

处理不同代价的属性

在某些学习任务中，实例的属性可能与代价相关。可以优先选择尽可能使用低价属性的决策树，仅当需要产生可靠的分类时才依赖高代价属性。

通过引入一个代价项到属性选择度量中，可以使ID3算法考虑属性代价。