决策树--ppt资料－金锄头文库

资源描述

《决策树--ppt资料》由会员分享，可在线阅读，更多相关《决策树--ppt资料（66页珍藏版）》请在金锄头文库上搜索。

1、决策树,根据李峰等人的PPT改编课件主要依据李航编写的统计学习方法编制，清华大学出版社另一本参考书：数据挖掘与数学建模国防工业出版社 2010,决策树,1.1 决策树模型与学习 1.2 特征选择 1.3 决策树的生成 1.4 决策树的剪枝 1.5 CART算法,1.1 决策树模型与学习,1.1.1 决策树模型 1.1.2 决策树与if-then规则 1.1.3 决策树与条件概率分布 1.1.4 决策树学习,1.1.1 决策树模型,什么是决策树？定义1.1（决策树）分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一

2、个特征或属性，叶节点表示一个类。,决策树学习算法的特点,决策树学习算法的最大优点是，它可以自学习。在学习的过程中，不需要使用者了解过多背景知识，只需要对训练实例进行较好的标注，就能够进行学习。显然，它属于有监督学习。从一类无序、无规则的事物(概念)中推理出决策树表示的分类规则。,决策树学习的主要算法,建立决策树的关键，即在当前状态下选择哪个属性作为分类依据。根据不同的目标函数，建立决策树主要有一下三种算法。 ID3 （J. Ross Quinlan-1975）核心：信息熵 C4.5ID3的改进，核心：信息增益比 CART（Breiman-1984），核心：基尼指数,例1. 找对象,决策树分

3、类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：女儿：多大年纪了？ (年龄) 母亲：26。女儿：长的帅不帅？ (长相) 母亲：挺帅的。女儿：收入高不？ (收入情况) 母亲：不算很高，中等情况。女儿：是公务员不？ (是否公务员) 母亲：是，在税务局上班呢。女儿：那好，我去见见。,1.1.2 决策树与if-then规则,由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。 If-then规则集合的一重要性质：互斥并且完备,1.1.3 决策树与条件概率分布,将特征空间划分为互不相交的单

4、元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。各叶结点(单元)上的条件概率往往偏向某一个类，即属于某一类的概率较大，决策树分类时将该结点的实例强行分到条件概率大的那一类去。,1.1.4 决策树学习,假设给定训练数据集 D=(1,1),(2,2),(,) 其中，= ( 1 , 2 , () ) 为输入实例，n为特征个数, 1,2,3, 为类标记，=1,2,为样本容量。学习目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。决策树学习本质：从训练数据集中归纳出一组分类规则。,1.1.4 决策树学习,目标：我们需要的是一个与训练数据矛盾较小的决策树

5、，同时具有很好的泛化能力。决策树学习的损失函数：（通常是）正则化的极大似然函数。但是基于损失函数找到全局最优决策树是NP-完全问题。现实中决策树学习通常采用启发式方法，即局部最优。具体做法：每次选择feature时，都挑选择当前条件下最优的那个feature作为划分规则，即局部最优的feature。,1.2 特征选择 1.2.1 特征选择问题,特征选择在于选取对训练数据具有分类能力的特征。如何判断一个特征对于当前数据集的分类效果？也即确定选择特征的准则。,例1.2 右表是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的四个特征。表的最后一列是类别，是否同意贷款，取2个值：

6、是、否。希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类。特征选择是决定用哪个特征来划分特征空间。,1.2.2 信息增益,熵-就分类而言，所有成员都属于一类，熵为零；不同类别数目相等，则熵等于1，类别数目不等，则熵介于0,1之间。,当随机变量只有两个值，例如1,0时，即X的分布为 P(X=1)=p , P(X=0)=1-p , 0=p=1. 则熵 = 2 1 2 1 熵H(p)随概率p变化的曲线如右图：可知，当p=0或p=1时，H(p)=0，随机变量完全没有不确定性。,条件熵,设有随机变量(X,Y),其联合概率分布为 = ,= = ,=1,2,;=1,2,

7、条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。定义： = =1 = , = = ,=1,2,. 当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵分别称为经验熵和经验条件熵。,信息增益,信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。定义5.2（信息增益）特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即 , = (|) 根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。,信息增

