第4章：决策树-2017-v2.ppt

第4章 1 分类 决策树 4 1预备知识4 2解决分类问题的一般方法4 3决策树归纳4 3 1决策树的工作原理4 3 2如何建立决策树补充 ID3决策树详解 后继C4 5 4 3 3表示属性测试条件的方法4 3 4选择最佳划分的度量4 4模型的过分拟合 分类的是利用一个分类函数 分类模型 分类器 该模型能把数据库中的数据映射到给定类别中的一个 训练样本 学习测试 分类属性分类界限or分类规则 思路 人如何学习 分类类比 计算机如何学习 分类 分类 基本概念 训练集 数据库中为建立模型而被分析的数据元组形成训练集 训练集中的单个元组称为训练样本 每个训练样本有一个类别标记 一个具体样本的形式可为 v1 v2 vn c 其中vi表示属性值 c表示类别 测试集 检验集 用于评估分类模型的准确率 数据分类 一个两步过程 1 第一步 建立一个模型 描述预定数据类集和概念集假定每个元组属于一个预定义的类 由一个类标号属性确定学习模型可以用分类规则 决策树或数学公式的形式提供 数据分类 一个两步过程 2 第二步 使用模型 对将来的或未知的对象进行分类首先评估模型的预测准确率对每个测试样本 将已知的类标号和该样本的学习模型类预测比较模型在给定测试集上的准确率是正确被模型分类的测试样本的百分比测试集要独立于训练样本集 否则会出现 过分适应数据 的情况如果准确性能被接受 则分类规则就可用来对新数据进行分类 有监督的学习VS 无监督的学习 有监督的学习 用于分类 模型的学习在被告知每个训练样本属于哪个类的 监督 下进行新数据使用训练数据集中得到的规则进行分类无监督的学习 用于聚类 每个训练样本的类编号是未知的 要学习的类集合或数量也可能是事先未知的通过一系列的度量 观察来建立数据中的类编号或进行聚类 分类模型的构造方法 1 机器学习方法 决策树法规则归纳2 统计方法 知识表示是判别函数和原型事例贝叶斯法非参数法 近邻学习或基于事例的学习 3 神经网络方法 BP算法 模型表示是前向反馈神经网络模型4 粗糙集 roughset 知识表示是产生式规则 4 1预备知识4 2解决分类问题的一般方法4 3决策树归纳4 3 1决策树的工作原理4 3 2如何建立决策树补充 ID3决策树详解 后继C4 5 4 3 3表示属性测试条件的方法4 3 4选择最佳划分的度量4 4模型的过分拟合 一个决策树的例子 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K SplittingAttributes 训练数据 模型 决策树 决策树的另一个例子 categorical categorical continuous class MarSt Refund TaxInc YES NO NO Yes No Married Single Divorced 80K 80K 用决策树归纳分类 什么是决策树 类似于流程图的树结构每个内部节点表示在一个属性上的测试每个分枝代表一个测试输出每个树叶节点代表类或类分布决策树的生成由两个阶段组成决策树构建开始时 所有的训练样本都在根节点递归的通过选定的属性 来划分样本 必须是离散值 树剪枝许多分枝反映的是训练数据中的噪声和孤立点 树剪枝试图检测和剪去这种分枝决策树的使用 对未知样本进行分类通过将样本的属性值与决策树相比较 为了对未知数据对象进行分类识别 可以根据决策树的结构对数据集中的属性进行测试 从决策树的根节点到叶节点的一条路径就形成了相应对象的类别测试 决策树可以很容易转换为分类规则 决策树分类任务 DecisionTree 一个决策树的例子 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K SplittingAttributes 训练数据 模型 决策树 应用决策树进行分类 测试数据 Startfromtherootoftree 应用决策树进行分类 测试数据 应用决策树进行分类 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 测试数据 应用决策树进行分类 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 测试数据 应用决策树进行分类 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 测试数据 应用决策树进行分类 Refund MarSt TaxInc YES NO NO NO Yes No Married Single Divorced 80K 80K 测试数据 AssignCheatto No 决策树分类 DecisionTree 4 1预备知识4 2解决分类问题的一般方法4 3决策树归纳4 3 1决策树的工作原理4 3 2如何建立决策树补充 ID3决策树详解 后继C4 5 4 3 3表示属性测试条件的方法4 3 4选择最佳划分的度量4 4模型的过分拟合 决策树 有许多决策树算法 Hunt算法信息增益 Informationgain ID3 增益比率 Gainration C4 5 基尼指数 Giniindex SLIQ SPRINT Hunt算法 设Dt是与结点t相关联的训练记录集算法步骤 如果Dt中所有记录都属于同一个类yt 则t是叶结点 用yt标记如果Dt中包含属于多个类的记录 则选择一个属性测试条件 将记录划分成较小的子集 对于测试条件的每个输出 创建一个子结点 并根据测试结果将Dt中的记录分布到子结点中 然后 对于每个子结点 递归地调用该算法 Dt Hunt算法 Don tCheat 决策树构建 Hunt算法采用贪心策略构建决策树 在选择划分数据的属性时 采取一系列局部最优决策来构造决策树 决策树归纳的设计问题如何分裂训练记录如何停止分裂过程 怎样选择最佳划分 选择最佳划分的度量通常是根据划分后子结点不纯性的程度 不纯性的程度越低 类分布就越倾斜结点不纯性的度量 不纯性大 不纯性小 怎样找到最佳划分 B Yes No NodeN3 NodeN4 A Yes No NodeN1 NodeN2 划分前 Gain M0 M12vsM0 M34 结点不纯性的测量 GiniEntropyclassificationerror 停止分裂过程 当所有的记录属于同一类时 停止分裂当所有的记录都有相同的属性时 停止分裂提前终止树的生长 三种著名的决策树 Cart 基本的决策树算法Id3 利用增益比不纯性 树采用二叉树 停止准则为当所有的记录属于同一类时 停止分裂 或当所有的记录都有相同的属性时 停止分裂C4 5 id3的改进版本 也是最流行的分类数算法 采用多重分支和剪枝技术 决策树 特点 决策树是一种构建分类模型的非参数方法不需要昂贵的的计算代价决策树相对容易解释决策树是学习离散值函数的典型代表决策数对于噪声的干扰具有相当好的鲁棒性冗余属性不会对决策树的准确率造成不利影响数据碎片问题 随着数的生长 可能导致叶结点记录数太少 对于叶结点代表的类 不能做出具有统计意义的判决子树可能在决策树中重复多次 使决策树过于复杂 4 1预备知识4 2解决分类问题的一般方法4 3决策树归纳4 3 1决策树的工作原理4 3 2如何建立决策树补充 ID3决策树详解 后继C4 5 4 3 3表示属性测试条件的方法4 3 4选择最佳划分的度量4 4模型的过分拟合 ID3算法详解 ID3使用信息增益作为属性选择度量 该度童基于香农 ClaudeShannon 在研究消息的值或 信息内容 的信息论方面的先驱工作 设结点N代表或存放分区D的元组 选择具有最高信息增益的属性作为结点N的分裂属性 该属性使结果分区中对元组分类所需要的信息量最小 并反映这些分区中的最小随机性或 不纯性 这种方法使得对一个对象分类所需要的期望测试数目最小 并确保找到一棵简单的 但不必是最简单的 树 ID3算法 对D中的元组分类所需要的期望信息由下式给出 其中 Pi是D中任意元组属于类Ci的非零概率 并用估计 Info D 是识别D中无组的类标号所需要的平均信息量 注意 此时我们所有的信息只是每个类的元组所占的百分比 Info D 又称为D的熵 entropy 非负性 Info D 大于等于0连续性 Info D 对任意q连续极值性 当q都等于1 K时Info D 达到最大值logK ID3算法 期望信息 熵 entropy ID3算法 计算Entropy的例子 P C1 0 6 0P C2 6 6 1Info D 1log1 0 0 P C1 1 6P C2 5 6Info D 1 6 log2 1 6 5 6 log2 1 6 0 65 P C1 2 6P C2 4 6Info D 2 6 log2 2 6 4 6 log2 4 6 0 92 P C1 3 6P C2 3 6Info D 1 2 log2 1 2 1 2 log2 1 2 1 现在 假设我们要按某属性A划分D中的元组 其中属性A根据训练数据的观测具有v个不同值如果A是离散值的 则这些值直接对应A上测试的v个输出 可以用属性A将D划分为v个分区或子集其中 Dj包含D中的元组 它们的A值为aj 这些分区对应于从结点N生长出来的分枝 理想情况下 我们希望该划分产生元组的准确分类 即我们希望每个分区都是纯的 然而 这些分区多半是不纯的 例如 分区可能包含来自不同类而不是来自单个类的元组 在此划分之后 为了得到准确的分类 我们还需要多少信息 这个量由划分A的期望信息度量 ID3算法 期望信息 熵 entropy 划分的期望信息项充当第j个分区的权重 InfoA D 是基于按A划分对D的元组分类所需要的期望信息 需要的期望信息越小 分区的纯度越高 信息增益定义为原来的信息需求 仅基于类比例 与新的信息需求 对A划分后1 之间的差 即 ID3算法 信息增益 信息增益定义为原来的信息需求 仅基于类比例 与新的信息需求 对A划分后1 之间的差 即换言之 Gain A 告诉我们通过A上的划分我们得到了多少 它是知道A的值而导致的信息需求的期望减少 选择具有最高信息增益Gain A 的属性A作为结点N的分裂属性 这等价于在 能做最佳分类 的属性A上划分 使得完成元组分类还需要的信息最小 即最小化Gain A ID3算法 信息增益 Trainingdataset Buys computerThedatasetfollowsanexampleofQuinlan sID3 PlayingTennis Resultingtree ID3算法 例子 一个标记类的元组的训练集D 随机地从AlIElectronics顾客数据库中选取 在这个例子中 每个属性都是离散值的 连续值属性已经被离散化 类标号属性buys compter有两个不同值 即 yes no 因此有两个不同的类 即m 2 设类C1对应于yes 而类C2对应于no 类yes有9个元组 类no有5个元组 为D中的元组创建 根 结点N 为了找出这些元组的分裂准则 必须计算每个属性的信息增益 ID3算法 例子 下一步 需要计算每个属性的期望信息需求 从属性age开始 需要对age的每个类考察yes和no元组的分布 ID3算法 例子 ClassP buys computer yes ClassN buys computer no 由于age在属性中具有最高的信息增益 所以它被选作分裂属性 结点N用age标记 并且每个属性值生长出一个分枝 然后元组据此划分 如图所示 ID3算法 例子 注意 落在分区age 30 40 的元组都属于相同的类 由于它们都属于类 yes 所以要在该分枝的端点创建一个树叶 并用 yes 标记 ID3算法 例子 信息增益度量偏向具有许多输出的测试 换句话说 它倾向于选择具有大量值的属性 例如 考虑充当唯一标识符的属性 如product ID 在product ID的划分将导致大量分区 与值一样多 每个只包含一个元组 由于每个分区都是纯的 所以基于该划分对数据集D分类所需要的信息Infoproduct ID D 0 因此 通过对该属性的划分得到的信息增益最大 显然 这种划分对分类没有用 1D3的后继C4 5使用一种称为增益率 gainratio 的信息增益扩充 试图克服这种偏倚 它用 分裂信息 splitinfonnation 值将信息增益规范化 C4 5算法 增益率 分裂信息 splitinfonnation 定义如下 该值代表由训练数据集D划分成对应于属性A测试的v个输出的v个分区共生的信息 注意 对于每个输出 它相对于D中元组的总数考虑具有该输出的元组数 增益率 gainratio 定义如下 GainRatio A Gain A SplitInfo A 属性income的测试将数据划分成3个分区 即low medium和high 分别包含4 6和4个元组 gain ratio income 0 029 1 557 0 019 C4 5算法 增益率 4 1预备知识4 2解决分类问题的一般方法4 3决策树归纳4 3 1决策树的工作原理4 3 2如何建立决策树补充 ID3决策树详解 后继C4 5 4 3 3表示属性测试条件的方法4 3 4选择最佳划分的度量4 4模型的过分拟合 怎样为不同类型的属性指定测试条件 依赖于属性的类型二元标称序数连续依赖于划分的路数2路划分多路划分 基于标称属性的分裂 多路划分 划分数 输出数 取决于该属性不同属性值的个数 二元划分 划分数为2 这种划分要考虑创建k个属性值的二元划分的所有2k 1 1种方法 OR 多路划分 划分数 输出数 取决于该属性不同属性值的个数 二元划分 划分数为2 需要保持序数属性值的有序性 基于序数属性的划分 OR 基于连续属性的划分 多路划分 vi A vi 1 i 1 k 二元划分 A v or A v 考虑所有的划分点 选择一个最佳划分点v 基于连续属性的划分 ID3算法如何计算连续值属性的信息增益 假设属性A是连续值的 而不是离散值的 例如 假定有属性age的原始值 而不是该属性的离散化版本 对于这种情况 必须确定A的 最佳 分裂点 其中分裂点是A上的阈值 首先 将A的值按递增序排序 典型地 每对相邻值的中点被看做可能的分裂点 这样 给定A的v个值 则需要计算v 1个可能的划分 例如 A的值ai和ai 1之间的中点是 ai ai 1 2如果A的值已经预先排序 则确定A的最佳划分只需要扫描一遍这些值 对于A的每个可能分裂点 计算lnfoA D 其中分区的个数为2 A具有最小期望信息需求的点选做A的分裂点 D1是满足A split poin的元组集合 而D2是满足A split point的元组集合 基于连续属性的划分 ID3算法 4 1预备知识4 2解决分类问题的一般方法4 3决策树归纳4 3 1决策树的工作原理4 3 2如何建立决策树补充 ID3决策树详解 后继C4 5 4 3 3表示属性测试条件的方法4 3 4选择最佳划分的度量4 4模型的过分拟合 怎样选择最佳划分 选择最佳划分的度量通常是根据划分后子结点不纯性的程度 不纯性的程度越低 类分布就越倾斜结点不纯性的度量 不纯性大 不纯性小 结点不纯性的测量 GiniEntropyclassificationerror 不纯性的测量 GINI 给定结点t的Gini值计算 p j t 是在结点t中 类j发生的概率 当类分布均衡时 Gini值达到最大值 1 1 nc 相反当只有一个类时 Gini值达到最小值0 计算GINI的例子 P C1 0 6 0P C2 6 6 1Gini 1 P C1 2 P C2 2 1 0 1 0 P C1 1 6P C2 5 6Gini 1 1 6 2 5 6 2 0 278 P C1 2 6P C2 4 6Gini 1 2 6 2 4 6 2 0 444 基于GINI的划分 当一个结点p分割成k个部分 孩子 划分的质量可由下面公式计算ni 孩子结点i的记录数 n 父结点p的记录数 基于ClassificationError的划分 给定结点t的ClassificationError值计算 当类分布均衡时 error值达到最大值 1 1 nc 相反当只有一个类时 error值达到最小值0 例子 P C1 0 6 0P C2 6 6 1Error 1 max 0 1 1 1 0 P C1 1 6P C2 5 6Error 1 max 1 6 5 6 1 5 6 1 6 P C1 2 6P C2 4 6Error 1 max 2 6 4 6 1 4 6 1 3 不纯性度量之间的比较 二元分类问题 4 1预备知识4 2解决分类问题的一般方法4 3决策树归纳4 3 1决策树的工作原理4 3 2如何建立决策树补充 ID3决策树详解 后继C4 5 4 3 3表示属性测试条件的方法4 3 4选择最佳划分的度量4 4模型的过分拟合 模型过分拟合和拟合不足 分类模型的误差大致分为两种 训练误差 是在训练记录上误分类样本比例泛化误差 是模型在未知记录上的期望误差一个好的分类模型不仅要能够很好的拟合训练数据 而且对未知样本也要能准确分类 换句话说 一个好的分类模型必须具有低训练误差和低泛化误差 当训练数据拟合太好的模型 其泛化误差可能比具有较高训练误差的模型高 这种情况成为模型过分拟合 模型过分拟合和拟合不足 当决策树很小时 训练和检验误差都很大 这种情况称为模型拟合不足 出现拟合不足的原因是模型尚未学习到数据的真实结构 随着决策树中结点数的增加 模型的训练误差和检验误差都会随之下降 当树的规模变得太大时 即使训练误差还在继续降低 但是检验误差开始增大 导致模型过分拟合 模型模型过分拟合和拟合不足 过分拟合 导致过分拟合的原因 1 噪声 导致过分拟合的原因 1 噪声 噪声导致的过分拟合例子 哺乳动物的分类问题十个训练记录中有两个被错误标记 蝙蝠和鲸如果完全拟合训练数据 决策树1的训练误差为0 但它在检验数据上的误差达30 人和海豚 针鼹误分为非哺乳动物相反 一个更简单的决策树2