6.-决策树分类.ppt

决策树分类决策树分类王成（副教授）王成（副教授）计算机科学与技术学院计算机科学与技术学院主要内容主要内容什么是决策树ID3算法算法改进C4.5算法CART算法Decision Tree ModelingDecision Tree Modeling决策树是一种简单且应用广泛的决策树是一种简单且应用广泛的决策树是一种简单且应用广泛的决策树是一种简单且应用广泛的预测预测预测预测方法方法方法方法决策树决策树图图3.1 3.1 常见的决策树形式常见的决策树形式决策树主要有二元分支（决策树主要有二元分支（binary splitbinary split）树和多分支（）树和多分支（multiway splitmultiway split）树。）树。一般时候采用二元分裂，因为二元分裂在穷举搜索中更加灵活。一般时候采用二元分裂，因为二元分裂在穷举搜索中更加灵活。决策树形式决策树形式决策树决策树决策树决策树（Decision Tree）又称为判定树判定树，是运用于分类的一种树结构树结构。其中的每个内部结点内部结点（internal node）代表对某个属性的一次测试测试，每条边边代表一个测试结果测试结果，叶结点叶结点（leaf）代表某个类类（class）或者类的分布（类的分布（class distributionclass distribution），），最上面的结点是根结点根结点决策树决策树提供了一种展示在什么条件下在什么条件下会得到什么类别什么类别这类规则规则的方法。下例是为了解决这个问题而建立的一棵决决策树策树，从中可以看到决策树的基本组成部分：决策结点决策结点、分支分支和叶结点叶结点决策树决策树下图给出了一个商业上使用的决策树商业上使用的决策树的例子。它表示了一个关心电子产品的用户是关心电子产品的用户是否会购买否会购买PC（buys_computer）的知识，用它可以预测某条记录（某个人）的购买意预测某条记录（某个人）的购买意向向决策树决策树这棵决策树对销售记录进行分类，指出一个电子产品消费者是否会购买一台计算机“buys_computer”。每个内部结点(方形框)代表对某个属性的一次检测。每个叶结点(椭圆框)代表一个类:buys_computers=yes 或者 buys_computers=no在这个例子中，特征向量为：(age,student,credit_rating,buys_computers)被决策数据的格式为:(age,student,credit_rating)输入新的被决策的记录，可以预测该记录隶属于哪个类。使用决策树进行分类使用决策树进行分类第1步：利用训练集建立并精化一棵决策树，建立决策树模型。这个过程实际上是一个从数据中获取知识，进行机器学习的过程第2步：利用生成完毕的决策树对输入数据进行分类。对输入的记录，从根结点依次测试记录的属性值，直到到达某个叶结点，从而找到该记录所在的类主要内容主要内容什么是决策树ID3算法算法改进C4.5算法CART算法如何从训练数据中学习决策树如何从训练数据中学习决策树?IDAgeHas-jobOwn_houseCredit_ratingClassClass1YoungFalseFalseFairNo2YoungFalseFalseGoodNo3YoungTrueFalseGoodYes4YoungTrueTrueFairYes5YoungFalseFalseFairNo6MiddleFalseFalseFairNo7MiddleFalseFalseGoodNo8MiddleTrueTrueGoodYes9MiddleFalseTrueExcellentYes10MiddleFalseTrueExcellentYes11OldFalseTrueExcellentYes12OldFalseTrueGoodYes13OldTrueFalseGoodYes14OldTrueFalseExcellentYes15OldFalseFalsefairno贷款申请数据集如何从训练数据中学习决策如何从训练数据中学习决策树树?Age？youngmiddleoldNo:3Yes:2No:2Yes:3No:4Yes:1Own_house？truefalseNo:0Yes:6No:6Yes:3(a)(b)两种可能的根节点选取方式哪种更好？ID3ID3算法算法ID3算法主要针对属性选择问题使用信息增益度选择测试属性ID3ID3决策树建立算法决策树建立算法1 决定分类属性集合；决定分类属性集合；2 对目前的数据表，建立一个节点对目前的数据表，建立一个节点N3 如果数据库中的数据都属于同一个类，如果数据库中的数据都属于同一个类，N就是树叶，在树叶上就是树叶，在树叶上 标出所属的类标出所属的类(纯的类别纯的类别)4 如果数据表中没有其他属性可以考虑，则如果数据表中没有其他属性可以考虑，则N也是树叶，按照少也是树叶，按照少 数服从多数的原则在树叶上标出所属类别数服从多数的原则在树叶上标出所属类别(不纯的类别不纯的类别)5 否则，否则，根据平均信息期望值根据平均信息期望值E或或GAIN值选出一个最佳属性作值选出一个最佳属性作 为节点为节点N的测试属性的测试属性6 节点属性选定后，对于该属性中的每个值：节点属性选定后，对于该属性中的每个值：从从N生成一个分支，并将数据表中与该分支有关的数据收集形生成一个分支，并将数据表中与该分支有关的数据收集形 成分支节点的数据表，在表中删除节点属性那一栏成分支节点的数据表，在表中删除节点属性那一栏 7如果分支数据表属性非空，则转如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树，运用以上算法从该节点建立子树信息熵信息熵(Entropy)(Entropy)我们常说信息很多，或信息很少，但却很难说清楚信息到底有多少比如一本50多万字的史记有多少信息量？或一套莎士比亚全集有多少信息量？这个问题几千年来都没有人给出很好的解答，直到1948年，香农(Claude Shannon)在他著名的论文“通信的数学原理”中提出了信息熵信息熵的概念，才解决了信息的度量信息的度量问题问题，并且量化出信息的作用量化出信息的作用信息熵信息熵(Entropy)(Entropy)一条信息的信息量和它的不确定性有着直接的关系比如，要搞清楚一件非常不确定的事，或是我们一无所知的事情，就需要了解大量信息。相反，如果我们对某件事已经有了较多了解，那么不需要太多信息就能把它搞清楚从这个角度看，信息量就等于不确定性的多少如何量化信息的度量呢？信息熵信息熵(Entropy)(Entropy)假如我错过了一个有32支球队参加的足球赛，赛后我问一个知道比赛结果的观众“哪支球队是冠军”？他不愿意直接告诉我，而让我猜，每猜一次，他要收一元钱才肯告诉我是否猜对，那我需要付多少钱才能知道谁是冠军呢？我可以把球队编号，从1到32，然后问“冠军球队在1-16号中吗？”，假如他告诉我猜对了，我就接着问“冠军在1-8号中吗？”，假如他说猜错了，那我就知道冠军在9-16号中。这样只要5次，我就能知道哪支球队是冠军当然，香农不是用钱，而是用比特(bit)来度量信息量，在上例中，这条消息的信息量是5比特信息量的比特数和所有可能情况的对数有关，例如本例中，信息量=log(球队数)，即 5=log(32)信息熵信息熵(Entropy)(Entropy)实际上可能不需要5次就能猜出谁是冠军，因为一些强队得冠的可能性更高，因此第一次猜测时可以把少数几支强队分成一组，其它球队分成另一组，然后猜冠军球队是否在那几支强队中这样，也许三次或四次就能猜出结果。因此，当每支球队夺冠的可能性(概率)不等时，这条信息的信息量比5比特少香农指出，它的准确信息量应该是p1,p2,.,p32分别是这32支球队夺冠概率，香农把它称作信息熵，单位为比特信息熵，单位为比特；可以算出，当32支球队夺冠概率相同时，对应的信息熵为5比特信息熵信息熵(Entropy)(Entropy)对于任意一个随机变量X(比如夺冠球队)，它的熵定义为变量的不确定性越大，熵也就越大，把它搞清楚所需要的信息量也就越大数据集的信息熵数据集的信息熵设数据集D中有m个不同的类C1,C2,C3,.,Cm设 Ci,D是数据集D中Ci类的样本的集合,|D|和|Ci,D|分别是D和 Ci,D中的样本个数其中pi是数据集D中任意样本属于类Ci的概率，用 估计数据集D的信息熵:例例:计算对下列数据集分类所需的信息计算对下列数据集分类所需的信息熵熵年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中等否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否|D|=14|C1,D|=5|C2,D|=9使用熵衡量数据纯度使用熵衡量数据纯度假设有一个数据集合假设有一个数据集合D，其中只有两个类，一个是正例类，一个是负例类，其中只有两个类，一个是正例类，一个是负例类计算计算D中正例类和负例类在三种不同的组分下熵的变化情况。中正例类和负例类在三种不同的组分下熵的变化情况。（1）D中包含有中包含有50%的正例和的正例和50%的负例。的负例。H(D)=-0.5*log20.5-0.5*log20.5=1（2）D中包含有中包含有20%的正例和的正例和80%的负例。的负例。H(D)=-0.2*log20.2-0.8*log20.8=0.722（3）D中包含有中包含有100%的正例和的正例和0%的负例。的负例。H(D)=-1*log21-0*log20=0可以看到一个趋势，可以看到一个趋势，当数据变得越来越当数据变得越来越“纯纯”时，熵的值变得越来越小时，熵的值变得越来越小。当当D中中正反例所占比例相同时，熵取最大值正反例所占比例相同时，熵取最大值。当当D 中中所有数据都只属于一个类时，熵得到最小值所有数据都只属于一个类时，熵得到最小值。因此因此熵可以作为数据纯净度或混乱度的衡量指标熵可以作为数据纯净度或混乱度的衡量指标。这正是决策树学习中。这正是决策树学习中需要的。需要的。数据集的信息熵数据集的信息熵假设按属性 A 划分 D 中的样本，且属性 A 根据训练数据的观测具有 v 个不同取值 a1,a2,.,aj,.,av。如果 A 是离散值离散值，可依属性 A 将 D 划分为 v 个子集 D1,D2,.,Dj,.,Dv 其中，Dj为D中的样本子集，它们在A上具有属性值aj 这些划分将对应于从该节点A出来的分支。按属性A对D划分后，数据集的信息熵:其中，充当第 j 个划分的权重。InfoA(D)越小，表示划分的纯度越高信息增益信息增益选择具有最高信息增益Gain(A)的属性A作为分裂属性按照能做“最佳分类”的属性A划分，使完成样本分类需要的信息量最小确定第一次分裂的属性：按确定第一次分裂的属性：按年龄年龄划分划分年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中等否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否年龄40的有5个,其中2个为“否”Info年龄(D)Gain(年龄)=Info(D)-Info年龄(D)=0.940-0.694=0.246确定第一次分裂的属性：按收入划分确定第一次分裂的属性：按收入划分年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否收入=高的有4个,其中2个为“否”收入=中的有6个,其中2个为“否”收入=低的有4个,其中1个为“否”Info收入(D)Gain(收入)=Info(D)-Info收入(D)=0.940-0.911=0.029确定第一次分裂的属性：按学生划分确定第一次分裂的属性：按学生划分年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否是学生的有7个,其中1个为“否”不是学生的有7个,其中4个为“否”Info学生(D)Gain(学生)=Info(D)-Info学生(D)=0.940-0.788=0.152确定第一次分裂的属性：按信用划分确定第一次分裂的属性：按信用划分年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否信用好的有6个,其中3个为“否”信用一般的有8个,其中2个为“否”Info信用(D)Gain(信用)=Info(D)-Info信用(D)=0.940-0.892=0.048收入收入学生学生信用信用 买了电脑买了电脑高否一般 否高否好否中否一般 否低是一般 是中是好是收入收入学生学生信用信用买了电脑买了电脑高否一般是低是好是中否好是高是一般是确定第一次分裂的属性确定第一次分裂的属性收入收入学生学生信用信用买了电脑买了电脑中否一般是低是一般是低是好否中是一般是中否好否年龄40“年龄”属性具体最高信息增益，成为分裂属性收入收入学生学生信用信用买了电脑买了电脑高否一般否高否好否中否一般否低是一般是中是好是 Info收入(D)=2/5*(-2/2*log2/2-0/2*log0/2)+2/5*(-1/2*log1/2-1/2*log1/2)+1/5*(-1/1*log1/1-0/1*log0/1)=0.400 Info学生(D)=3/5*(-3/3*log3/3-0/3*log0/3)+2/5*(-2/2*log2/2-0/2*log0/2)=0 Info信用(D)=3/5*(-2/3*log2/3-1/3*log1/3)+2/5*(-1/2*log1/2-1/2*log1/2)=0.951“学生”属性具体最高信息增益，成为分裂属性确定第二次分裂的属性确定第二次分裂的属性年龄40学生不买买不是学生是学生.买ID3ID3决策树建立算法决策树建立算法1 决定分类属性；决定分类属性；2 对目前的数据表，建立一个节点对目前的数据表，建立一个节点N3 如果数据库中的数据都属于同一个类，如果数据库中的数据都属于同一个类，N就是树叶，在树叶上就是树叶，在树叶上 标出所属的类标出所属的类4 如果数据表中没有其他属性可以考虑，则如果数据表中没有其他属性可以考虑，则N也是树叶，按照少也是树叶，按照少 数服从多数的原则在树叶上标出所属类别数服从多数的原则在树叶上标出所属类别5 否则，否则，根据平均信息期望值根据平均信息期望值E或或GAIN值选出一个最佳属性作值选出一个最佳属性作 为节点为节点N的测试属性的测试属性6 节点属性选定后，对于该属性中的每个值：节点属性选定后，对于该属性中的每个值：从从N生成一个分支，并将数据表中与该分支有关的数据收集形生成一个分支，并将数据表中与该分支有关的数据收集形 成分支节点的数据表，在表中删除节点属性那一栏成分支节点的数据表，在表中删除节点属性那一栏7如果分支数据表属性非空，则转如果分支数据表属性非空，则转1，运用以上算法从该节点建立子树，运用以上算法从该节点建立子树它首先对数据进行处理，利用归纳法生成它首先对数据进行处理，利用归纳法生成可读的规则和决策树，然后使用决策对新可读的规则和决策树，然后使用决策对新数据进行分析。本质上决策树是通过一系数据进行分析。本质上决策树是通过一系列规则对数据进行分类的过程。决策树技列规则对数据进行分类的过程。决策树技术发现数据模式和规则的核心是采用术发现数据模式和规则的核心是采用递归递归分割的贪婪算法分割的贪婪算法。决策树的基本原理决策树的基本原理 分类决策树分类决策树A decision tree is so called because the predictive model can be represented in a tree-like structure.the target is categorical,the model is a called a classification tree.分类树采用的标准：分类树采用的标准：分类错误率分类错误率:Gini 指数指数:信息熵信息熵:主要内容主要内容什么是决策树ID3算法算法改进C4.5算法CART算法C4.5C4.5算法对算法对ID3ID3的改进的改进改进1：用信息增益率信息增益率代替信息增益信息增益来选择属性属性改进2：能够完成对连续值属性连续值属性的离散化处离散化处理理改进3：能处理属性值缺失属性值缺失的情况改进4：在决策树构造完成之后进行剪枝剪枝十大数据挖掘算法十大数据挖掘算法C4.5k-MeansSVMAprioriEMPageRankAdaBoostkNNNave BayesCART改进改进1 1：信息增益的问题：信息增益的问题假设按属性 A 划分 D 中的样本，且属性 A 根据训练数据的观测具有 v 个不同取值 a1,a2,.,aj,.,av。如果 A 是离散值离散值，可依属性 A 将 D 划分为 v 个子集 D1,D2,.,Dj,.,Dv 其中，Dj为D中的样本子集，它们在A上具有属性值aj 这些划分将对应于从该节点A出来的分支。信息增益度量信息增益度量偏向于对取值较多取值较多的属性属性进行测试，即它倾向于选择v较大较大的属性属性A举个极端的例子：考虑充当唯一标识的属性PID。对PID的分裂将产生大量划分（与样本个数一样多），每个分类只包含一个样本，且每个划分都是纯的。对属性PID划分得到的信息增信息增益最大益最大，显然，这种划分对分划分对分类没有用处类没有用处。改进改进1 1：信息增益率：信息增益率C4.5使用分裂信息分裂信息(split information)将信息增益规范化信息增益规范化该值表示数据集D按属性A分裂的v个划分产生的信息选择具有最大信息增益率最大信息增益率的属性作为分裂属性分裂属性改进改进1 1：信息增益率：信息增益率年龄年龄收入收入学生学生信用信用买了电脑买了电脑30高否一般否40中否一般是40低是一般是40低是好否30-40低是好是30中否一般否40中是一般是40中否好否Info(D)=0.940Info收入(D)=0.911Gain(收入)=0.029高收入的有4个中等收入的有6个低收入的有4个SplitInfo收入(D)=-4/14*log4/14 -6/14*log6/14 -4/14*log4/14=1.557 GainRatio(收入)=Gain(收入)/SplitInfo收入(D)=0.029/1.557=0.019改进改进2 2：连续值属性与分裂点：连续值属性与分裂点对于连续值属性连续值属性，按属性值大小从小到大排序，取每对相邻值的中点相邻值的中点作为可能的可能的分裂点分裂点split_point。假设一连续值属性共有N个不同的属性值，则可找到N-1个可能的分裂点分裂点。检查每个可能分裂点，取能使得信息增益最大的分裂点信息增益最大的分裂点，将D分裂成D1:A split_point(一个分裂点，二分法，二叉树一个分裂点，二分法，二叉树)56105.588C4.5不使用中点，而是直接使用一对值中较小的值作为可能的分裂点，如本例中将使用5,6作为可能分裂点多个分裂点？多分法，多叉决策树多个分裂点？多分法，多叉决策树改进改进3 3：缺失值的处理：缺失值的处理在某些情况下，可供使用的数据可能缺少某些属性的值，例如一种简单的办法是赋予它该属性最常见的值，例如将“晴”或“雨”赋予第6个实例的天气属性一种更复杂的策略是为一种更复杂的策略是为A的每的每个可能值赋予一个概率个可能值赋予一个概率改进改进3 3：缺失值的处理：缺失值的处理建树过程（学习过程）选定训练样本实例有缺失值，如何知道要将其分配到哪个分支？分类过程（测试过程或者工作过程）待分类实例有缺失值，如何测试该实例属于哪个分支？天气晴多云雨(天气天气=缺失缺失，温度=72，湿度=90.)改进改进3 3：C4.5 C4.5中缺失值的处理中缺失值的处理-建树过程建树过程（学习过程）（学习过程）Gain(A)=F(Info(D)InfoA(D)其中 F 为属性值未缺失的实例所占比例；计算 Info(D)和 InfoA(D)时忽略属性值缺失的实例 Info(D)=-8/13log(8/13)-5/13log(5/13)=0.961 bits Info天气(D)=5/13(-2/5log(2/5)-3/5log(3/5)+3/13(-3/3log(3/3)-0/3log(0/3)+5/13(-3/5log(3/5)-2/5log(2/5)=0.747 bits Gain(天气)=13/14 (0.961-0.747)=0.199 bits改进改进3 3：C4.5 C4.5中缺失值的处理中缺失值的处理-建树过程建树过程（学习过程）（学习过程）计算 SplitInfo 时，将缺失的属性值当作一个正常值进行计算，本例中，当作天气有四个值，分别是晴,多云,雨,?，再计算其 SplitInfoSplitInfo天气(D)=-5/14log(5/14)-3/14log(3/14)-5/14log(5/14)-1/14log(1/14)=1.809 bits晴多云雨缺失缺失 GainRatio(天气)=Gain(天气)/SplitInfo天气(D)=0.199/1.809改进改进3 3：C4.5 C4.5中缺失值的处理中缺失值的处理-建树过程建树过程（学习过程）（学习过程）分裂时，将属性值缺失的实例分配给所有分支，但是带一个权重湿度有风玩？权重70908595709090有有无无无有有玩不玩不玩不玩玩玩玩111115/135/13湿度有风玩？权重9090786575有有无有无玩玩玩玩玩3/133/13111T1:(天气=晴)T1:(天气=多云)湿度有风玩？权重80708080969090有有无无无有有不玩不玩玩玩玩玩玩111115/135/13T1:(天气=雨)本例14个实例中共13个实例天气属性值未缺失：其中5个实例的天气属性为“晴”，3个实例的天气属性为“多云”，5个实例的天气属性为“雨”本例14个实例中共1个实例天气属性值缺失，因此估算出天气属性值缺失的第6个实例：天气是晴的概率是5/13，天气是多云的概率是3/13，天气是雨的概率是5/13改进改进3 3：C4.5 C4.5中缺失值的处理中缺失值的处理-建树过程建树过程（学习过程）（学习过程）湿度有风玩？权重70908595709090有有无无无有有玩不玩不玩不玩玩玩玩111115/13=0.45/13=0.4T1:(天气=晴)湿度 75 5/13玩，3不玩湿度玩(2.0)不玩(3.4/0.4)75叶节点以(N/E)的形式定义，其中 N 为到达该叶节点的实例数，E 为其中属于其它分类的实例数。例如，不玩不玩(3.4/0.4)表示3.4个实例到达“不玩”节点，其中0.4个实例不属于“不玩”改进改进3 3：C4.5 C4.5中缺失值的处中缺失值的处理理-分类过程分类过程湿度玩(2.0)不玩(3.4/0.4)75天气晴(天气=晴，温度=90，湿度湿度=缺失缺失.)对于任一实例，湿度 75 的可能性是 3.4/(2.0+3.4)当湿度 75 时，分类为玩的可能性=0.4/3.4=12%分类为不玩的可能性=3/3.4=88%最终分类的概率分布为：玩=2.0/5.4100%+3.4/5.412%=44%不玩=3.4/5.488%=56%改进改进4 4：学习过程中的过度拟：学习过程中的过度拟合合上述的决策树算法增长树的每一个分支的深度，直到恰好能对训练样例比较完美地分类。实际应用中，当训练样本中有噪声或训练样例的数量太少以至于不能产生目标函数的有代表性的采样时，该策略可能会遇到困难在以上情况发生时，这个简单的算法产生的树会过度拟合训练样例过度拟合训练样例(过度拟合:Over fitting)过度拟合产生的原因：训练样本中有噪声，训练样例太小等改进改进4 4：欠拟合、合适拟合、：欠拟合、合适拟合、过拟合过拟合欠拟合合适拟合过拟合改进改进4 4：过度拟合：过度拟合训练样本中噪声导致的过度拟合错误的类别值/类标签，属性值等训练样本中缺乏代表性样本所导致的过度拟合根据少量训练记录作出的分类决策模型容易受过度拟合的影响。由于训练样本缺乏代表性的样本，在没有多少训练记录的情况下，学习算法仍然继续细化模型就会导致过度拟合改进改进4 4：缺乏代表性样本所导致的过度拟合缺乏代表性样本所导致的过度拟合名称体温胎生4条腿冬眠哺乳动物蝾螈冷血NYYN虹鳉冷血YNNN鹰鹰恒温恒温NNNN弱夜鹰恒温NNYN鸭嘴兽恒温YYYY哺乳动物分类的训练样例名称体温胎生4条腿冬眠哺乳动物人恒温YNNY大象恒温YYNY鸽子恒温NNNN体温体温恒温恒温冷血冷血冬眠冬眠NY N N4条腿条腿Y N NY按照训练模型。人和大象都不是按照训练模型。人和大象都不是哺乳动物。决策树作出这样的判哺乳动物。决策树作出这样的判断是因为只有一个训练样例具有断是因为只有一个训练样例具有这些特点（鹰，恒温，不冬眠）这些特点（鹰，恒温，不冬眠）被划分为非哺乳动物。被划分为非哺乳动物。该例清楚表明，当决策树的叶节该例清楚表明，当决策树的叶节点没有足够的代表性时，可能会点没有足够的代表性时，可能会预测错误。预测错误。哺乳动物分类的测试样例改进改进4 4：决策树剪枝：决策树剪枝How?预剪枝(prepruning)后剪枝(postpruning)在完全正确分类训练集之前就停止树的生长。由“完全生长”的树剪去子树。改进改进4 4：预剪枝：预剪枝yesyesno 剪枝处理yesno45311no否否否否是是是是最直接的方法：事先限定树的最大生长高度如果设为3，则如图剪枝改进改进4 4：后剪枝：后剪枝训练过程训练过程中允许对数据中允许对数据的过度拟合，然后再利的过度拟合，然后再利用用测试集测试集对树进行修剪对树进行修剪树叶用被替换的子树最频繁的类标号yesyesnoyesno41311no2yes/no2NO是是是是是是否否否否否否改进改进4 4：后剪枝：后剪枝在测试集上在测试集上定义损失函数C，我们的目标是通过剪枝使得在测试在测试集上集上C的值下降。例如通过剪枝使在测试集上在测试集上误差率降低。1.自底向上的遍历每一个非叶节点(除了根节点)，将当前的非叶节点从树中减去，其下所有的叶节点合并成一个节点，代替原来被剪掉的节点。2.计算剪去节点前后的损失函数，如果剪去节点之后损失函数变小了，则说明该节点是可以剪去的，并将其剪去；如果发现损失函数并没有减少，说明该节点不可剪去，则将树还原成未剪去之前的状态。3.重复上述过程，直到所有的非叶节点(除了根节点)都被尝试了。从决策树导出产生式规则从决策树导出产生式规则大型决策树可读性较低，可通过从决策树导出产生式规则以提高可读性把从根结点到叶子结点的路径中遇到的所有测试条件联合起来，便可建立相对应的规则集从决策树导出产生式规则从决策树导出产生式规则但这样的规则会导致某些不必要的复杂性可用类似的方法对规则集进行剪枝对于某一规则，将它的单个条件暂时去除，在测试集上在测试集上估计误差率，并与原规则的误差率进行比较，若新规则的结果较好，则删除这个条件IF 天气=晴 AND 湿度=75THEN 玩IF 天气=晴THEN 玩主要内容主要内容什么是决策树ID3算法算法改进C4.5算法CART算法CARTCART算法算法分类回归树（分类回归树（CART:Classification and CART:Classification and Regression TreeRegression Tree）其特点是在计算过程中充分利用二分支树其特点是在计算过程中充分利用二分支树的结构（的结构（Bianry Tree-structuredBianry Tree-structured），即），即根节点包含所有样本，在一定的分裂规则根节点包含所有样本，在一定的分裂规则下根节点被分裂为两个子节点，这个过程下根节点被分裂为两个子节点，这个过程又在子节点上重复进行，直至不可再分，又在子节点上重复进行，直至不可再分，成为叶节点为止。成为叶节点为止回归树（回归树（Regression Tree）因变量因变量-continuous，叶子为叶子为因变量因变量的预测值。的预测值。Boston Housing DataLeaves=Boolean RulesLeaves=Boolean Rules（布尔规则）（布尔规则）Leaf12345678RM6.56.56.56.5,6.9)6.96.9,7.4)7.46.9NOX.51.51,.63).63,.67).67.67.66.66.66Predicted MEDV2219272714334616If RM values&NOX values,then MEDV=valueCARTCART算法算法CART:Classification And Regression Trees可用于分类和回归(数值预测)使用GINI指标来选择分裂属性使用二元切分(将生成二叉树)基于代价-复杂度剪枝GiniGini指标指标 指标用来度量数据划分或者数据集的不纯度。其中，是 中样本属于 类的概率，并用 估计。电脑销售数据集中，9个样本属于“购买电脑”，5个样本属于“未购买电脑”GiniGini指标指标如果按照 的二元分裂，将 划分成 和 ，则给定该划分的 指标为：Gini指标最小，划分越纯。选择具有最小Gini指标(或最大Gini)的属性作为分裂属性处理离散值属性处理离散值属性以收入为例，对收入属性的所有可能子集：低，中，高，低，中，低，高，中，高，低，中，高考虑所有可能的二元划分，并计算划分前后的Gini指标，选择能产生最小Gini指标的子集作为分裂子集收入中，高.是否回归树的生成回归树的生成 数据：N个观测，p个自变量，1个因变量(连续型)目标：自动地选择分裂变量及其分裂点假设有一个分裂把自变量空间分成M个区域:在每个区域，我们用一个常数来拟合因变量：优化目标：误差平方和最小 上最优的拟合解为 从根节点开始，考虑一个分裂变量从根节点开始，考虑一个分裂变量j j和分裂和分裂点点s s，得到，得到2 2个区域：个区域：最优的变量最优的变量j j和分裂点和分裂点s s，要满足，要满足对于给定的对于给定的j j和和s s，最里层的优化问题的解，最里层的优化问题的解为为而对于给定的而对于给定的j j,分裂点分裂点s s很快能找到很快能找到.这样，遍历所有的自变量，就能找到最佳这样，遍历所有的自变量，就能找到最佳的一对的一对j j和和s s.递归分割递归分割-greedy algorithm剪枝剪枝 最大的决策树能对训练集的准确率达到最大的决策树能对训练集的准确率达到100%100%，最大的分类树的结果会导致过拟合，最大的分类树的结果会导致过拟合（对信号和噪声都适应）。因此建立的树（对信号和噪声都适应）。因此建立的树模型不能很好的推广到总体中的其他样本模型不能很好的推广到总体中的其他样本数据。同样，太小的决策树仅含有很少的数据。同样，太小的决策树仅含有很少的分支，会导致欠拟合。一个好的树模型有分支，会导致欠拟合。一个好的树模型有低的偏倚和低的方差，模型的复杂性往往低的偏倚和低的方差，模型的复杂性往往在偏倚和方差之间做一个折中，因此要对在偏倚和方差之间做一个折中，因此要对树进行剪枝。这里介绍树进行剪枝。这里介绍cost-complexity cost-complexity pruningpruning。最大树最大树决策树能长到每个叶子都是纯的。最大的分类决策树能长到每个叶子都是纯的。最大的分类可以达到可以达到100%100%的准确，最大的回归树残差为的准确，最大的回归树残差为0 0。恰当的树恰当的树先生成一个大的树先生成一个大的树 考虑一个子树考虑一个子树 子树就是由大树进行删减内部节点而得到子树就是由大树进行删减内部节点而得到.用用|T|表示树表示树T 的叶节点（最终节点）的个数的叶节点（最终节点）的个数.定义定义cost complexity criterion:对于每个对于每个 ，寻找子树，寻找子树 使得使得 达到最小达到最小.而而 则起到了平衡树的大小和数据拟合好坏则起到了平衡树的大小和数据拟合好坏的作用的作用.较大会得到较小的树，较大会得到较小的树，较小则会得较小则会得到较大的树到较大的树.对于每个对于每个 ，可以证明存在唯一的最小的，可以证明存在唯一的最小的子树子树 使得使得达到最小达到最小.To find we use weakest link pruning:we successively collapse the internal node that produces the smallest per-node increase in ,and continue until we produce the single-node(root)tree.This gives a sequence of subtrees,and this sequence must contains Estimation of is achieved by cross-validation:we choose the value to minimize the cross-validation sum of squares.用于回归用于回归要预测的属性是数值属性，非离散值属性不纯度度量：计算所有数据的均值，再计算每条数据的值到均值的差值的平方和叶子结点用均值表示C4.5k-MeansSVMAprioriEMPageRankAdaBoostkNNNave BayesCART高伸缩性决策树算法高伸缩性决策树算法SLIQ、SPRINT、BOAT决策树基本概念决策树基本概念决策树的优点1、推理过程容易理解，决策推理过程可以表示成If Then形式；2、推理过程完全依赖于属性变量的取值特点；3、可自动忽略目标变量没有贡献的属性变量，也为判断属性 变量的重要性，减少变量的数目提供参考。决策树基本概念决策树基本概念关于归纳学习(1)决策树技术发现数据模式和规则的核心是归纳算法。归纳是从特殊到一般的过程。归纳推理从若干个事实中表征出的特征、特性和属性中，通过比较、总结、概括而得出一个规律性的结论。归纳推理试图从对象的一部分或整体的特定的观察中获得一个完备且正确的描述。即从特殊事实到普遍性规律的结论。归纳对于认识的发展和完善具有重要的意义。人类知识的增长主要来源于归纳学习。决策树基本概念决策树基本概念关于归纳学习(2)归纳学习的过程就是寻找一般化描述的过程。这种一般性描述能够解释给定的输入数据，并可以用来预测新的数据。锐角三角形内角和等于180度；钝角三角形内角和等于180度；三角形内角和 直角三角形内角和等于180度；等于180度 已知三角形ABC，A角等于76度，B角等于89度，则其C角等于15度 归纳学习由于依赖于检验数据，因此又称为检验学习。归纳学习存在一个基本的假设：任一假设如果能够在足够大的训练样本集中很好的逼近目标函数，则它也能在未见样本中很好地逼近目标函数。该假定是归纳学习的有效性的前提条件。决策树基本概念决策树基本概念关于归纳学习(3)决策树基本概念决策树基本概念关于归纳学习(4)归纳过程就是在描述空间中进行搜索的过程。归纳可分为自顶向下，自底向上和双向搜索三种方式。自底向上法一次处理一个输入对象。将描述逐步一般化。直到最终的一般化描述。自顶向下法对可能的一般性描述集进行搜索，试图找到一些满足一定要求的最优的描述。决策树基本概念决策树基本概念从机器学习看分类及归纳推理等问题（1）从特殊的训练样例中归纳出一般函数是机器学习的中心问题；从训练样例中进行学习通常被视为归纳推理。每个例子都是一个对偶（序偶）（x,f(x)），对每个输入的x，都有确定的输出f(x)。学习过程将产生对目标函数f的不同逼近。F的每一个逼近都叫做一个假设。假设需要以某种形式表示。例如，y=ax+b。通过调整假设的表示，学习过程将产生出假设的不同变