机器学习导论-第6章决策树.ppt

1、第第6章章 决策树决策树n熟悉决策树的概念以及决策树的生成策略。熟悉决策树的概念以及决策树的生成策略。n熟悉熟悉ID3、C4.5、CART算法中所用的特征选择指标算法中所用的特征选择指标。n了解了解ID3、C4.5、CART三种算法的优缺点及适用场合。三种算法的优缺点及适用场合。n了解决策树的剪枝处理方法。了解决策树的剪枝处理方法。n熟悉决策树的优缺点。熟悉决策树的优缺点。本章学习目标本章学习目标n6.1 概述概述n6.2 决策树学习决策树学习n6.3 特征（或属性）选择特征（或属性）选择n6.4 ID3算法算法n6.5 C4.5算法算法n6.6 CART算法算法n6.7 决策树的剪枝决策树的

2、剪枝n6.8 决策树的优缺点决策树的优缺点第第6章章 决策树决策树6.1 概述概述n决策树决策树:从训练数据中学习得出一个树状结构的模型，从训练数据中学习得出一个树状结构的模型，由一系列由一系列节点节点和和分支分支组成。组成。n节点节点代表决策或学习过程中所考虑的特征代表决策或学习过程中所考虑的特征(或属性或属性)，而不同特征，而不同特征(或属性或属性)的值形成不同的的值形成不同的分支分支。n节点节点分为分为根节点根节点、内部节点内部节点和和叶子节点叶子节点。n根节点根节点：决策树开始的第一个节点。：决策树开始的第一个节点。n叶子节点叶子节点：是分支的终点，包含学习或决策结果。：是分支的终点，

3、包含学习或决策结果。n决策树决策树属于属于判别模型判别模型，通过把数据样本划分到某个叶子结点来确定数据通过把数据样本划分到某个叶子结点来确定数据集中样本所属的集中样本所属的类别类别。n决策树的决策过程从决策树的决策过程从根节点根节点开始，每进行一次划分，都会在树的开始，每进行一次划分，都会在树的内部节内部节点点处用某一特征处用某一特征(或属性或属性)值进行判断，根据判断结果值进行判断，根据判断结果选择输出分支，选择输出分支，直到到达直到到达叶子节点叶子节点，将叶子节点存放的类别作为决策结果。将叶子节点存放的类别作为决策结果。6.1 概述概述6.1 概述概述n决策树算法包括：决策树算法包括：nC

4、LS，ID3，C4.5，CARTn算法的发展过程算法的发展过程n1966年，年，Hunt、Marin和和Stone 提出的提出的的概念学习系统概念学习系统(Concept Learning System,CLS)就有了决策树的概念。就有了决策树的概念。n1979年年,J.R.Quinlan 提出提出ID3算法原型。算法原型。n1983年和年和1986年，年，J.R.Quinlan对对ID3 进行了总结和简化，使进行了总结和简化，使其成为决策树学习算法的典型。其成为决策树学习算法的典型。n1986年，年，Schlimmer 和和 Fisher 对对ID3进行改进，发展成进行改进，发展成 ID4算

5、算法。法。n1993年，年，Quinlan 进一步发展了进一步发展了ID3算法，改进成算法，改进成C4.5算法。算法。nID3算法的另一个分支是分类与回归树（算法的另一个分支是分类与回归树（CART）。与）。与C4.5算算法只能支持分类模型不同，法只能支持分类模型不同，CART 同时支持分类模型和回归同时支持分类模型和回归模型。模型。6.1 概述概述n6.1 概述概述n6.2 决策树学习决策树学习n6.3 特征（或属性）选择特征（或属性）选择n6.4 ID3算法算法n6.5 C4.5算法算法n6.6 CART算法算法n6.7 决策树的剪枝决策树的剪枝n6.8 决策树的优缺点决策树的优缺点第第6

