《第四章：决策树学习报告》由会员分享，可在线阅读，更多相关《第四章：决策树学习报告（43页珍藏版）》请在文档大全上搜索。
1、Decision tree learn report4.1.基本流程决策树是一类常见的机器学习方法。从给定的训练数据集学得一个模型用以对新示例进行分类，某种问题的“决策”或“判定”过程。决策树一个根结点（包含样本全集）对应一个属性测试内部结点对应一个属性测试叶结点对应决策结果4.1.(1)决策树目的：产生一颗泛化能力强，即处理未见示例能力强的决策树决策树的生成是一个递归的过程，在基本算法中，有三种情形会导致递归返回： 当前结点包含的样本全属于同一类别，无需划分1 当前属性集为空，或是所有样本在所有属性上取值相同，无法划分2 当前结点包含的样本集合为空，不能划分34.2.划分选择决策树学习的关键
2、：如何选择最优化分属性随着划分过程不断进行，我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”（purity）越来越高。4.2(1)信息熵信息熵（information entropy）是度量样本集合纯度最常用的一种指标。假定当前样本集合D中第k类样本所占的比例为 (k=1,2, ),则D的信息熵定义为：Ent(D)的值越小，则D的纯度越高。kpy21()logkypkkEnt Dp 4.2(2)信息熵计算信息熵时约定：若p=0,则 Ent(D)的最小值为0，最大值为 例：假设D中有8个样本，且有k=8，则 2log0pp2logy18kp82111()log88kEnt
3、 D 4.2(3)信息增益假定离散属性a有V个可能的取值 ，若使用a来对样本集D进行划分，则会产生V个分支结点，其中第v个分支结点包含了D中所有在属性a上取值为 的样本，记为 。根据不同分支结点包含的样本数不同，给分支结点赋予权重： 即样本数越多的分支结点的影响越大。12,.,Va aavavD/vDD4.2(4)信息增益属性a对样本集D进行划分所获得的“信息增益”（information gain）信息增益越大，则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此，可用信息增益来进行决策树的划分属性选择。1( , )()()vVvvDGain D aEnt DEnt DD编号编号色泽色
4、泽根蒂根蒂敲声敲声纹理纹理脐部脐部触感触感好瓜好瓜1青绿蜷缩浊响清晰凹陷硬滑是2乌黑蜷缩沉闷清晰凹陷硬滑是3乌黑蜷缩浊响清晰凹陷硬滑是4青绿蜷缩沉闷清晰凹陷硬滑是5浅白蜷缩浊响清晰凹陷硬滑是6青绿稍蜷浊响清晰稍凹软粘是7乌黑稍蜷浊响稍糊稍凹软粘是8乌黑稍蜷浊响清晰稍凹硬滑是9乌黑稍蜷沉闷稍糊稍凹硬滑否10青绿硬挺清脆清晰平坦软粘否11浅白硬挺清脆模糊平坦硬滑否12浅白蜷缩浊响模糊平坦软粘否13青绿稍蜷浊响稍糊凹陷硬滑否14浅白稍蜷沉闷稍糊凹陷硬滑否15乌黑稍蜷浊响清晰稍凹软粘否16浅白蜷缩浊响模糊平坦硬滑否17青绿蜷缩沉闷稍糊稍凹硬滑否4.2(5)信息增益以上表为例,该数据集包含17个训练样例
5、，用以学习一颗能预测没剖开的瓜是不是好瓜的决策树.显然 .在决策树开始学习时,根结点包含D中的所有样例,其中正例占 ,反例占 .根据(1)式可算出根结点的信息熵为：2y 1817p 2917p 222218899( )log(loglog)0.99817171717kkkEnt Dpp4.2(6)然后我们要计算出当前属性集合色泽,根蒂,敲声,纹理,脐部,触感中每个属性的信息增益.以色泽为例,它有三个可能的取值：青绿,乌黑,浅白.对D进行划分,则可得到3个子集,分别为： (色泽=青绿), (色泽=乌黑), (色泽=浅白).D1=1,4,6,10,13,17D2=2,3,7,8,9,15D3=5,
6、11,12,14,16所以1D2D3D13 6p 23 6p 14 6p 22 6p 11 5p 24 5p 1223333()(loglog)1.0006666Ent D 2224422()(loglog)0.9186666Ent D 321144()(loglog)0.7225555Ent D 4.2(7)于是，我们可以算出属性”色泽”的信息增益为：Gain(D,色泽)类似的，可以算出： Gain(D,根蒂)=0.143 Gain(D,敲声)=0.141 Gain(D,纹理)=0.381 Gain(D,脐部)=0.289 Gain(D,触感)=0.00631( )()6650.998 (1
7、.0000.9180.722)1717170.109vvvDEnt DEnt DD4.2(8)显然,属于“纹理”的信息增益最大,于是它被选为划分属性.然后,决策树学习算法将对每个分支结点做进一步划分.可用属性集合色泽,根蒂,敲声,脐部,触感基于各结点的集合样例计算出各属性的信息增益.纹理1,2,3,4,5,6,8,10,157,9,13,14,1711,12,16清晰稍糊模糊4.2(9)基于D1(纹理=清晰)=1,2,3,4,5,6,8,10,15计算出的各属性的信息增益为：Gain(D1,色泽)=0.043 Gain(D1,根蒂)=0.458Gain(D1,敲声)=0.331 Gain(D1
8、,脐部)=0.458Gain(D1,触感)=0.458根蒂、脐部、触感3个属性均取得最大的信息增益，可任选之一作为划分属性.类似的,对每个分支结点进行上述操作,最终得到的决策树如下：4.2(10)决策树：根蒂=？触感=？纹理色泽=？触感=？坏瓜坏瓜好瓜坏瓜好瓜好瓜好瓜好瓜坏瓜清晰稍糊模糊软粘硬滑蜷缩硬挺稍蜷青绿浅白乌黑硬滑软粘4.2.2增益率信息增益准则对可取值数目较多的属性有所偏好,例如“编号”,它的信息增益为0.998,远大于其他属性,“编号”将产生17支分支,每个分支结点仅包含一个样本,这些分支结点的纯度达到最大.然而,这样的决策树显然不具有泛化能力,无法对新样本进行有效的预测.C4.5
9、决策树算法Quinlan,1993不直接使用信息增益,而是用“增益率”(gain ratio)来选择最优划分属性.4.2.2(1)增益率：属性a可能取值数目越多(即V越大),则IV(a)的值通常会越大增益率准则对可取值数目较少的属性有所偏好,因此,C4.5算法并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式Quinlan,1993:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的.( , )_( )Gain D aGainratioIV a21( )logvvVvDDIV aDD 属性a的固有值4.2.3基尼指数(Gini index)CART决策树Brei
10、man et al.,1984使用“基尼指数”来选择划分属性.数据集D的纯度可用基尼值来度量：1()ykkkkkGini Dp p211ykkpGini(D)反应了从数据集D中随机抽取两个样本,其类别标记不一致的概率.Gini(D)越小,则数据集D的纯度越高4.2.3(1)属性a的基尼指数定义为：于是,我们在候选属性集合A中,选择那个使得划分后基尼指数最小的属性作为最优划分属性.1_(, )()vVvvDGiniindex D aGini DD4.3剪枝处理剪枝(ppruning)是决策树学习算法对付“过拟合”的主要手段.基本策略：预剪枝(prepruning) 后剪枝(post-prunin
11、g)在决策树生成过程中,对每个结点在划分前先进性估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点.先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若将该结点对应的子树替换为叶结点能带来泛化能力提升,则将该子树替换为叶结点4.3(1)随机划分出两部分：Train:1,2,3,6,7,10,14,15,16,17Test:4,5,8,9,11,12,13脐部=？色泽=？根蒂=？色泽=？纹理=？坏瓜好瓜坏瓜好瓜坏瓜好瓜好瓜好瓜好瓜好瓜坏瓜凹陷稍凹平坦青绿乌黑浅白稍蜷蜷缩硬挺青绿乌黑浅白稍糊清晰模糊4,13511,12984.3.1预剪枝基于信息增
12、益准则,我们选择“脐部”来对train进行划分,并产生3个分支.预剪枝要对划分后的泛化性能进行估计：脐部=？好瓜好瓜坏瓜凹陷稍凹平坦验证集精度划分前：42.9%划分后：71.4%预剪枝决策：划分验证集精度色泽=？划分前：71.4% 划分后：57.1%预剪枝决策：禁止划分验证集精度根蒂=? 划分前：71.4% 划分后：71.4%预剪枝决策：禁止划分4,5,138,911,12仅有一层划分的决策树，亦称为“决策树桩”4.3.1(1)划分后：1,2,3,14 10,16 6,7,15,17其中4,5,8,11,12被分类正确,验证集精度为 42.9%色泽划分后：好瓜4(1),13(0),坏瓜5(1)
13、根蒂划分后：好瓜8(1),9(0)5100% 71.4%74.3.1(2)预剪枝使得决策树的很多分支都没有“展开”,这不仅降低了过拟合的风险,还显著减少了决策树的训练时间开销和预测试时间开销.另一方面,有些分支的当前划分虽不能提升泛化性能、甚至可能导致泛化性能暂时下降,但在其基础上进行的后续划分却有可能导致性能显著提高.预剪枝基于“贪心”本质禁止这些分支展开,给预剪枝决策树带来了欠拟合的风险.4.3.2后剪枝后剪枝先从训练集生成一棵完整的决策树基于train :1,2,3,6,7,10,14,15,16,17得到决策树脐部=？根蒂=？色泽=？好瓜坏瓜好瓜好瓜好瓜坏瓜坏瓜凹陷稍凹平坦稍蜷蜷缩硬挺
14、青绿乌黑浅白原分支“色泽=？”验证集精度剪枝钱：57.1%剪枝后：71.4%后剪枝决策：剪枝原分支“纹理=？”验证集精度剪枝钱：42.9%剪枝后：57.1%后剪枝决策：剪枝4.3.2(1)后剪枝决策树通常比预剪枝决策树保留了更多的分支,一般情况下,后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树.但后剪枝过程是在生成完全决策树之后进行的,并且要自底向上地对树中的所有非叶结点进行逐一考察.因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多.4.4连续与缺失值现实学习任务中常会遇到连续属性.连续属性的可取值数目不再有限,因此,不能直接根据连续属性的可取值来对结点进行划分.连续属性离
15、散化技术：二分法(bi-partitiom)4.4.1连续值处理给定样本集合D和连续属性a,假定a在D上出现了n个不同的取值,将这些值从小到大排序,记为 .基于划分点t可将D分为子集 和 ,其中 包含哪些在属性a上取值不大于t的样本,而 则包含那些在属性a上取值大于t的样本.显然,对于相邻的属性 与 来说,t在区间中取任意值所产生的划分结果相同.12,.,na aatDtDtDtDia1ia1,iia a4.1.1(1)对属性a,我们考察包含n-1个元素的候选划分点:即把中位点作为候选划分点.像离散属性值一样来考察这些划分点,选取最优划分点进行样本集合的划分：1|112iiaaaTin( ,
16、)max( , , )at TGain D aGain D a t , max()()attt TDEnt DEnt DD 4.1.1(2)其中Gain(D,a,t)是样本集D基于划分点t二分后的信息增益.于是,我们可选择使Gain(D,a,t)最大化的划分点.(密度，含糖率)123456780.6970.7740.6340.6080.5560.4030.4810.4370.4600.3760.2640.3180.2150.2370.1490.211910111213141516170.6660.2430.2450.3430.6390.6570.3600.5930.7190.0910.2670
17、.0570.0090.1610.1980.3700.0420.1034.1.1(3)对于密度,该属性有16个候选划分点：T=0.244,0.294,0.351,0.381,0.420,0.459,0.518,0.574,0.600,0.621,0.636,0.648,0.661,0.681,0.708,0.746根据(6)式可计算出其信息增益为0.262,对应划分点0.381222218899()log(loglog)0.99817171717kkkEnt Dpp 2222 , 11413()( log )(log)1717ttkkkkkkDMEnt DppppD 22138855130(lo
18、glog)0.736(0.764)1713131313174.1.1(4)所以,由(6)式得Ent(D)-M=0.262类似的,对于含糖率也可计算出信息增益为0.349.须注意是,与离散是寻根不同,若当前结点划分属性为连续属性,该属性还可作为其后代结点的划分属性.个属性的信息增益Gain(D,色泽)=0.109 Gain(D,根蒂)=0.143Gain(D,敲声)=0.141 Gain(D,纹理)=0.381Gain(D,脐部)=0.289 Gain(D,触感)=0.006Gain(D,密度)=0.262 Gain(D,含糖率)=0.3494.4.2缺失值处理现实中往往会遇见不完整样本,即样本
19、的某些属性值缺失.如果放弃不完整样本,仅使用无缺失值的样本来学习,显然是对数据信息的极大浪费.我们需要解决的问题：如何在属性值缺失的情况下进行划分属性选择？给定划分属性,若样本在该属性上的值缺失,如何对样本进行划分？4.2.2(1)问题一给定训练集D和属性a,令 表示D中在属性a上没有缺失值的样本子集.对于(1)可以用 来判断属性a的优劣.假定属性a有V个可取值 ,令 表示 中在属性a上取值为 的样本子集, 表示 中属于第k类(k=1,2, )的样本子集,显然有DD12,.,Va aavDDvakDDy1ykkDD1VvvDD4.2.2(2)我们为每个样本x赋予一个权重 ,并定义：xwxx D
20、xx Dwwkxx Dkxx Dwpwvxx Dvxx Dwrw(1)ky(1)vVP表示无缺失值样本所占的比例表示无缺失值样本中第k类所占的比例表示无缺失值样本中在属性a上取值a(v)的样本所占比例4.2.2(3)显然,基于上述定义,我们可以将信息增益的计算式推广：11ykkp11Vvvr( , )( , )Gain D aGain D a1()()VvvvEnt Dr Ent D4.2.2(4)问题二若样本x在属性a上的取值已知,则将x划入与其值对应的子结点,且样本权值在子结点中保持为w(x).若样本x在属性a上的取值未知,则将x同时划入所有子结点,且样本权值在与属性值a(v)对应的子结点
21、中调整为 ;(就是让同一个样本以不同的概率划入到不同的子结点中去)C4.5算法使用了上述解决方案Quinlan,1993vxr w4.2.2(5)以属性色泽为例,根结点包含17个样例.各样例的权值为1.该属性上的无缺失值的样例子集 包含2,3,4,6,7,8,9,10,11,12,14,15,16,17(14) 的信息熵为：令 分别表示“色泽”上取值为“青绿”“乌黑”“浅白”的样本子集.有DD221()log.0.985kkkEnt Dpp 123,D DD1()1.000Ent D2()0.918Ent D3()0.000Ent D4.2.2(6)样本子集D()上属性a(色泽)的信息增益为：
22、于是,样本集D上属性a(色泽)的信息增益为：31( ,)()()0.306vvvGain D sezeEnt Dr Ent D( ,)( ,)0.252Gain D sezeGain D seze4.2.2(7)类似的可以计算出所有属性在D上的信息增益.纹理在所有属性中取得最大的信息增益,被用于根结点进行划分.稍糊7,9,13,14,17清晰1,2,3,4,5,6,15模糊11,12,16而8,10样本在纹理属性上缺失值,将其加上权值分别分入三个分支Gain(D,色泽)=0.252 Gain(D,根蒂)=0.171Gain(D,敲声)=0.145 Gain(D,纹理)=0.424Gain(D,
23、脐部)=0.289 Gain(D,触感)=0.0064.5多变量决策树若我们把每个属性视为坐标空间中的一个坐标轴,则d个属性描述的样本就对应了d维空间的一个数据点,对样本分类则意味着在这个坐标空间中寻找不同类样本之间的分类边界.决策树所形成的分类边界特点：轴平行(分类边界由若干个与坐标轴平行的分段组成)每一段划分都直接对应了某个属性取值,这样的分类边界使得学习结果有较好的可解释性.但在真实分类边界比较复杂时,必须用很多段划分才能获得较好的近似.此时的决策树会相当复杂,预测时间开销会很大.4.5(1)简化决策模型：多变量决策树 斜划分：用斜的划分边界非叶结点不再是仅对某个属性,而是对属性的线性组合进行测试：W(i)是属性a(i)的权重.w和t可在该结点所含的样本集合属性集上学得.1diiiw at4.5(2)与单变量决策树不同,多变量决策树的学习过程中,不是为每个非叶结点寻找一个最后划分属性,而是试图建立一个合适的线性分类器.-0.800*密度-0.044*含糖率=-0.313？-0.365*密度+0.366*含糖率=-0.158？坏瓜坏瓜好瓜是是否否
