机器学习算法与实践 课件 第7章 决策树

第七章决策树决策树（DecisionTree）是一种基本的分类与回归方法，是最早的机器学习算法之一。1979年，J.RossQuinlan提出了ID3算法原型，并于1983年和1986年对ID3算法进行了总结和简化，正式确立了决策树理论。此间的1984年，LeoBreiman,JeromeFriedman,RichardOlshen与CharlesStone共同提出了分类与回归树（ClassificationandRegressionTrees），即CART算法。1993年，Quinlan在ID3算法的基础上又提出了著名的C4.5算法。相对于其他算法，决策树算法的基本原理更加符合人的思维方式，可以产生可视化的分类或回归规则，生成的模型也具有可解释性，因此其应用十分广泛。本章主要介绍上述3种决策树算法的原理、流程及实现。17.1决策树概述决策树是一种呈树形结构的层次模型，可以是二又树也可以是多叉树。在分类问题中，树的每个非叶节点表示对一个特征的判断，每个分支代表该特征在某个值域上的输出，而每个叶节点存放一个类别。使用决策树进行决策的过程就是从根节点开始，逐个判断待分类项中相应的特征，并按照其值选择输出分支，直到到达叶节点，将叶节点存放的类别作为决策的结果。每一个样本只会被一条路径覆盖（样本的特征与路径上的特征一致或样本满足规则的条件）。27.1决策树概述如果想知道在不同天气情况下人们是否会去室外打球，就可以建立图7-1中的决策树。图中的菱形框表示对一个特征的判断，菱形框下方线段上的文字表示每个判断的所有可能的取值。图中最上方的矩形框为“根节点”，中间矩形框为“中间节点”，最下方矩形框为“叶节点”。图7-1决策树算法原理举例3称箭头的起点是终点的“父节点”，终点是起点的“子节点”。当子节点只有两个时，通常把他们称为“左子节点”和“右子节点”。7.1决策树概述决策树构造过程：1）从根节点开始，将数据集依照某个特征的取值划分为互不相交的几个子集；2）如果某个子集中的样本都属于同一个类别或某一个类别所占的百分比大于设定的阈值，则将其设置为叶节点，并将多数样本的类别作为该叶节点的类别。否则将该子集设置为中间节点，并依照某个特征的取值继续划分；3）重复步骤2）直至所有分支的末尾一行均为叶节点。

47.1决策树概述构造决策树的关键是如何进行最优特征划分，即确定非叶节点对应的特征及其判断阈值。最优特征划分的方法有很多，每种决策树之所以不同，一般都是因为最优特征选择的标准上有所差异，不同的标准导致生成不同类型的决策树。本章介绍其中三个相对而言比较基本且使用广泛的算法：ID3、C4.5和CART。三种算法是以递进的关系产生的。1）ID3算法是最基础的决策树算法，可以解决离散型数据的分类问题。2）C4.5算法在ID3算法的基础上进一步发展，可以解决混合型数据的分类问题。3）CART算法则更进一步，在分类问题的基础上，还可以解决回归问题。虽说上述算法的功能越来越强大，但其核心思想都是一致的，即算法通过不断划分数据集来生成决策树，其中每一步都选择最优的划分特征。5一般而言，随着划分过程不断进行，希望决策树的每个分枝中所包含的样本尽可能属于同一类别，即节点的“纯度”越来越高。因此，对于一个包含多个特征的数据集，应尽量选择对划分后子集的纯度提升最多的特征。信息熵可以用来度量一个系统的有（无）序程度。如果将其应用在数据集上，那么一个集合中包含样本的类别越多，则说明数据越“混乱”，信息墒越大；否则说明数据越“纯净”，信息墒越小。而我们要做的就是保证每一次划分都让划分后的信息墒降低的最多，也就是信息墒的增益最大。ID3决策树算法就是以信息增益作为决策树分支的划分依据，每次选择信息增益最大的特征进行划分。ID3算法只能处理离散数据，即可以处理像性别特征、布尔值特征等离散型特征，但没法处理特征值在某个区间内可以任意取值的特征，如身高特征、年龄特征等。7.2

ID3算法6

7.2.1信息熵和信息增益7

7.2.1信息熵和信息增益8

7.2.1信息熵和信息增益9

7.2.2

ID3算法流程10（8）对每个子集从步骤（1）开始继续执行。其中步骤（6）的“停止条件”（也可称为“预剪枝”）有多种定义方法，较为常用的是如下两种：1）若选择作为划分特征时的信息增益小于某个阈值，则停止；2）事先把数据集分为训练集与测试集，若由训练集得到的节点并不能降低测试集上的错误率，则停止。这两种停止条件通用于C4.5算法和CART算法。同时，决策树会在许多地方应用到递归的思想，上述算法中的步骤（7）正是经典的递归。7.2.2

ID3算法流程11例7-1：表7-1给出了一个哺乳动物数据集包含14个样本，样本有“饮食习性”、“胎生动物”、“水生动物”、“会飞”四个特征，“哺乳动物”为样本的类别标记，有“是”与“否”两种取值。

7.2

ID3算法表7-1

哺乳动物分类数据集12

7.2

ID3算法13

7.2

ID3算法14

7.3

