决策树学习资料55558

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,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,所有样本属于同一分类，返回标号为该分类的叶结点,Else if,属性值为空，返回标号为最普遍分类的叶结点,Else,选取一个属性，,A，,作为根结点,For,A,的每一个可能的值,v,i,令,examples,i,为具有,A,=,v,i,的样本子集 从根结点出发增加分支（,A=v,i,),如果,examples,i,为空 则创建标号为最普遍分类的叶结点 否则递归创建子树调用,DTree(examples,i,attributes-A),2001年6月2日,根属性的选取,决策树要尽可能小,寻找一组数据对应的最小决策树是NP-hard的,简单递归算法是贪婪启发式搜索，无法保证最优,子集应尽可能“纯”，从而易于成为叶结点,最常用的启发规则是基于信息增益(Information Gain),2001年6月2日,熵(Entropy),一组样本,S,对于二元分类的熵(混淆度)为：其中,p,+,和,p,-,为S中的正例,、,反例所占比例,若所有样本属于同一分类，则熵为0(定义0,log0=0,),若样本平均分布(,p,+,=p,-,=0.5),，,则熵最大(=1),可把熵视为对样本集分类进行编码所需的平均二进制位数，采用哈夫曼编码压缩，越普遍的分类编码越短,对于多分类问题（假设有,c,个分类），则熵的推广定义：其中,p,i,为属于分类,i,的样本在,S,中所占比例,2001年6月2日,信息增益,属性的信息增益是按该属性分割后熵的消减期望值：其中,S,v,是,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日,决策树研究的历史,1960s：Hunt的完全搜索决策树方法（CLS）对概念学习建模,1970后期：Quinlan发明用信息增益作为启发策略的ID3方法，从样本中学习构造专家系统,同时，Breiman和Friedman开发的CART（分类与回归树）方法类似于ID3,1980s：对噪声、连续属性、数据缺失、改善分割条件等进行研究,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：For each 树中非叶结点n 临时修剪掉n下子树，用标号为主要分类的叶子代替 在验证集上计算该树的精度 修剪掉那些对精度影响最大的分支,当训练集很小时，可能会严重损害分类精度,最好能给定合适的结点数，达到最佳折衷,2001年6月2日,连续属性,用分区方法，将连续值映射为离散值,结点分裂，以获得最大信息增益,达到最大信息增益的单阈值分裂算法,For each,连续特征,A,i,根据,A,i,的值对样本排序,For each,序列中的每对,X,i,X,i+1,If X,i,和,X,i+1,的,分类不同 将,X,i,和,X,i+1,的中点作为可能的阈值进行检验，即,例如：长度(,L):10 15 21 28 32 40 50 (,已排序,)分类:-+-+-,检查阈值：,L12.5,L24.5,L30,L0.5 then,终止，,else,继续 令,t,=,t,/(1-,t,),将,h,t,正确分类出的样本的权重乘以,t,权重归一化以保证总和为1,在测试时，每个假设,h,t,获得投票的权重为,log(1/,t,),，,票数最多的假设作为最终决策,2001年6月2日,多重模型的实验结果,多决策树模型应用范围更广也更准确,引导算法性能比装袋算法好,引导算法偶尔也会降低性能,2001年6月2日,