6、章章 决策树决策树6.2 决策树学习决策树学习n决策树决策树模型的构建主要涉及三个方面模型的构建主要涉及三个方面:特征特征(或属性或属性)选择、递选择、递归划分、剪枝。归划分、剪枝。n特征特征(或属性或属性)选择选择 决策树生成时，需要从训练样本的多个特征决策树生成时，需要从训练样本的多个特征 (或属性或属性)中选取一个作为当前节点的划分标准。常用的特征选择中选取一个作为当前节点的划分标准。常用的特征选择指标有指标有信息增益信息增益、信息增益比信息增益比、基尼指数基尼指数等。等。n递归划分递归划分 根据每个节点选择的特征根据每个节点选择的特征 (或属性或属性)，从根节点开始，从根节点开始，递归

7、地产生子节点，直到样本不可分产生叶子节点，决策树停止递归地产生子节点，直到样本不可分产生叶子节点，决策树停止生长。生长。n剪枝剪枝 完全划分的决策树易产生过拟合问题，剪枝操作可以缩小树完全划分的决策树易产生过拟合问题，剪枝操作可以缩小树的结构规模，提高决策树的泛化能力。的结构规模，提高决策树的泛化能力。n6.1 概述概述n6.2 决策树学习决策树学习n6.3 特征（或属性）选择特征（或属性）选择n6.4 ID3算法算法n6.5 C4.5算法算法n6.6 CART算法算法n6.7 决策树的剪枝决策树的剪枝n6.8 决策树的优缺点决策树的优缺点第第6章章 决策树决策树6.3 特征（或属性）选择特征

8、（或属性）选择n决策树决策树的核心内容是在每一个非叶子节点如何选择最优的的核心内容是在每一个非叶子节点如何选择最优的特征特征(或属性或属性)对样本进行划分。对样本进行划分。n一般而言，随着划分过程不断进行，我们希望决策树的分一般而言，随着划分过程不断进行，我们希望决策树的分支节点所包含的样本支节点所包含的样本尽可能属于同一类别，即节点的尽可能属于同一类别，即节点的“纯纯度度”(purity)越来越高。越来越高。n在实际建立决策树的过程中，每次特征选择时，通常采用在实际建立决策树的过程中，每次特征选择时，通常采用信息增益信息增益、信息增益比信息增益比、基尼指数基尼指数等作为特征等作为特征(或属性

9、或属性)选选择的指标。择的指标。122111(,.,)()()log()nnniiiiiI a aaI ap ap a)(1log)()(2iiiapapaIn1948年年Shannon 提出信息论。提出信息论。n熵熵(entropy)：信息量大小的度量，即表示随机变量不确：信息量大小的度量，即表示随机变量不确定性的度量。定性的度量。n熵的熵的通俗解释通俗解释：事件：事件 的信息量的信息量 可度量为可度量为n其中其中 表示事件表示事件 发生的概率。发生的概率。n假设有假设有n个互不相容的事件个互不相容的事件 ,它们中有它们中有且仅有一个发生，则其平均的信息量（熵）可度量为且仅有一个发生，则其平

10、均的信息量（熵）可度量为n6.3.1信息增益信息增益6.3 特征（或属性）选择特征（或属性）选择n熵越大，随机变量的不确定性越大。熵越大，随机变量的不确定性越大。n当当X为为1,0分布时：分布时：n熵：熵：6.3 特征（或属性）选择特征（或属性）选择n6.3.1信息增益信息增益n设有随机变量设有随机变量(X,Y),其联合概率分布为：其联合概率分布为：n条件熵条件熵H(Y|X)：表示在己知随机变量：表示在己知随机变量X的条件下随机变量的条件下随机变量Y的不确定的不确定性，定义为性，定义为X给定条件下给定条件下Y的条件概率分布的熵对的条件概率分布的熵对X的数学期望：的数学期望：n当熵和条件熵中的概

11、率由数据估计（特别是极大似然估计）得到时，当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为所对应的熵与条件熵分别称为经验熵经验熵（empirical entropy)和和经验条件经验条件熵熵（empirical conditional entropy)6.3 特征（或属性）选择特征（或属性）选择n6.3.1信息增益信息增益n信息信息增益增益的定义的定义:特征特征A对训练数据集对训练数据集D的信息的信息增益增益 g(D,A)定义为集定义为集合合D的经验熵的经验熵H(D)与特征与特征A给定条件下给定条件下D的经验条件熵的经验条件熵H(D|A)之差，之差，即即