C4.5算法ID3算法存在一个问题，就是偏向于多值特征。例如，如果一个特征是样本的唯一标识，则ID3会选择它作为最优划分特征。这样虽然使得划分充分纯净，但这种划分对分类几乎毫无用处，而且小数目子集在分类效果上是不如大数目子集好的（如过拟合、抗噪差等问题）。所以，为了解决这个问题，可以对会产生大量“小数目”子集的划分进行惩罚，即划分后产生的子集越小，它的信息熵要惩罚性的增大。这样虽然ID3算法中会因为很多划分后的小数量子集而产生较低的信息熵，但做惩罚值处理后，熵值就会平衡性的增大。这就是C4.5算法的改进方向，它不再使用信息增益而是改用信息增益率来对最优划分特征进行选择，克服了使用信息增益选择特征时偏向于多值特征的不足。此外，C4.5算法还可以处理连续型特征。15

7.3.1信息增益率

16

7.3.1信息增益率由此看出，划分的子集越多、子集中样本数量越少，惩罚值越大，相除后的信息增益率也就越小，依此做到了一定的平衡。由于“惩罚”了产生小样本数量子集的划分，其由于样本数量少带来信息增益抗噪性差的问题也得到一定程度的解决，这就是C4.5算法的最大好处。另外C4.5和ID3算法还有一个特点，这两个算法的根本都要计算信息增益，而信息增益的一个大前提就是要先进行划分，然后才能计算。所以，每计算一次增益也就代表进行了一次划分，而划分特征接下来就不能再用了，所以ID3和C4.5算法在分类时会不断消耗特征。17

7.3.2连续型特征处理

18

7.3.2连续型特征处理

19

7.3.2连续型特征处理

20

7.3.3C4.5算法流程

21

7.3.3C4.5算法流程

22

7.4分类与回归树分类与回归树（ClassificationAndRegressionTree，CART）算法是目前决策树算法中最为成熟的一类算法，它既可用于分类，也可用于回归。其一大特色就是假设最终生成的决策树为二叉树，即它在处理离散型和连续型特征时都会通过二分标准来划分数据。在处理分类问题时，CART算法一般会使用基尼系数作为划分优劣的度量，算法的其他流程与C4.5算法类似。在处理回归问题时，CART算法使用平方误差最小化准则（SquaredResidualsMinimization）。将数据集划分后，利用线性回归建模，如果每次划分后的子集仍然难以拟合则继续划分。这样创建出来的决策树，每个叶节点都是一个线性回归模型。这些线性回归模型反映了数据集中蕴含的模式，也称为模型树。因此，CART不仅支持整体预测，也支持局部模式的预测，并有能力从整体中找到模式或根据模式组合成一个整体。整体与模式之间的相互结合，对于预测分析非常有价值。237.4.1基尼系数

247.4.1基尼系数

257.4.2回归树

267.4.2回归树

277.4.2回归树

287.5剪枝策略从直观上来说，只要决策树足够深，划分标准足够细，它在训练集上的表现就能接近完美：但同时也容易想象，由于它可能把训练集的一些“特性”当作所有数据的“特性”来看待，它在未知的测试数据上的表现可能就会比较一般，亦即会出现过拟合的问题。模型出现过拟合问题一般是因为模型太过复杂，所以决策树解决过拟合的方法是采取适当的“剪枝”。297.5剪枝策略剪枝通常分为两类：“预剪枝”和“后剪枝”，其中“预剪枝”的概念在前文中已有使用，彼时采取的说法是“停止条件”，如树的深度超出阈值、当前节点的样本数量小于阈值、信息增益小于阈值等等。但是选取适当的阈值比较困难，过高会导致过拟合，而过低会导致欠拟合，因此需要人工反复地训练样本才能得到很好的效果。预剪枝也有优势，由于它不必生成整棵决策树，且算法简单、效率高，适合大规模问题的粗略估计。而“后剪枝”是指在完全生成的决策树上，剪掉树中不具备一般代表性的子树，使用叶节点取而代之，进而形成一棵规模较小的新树。换句话说，后剪枝是从全局出发，通过某种标准对一些节点进行局部剪枝，这样就能减少决策树中节点的数目，从而有效地降低模型复杂度。307.5剪枝策略问题的关键在于如何定出局部剪枝的标准。通常来说有两种做法：1）应用交叉验证的思想，若局部剪枝能够使得模型在测试集上的错误率降低，则进行局部剪枝（预剪枝中也可应用类似的思想）；2）应用正则化的思想，综合考虑不确定性和模型复杂度来定出一个新的损失函数（此前的损失函数只考虑了误差），用该损失函数作为一个节点是否进行局部剪枝的标准。第二种做法又涉及另一个关键问题：如何定量分析决策树中一个节点的复杂度？一个直观且合理的方法是：直接使用该节点下属叶节点的个数作为复杂度，这种方法称为代价复杂度剪枝法（CostComplexityPruning）。317.5剪枝策略

327.5剪枝策略

33图7-1决策树算法原理举例

7.5.1单一因子策略

34

7.5.1单一因子策略

357.5.2最优因子策略

367.5.2最优因子策略

377.5.2最优因子策略

38

7.6

本章小结本章主要介绍了决策树算法中的ID3算法、C4.5算法以及CAR