决策树PPT课件.ppt

决策树,根据李峰等人的PPT改编课件主要依据李航编写的统计学习方法编制，清华大学出版社另一本参考书：数据挖掘与数学建模国防工业出版社2010,决策树,1.1决策树模型与学习1.2特征选择1.3决策树的生成1.4决策树的剪枝1.5CART算法,1.1决策树模型与学习,1.1.1决策树模型1.1.2决策树与if-then规则1.1.3决策树与条件概率分布1.1.4决策树学习,1.1.1决策树模型,什么是决策树？定义1.1（决策树）分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个类。,决策树学习算法的特点,决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练实例进行较好的标注，就能够进行学习。显然，它属于有监督学习。从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。,决策树学习的主要算法,建立决策树的关键，即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有一下三种算法。ID3（J.RossQuinlan-1975）核心：信息熵C4.5ID3的改进，核心：信息增益比CART（Breiman-1984），核心：基尼指数,例1.找对象,决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：女儿：多大年纪了？(年龄)母亲：26。女儿：长的帅不帅？(长相)母亲：挺帅的。女儿：收入高不？(收入情况)母亲：不算很高，中等情况。女儿：是公务员不？(是否公务员)母亲：是，在税务局上班呢。女儿：那好，我去见见。,1.1.2决策树与if-then规则,由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。If-then规则集合的一重要性质：互斥并且完备,1.1.3决策树与条件概率分布,将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。各叶结点(单元)上的条件概率往往偏向某一个类，即属于某一类的概率较大，决策树分类时将该结点的实例强行分到条件概率大的那一类去。,1.1.4决策树学习,假设给定训练数据集D=(1,1),(2,2),(,)其中，=(1,2,()为输入实例，n为特征个数,1,2,3,为类标记，=1,2,为样本容量。学习目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。决策树学习本质：从训练数据集中归纳出一组分类规则。,1.1.4决策树学习,目标：我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。决策树学习的损失函数：（通常是）正则化的极大似然函数。但是基于损失函数找到全局最优决策树是NP-完全问题。现实中决策树学习通常采用启发式方法，即局部最优。具体做法：每次选择feature时，都挑选择当前条件下最优的那个feature作为划分规则，即局部最优的feature。,1.2特征选择1.2.1特征选择问题,特征选择在于选取对训练数据具有分类能力的特征。如何判断一个特征对于当前数据集的分类效果？也即确定选择特征的准则。,例1.2右表是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的四个特征。表的最后一列是类别，是否同意贷款，取2个值：是、否。希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类。特征选择是决定用哪个特征来划分特征空间。,1.2.2信息增益,熵-就分类而言，所有成员都属于一类，熵为零；不同类别数目相等，则熵等于1，类别数目不等，则熵介于0,1之间。,当随机变量只有两个值，例如1,0时，即X的分布为P(X=1)=p,P(X=0)=1-p,0=p=0),算法1.4树的剪枝算法,输入：生成算法产生的整个树T,参数a;输出：修建后的子树.(1)计算每个结点的经验熵.(2)递归地从树的叶结点向上回缩.设一组叶结点回缩到其父结点之前与之后的整体树分别为与，其对应的损失函数分别是()与()，如果()7.5，所以决定将子树T4替换这一个叶子节点。,Cost-ComplexityPruning（CCP，代价复杂度剪枝),该算法为子树Tt定义了代价（cost）和复杂度（complexity），以及一个可由用户设置的衡量代价与复杂度之间关系的参数，其中，代价指在剪枝过程中因子树Tt被叶节点替代而增加的错分样本，复杂度表示剪枝后子树Tt减少的叶结点数，则表示剪枝后树的复杂度降低程度与代价间的关系，定义为其中，|N1|：子树Tt中的叶节点数；R（t）：结点t的错误代价，计算公式为R（t）=r（t）*p（t），r（t）为结点t的错分样本率，p（t）为落入结点t的样本占所有样本的比例；R（Tt）：子树Tt错误代价，计算公式为R（Tt）=R(i)，i为子树Tt的叶节点。,例子,我们以非叶结点T4为例，假设已有的数据有60条，那么R(t)=r(t)*p(t)=(7/16)*(16/60)=7/60R（Tt）=R(i)=(2/5)*(5/60)+(0/2)*(2/60)+(3/9)*(9/60)=5/60=（R(t)-R（Tt）)/(|N1|-1)=1/60,CCP续,CCP剪枝算法分为两个步骤：1.对于完全决策树T的每个非叶结点计算值，循环剪掉具有最小值的子树，直到剩下根节点。在该步可得到一系列的剪枝树T0，T1，T2.Tm,其中T0为原有的完全决策树，Tm为根结点，Ti+1为对Ti进行剪枝的结果；2.从子树序列中，根据真实的误差估计选择最佳决策树。,CCP续,通常使用1-SE（1standarderrorofminimumerror）规则从步骤1产生的一系列剪枝树中选择一棵最佳的剪枝决策树。方法为，假定一个含有N个样本的剪枝集，分别用在步骤1中产生的剪枝树Ti对该剪枝集进行分类，记Ti所有叶结点上长生的错分样本数为Ei，令E=minEi，定义E的标准错误为：，所得的最佳剪枝树Tbest是满足条件EiE+SE（E）且包含的接点数最少的那棵剪枝树Ti。,几种后剪枝方法的比较,1.5CART（分类与回归树）算法,CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否。这样的决策树等价于递归地二分每个特征。步骤：（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。,1.5.1CART生成,决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数(Giniindex)最小化准则，进行特征选择，生成二叉树。,最开始我们可以按：表面覆盖为毛发与非毛发表面覆盖为鳞片与非鳞片恒温与非恒温来产生当前结点的左右两个孩子。我们将Gini指数来作为准则判别哪种划分比较好。,GINI指数,定义：分类问题中，假设有K个类，样本点属于第k类的概率为,则概率分布的基尼指数定义为：=1(1)=1-=12比如体温为恒温时包含哺乳类5个，鸟类2个：=1572+272=2049体温为非恒温时包含爬行类3个、鱼类3个、两栖类2个，则=1382+382+282=4264Gini增益为：=7152049+8154264最好的划分就是使得_最小的划分.,1.5.2CART剪枝,算法步骤：首先从生成算法产生的决策树0低端开始不断剪枝，直到0的根结点，形成一个子树序列0,1,。然后通过交叉验证法在独立的验证数据集上对于子树序列进行测试，从中选取最优子树。,实验结果,解决决策树过拟合的另一种方法随机森林,Bootstraping,Bootstraping的名称来自成语“pullupbyyourownbootstraps”，意思是依靠你自己的资源，称为自助法，它是一种有放回的抽样方法。注：Bootstrap本义是指高靴子口后面的悬挂物、小环、带子，是穿靴子时用手向上拉的工具。“pullupbyyourownbootstraps”即“通过拉靴子让自己上升”，意思是“不可能发生的事情”。后来意思发生了转变，隐喻“不需要外界帮助，仅依靠自身力量让自己变得更好”,解决决策树过拟合的另一种方法随机森林,组合模型Bagging的策略（三个臭皮匠顶个诸葛亮的意思）,*bootstrapaggregation*从样本集中重采样(有重复的)选出n个样本*在所有属性上，对这n个样本建立分类器(ID3、C4.5、CART、SVM、Logistic回归等)*重复以上两步m次，即获得了m个分类器*将数据放在这m个分类器上，最后根据这m个分类器的投票结果，决定数据属于哪一类,解决决策树过拟合的另一种方法随机森林,解决决策树过拟合的另一种方法随机森林,随机森林应用非常广泛，根据目标变量的取值类型大致可分为两类一种是分类：当目标变量取值为离散型时（属性变量、种类变量、有序变量、多级变量等），采用该法可进行分类；当目标变量为连续型，则可做回归，对应的预测结果是目标变量的分布。优点：可以产生高准确度的分类器,解决决策树过拟合的另一种方法随机森林,随机森林在bagging基础上做了修改。*从样本集中用Bootstrap采样选出n个样本；*从所有属性中随机选择k个属性，选择最佳分割属性作为节点建立CART决策树；*重复以上两步m次，即建立了m棵CART决策树*这m个CART形成随机森林，通过投票表决结果，决定数据属于哪一类,解决决策树过拟合的另一种方法随机森林,随机森林/Bagging和决策树的关系,*当然可以使用决策树作为基本分类器*但也可以使用SVM、Logistic回归等其他分类器，习惯上，这些分类器组成的“总分类器”，仍然叫做随机森林。,回归问题,下图离散点是样本集合，描述了臭氧(横轴)和温度(纵轴)的关系，试拟合二者的变化曲线,使用Bagging,记原始数据为D，长度为N(即图中有N个离散点),算法过程做100次bootstrap，每次得到的数据Di，Di的长度为N对于每一个Di，使用局部回归(LOESS)拟合一条曲线(图中灰色线是其中的10条曲线)将这些曲线取平均，即得到红色的最终拟合曲线显然，红色的曲线更加稳定，并且没有明显过拟合,投票机制,简单投票机制一票否决(一致表决)少数服从多数有效多数(加权)阈值表决贝叶斯投票机制,贝叶斯投票机制,简单投票法假设每个分类器都是平等的。在实际生活中，我们听取一个人的意见，会考虑这个人过去的意见是否有用，从而加大或者减少权值。贝叶斯投票机制基于每个基本分类器在过去的分类表现设定一个权值，然后按照这个权值进行投票。,投票机制举例,假定有N个用户可以为X个电影投票(假定投票者不能给同一电影重复投票)，投票有1、2、3、