12、g(D,A)=H(D)-H(D|A)n信息增益信息增益(Information gain)表示得知特征表示得知特征X的信息而使得类的信息而使得类Y的信息的信息的不确定性减少的的不确定性减少的程度。程度。n般地，熵般地，熵H(Y)与条件熵与条件熵H(Y|X)之差称为之差称为互信息互信息（mutual information)。n决策树决策树学习中的学习中的信息增益信息增益等价于训练数据集中类与特征的等价于训练数据集中类与特征的互信息互信息。6.3 特征（或属性）选择特征（或属性）选择n6.3.1信息增益信息增益n设训练数据集为设训练数据集为Dn|D|表示其样本容量，即样本个数表示其样本容量，即样

13、本个数n设有设有K个类个类Ck,k=1,2，K，n|Ck|为属于类为属于类Ck的样本个数的样本个数n特征特征A有有n个不同的个不同的 取值取值a1,a2an根据特征根据特征A的取的取值将值将D划分为划分为n个子集个子集D1.。Dnn|Di|为为 Di的样本个数的样本个数n记子集记子集Di中属于类中属于类Ck的样本集合为的样本集合为Dikn|Dik|为为Dik的样本个数的样本个数n信息增益的计算信息增益的计算6.3 特征（或属性）选择特征（或属性）选择n输入：训练数据集输入：训练数据集D和特征和特征A；n输出：特征输出：特征A对训练数据集对训练数据集D的的信息增益信息增益g(D,A)（1）计算数

14、据集）计算数据集D的经验熵的经验熵H(D)（2）计算特征）计算特征A对数据集对数据集D的经验条件熵的经验条件熵H(D|A)（3）计算信息增益）计算信息增益6.3 特征（或属性）选择特征（或属性）选择n信息增益的计算信息增益的计算经验经验熵熵数量是否经验熵15960.9716.3 特征（或属性）选择特征（或属性）选择n信息增益的计算信息增益的计算年龄年龄有工作有工作有房子有房子 信用信用类别类别0 0青年青年否否否否一般一般否否1 1青年青年否否否否好好否否2 2青年青年是是否否好好是是3 3青年青年是是是是一般一般是是4 4青年青年否否否否一般一般否否5 5中年中年否否否否一般一般否否6 6中

15、年中年否否否否好好否否7 7中年中年是是是是好好是是8 8中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010老年老年否否是是非常好非常好是是1111老年老年否否是是好好是是1212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否按年龄划分年龄年龄有工作有工作有房子有房子 信用信用类别类别0 0青年青年否否否否一般一般否否1 1青年青年否否否否好好否否2 2青年青年是是否否好好是是3 3青年青年是是是是一般一般是是4 4青年青年否否否否一般一般否否5 5中年中年否否否否一般一般否否6 6中年中年否否否否好好否否7 7

16、中年中年是是是是好好是是8 8中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010老年老年否否是是非常好非常好是是1111老年老年否否是是好好是是1212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否年龄年龄数量数量是是否否经验熵经验熵青年青年5 52 23 30.97100.9710中年中年5 53 32 20.97100.9710老年老年5 54 41 10.72190.7219年龄年龄有工作有工作有房子有房子信用信用6.3 特征（或属性）选择特征（或属性）选择n信息增益的计算信息增益的计算经验条件熵经验条件熵

