决策树--PPT

决策树李峰4月17日第五章决策树•5.1决策树模型与学习•5.2特征选择•5.3决策树的生成•5.4决策树的剪枝•5.5CART算法5.1决策树模型与学习•5.1.1决策树模型•5.1.2决策树与if-then规则•5.1.3决策树与条件概率分布•5.1.4决策树学习5.1.1决策树模型•什么是决策树？•定义5.1（决策树）分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个类。例1.找对象•决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友，于是有了下面的对话：•女儿：多大年纪了？(年龄)母亲：26。女儿：长的帅不帅？(长相)母亲：挺帅的。女儿：收入高不？(收入情况)母亲：不算很高，中等情况。女儿：是公务员不？(是否公务员)母亲：是，在税务局上班呢。女儿：那好，我去见见。5.1.2决策树与if-then规则•由决策树的根结点到叶结点的每一条路径构建一条规则；•路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。•If-then规则集合的一重要性质：互斥并且完备5.1.3决策树与条件概率分布将特征空间划分为互不相交的单元或区域，并在每个单元定义一个类的概率分布就构成了一个条件概率分布。各叶结点(单元)上的条件概率往往偏向某一个类，即属于某一类的概率较大，决策树分类时将该结点的实例强行分到条件概率大的那一类去。5.1.4决策树学习•假设给定训练数据集D={(𝑥1,𝑦1),(𝑥2,𝑦2),…,(𝑥𝑁,𝑦𝑁)}其中，𝑥𝑖=(𝑥𝑖1,𝑥𝑖2,…,𝑥𝑖(𝑛))𝑇为输入实例，n为特征个数,𝑦𝑖∈1,2,3,…,𝐾为类标记，𝑖=1,2,…,𝑁,𝑁为样本容量。•学习目标：根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。•决策树学习本质：从训练数据集中归纳出一组分类规则。5.1.4决策树学习•目标：我们需要的是一个与训练数据矛盾较小的决策树，同时具有很好的泛化能力。•决策树学习的损失函数：（通常是）正则化的极大似然函数。但是基于损失函数找到全局最优决策树是NP-完全问题。•现实中决策树学习通常采用启发式方法，即局部最优。•具体做法：每次选择feature时，都挑选择当前条件下最优的那个feature作为划分规则，即局部最优的feature。5.2特征选择5.2.1特征选择问题•特征选择在于选取对训练数据具有分类能力的特征。•如何判断一个特征对于当前数据集的分类效果？也即确定选择特征的准则。ID年龄有工作有自己的房子信贷情况类别1青年否否一般否2青年否否好否3青年是否好是4青年是是一般是5青年否否一般否6中年否否一般否7中年否否好否8中年是是好是9中年否是非常好是10中年否是非常好是11老年否是非常好是12老年否是好是13老年是否好是14老年是否非常好是15老年否否一般否例5.1右表是一个由15个样本组成的贷款申请训练数据。数据包括贷款申请人的四个特征。表的最后一列是类别，是否同意贷款，取2个值：是、否。希望通过所给的训练数据学习一个贷款申请的决策树，用以对未来的贷款申请进行分类。特征选择是决定用哪个特征来划分特征空间。5.2.2信息增益•熵：在信息论中，是接收的每条消息中包含的信息的平均量；（比较不可能发生的事情，当它发生了，会提供更多的信息）•熵：表示随机变量不确定性的度量。熵越大，随机变量的不确定性就越大。（举例：抛硬币）•设X是一个取有限个值的离散随机变量，其概率分布为𝑃𝑋=𝑥𝑖=𝑝𝑖,𝑖=1,2,…,𝑛则随机变量X的熵定义为𝐻𝑋=−𝑝𝑖𝑙𝑜𝑔𝑝𝑖𝑛𝑖=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)例5.2对表5.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.3635.2.3信息增益比•以信息增益作为划分训练数据集的特征，存在偏向于选择取值较多的特征的问题。•定义5.3（信息增益比）特征A对训练数据集D的信息增益比𝑔𝑅(𝐷,𝐴)定义为其信息增益𝑔(𝐷,𝐴)与训练数据集D关于特征A的值的熵𝐻𝐴𝐷之比，即𝑔𝑅𝐷,𝐴=𝑔(𝐷,𝐴)𝐻𝐴(𝐷)5.3决策树的生成5.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),得到子树𝑇𝑖,返回𝑇𝑖.例5.3对表5.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老年一般否表45.3.2C4.5的生成算法•C4.5算法与ID3算法相似，C4.5算法对ID3算法进行了改进.C4.5在生成的过程中，用信息增益比来选择特征。5.4决策树的剪枝•决策树生成算法对于训练集是很准确的，但是会造成过拟合，所以需要通过剪枝来提高泛化能力。•剪枝思路：就是在决策树对训练数据的预测误差和树复杂度之间找到一个balance。•预测误差：为所有叶结点的经验熵的和，设树T的叶结点个数为|T|，t是树T的叶结点，𝑁𝑡表示该叶结点的样本点个数，其中𝑘类样本点有𝑁𝑡𝑘个，𝑘=1,2,…,K,而𝐻𝑡𝑇表示叶结点t的经验熵。𝐻𝑡𝑇=−𝑁𝑡𝑘𝑁𝑡log𝑁𝑡𝑘𝑁𝑡𝑘•决策树学习的损失函数为：𝐶𝑎𝑇=𝑁𝑡|𝑇|𝑡=1𝐻𝑡𝑇+𝑎|𝑇|.(𝑎=0)算法5.4树的剪枝算法•输入：生成算法产生的整个树T,参数a;•输出：修建后的子树𝑇𝑎.(1)计算每个结点的经验熵.(2)递归地从树的叶结点向上回缩.设一组叶结点回缩到其父结点之前与之后的整体树分别为𝑇𝐵与𝑇𝐴，其对应的损失函数分别是𝐶𝑎(𝑇𝐵)与𝐶𝑎(𝑇𝐴)，如果𝐶𝑎(𝑇𝐴)=𝐶𝑎(𝑇𝐵)则进行剪枝，即将父结点变为新的叶结点。(3)返回(2)，直至不能继续为止，得到损失函数最小的子树𝑇𝑎.5.5CART（分类与回归树）算法•CART同样由特征选择、树的生成及剪枝组成，即可以用于分类也可以用于回归。•CART假设决策树是二叉树，内部结点特征的取值为“是”和“否。这样的决策树等价于递归地二分每个特征。步骤：（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。5.5.1CART生成•决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数(Giniindex)最小化准则，进行特征选择，生成二叉树。最开始我们可以按：表面覆盖为毛发与非毛发表面覆盖为鳞片与非鳞片恒温与非恒温来产生当前结点的左右两个孩子。我们将Gini指数来作为准则判别哪种划分比较好。GINI指数定义：分类问题中，假设有K个类，样本点属于第k类的概率为𝑝𝑘,则概率分布的基尼指数定义为：𝐺𝑖𝑛𝑖𝑝=𝑝𝑘(1−𝑝𝑘)𝐾𝑘=1=1-𝑝𝑘2𝐾𝑘=1比如体温为恒温时包含哺乳类5个，鸟类2个：𝐺𝑖𝑛𝑖=1−[572+272]=2049体温为非恒温时包含爬行类3个、鱼类3个、两栖类2个，则𝐺𝑖𝑛𝑖=1−382+382+282=4264Gini增益为：𝐺𝑖𝑛𝑖