第四章-决策树

决策树1大纲什么是决策树决策树算法ID3C4.5剪枝树连续属性处理缺失值处理可解释性

总结2决策树预备知识:根节点,叶子节点,非叶子节点每个非叶子节点代表一个属性的划分每次划分的结果要么导致下一个的决策问题要么导致最终结论

决策树通过从根节点开始沿着分支直到叶子节点结束来对样本进行分类决策树最终的结论（叶子节点）对应一个目标值3构建决策树的要素构建决策树的要素1、属性及属性值2、预定义的类别（目标值）3、充足的标记数据4训练集5训练集对应三个要素构建决策树的三个问题（3）什么时候停止并得到目标值？（1）

从哪个属性开始或者说选择哪个属性作为根节点？6（2）选择哪个属性作为后继节点？决策树决策树算法的基本思想：选择最优属性划分当前样本集合并把这个属性作为决策树的一个节点不断重复这个过程构造后继节点直到满足下面三个条件之一停止:对于当前节点，所有样本属于同一类或者没有属性可以选择了或者没有样本可以划分了7属性选择决策树算法的一个关键问题：属性选择不同决策树算法的差异：属性选择方法不同下面以

ID3

算法为例讲解怎么构造决策树(ID3:

InteractiveDichotomize3[RossQuinlan/1975])8ID3ID3依据信息增益来选择最优属性信息增益是通过信息熵计算而来信息熵衡量一个集合的纯度例如：集合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个坏瓜

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的缺陷例如：如果我们把“编号”作为一个属性，那么“编号”将会被选为最优属性

。但实际上“编号”是无关属性，它对西瓜分类并没有太大作用。16ID3倾向于选择取值比较多的属性缺陷：

有些属性可能会对分类任务没有太大作用，但是他们可能会被选为最优属性。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?24

ifAd<

Taotherwise连续属性处理训练集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-}

缺失值处理举例32Similarly,缺失值处理举例33

{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对于后续节点同理可求信息增益：

可解释性决策边界是平行坐标轴的对于过于复杂的问题，会导致很多小的划分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作业请阐述ID3和C4.5异同点?请阐述预剪枝和后剪枝的异同点?阐述如何解决构建决策树过程中遇到的连续属性问题?就你的理解，决策树存在哪些优缺点并阐述原因？讨论如何使用决策树技术对某校的男女生进行分类。并讨论你的方案可能存在的问题。38资源C4.5package:/Personal/c4.5r8.tar.gzWikipediapagefordecisiontree:/wiki/Decision_tree_learningRandomForests(LeoBreimanandAdeleCutler):/~breiman/RandomForests/ICCV2013tutorial:DecisionForestsandFieldsforComputerVision:/enus/um/cambridge/projects/iccv2013tutorial/39引用[Rastogi,etal.,1998]R.RastogiandK.Shim.PUBLIC:ADecisionTreeClassifierthatIntegratesBuildingandPruning.InProceedingsofthe24thInternationalConferenceonVeryLargeDataBases(VLDB’98),pp.404–415,Aug.1998.[Shafer,etal.,1996]J.C.Shafer,R.Agrawal,andM.Mehta.SPRINT:AScalableParallelClassifierforDataMining.InProceedingsofthe22thInternationalConferenceonVeryLargeDataBases(