17、6.3 特征（或属性）选择特征（或属性）选择n信息增益的计算信息增益的计算年龄年龄有工作有工作有房子有房子信用信用年龄年龄数量数量是是否否经验熵经验熵青年青年5 52 23 30.97100.9710中年中年5 53 32 20.97100.9710老年老年5 54 41 10.72190.7219年龄年龄有工作有工作有房子有房子 信用信用类别类别0 0青年青年否否否否一般一般否否1 1青年青年否否否否好好否否2 2青年青年是是否否好好是是3 3青年青年是是是是一般一般是是4 4青年青年否否否否一般一般否否5 5中年中年否否否否一般一般否否6 6中年中年否否否否好好否否7 7中年中年是是是是好

18、好是是8 8中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010老年老年否否是是非常好非常好是是1111老年老年否否是是好好是是1212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否信息增益信息增益6.3 特征（或属性）选择特征（或属性）选择n信息增益的计算信息增益的计算年龄年龄有工作有工作有房子有房子 信用信用类别类别0 0青年青年否否否否一般一般否否1 1青年青年否否否否好好否否2 2青年青年是是否否好好是是3 3青年青年是是是是一般一般是是4 4青年青年否否否否一般一般否否5 5中年中年否否否否一般一般否否6

19、 6中年中年否否否否好好否否7 7中年中年是是是是好好是是8 8中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010老年老年否否是是非常好非常好是是1111老年老年否否是是好好是是1212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否n以以信息增益信息增益作为划分训练数据集的特征作为划分训练数据集的特征，存在偏向于选择取值较存在偏向于选择取值较多的特征的问题多的特征的问题。n使用使用信息增益比信息增益比可以对这一问题进行校正可以对这一问题进行校正。n信息增益比信息增益比的的定义定义：特征特征A对训练数据集对训练数据

20、集D的信息增益比定义为信的信息增益比定义为信息增益与训练数据集息增益与训练数据集D关于特征关于特征A的值的的值的熵熵之比之比6.3 特征（或属性）选择特征（或属性）选择n6.3.2 信息增益比信息增益比6.3 特征（或属性）选择特征（或属性）选择n6.3.2 信息增益比信息增益比年龄年龄有工作有工作有房子有房子 信用信用类别类别0 0青年青年否否否否一般一般否否1 1青年青年否否否否好好否否2 2青年青年是是否否好好是是3 3青年青年是是是是一般一般是是4 4青年青年否否否否一般一般否否5 5中年中年否否否否一般一般否否6 6中年中年否否否否好好否否7 7中年中年是是是是好好是是8 8中年中年

21、否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010老年老年否否是是非常好非常好是是1111老年老年否否是是好好是是1212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否n基尼基尼指数指数（Gini Index）用来）用来度量样本集的不度量样本集的不纯度。纯度。n基基尼指数越尼指数越小，表明小，表明样本只属于同一类的样本只属于同一类的概率越高，即概率越高，即样本样本的的“纯度纯度”越高。越高。n在分类问题在分类问题中，假设中，假设有有 个个类别，样本类别，样本属于第属于第 类的概率类的概率为为 ，则，则该概率分布的基该概率

22、分布的基尼指数尼指数定义定义为为6.3 特征（或属性）选择特征（或属性）选择n6.3.3 基尼指数基尼指数6.3 特征（或属性）选择特征（或属性）选择n6.3.3 基尼指数基尼指数年龄年龄有工作有工作有房子有房子 信用信用类别类别0 0青年青年否否否否一般一般否否1 1青年青年否否否否好好否否2 2青年青年是是否否好好是是3 3青年青年是是是是一般一般是是4 4青年青年否否否否一般一般否否5 5中年中年否否否否一般一般否否6 6中年中年否否否否好好否否7 7中年中年是是是是好好是是8 8中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010老年老年否否是是非常好非常好是

