2 机器学习-决策树学习.ppt

决策树学习，创建：Chang ray，来源：www . cs . utxas . edu/users/mooney/cs 391 l，决策树，决策树是实例(以唯一向量显示)的分类器。节点测试特征，边表示特征的每个值，叶节点对应于分类。可以表示任意提取和合并范例。也就是说，任意离散函数和离散特征可以将实例分为多个分类(2)，以提取范式(DNF)形式的red circle-positive circle-ablue-b；red square-b green-c；Red triangle-c、决策树学习、实例以(属性-值)对的形式显示。离散值处理简单，连续值可以划分地块。输出可以是离散分类或实数(回归树)。可以有效地处理大量数据，包括缺少或可处理噪声数据(分类噪声、属性噪声)属性值、默认决策树算法、培训数据放置、由上而下递归配置决策树DTree(examples，attributes)If所有示例属于同一分类，并返回该分类的标签的叶节点Elseif属性值为空a用作根节点ForA的每个可能值。VI是带有A=vi的示例子集，用于增加根节点中的分支(A=vi)。如果examplesi为空，则创建最常用的分类标签叶节点。否则，子树将调用DTree(examplesi)。属性-A，根属性选择，决策树数据集尽可能小的最小决策树NP-hard的简单递归算法是贪心启发式搜索，不保证最优子集必须尽可能“纯”，因此最常用的启发式规则是信息增益其中p和p-是s的正示例，反例是，如果所有样本属于同一分类，则熵为0(定义为0log0=0)，如果样本分布均匀(p=p-=0.5)，则熵被认为是对样本集分类进行编码所需的平均二进制位数，并被压缩为仅huff编码。更常见的分类编码越短，多分类问题(假定有c个分类)的熵的广义定义：其中pi是属于分类I的样本在s中所占的比例、信息增益、属性的信息增益是按该属性分割后熵的减少期望值。其中Sv是s中属性a值为v的子集示例：big、red、circle: small、red、Circle : small、red、square :-big、blue、blue摘要该空间内的搜索生成与数据相匹配的单个离散假设，因此，在不提供可靠性或构造有用的查询爬山搜索方面存在局部最优问题。可以找到适合所有无噪音数据集的树，但不一定是最小的批量学习。每个决策需要数据集扫描，可以提前结束学习以减少噪声的影响，在决策树学习中有误导性，树的深度必须最小化。但是，贪婪搜索可能找不到最小树。顶层节点不一定是高分隔。计算复杂性，最坏情况下，组织整个树。每个路径测试每个层次中其馀|A|-i属性计算的I。通常，性能和属性的数量是线性的。决策树研究的过去，1960s: hunt的完整搜索描述树方法(CLS)的概念学习建模20世纪70年代后期：Quinlan使用信息增益作为灵感策略的ID3方法，在从示例中学习构造专家系统的同时，B rehman和Friedman 学习教育数据并构建分类树可能无法达到最佳的一般化性能，噪声数据的影响部分决定仅基于少量数据，因此与客观事实不符。 据说h对教育数据进行了过度拟合。也就是说，在其他假设的情况下，在培训集中，H的误差小于H ，但在测试集中，H 的误差小于H，过度拟合和噪声、分类或属性噪声由于过度拟合而导致噪声实例增加(实际上-)，噪波直接导致样品的碰撞(相同说明，不同分类)。叶节点标签必须指定为主分类，如果-属性不完整且不足以确定分类，则可能会发生示例冲突以避免过度拟合。有两种基本方法需要修剪，即预先修剪。如果没有足够的支持，树的生长后修剪将停止。如果可信度不足，则是否需要修剪相应子树的确定方法：交叉检验：保留一些用于验证统计测试的培训数据：通过培训集的统计信息确定最小说明长度(MDL):确定此假设没有内存异常更复杂，减少错误修剪，后期修剪，交叉验证方法将培训数据称为“增长”和“验证”使用“增长”数据降低整个树Until验证数据集的精度。do: foreach树中的非叶节点n暂时修剪n子树，并修剪对精度影响最大的分支(指定为“主要分类”的叶)，而不是在验证集中计算树的准确度。最大信息增益可达到最大信息增益的单阈值分割算法Foreach连续特征Ai最好基于Ai值将样本排序为Foreach序列中的每个Xi对，以实现最佳平衡点，分割属性，将连续值映射为离散值节点分割。Xi 1IfXi和Xi 1的分类将Xi和Xi 1的中点作为可能的阈值(例如长度(:152128832450(顺序)分类： -检查阈值：L12.5、L24.5、L30、