决策树--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.5—ID3的改进，核心：信息增益比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特征选择问题•特征选择在于选取对训练数据具有分类能力的特征。•如何判断一个特征对于当前数据集的分类效果？也即确定选择特征的准则。ID年龄有工作有自己的房子信贷情况类别1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否例1.2右表是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的四个特征。表的最后一列是类别，是否同意贷款，取2个值：是、否。希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类。特征选择是决定用哪个特征来划分特征空间。1.2.2信息增益熵-就分类而言，所有成员都属于一类，熵为零；不同类别数目相等，则熵等于1，类别数目不等，则熵介于0,1之间。•当随机变量只有两个值，例如1,0时，即X的分布为P(X=1)=p,P(X=0)=1-p,0=p=1.则熵𝐻𝑝=−𝑝𝑙𝑜𝑔2𝑝−1−𝑝𝑙𝑜𝑔21−𝑝•熵H(p)随概率p变化的曲线如右图：•可知，当p=0或p=1时，H(p)=0，随机变量完全没有不确定性。条件熵•设有随机变量(X,Y),其联合概率分布为𝑃𝑋=𝑥𝑖,𝑌=𝑦𝑗=𝑝𝑖𝑗,𝑖=1,2,…,𝑛;𝑗=1,2,…,𝑚•条件熵H(Y|X)表示在已知随机变量X的条件下随机变量Y的不确定性。•定义：𝐻𝑌𝑋=𝑝𝑖𝐻𝑌𝑋=𝑥𝑖,𝑝𝑖=𝑃𝑋=𝑥𝑖,𝑖=1,2,…,𝑛.𝑛𝑖=1•当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵分别称为经验熵和经验条件熵。信息增益•信息增益表示得知特征X的信息而使得类Y的信息不确定性减少的程度。•定义5.2（信息增益）特征A对训练数据集D的信息增益g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即𝑔𝐷,𝐴=𝐻𝐷−𝐻(𝐷|𝐴)•根据信息增益准则的特征选择方法是：对训练数据集（或子集）D，计算其每个特征的信息增益，并比较它们的大小，选择信息增益最大的特征。信息增益的具体公式•设训练数据集为D，|D|表示其样本容量，即样本个数。设有K个类𝐶𝑘，k=1,2,…,K.|𝐶𝑘|为属于类𝐶𝑘的样本个数，𝐶𝑘=𝐷.设特征𝐴有𝑛个不同的取值{𝑎1𝐾𝑘=1,𝑎2,…,𝑎𝑛},根据特征A的取值将D划分为n个子集𝐷1,𝐷2,…,𝐷𝑛,𝐷𝑡为𝐷𝑖的样本个数，𝐷𝑖=𝐷.记子集𝐷𝑖中属于类𝑛𝑖=1𝐶𝑘的样本的集合为𝐷𝑖𝑘,|𝐷𝑖𝑘|为𝐷𝑖𝑘的样本个数。信息增益算法•输入：训练数据集D和特征A；•输出：特征A对训练数据集D的信息增益g(D,A).•(1)计算数据集D的经验熵H(D)𝐻𝐷=−|𝐶𝑘||𝐷|log2|𝐶𝑘||𝐷|𝐾𝑘=1(2)计算特征A对数据集D的经验条件熵H(D|A)𝐻𝐷𝐴=𝐷𝑖𝐷𝐻𝐷𝑖=−𝐷𝑖𝐷|𝐷𝑖𝑘||𝐷𝑖|log2|𝐷𝑖𝑘||𝐷𝑖|𝐾𝑘=1𝑛𝑘=1𝑛𝑖=1(3)计算信息增益g(D,A)=H(D)-H(D|A)例1.3对表1.1所给的训练数据集D,根据信息增益准则选择最优特征。ID年龄有工作有自己的房子信贷情况类别1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否这里分别以A1，A2，A3，A4依次表示这四个特性。𝑔𝐷,𝐴3=0.420𝑔(𝐷,𝐴4)=0.3631.2.3信息增益比•以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。•定义5.3（信息增益比）特征A对训练数据集D的信息增益比𝑔𝑅(𝐷,𝐴)定义为其信息增益𝑔(𝐷,𝐴)与训练数据集D关于特征A的值的熵𝐻𝐴𝐷之比，即𝑔𝑅𝐷,𝐴=𝑔(𝐷,𝐴)𝐻𝐴(𝐷)1.3决策树的生成1.3.1ID3算法•输入：训练数据集D,特征集A，阈值ε；•输出：决策树T.•（1）若D中所有实例属于同一类𝐶𝑘,则T为单结点树，并将类𝐶𝑘作为该结点的类标记，返回T;•（2）若A=Ø，则T为单结点树，并将D中实例数最大的类𝐶𝑘作为该结点的类标记，返回T;•（3）否则，计算A中各特征对D的信息增益，选择信息增益最大的特征𝐴𝑔;•（4）如果𝐴𝑔的信息增益小于阈值ε，则置T为单结点树，并将D中实例数最大的类𝐶𝑘作为该结点的类标记，返回T;•（5）否则，对𝐴𝑔的每一个可能值𝑎𝑖,依𝐴𝑔=𝑎𝑖将D分割为若干个非空子集𝐷𝑖,将𝐷𝑖中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T;•（6）对第𝑖个子结点，以𝐷𝑖为训练集，以𝐴−{𝐴𝑔}为特征集，递归地调用步(1)~(5),得到子树𝑇𝑖,返回𝑇𝑖.例1.4对表1.1的训练数据集，利用ID3算法建立决策树ID年龄有工作信贷情况类别1青年否一般否2青年否好否3青年是好是5青年否一般否6中年否一般否7中年否好否13老年是好是14老年是非常好是15老年否一般否有自己的房子(A3)ID年龄有工作信贷情况类别4青年是一般是8中年是好是9中年否非常好是10中年否非常好是11老年否非常好是12老年都好是是否表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（有工作）作为结点的特征。有自己的房子是否是是否有工作ID年龄信贷情况类别3青年好是13老年好是14老年非常好是表3ID年龄信贷情况类别1青年一般否2青年好否5青年一般否6中年一般否7中年好否15老年一般否表4这里生成的决策树只用到两个特征（两个内节点），ID3算法容易存在过拟合问题。补充：如何解决决策树的过拟合问题概念原因解决什么是过度拟合数据过度拟合数据是怎么产生的怎么去解决这个问题补充：如何解决决策树的过拟合问题——概念过度拟合（overfitting）：如果决策树对训练样本的特征描述得“过于精确”，无法实现对新样本的合理分析，所以此时它不是一棵分析新数据的最佳决策树。一棵完全决策树能非常准确地反映训练集中数据的特征，但因失去了一般代表性而无法用于对新数据的分类或预测，这种现象一般称为“过拟合”。定义：给定一个假设H，如果在假设空间上存在另一个假设H'，使得在训练集上H的错误率差比H'小，而在测试集上H的错误率却比H'要大，那么称假设H过度拟合训练数据。二.产生过度拟合数据问题的原因有哪些？原因1：样本问题（1）样本里的噪音数据干扰过大，大到模型过分记住了噪音特征，反而忽略了真实的输入输出间的关系；（什么是噪音数据？）（2）样本抽取错误，包括（但不限于）样本数量太少，抽样方法错误，抽样时没有足够正确考虑业务场景或业务特点，等等导致抽出的样本数据不能有效足够代表业务逻辑或业务场景；（3）建模时使用了样本中太多无关的输入变量。原因2：构建决策树的方法问题在决策树模型搭建中，我们使用的算法对于决策树的生长没有合理的限制和修剪的话，决策树的自由生长有可能每片叶子里只包含单纯的事件数据或非事件数据，可以想象，这种决策树当然可以完美匹配（拟合）训练数据，但是一旦应用到新的业务真实数据时，效果是一塌糊涂。三.如何解决过度拟合数据问题？针对原因1的解决方法：合理、有效地抽样，用相对能够反映业务逻辑的训练集去产生决策树；针对原因2的主要解决方法：剪枝：提前停止树的增长或者对已经生成的树按照一定的规则进行后剪枝。1.3.2C4.5的生成算法•C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进.C4.5在生成的过程中，用信息增益比来选择特征。1.4决策树的剪枝•决策树生成算法对于训练集是很准确的，但是会造成过拟合，所以需要通过剪枝来提高泛化能力。•剪枝思路：就是在决策树对训练数据的预测误差和树复杂度之间找到一个balance。•预测误差：为所有叶结点的经验熵的和，设树T的叶结点个数为|T|，t是