9、 log 2 | | | | (3)计算信息增益 g(D,A)=H(D)-H(D|A),例1.3 对表1.1所给的训练数据集D, 根据信息增益准则选择最优特征。,这里分别以A1，A2，A3，A4依次表示这四个特性。 , 3 =0.420 (, 4 )=0.363,1.2.3 信息增益比,以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。定义5.3（信息增益比）特征A对训练数据集D的信息增益比 (,)定义为其信息增益(,)与训练数据集D关于特征A的值的熵之比，即 , = (,) (),1.3 决策树的生成 1.3.1 ID3算法,输入：训练数据集D,特征集A，阈值；输

10、出：决策树T. （1）若D中所有实例属于同一类 ,则T为单结点树，并将类作为该结点的类标记，返回T; （2）若A=，则T为单结点树，并将D中实例数最大的类作为该结点的类标记，返回T; （3）否则，计算A中各特征对D的信息增益，选择信息增益最大的特征 ; （4）如果的信息增益小于阈值，则置T为单结点树，并将D中实例数最大的类作为该结点的类标记，返回T; （5）否则，对的每一个可能值 ,依 = 将D分割为若干个非空子集 ,将中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T; （6）对第个子结点，以为训练集，以为特征集，递归地调用步(1)(5),得到子树 ,返回

11、 .,例1.4 对表1.1的训练数据集，利用ID3算法建立决策树,有自己的房子(A3),是,否,表1,表2, 2 需从特征 1 （年龄）， 2 （有工作）， 3 （信贷情况）中选择新的特征，计算各个特征的信息增益： ( 2 , 1 )=H( 2 )-H( 2 | 1 )=0.918-0.667=0.251 ( 2 , 2 )=H( 2 )-H( 2 | 2 )=0.918 ( 2 , 4 )=H( 2 )-H( 2 | 4 )=0.474 于是选择信息增益最大的特征 2 （有工作）作为结点的特征。,有自己的房子,是,否,是,是,否,有工作,表3,表4,这里生成的决策树只用到两个特征（两个内节点

12、），ID3算法容易存在过拟合问题。,补充：如何解决决策树的过拟合问题,概念,原因,解决,什么是过度拟合数据,过度拟合数据是怎么产生的,怎么去解决这个问题,补充：如何解决决策树的过拟合问题概念,过度拟合（overfitting）：如果决策树对训练样本的特征描述得“过于精确”，无法实现对新样本的合理分析，所以此时它不是一棵分析新数据的最佳决策树。一棵完全决策树能非常准确地反映训练集中数据的特征，但因失去了一般代表性而无法用于对新数据的分类或预测，这种现象一般称为“过拟合”。,定义：给定一个假设H，如果在假设空间上存在另一个假设H，使得在训练集上H的错误率差比H小，而在测试集上H的错误率却比H要大，

13、那么称假设H过度拟合训练数据。,二.产生过度拟合数据问题的原因有哪些？,原因1：样本问题（1）样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系；（什么是噪音数据？）（2）样本抽取错误，包括（但不限于）样本数量太少，抽样方法错误，抽样时没有足够正确考虑业务场景或业务特点，等等导致抽出的样本数据不能有效足够代表业务逻辑或业务场景；（3）建模时使用了样本中太多无关的输入变量。原因2：构建决策树的方法问题在决策树模型搭建中，我们使用的算法对于决策树的生长没有合理的限制和修剪的话，决策树的自由生长有可能每片叶子里只包含单纯的事件数据或非事件数据，可以想象，

14、这种决策树当然可以完美匹配（拟合）训练数据，但是一旦应用到新的业务真实数据时，效果是一塌糊涂。,三.如何解决过度拟合数据问题？,针对原因1的解决方法：合理、有效地抽样，用相对能够反映业务逻辑的训练集去产生决策树；针对原因2的主要解决方法：剪枝：提前停止树的增长或者对已经生成的树按照一定的规则进行后剪枝。,1.3.2 C4.5的生成算法,C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进.C4.5在生成的过程中，用信息增益比来选择特征。,1.4 决策树的剪枝,决策树生成算法对于训练集是很准确的，但是会造成过拟合，所以需要通过剪枝来提高泛化能力。剪枝思路：就是在决策树对训练数据的预测误差和树复杂度之间找到一个balance。预测误差：为所有叶结点

展开阅读全文