《机器学习Python实战》课件 14-项目7 决策树算法原理讲解

机器学习项目六|6.1项目知识准备|朴素贝叶斯分类算法实战《机器学习Python实战》

机器学习

项目7决策树与随机森林预测建模17.1.1决策树的算法原理和构造27.1.2随机森林的算法原理和构造目录CONTENTS学习目标知识目标1．理解决策树的算法原理和构造。2．掌握随机森林的算法原理和构造能力目标1．能够正确使用决策树模型。2．能熟练使用决策树和随机森林解决分类和回归问题素质目标1．培养数据分析与决策能力。2．培养科技兴国抱负017.1.1决策树的算法原理和构造决策树的算法原理和构造▪决策树算法可以被看作一个多级嵌套的选择结构，通过一系列问题的回答，逐步选择树中的路径，最终到达一个表示结论或类别的叶子节点▪典型应用：预测明天是否下雨、判断某个商品是否畅销、评估是否能申请贷款、根据成绩推荐合适的志愿等▪随机森林算法是由多棵决策树组成的集成方法，通过综合各决策树的结果来得出最终结论▪例如挑选好西瓜：先收集西瓜的相关特征数据，再使用决策树或随机森林模型进行分析，输入特征数据后，模型将输出关于西瓜好坏的判断结果本项目围绕决策树与随机森林展开，完成“算法原理→项目实训→算法详解→项目拓展”的完整学习闭环决策树的算法原理和构造▪决策树（decisiontree）是一种常用的监督学习方法，既可用于分类任务，也可用于回归任务▪它通过对样本特征进行递归划分，构建出一个类似树形结构的模型，从而实现对未知样本类别或数值的预测▪决策树通过信息熵、信息增益或基尼系数等指标选择最优特征，逐步形成具有可解释性的决策规则分类任务预测离散类别标签，如“是否适合开发”回归任务预测连续数值，如房价、销量可解释性每条路径都是一条“如果…就…”规则决策树的算法原理和构造根节点内部节点内部节点叶子节点叶子节点叶子节点叶子节点分支分支图7-1决策树的基本结构▪根节点：表示样本全集▪内部节点：对应一个特征或测试特征▪叶子节点：对应决策结果▪从根节点到每个叶子节点的路径对应一系列特征判断，其组合形成一条完整的决策规则▪决策过程：从根节点开始测试特征，按取值选择分支，直至到达叶子节点1.决策树的基本结构决策树的算法原理和构造2.决策实例：周末是否打球天气？不打球是否加班？不打球球场满员？不打球打球雨天晴天是否满员不满员图7-2生成决策树▪决策时遵循自上而下的逻辑规则▪首先找到最重要的特征进行分类▪结果不能再分→作为叶子节点▪仍能细分→选择下一个重要特征继续判断▪决策树本质上是一种简单的分类方法决策树的算法原理和构造3.决策树的构造：核心问题与流程▪核心问题：在每一步选择适当的特征对样本进行拆分▪从已知类别标签的训练样本中学习并构造决策树，是一个自上而下、分而治之的过程▪关键是选择具有决定性作用的特征作为首要决策点（根节点），需要评估每个特征并按重要性排序①计算信息熵度量数据集的不确定性→②计算信息增益划分数据集前后信息熵的差值→③评价特征重要性按信息增益排序，选择最优特征→④递归构建决策树对每个分支重复上述过程构造决策树需利用已知样本数据及其目标标签进行训练，生成模型后再对未知样本进行分类（或回归预测）决策树的算法原理和构造4.常用的决策树算法决策树算法算法描述ID3算法核心是在决策树的各级节点使用信息增益作为特征的选择标准，帮助确定生成每个节点时所应采用的合适特征C4.5算法相对ID3的重要改进：使用信息增益率选择节点特征；ID3只适用于离散特征，C4.5既能处理离散特征，也能处理连续特征CART算法十分有效的非参数分类和回归算法，通过构建树、修剪树、评估树来构建二叉树；目标为连续变量时创建回归树，为分类变量时创建分类树注意：熵是对事件结果不确定性的度量；信息增益率是信息增益与熵的比值；二叉树每个节点最多有两棵子树，且左右子树有序决策树的算法原理和构造ID3算法实例：公交车上车人次▪根据节假日、周末、天气等特征预测公交车上车人次▪对智能调节公交车发车间隔、减少资源浪费有很大的意义▪数据集共30条记录，上车人次按阈值划分为“1”（多）和“0”（少）两类节假日周末天气上车人次101110111101……………………001000000010……………………特征值设置▪是节假日→“1”，不是→“0”▪是周末→“1”，非周末→“0”▪天气好→“1”，天气不好→“0”▪上车人次大于阈值→“1”，小于阈值→“0”表7-2处理后的公交车上车人次数据决策树的算法原理和构造实施步骤（1）：计算总的信息熵▪数据集共有30条记录，上车人次为“1”的记录有16条，为“0”的记录有14条I(16,14)＝−(16/30)·log₂(16/30)−(14/30)·log₂(14/30)

