决策树学习
决策树学习是应用最广的归纳推理算法之一.它是一种逼近离散函数的方法,且对噪声数据有很好的鲁棒性,能够学习析取表达式.本章描述了一系列决策树学习算法,包括象ID3,ASSISTANT和C4.5这样广为应用的算法.这些决策树学习方法搜索完整表示的假设空间,从而避免了受限假设空间的不足.决策树学习的归纳偏置是优先选择较小的树.
简介
决策树学习是一种逼近离散值目标函数的方法,在这种方法中学习到的函数被表示为一棵决策树.学习得到的决策树也能再被表示为多个if-then的规则,以提高可读性.这种学习算法是最流行的归纳推理算法之一,已经被成功地应用到从学习医疗诊断到学习评估贷款申请的信用风险的广阔领域.
决策树表示法
决策树通过把实例从根结点排列(sort)到某个叶子结点来分类实例,叶子结点即为实例所属的分类.树上的每一个结点指定了对实例的某个属性(attribute)的测试,并且该结点的每一个后继分支对应于该属性的一个可能值.分类实例的方法是从这棵树的根结点开始,测试这个结点指定的属性,然后按照给定实例的该属性值对应的树枝向下移动.这个过程再在以新结点为根的子树上重复.
53
图3-1 概念PlayTennis的决策树
分类一个样例的方法是,将其沿根结点排列到合适的叶子结点,然后返回与这个叶子结点关联的分类(本例中为Yes或No).这棵决策树根据天气分类"星期六上午是否适合打网球".
图3-1画出了一棵典型的学习到的决策树.这棵决策树根据天气情况分类"星期六上午是否适合打网球".例如,下面的实例:

将被沿着这棵决策树的最左分支向下排列,因而被评定为反例(也就是这棵树预测这个实例PlayTennis=No).这棵树以及表3-2中用来演示ID3学习算法的例子摘自(Quinlan 1986).
通常决策树代表实例属性值约束的合取(conjunction)的析取式(disjunction).从树根到树叶的每一条路径对应一组属性测试的合取,树本身对应这些合取的析取.例如,图3-1表示的决策树对应于以下表达式:
(Outlook=Sunny Humidity=Normal)
(Outlook=Overcast)
(Outlook=Rain Wind=Weak)
决策树学习的适用问题
尽管已经开发的种种决策树学习算法有这样或那样不太一致的能力和要求,通常决策树学习最适合具有以下特征的问题:
实例是由"属性-值"对(pair)表示的.实例是用一系列固定的属性(例如,Temperature)和它们的值(例如,Hot)来描述的.最简单的决策树学习中,每一个属性取少数的分离的值(例如,Hot,Mild,Cold).然而,扩展的算法(在3.7.2节中讨论)也允许处理值域为实数的属性(例如,数字表示的温度).
目标函数具有离散的输出值.图3-1的决策树给每个实例赋予一个布尔型的分类(例如,yes或no).决策树方法很容易扩展到学习有两个以上输出值的函数.一种更强有力的扩展算法允许学习具有实数值输出的函数,尽管决策树在这种情况下的应用不太常见.
可能需要析取的描述(disjunctive description).如上面指出的,决策树很自然地代表了析取表达式.
训练数据可以包含错误.决策树学习对错误有很好的鲁棒性,无论是训练样例所属的分类错误还是描述这些样例的属性值错误.
训练数据可以包含缺少属性值的实例.决策树学习甚至可以在有未知属性值的训练样例中使用(例如,仅有一部分训练样例知道当天的湿度).这个问题将在第3.7.4小节中讨论.
已经发现很多实际的问题符合这些特征,所以决策树学习已经被应用到很多问题中.例如根据疾病分类患者;根据起因分类设备故障;根据拖欠支付的可能性分类贷款申请.对于这些问题,核心任务都是要把样例分类到各可能的离散值对应的类别(category)中,因此经常被称为分类问题(Classification Problem).
这一章的其余部分是这样安排的.3.4节给出学习决策树的基本ID3算法并演示它的具体操作.3.5节分析使用这种学习算法进行的假设空间搜索,并与第2章的算法进行了比较.3.6节刻画了决策树学习算法的归纳偏置,并更一般化的探索了一种被称为奥坎姆剃刀的归纳偏置,该偏置优先选择最简单的假设.3.7节讨论了训练数据的过度拟合(overfitting),以及解决这种问题的策略,比如规则后修剪(post-pruning).这一节还讨论了一些更深入的话题,比如将算法扩展以适应实数值属性,带有未观测到属性的训练数据,以及有不同代价的属性.

下一页