《机器学习导论-第6章决策树.ppt》由会员分享，可在线阅读，更多相关《机器学习导论-第6章决策树.ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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、择的指标。的指标。n1948年年Shannon 提出信息提出信息论论。n熵熵(entropy)：信息量大小的度量，即表示随机：信息量大小的度量，即表示随机变变量不确量不确定性的度量。定性的度量。n熵熵的的通俗解通俗解释释：事件：事件 的信息量的信息量 可度量可度量为为n其中其中 表示事件表示事件 发发生的概率。生的概率。n假假设设有有n个互不相容的事件个互不相容的事件 ,它它们们中有中有且且仅仅有一个有一个发发生，生，则则其平均的信息量（其平均的信息量（熵熵）可度量）可度量为为n6.3.1信息增益信息增益6.3 特征（或属性）选择特征（或属性）选择n熵越大，随机变量的不确定性越大。熵越大，随机
10、变量的不确定性越大。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)之之差差，即即 g(D,A)=H(D)-H(D|A)n信信息息增增益益(Information gain)表表示示得得知知特特征征X的的信信息息而而使使得得类类Y的的信
12、信息息的不确定性减少的的不确定性减少的程度。程度。n般般 地地，熵熵 H(Y)与与 条条 件件 熵熵 H(Y|X)之之 差差 称称 为为 互互 信信 息息（mutual information)。n决策决策树树学学习习中的中的信息增益信息增益等价于等价于训练训练数据集中数据集中类类与特征的与特征的互信息互信息。6.3 特征（或属性）选择特征（或属性）选择n6.3.1信息增益信息增益n设训练设训练数据集数据集为为Dn|D|表示其表示其样样本容量，即本容量，即样样本个数本个数n设设有有K个个类类Ck,k=1,2，K，n|Ck|为为属于属于类类Ck的的样样本个数本个数n特征特征A有有n个不同的个不同
13、的 取取值值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）计计算数据集算数据集D的的经验熵经验熵H(D)（2）计计算特征算特征A对对数据集数据集D的的经验经验条件条件熵熵H(D|A)（3）计计算
14、信息增益算信息增益6.3 特征（或属性）选择特征（或属性）选择n信息增益的计算信息增益的计算经验经验熵熵数量是否经验熵15960.9716.3 特征（或属性）选择特征（或属性）选择n信息增益的计算信息增益的计算年龄年龄有工作有工作有房子有房子 信用信用类别类别0 0青年青年否否否否一般一般否否1 1青年青年否否否否好好否否2 2青年青年是是否否好好是是3 3青年青年是是是是一般一般是是4 4青年青年否否否否一般一般否否5 5中年中年否否否否一般一般否否6 6中年中年否否否否好好否否7 7中年中年是是是是好好是是8 8中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010
15、老年老年否否是是非常好非常好是是1111老年老年否否是是好好是是1212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否按年龄划分年龄年龄有工作有工作有房子有房子 信用信用类别类别0 0青年青年否否否否一般一般否否1 1青年青年否否否否好好否否2 2青年青年是是否否好好是是3 3青年青年是是是是一般一般是是4 4青年青年否否否否一般一般否否5 5中年中年否否否否一般一般否否6 6中年中年否否否否好好否否7 7中年中年是是是是好好是是8 8中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010老年老年否否是是非常好非常好
16、是是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信息增益的计算信息增益的计算经验经验条件条件熵熵6.3 特征（或属性）选择特征（或属性）选择n信息增益的计算信息增益的计算年龄年龄有工作有工作有房子有房子信用信用年龄年龄数量数量是是否
17、否经验熵经验熵青年青年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中年中年是是是是好好是是8 8中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010老年老年否否是是非常好非常好是是1111老年老
18、年否否是是好好是是1212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否信息增益信息增益6.3 特征（或属性）选择特征（或属性）选择n信息增益的计算信息增益的计算年龄年龄有工作有工作有房子有房子 信用信用类别类别0 0青年青年否否否否一般一般否否1 1青年青年否否否否好好否否2 2青年青年是是否否好好是是3 3青年青年是是是是一般一般是是4 4青年青年否否否否一般一般否否5 5中年中年否否否否一般一般否否6 6中年中年否否否否好好否否7 7中年中年是是是是好好是是8 8中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1
19、010老年老年否否是是非常好非常好是是1111老年老年否否是是好好是是1212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否n以以信信息息增增益益作作为为划划分分训训练练数数据据集集的的特特征征，存存在在偏偏向向于于选选择择取取值值较较多多的特征的的特征的问题问题。n使用使用信息增益比信息增益比可以可以对这对这一一问题进问题进行校正行校正。n信信息息增增益益比比的的定定义义：特特征征A对对训训练练数数据据集集D的的信信息息增增益益比比定定义义为为信信息增益与息增益与训练训练数据集数据集D关于特征关于特征A的的值值的的熵熵之比之比6.3 特征
20、（或属性）选择特征（或属性）选择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中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010老年老年否否是是非常好非常好是是1111老年老年否否是是好好是是1
21、212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否n基尼基尼指数指数（Gini Index）用来）用来度量度量样样本集的不本集的不纯纯度。度。n基基尼尼指指数数越越小小，表表明明样样本本只只属属于于同同一一类类的的概概率率越越高高，即即样样本本的的“纯纯度度”越高。越高。n在分在分类问题类问题中，假中，假设设有有 个个类别类别，样样本本属于第属于第 类类的概率的概率为为 ，则则该该概率分布的基概率分布的基尼指数尼指数定定义义为为6.3 特征（或属性）选择特征（或属性）选择n6.3.3 基尼指数基尼指数6.3 特征（或属性）选择特征（或属性
22、）选择n6.3.3 基尼指数基尼指数年龄年龄有工作有工作有房子有房子 信用信用类别类别0 0青年青年否否否否一般一般否否1 1青年青年否否否否好好否否2 2青年青年是是否否好好是是3 3青年青年是是是是一般一般是是4 4青年青年否否否否一般一般否否5 5中年中年否否否否一般一般否否6 6中年中年否否否否好好否否7 7中年中年是是是是好好是是8 8中年中年否否是是非常好非常好是是9 9中年中年否否是是非常好非常好是是1010老年老年否否是是非常好非常好是是1111老年老年否否是是好好是是1212老年老年是是否否好好是是1313老年老年是是否否非常好非常好是是1414老年老年否否否否一般一般否否n
23、6.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 算算法法计算算每每个个属属性性的的信信息息增增益益，并并选取取具具有有最最大大信信息息增增益益的属性作的属性作为给定的定的测试属性。属性。6.4 ID3算法算法（1）决定）决定分分类
24、类属性；属性；（2）对对目前的数据表，建立一个目前的数据表，建立一个节节点点N；（3）如果）如果数据数据库库中的数据都属于同一个中的数据都属于同一个类类，N就是就是树树叶，在叶，在树树叶上叶上标标出所属的出所属的类类；（4）如如果果数数据据表表中中没没有有其其他他属属性性可可以以考考虑虑，则则N也也是是树树叶叶，按按照照少少数数服服从从多多数数的的原原则则在在树树叶上叶上标标出所属出所属类别类别；（5）否）否则则，根据平均信息期望，根据平均信息期望值值E或或GAIN值选值选出一个最佳属性作出一个最佳属性作为节为节点点N的的测试测试属性；属性；（6）节节点点属性属性选选定后，定后，对对于于该该属
25、性中的每个属性中的每个值值：n从从N生生成成一一个个分分支支，并并将将数数据据表表中中与与该该分分支支有有关关的的数数据据收收集集形形成成分分支支节节点点的的数数据据表表，在在表表中中删删除除节节点点属属性性那那一一栏栏如如果果分分支支数数据据表表非非空空，则则运运用用以以上上算算法法从从该该节节点点建立子建立子树树。nID3算法流程算法流程6.4 ID3算法算法nID3算法的缺点算法的缺点nID3 ID3 没有剪枝策略，容易过拟合；没有剪枝策略，容易过拟合；n信息增益准则对可取值数目较多的特征有所偏好，类似信息增益准则对可取值数目较多的特征有所偏好，类似“编号编号”的特征其信息增益接近于的特
26、征其信息增益接近于 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.8 决策树的优缺点决策树的优缺点第第6章章 决策树决策树n针对针对ID3 算法存在的缺点，算法存在的缺点，1993年，年，J.Ross Quinlan 将将 ID3算法算法改改进进成成
27、C4.5算法算法，给给出了如下解决出了如下解决办办法：法：n针针对对ID3 算算法法容容易易倾倾向向于于优优先先选选取取取取值值种种类类较较多多的的特特征征(或或属属性性)的的缺缺点点，C4.5 算算法法的的解解决决办办法法就就是是用用信信息息增增益益比比来来替替代代信信息息增增益益作作为为特征特征(或属性或属性)选择选择的指的指标标。n针针对对ID3 决决策策树树不不能能处处理理连连续续数数值值型型特特征征(或或属属性性)的的缺缺点点，C4.5算算法的思路是先将法的思路是先将连续连续数数值值型特征型特征(或属性或属性)进进行离散化行离散化处处理。理。n针针对对ID3决决策策树树容容易易过过拟
28、拟合合的的缺缺点点，C4.5算算法法的的解解决决办办法法是是引引入入了了正正则则化系数化系数进进行初步的剪枝来行初步的剪枝来缓缓解解过拟过拟合合问题问题。6.5 C4.5算法算法nC4.5算法算法虽然虽然在在 ID3 算法的基础上做了一些算法的基础上做了一些改进，但改进，但还是存在一些还是存在一些不足不足：nC4.5算算法法以以信信息息增增益益比比作作为为选选择择特特征征(或或属属性性)的的指指标标，每每次次划划分分子子树树的的过过程中程中会涉及很多会涉及很多对对数数计计算，算，计计算算过过程程较为较为复复杂杂；nID3 决决策策树树和和 C4.5决决策策树树采采用用的的都都是是多多叉叉树树形
29、形式式，即即每每次次分分叉叉成成子子树树时时都是都是按照按照其所其所选选特征特征(或属性或属性)包含的所有种包含的所有种类类数来划分数来划分的；的；nID3 决决策策树树和和 C4.5决决策策树树无无法法处处理理一一个个连连续续数数值值预预测测的的回回归归问问题题。6.5 C4.5算法算法n6.1 概述概述n6.2 决策树学习决策树学习n6.3 特征（或属性）选择特征（或属性）选择n6.4 ID3算法算法n6.5 C4.5算法算法n6.6 CART算法算法n6.7 决策树的剪枝决策树的剪枝n6.8 决策树的优缺点决策树的优缺点第第6章章 决策树决策树n分分类类回回归归树树（Classifica
30、tion and Regression Tree，CART）是决策是决策树树的一种。的一种。nCART算法既可以用于算法既可以用于创创建建分分类树类树，也可以用于，也可以用于创创建建回回归树归树，两者在，两者在构建的构建的过过程中稍有差异。程中稍有差异。nCART分分类类树树的生成的生成过过程以程以基尼指数基尼指数最小准最小准则则来来选择选择特征特征(或属性或属性)。nCART回回归归树树在在选选取特征（或属性）的最取特征（或属性）的最优优划分点划分点时时，使用了，使用了均方均方误误差差来度量来度量。nCART分分类类树树的的输输出出结结果是果是类别标签类别标签。nCART回回归树归树的的输输
31、出出结结果不是果不是类别类别，它把最，它把最终终各个叶子中所有各个叶子中所有样样本本对对应结应结果果值值的均的均值值或者中位数当作或者中位数当作预测预测的的结结果果输输出出。6.6 CART算法算法n基尼基尼指数指数（Gini Index）用来）用来度量度量样样本集的不本集的不纯纯度。度。n基基尼尼指指数数越越小小，表表明明样样本本只只属属于于同同一一类类的的概概率率越越高高，即即样样本本的的“纯纯度度”越高。越高。n在分在分类问题类问题中，假中，假设设有有 个个类别类别，样样本本属于第属于第 类类的概率的概率为为 ，则则该该概率分布的基概率分布的基尼指数尼指数定定义义为为n6.6.1 CAR
32、T分分类树类树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 决策树的优缺点决策树的优缺点第第6章章 决策树决策树n为什么为什么要要剪枝剪枝n“剪枝剪枝”是决策树学习算法是决策树学习算法对付对付“过拟合过拟合”的主要的主要手段。手段。n可可通通过过“剪剪枝枝”来来一一定定程程度度避避免免因因决
33、决策策分分支支过过多多，以以致致于于把把训训练练集集自自身身的一些特点当做所有数据都具有的一般性质而导致的过的一些特点当做所有数据都具有的一般性质而导致的过拟合。拟合。n 剪枝的基本策略剪枝的基本策略n预预剪剪枝枝-在在决决策策树树的的生生成成过过程程中中采采取取一一定定措措施施来来限限制制某某些些不不必必要要的的子子树树的的生生成成，通通常常设设置置一一个个预预定定义义的的划划分分阈阈值值，用用来来决决定定每每个个节节点点是否应该继续是否应该继续划分。划分。n后后剪剪枝枝-先先让让决决策策树树充充分分生生长长，生生成成一一棵棵最最大大的的树树，然然后后根根据据一一定定的的规规则则，从从决决策
34、策树树的的底底端端开开始始剪剪掉掉树树中中不不具具备备一一般般代代表表性性的的子子树树，使使用用叶叶子子节节点点取而代之，从而取而代之，从而形成一棵形成一棵规模较小规模较小的新的新树，以树，以降低模型的复杂降低模型的复杂度。度。6.7 决策树的剪枝决策树的剪枝n预剪枝的优缺点预剪枝的优缺点n优点优点n降低过拟合降低过拟合风险。风险。n避免避免生成过于复杂的生成过于复杂的决策树，计算决策树，计算复杂度复杂度较低。较低。n缺点缺点n欠拟合风险欠拟合风险：有些分支的当前划分虽然不能提升泛化性能，但在其基：有些分支的当前划分虽然不能提升泛化性能，但在其基础上进行的后续划分却有可能导致性能显著提高。预剪
35、枝基于础上进行的后续划分却有可能导致性能显著提高。预剪枝基于“贪心贪心”本质禁止这些分支展开，带来了欠拟合本质禁止这些分支展开，带来了欠拟合风险。风险。6.7 决策树的剪枝决策树的剪枝n后剪枝的优缺点后剪枝的优缺点n优点优点n后后剪剪枝枝比比预预剪剪枝枝保保留留了了更更多多的的分分支支，欠欠拟拟合合风风险险小小，泛泛化化性性能能往往往往优于预剪枝决策树。优于预剪枝决策树。n缺点缺点n训训练练时时间间开开销销大大：后后剪剪枝枝过过程程是是在在生生成成整整个个决决策策树树之之后后进进行行的的，需需要自底向上对所有非叶节点逐一考察。要自底向上对所有非叶节点逐一考察。6.7 决策树的剪枝决策树的剪枝n
36、6.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既可以处理类别型离散值也可以处理数值型连续值。既可以处理类别型离散值也可以处理数值型连续值。n可以处理多分类和非线性分类问题。可以处理多分类和非线性分类问题。n模型训练好后进行预测时运行速度可以很快。模型训练好后进行预测时运行速度可以很快。n
37、适合用作随机森林等集成学习模型的基学习器。适合用作随机森林等集成学习模型的基学习器。6.8 决策树的优缺点决策树的优缺点n缺点：缺点：n对对噪噪声声比比较较敏敏感感，在在训训练练集集噪噪声声较较大大时时得得到到的的模模型型容容易易过过拟拟合合，但可以通过但可以通过剪枝剪枝和和集成学习集成学习来改善。来改善。n在处理特征关联性较强的数据时表现不太好。在处理特征关联性较强的数据时表现不太好。n寻寻找找最最优优的的决决策策树树是是一一个个非非确确定定性性多多项项式式的的问问题题，一一般般是是通通过过启启发发式式方方法法，容容易易陷陷入入局局部部最最优优。可可以以通通过过集集成成学学习习之之类类的的方方法来改善。法来改善。6.8 决策树的优缺点决策树的优缺点Question?