3.决策树学习

2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏1机器学习第3章决策树学习2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏2概论•决策树学习是应用最广的归纳推理算法之一•是一种逼近离散值函数的方法•很好的健壮性•能够学习析取表达式•ID3,Assistant,C4.5•搜索一个完整表示的假设空间•归纳偏置是优先选择较小的树•决策树表示了多个if-then规则2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏3提纲•决策树定义•适用问题特征•基本ID3算法•决策树学习的归纳偏置•训练数据的过度拟合•更深入的话题2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏4决策树表示法•决策树–通过把实例从根节点排列到某个叶子节点来分类实例。–叶子节点即为实例所属的分类–树上每个节点说明了对实例的某个属性的测试–节点的每个后继分支对应于该属性的一个可能值•图3-1•决策树代表实例属性值约束的合取的析取式。从树根到树叶的每一条路径对应一组属性测试的合取，树本身对应这些合取的析取。2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏5决策树学习的适用问题•适用问题的特征–实例由“属性-值”对表示–目标函数具有离散的输出值–可能需要析取的描述–训练数据可以包含错误–训练数据可以包含缺少属性值的实例•问题举例–根据疾病分类患者–根据起因分类设备故障–根据拖欠支付的可能性分类贷款申请•分类问题–核心任务是把样例分类到各可能的离散值对应的类别2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏6基本的决策树学习算法•大多数决策树学习算法是一种核心算法的变体•采用自顶向下的贪婪搜索遍历可能的决策树空间•ID3是这种算法的代表2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏7基本的决策树学习算法（2）•ID3的思想–自顶向下构造决策树–从“哪一个属性将在树的根节点被测试”开始–使用统计测试来确定每一个实例属性单独分类训练样例的能力•ID3的过程–分类能力最好的属性被选作树的根节点–根节点的每个可能值产生一个分支–训练样例排列到适当的分支–重复上面的过程2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏8表3-1用于学习布尔函数的ID3算法概要•ID3(Examples,Target_attribute,Attributes)•创建树的root节点•如果Examples都为正,返回label=+的单节点树root•如果Examples都为反,返回label=-的单节点树root•如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值•否则开始–AAttributes中分类examples能力最好的属性–root的决策属性A–对于A的每个可能值vi•在root下加一个新的分支对应测试A=vi•令Examplesvi为Examples中满足A属性值为vi的子集•如果Examplesvi为空–在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值–否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-{A}）•结束•返回root2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏9最佳分类属性•信息增益–用来衡量给定的属性区分训练样例的能力–ID3算法在增长树的每一步使用信息增益从候选属性中选择属性•用熵度量样例的均一性–熵刻画了任意样例集的纯度–给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为Entropy(S)=-p+log2p+-p-log2p-–信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数–更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为Entropy(S)=ciiipp12log2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏10最佳分类属性（2）•用信息增益度量期望的熵降低–属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低–Gain(S,A)是在知道属性A的值后可以节省的二进制位数–例子)()(||)(),(AValuesvvvSEntropySSSEntropyASGain2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏11ID3算法举例•表3-2–…–继续这个过程，直到满足以下两个条件中的一个•所有的属性已经被这条路经包括•与这个节点关联的所有训练样例都具有相同的目标属性值2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏12决策树学习中的假设空间搜索•观察ID3的搜索空间和搜索策略，认识到这个算法的优势和不足–假设空间包含所有的决策树，它是关于现有属性的有限离散值函数的一个完整空间–维护单一的当前假设（不同于第二章的变型空间候选消除算法）–不进行回溯，可能收敛到局部最优–每一步使用所有的训练样例，不同于基于单独的训练样例递增作出决定，容错性增强2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏13决策树学习的归纳偏置•ID3的搜索策略–优先选择较短的树–选择那些信息增益高的属性离根节点较近的树–很难准确刻画ID3的归纳偏置•近似的ID3的归纳偏置–较短的树比较长的树优先–近似在于ID3得到局部最优，而不一定是全局最优–一个精确具有这个归纳偏置的算法，BFS-ID3•更贴切近似的归纳偏置–较短的树比较长的树优先，信息增益高的属性更靠近根节点的树优先2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏14限定偏置和优选偏置•ID3和候选消除算法的比较–ID3的搜索范围是一个完整的假设空间，但不彻底地搜索这个空间–候选消除算法的搜索范围是不完整的假设空间，但彻底地搜索这个空间–ID3的归纳偏置完全是搜索策略排序假设的结果，来自搜索策略–候选消除算法完全是假设表示的表达能力的结果，来自对搜索空间的定义2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏15限定偏置和优选偏置•优选偏置–ID3的归纳偏置是对某种假设胜过其他假设的一种优选，对最终可列举的假设没有硬性限制•限定偏置–候选消除算法的偏置是对待考虑假设的一种限定•通常优选偏置比限定偏置更符合归纳学习的需要•优选偏置和限定偏置的结合–考虑第1章的例子2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏16为什么短的假设优先•ID3的归纳偏置的哲学基础•奥坎姆剃刀–优先选择拟合数据的最简单的假设•科学上的例子–物理学家优先选择行星运动的简单假设–简单假设的数量远比复杂假设的数量少–简单假设对训练样例的针对性更小，更像是泛化的规律，而不是训练样例的另一种描述2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏17为什么短的假设优先•奥坎姆剃刀的困难–我们反问，使用上页的推理，应该优先选择包含恰好17个叶子节点和11个非叶子节点的决策树？–假设的规模由学习器内部使用的特定表示决定•从生物进化的观点看内部表示和奥坎姆剃刀原则2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏18决策树学习的常见问题•决策树学习的实际问题–确定决策树增长的深度–处理连续值的属性–选择一个适当的属性筛选度量标准–处理属性值不完整的训练数据–处理不同代价的属性–提高计算效率•针对这些问题，ID3被扩展成C4.52003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏19避免过度拟合数据•过度拟合–对于一个假设，当存在其他的假设对训练样例的拟合比它差，但事实上在实例的整个分布上表现得却更好时，我们说这个假设过度拟合训练样例–定义：给定一个假设空间H，一个假设hH，如果存在其他的假设h’H，使得在训练样例上h的错误率比h’小，但在整个实例分布上h’的错误率比h小，那么就说假设h过度拟合训练数据。–图3-6的例子2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏20避免过度拟合数据（2）•导致过度拟合的原因–一种可能原因是训练样例含有随机错误或噪声–当训练数据没有噪声时，过度拟合也有可能发生，特别是当少量的样例被关联到叶子节点时，很可能出现巧合的规律性，使得一些属性恰巧可以很好地分割样例，但却与实际的目标函数并无关系。2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏21避免过度拟合数据（3）•避免过度拟合的方法–及早停止树增长–后修剪法•两种方法的特点–第一种方法更直观–第一种方法中，精确地估计何时停止树增长很困难–第二种方法被证明在实践中更成功2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏22避免过度拟合数据（4）•避免过度拟合的关键–使用什么样的准则来确定最终正确树的规模•解决方法–使用与训练样例截然不同的一套分离的样例，来评估通过后修剪方法从树上修建节点的效用。–使用所有可用数据进行训练，但进行统计测试来估计扩展（或修剪）一个特定的节点是否有可能改善在训练集合外的实例上的性能。–使用一个明确的标准来衡量训练样例和决策树的复杂度，当这个编码的长度最小时停止树增长。2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏23避免过度拟合数据（5）•方法评述–第一种方法是最普通的，常被称为训练和验证集法。–可用数据分成两个样例集合：•训练集合，形成学习到的假设•验证集合，评估这个假设在后续数据上的精度–方法的动机：即使学习器可能会被训练集合误导，但验证集合不大可能表现出同样的随机波动–验证集合应该足够大，以便它本身可提供具有统计意义的实例样本。–常见的做法是，样例的三分之二作训练集合，三分之一作验证集合。2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏24错误率降低修剪•将树上的每一个节点作为修剪得候选对象•修剪步骤–删除以此节点为根的子树，使它成为叶结点–把和该节点关联的训练样例的最常见分类赋给它–反复修剪节点，每次总是选取那些删除后可以最大提高决策树在验证集合上的精度的节点•继续修剪，直到进一步的修剪是有害的为止•数据分成3个子集–训练样例，形成决策树–验证样例，修剪决策树–测试样例，精度的无偏估计•如果有大量的数据可供使用，那么使用分离的数据集合来引导修剪2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏25规则后修剪•从训练集合推导出决策树，增长决策树直到尽可能好地拟合训练数据，允许过度拟合发生•将决策树转化为等价的规则集合，方法是为从根节点到叶节点的每一条路径创建一条规则•通过删除任何能导致估计精度提高的前件来修剪每一条规则•按照修剪过的规则的估计精度对它们进行排序，并按这样的顺序应用这些规则来分类后来的实例2003.11.18机器学习-决策树学习译者：曾华军等作者：Mitchell讲者：陶晓鹏26规则后修剪（2）•例子–图3-1的最左一条路径–if(outlook=sunny)(Humidity=High)thenPlayTennis=No–考虑删除先行词(outlook=sun