[幼儿读物]2 机器学习-决策树学习.pptVIP

决策树学习 编写：张磊 决策树 决策树是实例（表示为特征向量）的分类器。结点测试特征，边表示特征的每个值，叶结点对应分类。 可表示任意析取和合取范式，从而表示任意离散函数和离散特征 可将实例分到多个分类(?2) 可以重写为规则，用析取范式（DNF）形式red ^ circle - positivered ^ circle - Ablue - B; red ^ square - Bgreen - C; red ^ triangle - C 决策树学习 实例用(属性-值)对表示。离散值处理简单，连续值可以划分区间。 输出可以是离散的分类，也可以是实数（回归树）。 能有效处理大量数据 可处理噪声数据（分类噪声，属性噪声） 属性值缺失，亦可处理 基本决策树算法 训练数据批处理，自顶向下递归构造决策树 DTree(examples, attributes)If 所有样本属于同一分类，返回标号为该分类的叶结点Else if 属性值为空，返回标号为最普遍分类的叶结点Else 选取一个属性，A，作为根结点 For A的每一个可能的值vi 令examplesi为具有A=vi的样本子集 从根结点出发增加分支（A=vi) 如果examplesi为空 则创建标号为最普遍分类的叶结点 否则递归创建子树——调用DTree(examplesi,attributes-{A}) 根属性的选取 决策树要尽可能小 寻找一组数据对应的最小决策树是NP-hard的 简单递归算法是贪婪启发式有哪些信誉好的足球投注网站，无法保证最优 子集应尽可能“纯”，从而易于成为叶结点 最常用的启发规则是基于信息增益(Information Gain) 熵(Entropy) 一组样本S对于二元分类的熵(混淆度)为：其中p+和 p-为S中的正例、反例所占比例 若所有样本属于同一分类，则熵为0(定义0log0=0) 若样本平均分布(p+=p-=0.5)，则熵最大(=1) 可把熵视为对样本集分类进行编码所需的平均二进制位数，采用哈夫曼编码压缩，越普遍的分类编码越短 对于多分类问题（假设有c个分类），则熵的推广定义：其中pi为属于分类i的样本在S中所占比例 信息增益 属性的信息增益是按该属性分割后熵的消减期望值：其中Sv是S中属性A值为v的子集 例子： big, red, circle : + small, red, circle : + small, red, square : - big, blue, circle : - 决策树归纳中的假设空间 决策树可以表示任何离散函数，归纳就是在此空间内的有哪些信誉好的足球投注网站 创建与数据一致的单一离散假设，所以无法提供置信度或构造有用的查询 爬山式有哪些信誉好的足球投注网站存在局部最优问题。它可以保证找到符合任何无噪声数据集的树，但未必是最小的 批量学习。每项决策需要一次数据集扫描，可提前结束学习以减少噪声影响 决策树学习中的误区 树的深度应尽量小。但贪婪有哪些信誉好的足球投注网站可能无法找到最小树，顶层结点可能不是高区分度的 计算复杂度 最坏情况是构造出一棵完全树，每条路径都测试了所有特征 各层i要对剩下的|A|-i个属性计算最佳分割 一般来说，性能与属性个数成线性关系 决策树研究的历史 1960’s：Hunt的完全有哪些信誉好的足球投注网站决策树方法（CLS）对概念学习建模 1970后期：Quinlan发明用信息增益作为启发策略的ID3方法，从样本中学习构造专家系统 同时，Breiman和Friedman开发的CART（分类与回归树）方法类似于ID3 1980’s：对噪声、连续属性、数据缺失、改善分割条件等进行研究 1993：Quinlan的改进决策树归纳包（C4.5），目前被普遍采用 过度拟合和修剪 通过学习训练数据来构造分类树，可能无法达到最好的泛化性能，因为 噪声数据的影响 某些决策仅基于少量数据，与客观事实不符合 一个假设H被称为对于训练数据是过度拟合的，指的是如果存在另一个假设H’，在训练集上H的误差比H‘小，但在测试集上H’的误差比H小 过度拟合与噪声 分类或属性噪声都会导致过度拟合增加噪声实例medium, green, circle, +（实际为-） 噪声也会直接导致样本的冲突(相同描述，不同分类)。应将叶结点标号为主要的分类big, red, circle, - (实际上为+) 若属性不完备且不足以判别分类时，也可能导致样本的冲突 避免过度拟合的方法 需要修剪时的两个基本方法 预修剪：支持度不够则停止树的增长 后修剪：置信度不够则修剪掉该分支 子树是否需要修剪的判别方法： 交叉检验：保留部分训练数据用于验证 统计测试：通过训练集的统计来判别 最小描述长度(MDL)：判别该假设的复杂度是否比记忆例外情况的复杂度更高 减