23、是1111老年老年否否是是好好是是1212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否n6.1 概述概述n6.2 决策树学习决策树学习n6.3 特征（或属性）选择特征（或属性）选择n6.4 ID3算法算法n6.5 C4.5算法算法n6.6 CART算法算法n6.7 决策树的剪枝决策树的剪枝n6.8 决策树的优缺点决策树的优缺点第第6章章 决策树决策树nID3 算法最早是算法最早是由由 J.Ross Quinlan于于1979年提出，是一种经典年提出，是一种经典的决策树学习算法的决策树学习算法。nID3 算法算法计算每个属性的计算每个属性的

24、信息增益信息增益，并选取具有，并选取具有最大信息增益最大信息增益的属性作为给定的测试属性。的属性作为给定的测试属性。6.4 ID3算法算法（1）决定）决定分类属性；分类属性；（2）对）对目前的数据表，建立一个节点目前的数据表，建立一个节点N；（3）如果）如果数据库中的数据都属于同一个类，数据库中的数据都属于同一个类，N就是树叶，在树叶上标出所属的就是树叶，在树叶上标出所属的类；类；（4）如果）如果数据表中没有其他属性可以考虑，则数据表中没有其他属性可以考虑，则N也是树叶，按照少数服从多数的原则在也是树叶，按照少数服从多数的原则在树叶上标出所属树叶上标出所属类别；类别；（5）否则）否则，根据平均

25、信息期望值，根据平均信息期望值E或或GAIN值选出一个最佳属性作为节点值选出一个最佳属性作为节点N的测试的测试属性；属性；（6）节点）节点属性选定后，对于该属性中的每个值：属性选定后，对于该属性中的每个值：n从从N生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据生成一个分支，并将数据表中与该分支有关的数据收集形成分支节点的数据表，在表中删除节点属性那一栏如果分支数据表非空，则运用以上算法从该节点表，在表中删除节点属性那一栏如果分支数据表非空，则运用以上算法从该节点建立子树。建立子树。nID3算法流程算法流程6.4 ID3算法算法nID3算法的缺点算法的缺点nID3 ID3 没

26、有剪枝策略，容易过拟合；没有剪枝策略，容易过拟合；n信息增益准则对可取值数目较多的特征有所偏好，类似信息增益准则对可取值数目较多的特征有所偏好，类似“编号编号”的特征其信息增益接近于的特征其信息增益接近于 1 1；n只能用于处理离散分布的特征只能用于处理离散分布的特征，不能处理连续数值型特，不能处理连续数值型特征征 (或属性或属性)；n没有考虑缺失值。没有考虑缺失值。6.4 ID3算法算法n6.1 概述概述n6.2 决策树学习决策树学习n6.3 特征（或属性）选择特征（或属性）选择n6.4 ID3算法算法n6.5 C4.5算法算法n6.6 CART算法算法n6.7 决策树的剪枝决策树的剪枝n6

27、.8 决策树的优缺点决策树的优缺点第第6章章 决策树决策树n针对针对ID3 算法存在的缺点，算法存在的缺点，1993年，年，J.Ross Quinlan 将将 ID3算算法改进成法改进成C4.5算法算法，给出了如下解决办法：，给出了如下解决办法：n针对针对ID3 算法容易倾向于优先选取取值种类较多的特征算法容易倾向于优先选取取值种类较多的特征(或属性或属性)的的缺点，缺点，C4.5 算法的解决办法就是用算法的解决办法就是用信息增益比信息增益比来替代信息增益作来替代信息增益作为特征为特征(或属性或属性)选择的指标。选择的指标。n针对针对ID3 决策树不能处理连续数值型特征决策树不能处理连续数值型