≈0.997▪信息熵越大，样本集合的不确定性越高▪总信息熵接近1，说明当前数据集中“1”和“0”两类几乎各占一半，不确定性很大，亟需用特征进行划分决策树的算法原理和构造实施步骤（2）：计算每个测试特征的信息熵测试特征特征值划分（人次“1”,人次“0”）条件信息熵E天气“1”：(5,10)，I≈0.918；“0”：(11,4)，I≈0.837E(天气)=15/30×I(5,10)+15/30×I(11,4)≈0.877周末“1”：(5,3)，I≈0.954；“0”：(11,11)，I＝1E(周末)=8/30×I(5,3)+22/30×I(11,11)≈0.988节假日“1”：(7,0)，I＝0；“0”：(9,14)，I≈0.966E(节假日)=7/30×I(7,0)+23/30×I(9,14)≈0.740▪条件信息熵越小，说明用该特征划分后数据的“纯净度”提升越多▪节假日特征的条件信息熵最小（0.740），其“1”分支下上车人次全部为“1”（I＝0，完全纯净）决策树的算法原理和构造实施步骤（3）：计算信息增益，选择根节点Gain(天气)＝I−E(天气)＝0.997−0.877＝0.120Gain(周末)＝I−E(周末)＝0.997−0.988＝0.009Gain(节假日)＝I−E(节假日)＝0.997−0.740＝0.257▪节假日特征的信息增益值最大→选为根节点，其两个特征值“1”和“0”成为根节点的两个分支▪然后对每个分支继续重复步骤（1）～（3）进行节点划分，直到没有新的内部节点，最终构成一棵决策树决策树的算法原理和构造用ID3算法生成的决策树节假日上车人次1天气周末周末0101

