第3章_决策树学习

Date:29.08.2019File:ML3.1MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering第3章决策树学习(Decision-TreeAlgorithm)Date:29.08.2019File:ML3.2MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering排名主题算法得票数发表时间作者陈述人1分类C4.5611993Quinlan,J.RHiroshiMotoda2聚类k-Means601967MacQueen,J.BJoydeepGhosh3统计学习SVM581995Vapnik,V.NQiangYang4关联分析Apriori521994RakeshAgrawalChristosFaloutsos5统计学习EM482000McLachlan,GJoydeepGhosh6链接挖掘PageRank461998Brin,S.ChristosFaloutsos7集装与推进AdaBoost451997Freund,Y.Zhi-HuaZhou8分类kNN451996Hastie,TVipinKumar9分类NaïveBayes452001Hand,D.JQiangYang10分类CART341984L.BreimanDanSteinberg共有145人参加了ICDM2006Panel(会议的专题讨论),并对18种候选算法进行投票，选出了机器学习10大算法ICDM2006会议的算法投票结果Date:29.08.2019File:ML3.3MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering概论•决策树学习是应用最广的归纳推理算法之一•是一种逼近离散值函数的方法•很好的健壮性•能够学习析取表达式•ID3,Assistant,C4.5•搜索一个完整表示的假设空间•归纳偏置是优先选择较小的树•决策树表示了多个if-then规则Date:29.08.2019File:ML3.4MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering提纲•决策树定义•适用问题特征•基本ID3算法•决策树学习的归纳偏置•训练数据的过度拟合•…Date:29.08.2019File:ML3.5MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering决策树基本概念关于分类问题分类（Classification）任务就是通过学习获得一个目标函数（TargetFunction）f,将每个属性集x映射到一个预先定义好的类标号y。分类任务的输入数据是记录的集合，每条记录也称为实例或者样例。用元组(X,y)表示，其中，X是属性集合，y是一个特殊的属性，指出样例的类标号（也称为分类属性或者目标属性）Date:29.08.2019File:ML3.6MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering决策树基本概念关于分类问题名称体温表皮覆盖胎生水生动物飞行动物有腿冬眠类标号人类恒温毛发是否否是否哺乳动物海龟冷血鳞片否半否是否爬行类鸽子恒温羽毛否否是是否鸟类鲸恒温毛发是是否否否哺乳类Xy分类与回归分类目标属性y是离散的，回归目标属性y是连续的Date:29.08.2019File:ML3.7MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering决策树基本概念解决分类问题的一般方法通过以上对分类问题一般方法的描述，可以看出分类问题一般包括两个步骤：1、模型构建（归纳）通过对训练集合的归纳，建立分类模型。2、预测应用（推论）根据建立的分类模型，对测试集合进行测试。Date:29.08.2019File:ML3.8MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering决策树基本概念解决分类问题的一般方法TIDA1A2A3类1Y100LN2N125SN3Y400LY4N415MN学习算法学习模型模型应用模型TIDA1A2A3类1Y100L？2N125S？3Y400L？4N415M？训练集（类标号已知）检验集（类标号未知）归纳推论Date:29.08.2019File:ML3.9MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering决策树表示法内部节点(包括根节点)指定了对实例的某个属性的测试节点的每个后继分支对应于该属性的一个可能值叶子节点即为实例所属的分类决策树代表实例属性值约束的合取的析取式图3-1概念PlayTennis的决策树OutlookHumidityWindNoYesNoYesYesSunnyRainyOvercastHighNormalStrongWeakDate:29.08.2019File:ML3.10MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering决策树学习的适用问题•适用问题的特征–实例由“属性-值”对表示–目标函数具有离散的输出值–可能需要析取的描述–训练数据可以包含错误–训练数据可以包含缺少属性值的实例•问题举例–医学中的应用（如根据疾病分类患者、疾病分析与预测）–根据起因分类设备故障（故障诊断）–根据拖欠支付的可能性分类贷款申请•分类问题–核心任务是把样例分类到各可能的离散值对应的类别Date:29.08.2019File:ML3.11MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering基本的决策树学习算法ID3•大多数决策树学习算法是一种核心算法的变体•采用自顶向下的贪婪搜索遍历可能的决策树空间•ID3是这种算法的代表•该方法使用信息增益度选择测试属性。Date:29.08.2019File:ML3.12MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineeringID3算法通过自顶向下构造决策树来进行学习。构造过程：ID3算法的核心问题是选取在树的每个节点要测试的属性。选择根节点－使用统计测试确定每一个实例属性单独分类训练样例的能力，分类能力最好的属性被选作树的根节点为根节点属性的每个可能值产生一个分支，并把训练样例排列到适当的分支重复上面的过程，用每个分支节点关联的训练样例来选取在该点被测试的最佳属性，直到满足以下两个条件中的任一个:1）所有的属性已经被这条路径包括；2）与这个节点关联的所有训练样例具有相同的目标属性值Date:29.08.2019File:ML3.13MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering表3-1用于学习布尔函数的ID3算法•ID3(Examples,Target_attribute,Attributes)•创建树的root节点•如果Examples都为正,返回label=+的单节点树root•如果Examples都为反,返回label=-的单节点树root•如果Attributes为空，那么返回单节点root，label=Examples中最普遍的Target_attribute值•否则开始–AAttributes中分类examples能力最好的属性–root的决策属性A–对于A的每个可能值vi•在root下加一个新的分支对应测试A=vi•令Examplesvi为Examples中满足A属性值为vi的子集•如果Examplesvi为空–在这个新分支下加一个叶子节点，节点的label=Examples中最普遍的Target_attribute值–否则在新分支下加一个子树ID3（Examplesvi,Target_attribute,Attributes-{A}）•结束•返回rootDate:29.08.2019File:ML3.14MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering最佳分类属性•信息增益(InformationGain)–用来衡量给定的属性区分训练样例的能力–ID3算法在增长树的每一步使用信息增益从候选属性中选择属性•用熵度量样例的均一性–给定包含关于某个目标概念的正反样例的样例集S，那么S相对这个布尔型分类的熵为–信息论中对熵的一种解释，熵确定了要编码集合S中任意成员的分类所需要的最少二进制位数–更一般地，如果目标属性具有c个不同的值，那么S相对于c个状态的分类的熵定义为Entropy(S)=ciiipp12log22()loglogppEntropySppDate:29.08.2019File:ML3.15MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering•S的所有成员属于同一类，Entropy(S)=0；•S的正反样例数量相等，Entropy(S)=1；•S的正反样例数量不等，熵介于0，1之间Date:29.08.2019File:ML3.16MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering•抛一枚均匀硬币的信息熵是多少？解：出现正面与反面的概率均为0.5，信息熵是1log(0.5log0.50.5log0.5)1qiiiExpxpxDate:29.08.2019File:ML3.17MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineering•用信息增益度量期望的熵降低–属性的信息增益，由于使用这个属性分割样例而导致的期望熵降低–一个属性A相对样例集合S的信息增益Gain(S,A)被定义为：Values(A)是属性A所有可能值的集合，Sv是S中属性A的值为v的子集–Gain(S,A)是在知道属性A的值后可以节省的二进制位数；()||(,)()()||vvvValuesASGainSAEntropySEntropySSDate:29.08.2019File:ML3.18MachineLearningPengKaixiang2015.Allrightsreserved.MachineLearningforControlEngineeringbig,red,circle:+small,red,circle:+smal