28、特征(或属性或属性)的缺点，的缺点，C4.5算算法的思路是先将连续数值型特征法的思路是先将连续数值型特征(或属性或属性)进行离散化处理。进行离散化处理。n针对针对ID3决策树容易过拟合的缺点，决策树容易过拟合的缺点，C4.5算法的解决办法是引入了算法的解决办法是引入了正则化系数进行初步的剪枝来缓解过拟合问题。正则化系数进行初步的剪枝来缓解过拟合问题。6.5 C4.5算法算法nC4.5算法算法虽然虽然在在 ID3 算法的基础上做了一些算法的基础上做了一些改进，但改进，但还是存在一些还是存在一些不足不足：nC4.5算法以算法以信息增益比信息增益比作为选择特征作为选择特征(或属性或属性)的的指标，每

29、次指标，每次划分子树划分子树的的过程中过程中会涉及很多对数会涉及很多对数计算，计算计算，计算过程较为过程较为复杂；复杂；nID3 决策树和决策树和 C4.5决策树采用的都是决策树采用的都是多叉树多叉树形形式，即式，即每次分叉成子树每次分叉成子树时都是时都是按照按照其所选特征其所选特征(或属性或属性)包含的所有种类数来划分包含的所有种类数来划分的；的；nID3 决策树和决策树和 C4.5决策树无法决策树无法处理一处理一个连续数值预测的回归个连续数值预测的回归问题。问题。6.5 C4.5算法算法n6.1 概述概述n6.2 决策树学习决策树学习n6.3 特征（或属性）选择特征（或属性）选择n6.4

30、ID3算法算法n6.5 C4.5算法算法n6.6 CART算法算法n6.7 决策树的剪枝决策树的剪枝n6.8 决策树的优缺点决策树的优缺点第第6章章 决策树决策树n分类回归分类回归树（树（Classification and Regression Tree，CART）是决策树是决策树的一种。的一种。nCART算法既可以用于创建算法既可以用于创建分类树分类树，也可以用于创建，也可以用于创建回归树回归树，两者在，两者在构建的过程中稍有差异。构建的过程中稍有差异。nCART分类分类树树的生成过程以的生成过程以基尼指数基尼指数最小准则来选择特征最小准则来选择特征(或属性或属性)。nCART回归回归树树

31、在选取特征（或属性）的最优划分点时，使用了在选取特征（或属性）的最优划分点时，使用了均方误均方误差差来度量来度量。nCART分类分类树树的输出的输出结果是结果是类别标签类别标签。nCART回归树回归树的输出结果不是类别，它把最终各个叶子中所有样本对的输出结果不是类别，它把最终各个叶子中所有样本对应结果值的均值或者中位数当作预测的结果输出应结果值的均值或者中位数当作预测的结果输出。6.6 CART算法算法n基尼基尼指数指数（Gini Index）用来）用来度量样本集的不度量样本集的不纯度。纯度。n基基尼指数越尼指数越小，表明小，表明样本只属于同一类的样本只属于同一类的概率越高，即概率越高，即样本

32、样本的的“纯度纯度”越高。越高。n在分类问题在分类问题中，假设中，假设有有 个个类别，样本类别，样本属于第属于第 类的概率类的概率为为 ，则，则该概率分布的基该概率分布的基尼指数尼指数定义定义为为n6.6.1 CART分类树分类树6.6 CART算法算法n6.6.1 CART分类树分类树6.6 CART算法算法6.6 CART算法算法n6.6.2 CART回归树回归树n6.1 概述概述n6.2 决策树学习决策树学习n6.3 特征（或属性）选择特征（或属性）选择n6.4 ID3算法算法n6.5 C4.5算法算法n6.6 CART算法算法n6.7 决策树的剪枝决策树的剪枝n6.8 决策树的优缺点决

33、策树的优缺点第第6章章 决策树决策树n为什么为什么要要剪枝剪枝n“剪枝剪枝”是决策树学习算法是决策树学习算法对付对付“过拟合过拟合”的主要的主要手段。手段。n可通过可通过“剪枝剪枝”来一定程度避免因来一定程度避免因决策分支过多决策分支过多，以致于把训练集自身，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过的一些特点当做所有数据都具有的一般性质而导致的过拟合。拟合。n 剪枝的基本策略剪枝的基本策略n预剪枝预剪枝-在决策树的生成过程中采取一定措施来限制某些不必在决策树的生成过程中采取一定措施来限制某些不必要的子树的要的子树的生成，通常生成，通常设置一个设置一个预定义预定义的划分