图7-3用ID3算法生成的决策树▪根节点为信息增益最大的节假日特征▪节假日＝“1”的分支上车人次全部为“1”（7,0），直接成为叶子节点▪节假日＝“0”时继续按天气划分▪“周末”特征信息增益过小，未被选中0101决策树的算法原理和构造提取决策规则规则①若节假日特征为“1”，则上车人次为“1”规则②若节假日特征为“0”，天气为“1”，周末特征为“1”或“0”，则上车人次为“0”规则③若节假日特征为“0”，天气为“0”，周末特征为“1”或“0”，则上车人次为“1”ID3的局限→C4.5的改进▪ID3采用信息增益选特征，会偏向取值多的“高度分支特征”，但这类特征不一定最优▪ID3只能处理离散型特征，连续型特征需先离散化；C4.5改用信息增益率，可处理连续特征决策树的算法原理和构造决策树的剪枝▪构造一棵完整的树计算量大、空间复杂度高；剪枝可在保证模型性能的前提下删除不必要的分支，是使决策树停止分支的方法之一预剪枝（prepruning）▪划分前先估计：若当前节点划分不能提升泛化性能，则停止划分并标记为叶子节点▪通过规则限制树的生长（如指定最大深度为3）▪降低过拟合风险、减少建树时间，但可能带来欠拟合▪适合大规模数据集后剪枝（postpruning）▪先生成一棵完整的决策树，再自底向上考察非叶子节点▪若子树替换为叶子节点能提升泛化性能，则执行替换▪是一种全局优化方法，可充分利用训练集全部信息▪计算代价比预剪枝大；小规模数据集上优于预剪枝决策树的算法原理和构造决策树的优缺点优点▪易于理解和实现，不需要使用者了解很多背景知识▪能够直接体现数据的特点，可解释性强▪数据准备工作简单，甚至不必预处理▪能同时处理数值型和常规型特征▪在较短时间内可对大型数据源得出可行且效果良好的结果缺点▪模型稳定性较差，对训练数据中的噪声较为敏感▪容易产生过拟合▪单棵决策树泛化能力有限，预测结果可能随数据微小变化而大幅波动▪实际应用中，往往通过剪枝或集成方法（如随机森林、梯度提升树）来弥补027.1.2随机森林的算法原理和构造随机森林的算法原理和构造随机森林的算法原理▪随机森林（randomforest，RF）是指用随机方式建立的包含很多决策树的森林，其中的决策树彼此没有关联▪得到森林后，每当有新的输入样本，就让森林中的每一棵决策树分别进行判断，看哪一类被选择的可能性最大，就预测该样本为那一类▪随机森林通常以CART决策树作为基学习模型：CART既可用于分类也可用于回归，能同时处理连续型和离散型特征▪通过在样本和特征两个层面引入随机性，可进一步提升模型的泛化能力形象理解随机森林是通过集成学习的思想将多棵决策树集成的一种算法，故其基本单元是决策树，而它本质上属于机器学习的一大分支—集成学习（ensemblelearning）。集成学习通过建立几个模型并将其组合起来解决单一预测问题。它的工作原理是生成多个模型，每个模型各自独立地学习和进行预测，然后将这些预测组合成单一预测（优于任何一个单分类模型的预测）。集成学习旨在解决单个模型固有的缺陷，从而整合更多的模型，取长补短，避免单个模型的局限性。随机森林的算法原理和构造随机森林的算法原理▪随机森林是通过集成学习的思想将多棵决策树集成的算法，其基本单元是决策树，本质上属于机器学习的一大分支——集成学习（ensemblelearning）▪集成学习：生成多个模型，各自独立学习和预测，再将预测组合成优于任何单一模型的预测结果Bagging＝bootstrapaggregating（自助抽样集成）将训练集分成m个新训练集→在每个新训练集上构建一个互不相干的模型→预测时整合m个模型的结果（分类用投票，回归用均值）▪随机森林是一种特殊的Bagging：基模型固定为决策树▪关键区别：节点分裂时不在全部特征中寻找最优，而是随机抽取一部分特征，再在抽到的特征中寻找最优解▪相当于对样本和特征都进行了采样，因此可以有效避免过拟合随机森林的算法原理和构造随机森林的组成两个随机性的引入，使得随机森林具有很好的抗噪声能力，不容易陷入过拟合。01能够处理很高维度的数据，并且不用做特征选择，对数据集的适应能力强02既能处理离散型数据，也能处理连续型数据，数据集无需规范化。03

图7-4

随机森林的组成随机森林的算法原理和构造随机森林的构造步骤①用N表示训练样本个数，M表示特征数目②输入特征数目m（m应远小于M），用于确定决策树中一个节点的决策结果③从N个训练样本中以有放回抽样（bootstrap）方式取样N次形成训练集，从根节点开始递归分裂构建整棵树④每个节点先从全部特征中随机选择m个特征作为候选子集，再依据信息增益或基尼指数等指标选择最优划分⑤每个节点都按步骤④分裂，直到满足停止条件；整个过程中不剪枝，每棵树完整生长⑥按步骤①～⑤建立大量决策树，进而构成随机森林注：同一特征可以在树的不同层级被多次用于节点分裂随机森林的算法原理和构造小结决策树的原理与构造▪树状结构：根节点、内部节点、叶子节点▪自上而下、分而治之地递归