机器学习决策树学习.ppt

决策树学习 编写 张磊 来源 www cs utexas edu users mooney cs391L 2001年6月2日 决策树 决策树是实例 表示为特征向量 的分类器 结点测试特征 边表示特征的每个值 叶结点对应分类 可表示任意析取和合取范式 从而表示任意离散函数和离散特征可将实例分到多个分类 2 可以重写为规则 用析取范式 DNF 形式red circle positivered circle Ablue B red square Bgreen C red triangle C 2001年6月2日 决策树学习 实例用 属性 值 对表示 离散值处理简单 连续值可以划分区间 输出可以是离散的分类 也可以是实数 回归树 能有效处理大量数据可处理噪声数据 分类噪声 属性噪声 属性值缺失 亦可处理 2001年6月2日 基本决策树算法 训练数据批处理 自顶向下递归构造决策树DTree examples attributes If所有样本属于同一分类 返回标号为该分类的叶结点Elseif属性值为空 返回标号为最普遍分类的叶结点Else选取一个属性 A 作为根结点ForA的每一个可能的值vi令examplesi为具有A vi的样本子集从根结点出发增加分支 A vi 如果examplesi为空则创建标号为最普遍分类的叶结点否则递归创建子树 调用DTree examplesi attributes A 2001年6月2日 根属性的选取 决策树要尽可能小寻找一组数据对应的最小决策树是NP hard的简单递归算法是贪婪启发式搜索 无法保证最优子集应尽可能 纯 从而易于成为叶结点最常用的启发规则是基于信息增益 InformationGain 2001年6月2日 熵 Entropy 一组样本S对于二元分类的熵 混淆度 为 其中p 和p 为S中的正例 反例所占比例若所有样本属于同一分类 则熵为0 定义0log0 0 若样本平均分布 p p 0 5 则熵最大 1 可把熵视为对样本集分类进行编码所需的平均二进制位数 采用哈夫曼编码压缩 越普遍的分类编码越短对于多分类问题 假设有c个分类 则熵的推广定义 其中pi为属于分类i的样本在S中所占比例 2001年6月2日 信息增益 属性的信息增益是按该属性分割后熵的消减期望值 其中Sv是S中属性A值为v的子集例子 big red circle small red circle small red square big blue circle 2001年6月2日 决策树归纳中的假设空间 决策树可以表示任何离散函数 归纳就是在此空间内的搜索创建与数据一致的单一离散假设 所以无法提供置信度或构造有用的查询爬山式搜索存在局部最优问题 它可以保证找到符合任何无噪声数据集的树 但未必是最小的批量学习 每项决策需要一次数据集扫描 可提前结束学习以减少噪声影响 2001年6月2日 决策树学习中的误区 树的深度应尽量小 但贪婪搜索可能无法找到最小树 顶层结点可能不是高区分度的 2001年6月2日 计算复杂度 最坏情况是构造出一棵完全树 每条路径都测试了所有特征各层i要对剩下的 A i个属性计算最佳分割一般来说 性能与属性个数成线性关系 2001年6月2日 决策树研究的历史 1960 s Hunt的完全搜索决策树方法 CLS 对概念学习建模1970后期 Quinlan发明用信息增益作为启发策略的ID3方法 从样本中学习构造专家系统同时 Breiman和Friedman开发的CART 分类与回归树 方法类似于ID31980 s 对噪声 连续属性 数据缺失 改善分割条件等进行研究1993 Quinlan的改进决策树归纳包 C4 5 目前被普遍采用 2001年6月2日 过度拟合和修剪 通过学习训练数据来构造分类树 可能无法达到最好的泛化性能 因为噪声数据的影响某些决策仅基于少量数据 与客观事实不符合一个假设H被称为对于训练数据是过度拟合的 指的是如果存在另一个假设H 在训练集上H的误差比H 小 但在测试集上H 的误差比H小 2001年6月2日 过度拟合与噪声 分类或属性噪声都会导致过度拟合增加噪声实例 实际为 噪声也会直接导致样本的冲突 相同描述 不同分类 应将叶结点标号为主要的分类 实际上为 若属性不完备且不足以判别分类时 也可能导致样本的冲突 2001年6月2日 避免过度拟合的方法 需要修剪时的两个基本方法预修剪 支持度不够则停止树的增长后修剪 置信度不够则修剪掉该分支子树是否需要修剪的判别方法 交叉检验 保留部分训练数据用于验证统计测试 通过训练集的统计来判别最小描述长度 MDL 判别该假设的复杂度是否比记忆例外情况的复杂度更高 2001年6月2日 减小误差的修剪 一种后修剪 交叉验证的方法将训练数据分割为两个集合 生长 和 验证 用 生长 数据构建一棵完全树Until验证数据集合上的精度降低do Foreach树中非叶结点n临时修剪掉n下子树 用标号为主要分类的叶子代替在验证集上计算该树的精度修剪掉那些对精度影响最大的分支当训练集很小时 可能会严重损害分类精度最好能给定合适的结点数 达到最佳折衷 2001年6月2日 连续属性 用分区方法 将连续值映射为离散值结点分裂 以获得最大信息增益达到最大信息增益的单阈值分裂算法Foreach连续特征Ai根据Ai的值对样本排序Foreach序列中的每对Xi Xi 1IfXi和Xi 1的分类不同将Xi和Xi 1的中点作为可能的阈值进行检验 即例如 长度 L 10152128324050 已排序 分类 检查阈值 L 12 5 L 24 5 L 30 L 45 2001年6月2日 替代属性选取启发策略 增益比率 信息增益缺点 偏爱那些有大量值的属性 产生很多小而纯的子集 如病人ID 姓名 日期等要降低这些情况下的增益首先计算与分类无关属性的信息量 即该属性的熵其中Si为S中具有属性A第i个值的子集 某属性按值分割样本越平均 则SplitInfo越大增益比率利用SplitInfo来避免选择这些属性 2001年6月2日 增益比率细述 然而 当 Si S 时SplitInfo可能很小甚至为0 从而导致信息比率过大甚至溢出C4 5对此进行了改进 它计算每个特征的信息增益 对于超过平均增益的特征 再进一步根据增益比率来选取特征 2001年6月2日 缺失的属性值 属性值可能未完全给出一种解决方法是根据已有样本属性值的先验概率来对样本计算属性值分布百分比在训练时 缺失的属性会按照其分布百分比逐个计算 例如 给定一个缺失了颜色属性值的正例 它将被视为0 6个red正例 0 2个blue正例和0 2个green正例 2001年6月2日 测试时的值缺失 若属性值未给出 则设定为 通配符 然后多路径到达叶结点 最后计算分类结果的各分类权重例如 将得到0 6个正例 0 2 0 2 0 4个反例将得到0 2个正例 0 5 0 3 0 8个反例将得到0 6x0 2 0 12个正例 0 2 0 2 0 3 0 18 0 88个反例 2001年6月2日 属性开销 有些领域中 某些属性比其它属性更容易获取其值 例如病人的体温比其胆固醇水平更容易得到 尽可能采用那些低开销的属性来分类在信息增益中增加属性开销是有效的 在不降低精度的同时降低了平均开销 2001年6月2日 递增式的决策树归纳 ID4和ID5可以递增更新已有的树ID4有时会丢弃某些实例 不保证和历史训练样本一致ID5则保证和ID3的决策相同ID4速度快 但精度降低ID5速度较快且精度不变 2001年6月2日 决策树中的重复部分 决策树比DNF更复杂 因为它常常存在重复部分范式必须分解为析取范式 导致了重复子树的出现解决 使用复杂特征或决策图构造性归纳 原子特征的逻辑组合或算术组合 2001年6月2日 边缘算法 决策树构造性归纳的叠代算法边缘算法 总是沿着树的边缘走 Until没有新的特征被创建或到达限定值do使用当前的所有特征从训练集构造决策树从边缘末端 正例 两个特征的联合来创建新特征将这些新特征加入现有特征集中 同时扩展每个样本的描述以包含所有新特征 2001年6月2日 边缘示例 2001年6月2日 多重模型 学习概念的多重候选定义最终决策是基于多个学习模型的 加权 投票 2001年6月2日 装袋 Bagging 用训练集的不同样本来训练同一个学习者 来创建多重模型 Breiman 1996 给定训练集大小为n 通过从原始数据取样 用替换方法 创建m个不同的训练集 大小为n 用简单的投票方法来合并这m个模型可用于任何学习方法减少了不稳定学习算法的一般化错误 即当训练数据轻微改动时会导致决策结果剧烈变动的那些学习方法 2001年6月2日 引导 Boosting 另一个生成多重模型的方法 重复更改同一个学习算法的数据对弱学习算法 假设的精度只要超过1 2即可 能保证性能的改进对样本加权 每次叠代产生一个新的假设 对那些导致最终假设精度变差的样本重新加权基本算法给所有样本赋予一个初始权重Forifrom1toTdo从加权的样本中学习一个假设hi减小那些与hi一致的样本的权重在测试时 每个假设会得到一个加权的投票 与训练数据上的精度成比例 2001年6月2日 引导算法 ForD中的每个样本 令其权重wi 1 D Fortfrom1t