34、的划分阈值，用来阈值，用来决定每个节点决定每个节点是否应该继续是否应该继续划分。划分。n后后剪枝剪枝-先让决策树充分先让决策树充分生长，生成生长，生成一棵最大的一棵最大的树，然后树，然后根据一定的根据一定的规规则，从决策树的则，从决策树的底端开始剪掉树中不具备一般代表性的子底端开始剪掉树中不具备一般代表性的子树，使用树，使用叶子叶子节点节点取而代之，从而取而代之，从而形成一棵形成一棵规模较小规模较小的新的新树，以树，以降低模型的复杂降低模型的复杂度。度。6.7 决策树的剪枝决策树的剪枝n预剪枝的优缺点预剪枝的优缺点n优点优点n降低过拟合降低过拟合风险。风险。n避免避免生成过于复杂的生成过于复杂

35、的决策树，计算决策树，计算复杂度复杂度较低。较低。n缺点缺点n欠拟合风险欠拟合风险：有些分支的当前划分虽然不能提升泛化性能，但在其基：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪枝基于础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心贪心”本质禁止这些分支展开，带来了欠拟合本质禁止这些分支展开，带来了欠拟合风险。风险。6.7 决策树的剪枝决策树的剪枝n后剪枝的优缺点后剪枝的优缺点n优点优点n后剪枝比预剪枝保留了更多的分支，后剪枝比预剪枝保留了更多的分支，欠拟合风险小欠拟合风险小，泛化性能往泛化性能往往优于预剪枝决策树。往优于预剪枝决

36、策树。n缺点缺点n训练时间开销大训练时间开销大：后剪枝过程是在生成整个决策树之后进行的，：后剪枝过程是在生成整个决策树之后进行的，需要自底向上对所有非叶节点逐一考察。需要自底向上对所有非叶节点逐一考察。6.7 决策树的剪枝决策树的剪枝n6.1 概述概述n6.2 决策树学习决策树学习n6.3 特征（或属性）选择特征（或属性）选择n6.4 ID3算法算法n6.5 C4.5算法算法n6.6 CART算法算法n6.7 决策树的剪枝决策树的剪枝n6.8 决策树的优缺点决策树的优缺点第第6章章 决策树决策树6.8 决策树的优缺点决策树的优缺点n优点：优点：n简单直观，易于理解。简单直观，易于理解。n既可以

37、处理类别型离散值也可以处理数值型连续值。既可以处理类别型离散值也可以处理数值型连续值。n可以处理多分类和非线性分类问题。可以处理多分类和非线性分类问题。n模型训练好后进行预测时运行速度可以很快。模型训练好后进行预测时运行速度可以很快。n适合用作随机森林等集成学习模型的基学习器。适合用作随机森林等集成学习模型的基学习器。6.8 决策树的优缺点决策树的优缺点n缺点：缺点：n对噪声比较敏感，在训练集噪声较大时得到的模型容易对噪声比较敏感，在训练集噪声较大时得到的模型容易过拟合过拟合，但可以通过但可以通过剪枝剪枝和和集成学习集成学习来改善。来改善。n在处理特征关联性较强的数据时表现不太好。在处理特征关联性较强的数据时表现不太好。n寻找最优的决策树是一个非确定性多项式的问题，一般是通过寻找最优的决策树是一个非确定性多项式的问题，一般是通过启发式方法，容易陷入局部最优。可以通过启发式方法，容易陷入局部最优。可以通过集成学习集成学习之类的方之类的方法来改善。法来改善。6.8 决策树的优缺点决策树的优缺点Question?