第四章-决策树

决策树1大纲什么是决策树决策树算法•ID3•C4.5•剪枝树•连续属性处理•缺失值处理•可解释性总结2决策树•预备知识:根节点,叶子节点,非叶子节点•每个非叶子节点代表一个属性的划分•每次划分的结果要么导致下一个的决策问题要么导致最终结论•决策树通过从根节点开始沿着分支直到叶子节点结束来对样本进行分类•决策树最终的结论（叶子节点）对应一个目标值3构建决策树的要素构建决策树的要素1、属性及属性值2、预定义的类别（目标值）3、充足的标记数据4训练集5训练集对应三个要素构建决策树的三个问题（3）什么时候停止并得到目标值？（1）从哪个属性开始或者说选择哪个属性作为根节点？6（2）选择哪个属性作为后继节点？决策树•决策树算法的基本思想：•选择最优属性划分当前样本集合并把这个属性作为决策树的一个节点•不断重复这个过程构造后继节点•直到满足下面三个条件之一停止:•对于当前节点，所有样本属于同一类•或者没有属性可以选择了•或者没有样本可以划分了7属性选择•决策树算法的一个关键问题：属性选择•不同决策树算法的差异：属性选择方法不同•下面以ID3算法为例讲解怎么构造决策树(ID3:InteractiveDichotomize3[RossQuinlan/1975])8ID3•ID3依据信息增益来选择最优属性•信息增益是通过信息熵计算而来•信息熵衡量一个集合的纯度例如：•集合1:10个好瓜•集合2:8个好瓜和2个坏瓜•集合3:5个好瓜和5个坏瓜纯度：集合1集合2集合39信息熵•pi是当前集合里类别为i的样本所占的比例,则：Entropy({p1,…,pk})=-sum(pilog(pi))•如果一个集合里的样本只有两个类别，那么：Entropy=-p1log(p1)-(1-p1)log(1-p1)•当集合里的所有样本都属于同一类时,信息熵是0•例如：集合1:10个好瓜•当集合里所有样本均匀混合时,信息熵是1•例如：集合2:5个好瓜，5个坏瓜p1=1orp1=0p1=0.510p1entropy信息熵当集合里所有样本属于同一类时（纯度最高时），信息熵最小。当集合里所有样本均匀混合时（纯度最低时），信息熵最大纯度越低，信息熵越大；纯度越高，信息熵越小11信息增益•一个属性的信息增益是本属性对样本集合进行划分所带来的信息熵下降•Di是集合D的第i个子集,a是一个属性，则:Gain(D,a)=Entropy(D)-∑(i=1tok)|Di|/|D|Entropy(Di)•划分:划分后信息熵越低信息增益越大•例如：D:5个好西瓜，5个坏瓜D1:2个好瓜,1个坏瓜D2:3个好瓜,4个坏瓜Gain(D,a)=Entropy(D)-(310Entropy(D1)+710Entropy(D2))12举例色泽：D1(色泽=青绿)={1+,4+,6+,10-,13-,17-}D2(色泽=乌黑)={2+,3+,7+,8+,9-,15-}D3(色泽=浅白)={5+,11-,12-,14-,16-}=13训练集举例同理：14举例D1={1+,2+,3+,4+,5+,6+,8+,10-,15-}15纹理=？{1+,2+,3+,4+,5+,6+,8+,10-,15-}{7+,9-,13-,14-,17-}{11-,12-,16-}清晰稍糊模糊ID3的缺陷例如：如果我们把“编号”作为一个属性，那么“编号”将会被选为最优属性。但实际上“编号”是无关属性，它对西瓜分类并没有太大作用。16ID3倾向于选择取值比较多的属性缺陷：有些属性可能会对分类任务没有太大作用，但是他们可能会被选为最优属性。C4.5信息增益比：17该项是对属性取值个数的度量属性属性的取值个数样本集合剪枝树•太多的属性和分支可能会导致过拟合•一种减少决策树中属性的技术：剪枝•两种剪枝类型：•预剪枝（前向剪枝）•后剪枝（后向剪枝）18剪枝•泛化能力：用验证集精度来衡量•预剪枝：在建造决策树的过程中停止添加属性•后剪枝：决策树构建完成后剪掉一些属性•预剪枝和后剪枝：都依据泛化能力19预剪枝举例如果我们停止添加这个属性，那么当前节点的标记是好瓜：验证集精度:3/7=42.9%如果我们添加这个属性到决策树，则验证集精度：(1+1+1+1+1)/7=71.4%42.9%所以我们添加此属性。20训练集验证集预剪枝举例预剪枝能够减少过拟合的风险，但它可能导致欠拟合预剪枝每次仅考虑了一个属性可能会带来泛化能力的下降，没有考虑后续多个属性的组合可能会带来的泛化能力的提升21后剪枝举例剪去纹理属性前验证集精度：3/7=42.9%当我们剪去纹理属性（节点6）:新的叶子节点包含：{7+,15-}，标记：好瓜验证集精度：57.1%42.9%所以剪枝。22好瓜训练集验证集剪枝举例后剪枝：预剪枝：23计算代价：高计算代价：低可能导致欠拟合连续属性处理•每个非叶子节点代表一个属性的划分（对于离散属性很容易）•对于连续属性：•把连续属性Ac划分成多个离散的区间•例如：找到一个阈值Ta把连续属性Ac转化成具有两个取值的离散属性Ad怎么选择阈值Ta?24Ad=𝑡𝑟𝑢𝑒𝑓𝑎𝑙𝑠𝑒ifAdTaotherwise连续属性处理训练集25(对应可能的划分)我们选择具有最高信息增益的划分所对应的阈值。缺失值处理26Q1：如何在属性值缺失的情况下进行属性选择？Q2：给定划分属性,若样本在该属性上的值缺失，如何对样本进行划分？缺失值处理27𝐷表示𝐷中在属性𝑎上有取值的样本子集；𝐷𝑣表示𝐷中在属性𝑎上取值为𝑎𝑣的样本子集；𝐷𝑘表示𝐷中属于第𝐾类的样本子集为每个样本𝒙赋予一个权重𝜔𝑥，并定义：无缺失值样本所占的比例无缺失值样本集𝐷中第𝐾类所占比例在属性𝑎无缺失值样本中取值𝑎𝑣的样本所占比例缺失值处理28基于上述定义，可得其中对于Q2：若样本在划分属性上的取值已知，则将划入与其取值对应的子结点，且样本权值在子结点中保持为若样本在划分属性上的取值未知，则将同时划入所有子结点，且样本权值在与属性值对应的子结点中调整为(直观来看，相当于让同一个样本以不同概率划入不同的子结点中去)缺失值处理举例色泽：={2+,3+,4+,6+,7+,8+,9-,10-,11-,12-,14-,15-,16-,17-}29Trainingset在色泽属性有取值的样本：首先初始化训练集每个样本的权重为1（后面会用到）。缺失值处理举例色泽：={2+,3+,4+,6+,7+,8+,9-,10-,11-,12-,14-,15-,16-,17-}青绿：={4+,6+,10-,17-}乌黑：={2+,3+,7+,8+,9-,15-}30Trainingset浅白：={11-,12-14-,16-}=缺失值处理举例Informationgain：31我们这里把含有色泽属性样本集的权重所占的比例考虑进去（每个样本的初始权重为1）：色泽：={2+,3+,4+,6+,7+,8+,9-,10-,11-,12-,14-,15-,16-,17-}含有14个样本，每个样本的权重为1，所以总权重为14；训练集D共包含17个样本，每个样本的权重为1，所以训练集D的总权重为17；所占权重比例为1417：缺失值处理举例32Similarly,缺失值处理举例33选择纹理属性后，我们把在纹理属性上有取值的样本划分到三个分支，权重不变；同时把在纹理属性上没有取值的样本8,10同时放进三个分支，在三个子节点的权重调整为即515,715,315。则：1.Dt1各个样本权重为：样本7,9,13,14,17的权重为1,样本8，10的权重为5152.Dt2各个样本权重为：样本1,2,3,4,5,6,15的权重为1,样本8，10的权重为7153.Dt2各个样本权重为：样本1,2,3,4,5,6,15的权重为1,样本8，10的权重为315{1,2,3,4,5,6,15,8,10}{7,9,13,14,17,8,10}{11,12,16,8,10}纹理(15个样本):{1,2,3,4,5,6,7,9,11,12,13,14,15,16,17}稍糊(5个样本):{7,9,13,14,17}清晰(7个样本):{1,2,3,4,5,6,15}模糊(3个样本):{11,12,16}缺失纹理属性取值的样本：{8,10}Dt1Dt2Dt3缺失值处理举例34{1,2,3,4,5,6,15,8,10}{7,9,13,14,17,8,10}{11,12,16,8,10}Dt1Dt2Dt3对于后续节点同理可求信息增益：1.Dt1各个样本权重为：样本7,9,13,14,17的权重为1,样本8，10的权重为5152.Dt2各个样本权重为：样本1,2,3,4,5,6,15的权重为1,样本8，10的权重为7153.Dt2各个样本权重为：样本1,2,3,4,5,6,15的权重为1,样本8，10的权重为315可解释性决策边界是平行坐标轴的对于过于复杂的问题，会导致很多小的划分35总结优点生成可理解的规则分类时计算代价很小能够选出对分类比较重要的属性对长方形分布的样本处理很好缺点决策树可能经历错误传播对于非长方形分布的样本处理不是很好（例如弧形）36++++-----++++++++-----++++++++-----++++------++++-----------++++-----------++++-----------++++-----------++++++++------++++++++------++++++++------++++++++实验介绍实验任务：实现ID3决策树，并在给定的数据集上进行5折交叉验证。并观测训所得到的决策树在训练集和测试集的准确率，从而判断该决策树是否存在过拟合。在此基础上实现预剪枝和后剪枝，并比较预剪枝树与后剪枝树在训练集和测试集上的准确率。数据集：鸢尾花卉Iris数据集描述：iris是鸢尾植物，这里存储了其萼片和花瓣的长宽，共4个属性，鸢尾植物分三类，分别是山鸢尾(Iris-setosa)，变色鸢尾(Iris-versicolor)和维吉尼亚鸢尾(Iris-virginica)。所以我们的数据集里每个样本含有四个属性，并且我们的任务是个三分类问题。。例如：样本一：5.1,3.5,1.4,0.2,Iris-setosa其中“5.1，3.5，1.4，0.2”代表当前样本的四个属性的取值，“Iris-setosa”代表当前样本的类别。37作业1.请阐述ID3和C4.5异同点?2.请阐述预剪枝和后剪枝的异同点?3.阐述如何解决构建决策树过程中遇到的连续属性问题?4.就你的理解，决策树存在哪些优缺点并阐述原因？5.讨论如何使用决策树技术对某校的男女生进行分类。并讨论你的方案可能存在的问题。38资源•C4.5package:•Wikipediapagefordecisiontree:•RandomForests(LeoBreimanandAdeleCutler):~breiman/RandomForests/•ICCV2013tutorial:DecisionForestsandFieldsforComputerVision:引用[Rastogi,etal.,1998]R.RastogiandK.Shim.PUBLIC:ADecisionTreeClassifierthatIntegratesBuildingandPruning.InProceedingsofthe24thInternationalConferenceo