机器学习--决策树二（预剪枝和后剪枝）

article/2025/9/16 0:23:39

一、什么是决策树的剪枝

对比日常生活中，环卫工人在大街上给生长茂密的树进行枝叶的修剪。在机器学习的决策树算法中，有对应的剪枝算法。将比较复杂的决策树，化简为较为简单的版本，并且不损失算法的性能。

二、为什么要剪枝

剪枝是决策树算法应对过拟合的一种策略，因为在学习过程中，决策树根据训练样本进行拟合，生成了针对于训练数据集精确性极高的模型。但是训练数据集，不可避免是一种有偏的数据。所以我们为了提高决策树的泛化性能，采取了剪枝的策略。使得决策树不那么对于训练数据精确分类，从而适应任何数据。

三、剪枝的基本策略

剪枝的策略可以分为预剪枝和后剪枝两种。

预剪枝：对每个结点划分前先进行估计，若当前结点的划分不能带来决策树的泛化性能的提升，则停止划分，并标记为叶结点。

后剪枝：现从训练集生成一棵完整的决策树，然后自底向上对非叶子结点进行考察，若该结点对应的子树用叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。

四、预剪枝和后剪枝的优缺点

        1、预剪枝

            优点：思想简单，算法高效，可以降低过拟合风险，减少训练时间。

            缺点：可能存在欠拟合的风险。

         2、后剪枝

            优点：欠拟合风险小，泛化能力优于预剪枝。

            缺点：相较于预剪枝，训练开销大。

五、奥卡姆剃刀定律

奥卡姆剃刀是一种思想，在效果相同，性能一致的情况下，模型越简单越好。在简直过程中，若复杂的决策树和简答的决策树的性能相同则优先选择结构简单的决策树。

六、预剪枝和后剪枝的具体实现

1.数据准备

数据依然采用的是集美大学计算机工程学院acm比赛校选的数据，其中每列的属性分别是成绩、用时、年级、奖项。并对其离散化。

 其中将成绩、用时、年级分为4个等级，数字越大，分别代表成绩越高，用时越长，年级越高。奖项分为3个等级，1等奖，2等奖，3等奖。

2.划分数据集

与以往不同的是，这次我们将数据集分为两部分，一部分是大于最优特征的特征值的，一部分是小于目标特征的特征值的。

#按照给定区间划分数据集
def splitDataSet_bydata_font(dataSet,axis,value):# 待划分的数据集 划分数据集的特征 比较的特征值retDataSet_font=[]if isinstance(dataSet,list) ==False:  #判断dataSet是不是列表dataSet=dataSet.tolist() #转化列表for featVec in dataSet:#遍历每一行if featVec[axis] <=value: reducedFeatVec=featVec[:axis]reducedFeatVec.extend(featVec[axis:])#放列表中的元素retDataSet_font.append(reducedFeatVec)#把整个列表放入return retDataSet_font#按照给定特征区间划分数据集
def splitDataSet_bydata_back(dataSet,axis,value):# 待划分的数据集 划分数据集的特征 比较的特征值retDataSet_back=[]if isinstance(dataSet,list) ==False:dataSet=dataSet.tolist()for featVec in dataSet:#遍历每一行if featVec[axis] >value: reducedFeatVec=featVec[:axis]reducedFeatVec.extend(featVec[axis:])#放列表中的元素retDataSet_back.append(reducedFeatVec)#把整个列表放入return retDataSet_back

3.判断最优值

通过计算各特征的信息增益，将信息增益最大的特征及最优的特征值当作划分的标准。

 

#判断最优值
def chooseBestData(dataset):num=len(dataset[0])-1 #除掉类别baseEnt=calcShannonEnt(dataset)#信息熵print("原本的信息熵",baseEnt)bestGain=0.0 bestFeature=-1bestdata=0for i in range(num):#0 1 2#创建唯一的分类标签列表featlist=[example[i] for example in dataset]#取该行数据的第“ i ”位元素for value in featlist:newEnt=0.0#计算每种划分方式的信息熵subDataSet_font=splitDataSet_bydata_font(dataset,i,value)subDataSet_back=splitDataSet_bydata_back(dataset,i,value)prob_font=len(subDataSet_font)/float(len(dataset))#计算比例prob_back=len(subDataSet_back)/float(len(dataset))newEnt=prob_font*calcShannonEnt(subDataSet_font)+prob_back*calcShannonEnt(subDataSet_back)#计算信息增益inforGain=baseEnt-newEnt#计算最好的信息熵if (inforGain>bestGain):print("当前信息熵增益为:",inforGain,"当前最优特征为",i,"划分值为:",value)bestGain=inforGainbestFeature=ibestdata=valuereturn bestFeature,bestdata

 上面的输出结果是第一次划分的所显示的结果。我们发现最佳的特征是成绩，最好的划分值是1。

4. 投票决策

 在构建决策树，可能会出现这一种情况，如果数据集已经处理了所有的属性，但是类标签依然不是唯一的。在这种情况下，我们通常会采用多数表决的方法决定叶子节点的分类。

#投票分类
def majorityCnt(classList):classCount={}for vote in classList:if vote not in classCount.keys():classCount[vote]=0classCount[vote]+=1sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)print(sortedClassCount)return sortedClassCount[0][0] #返回出现次数最多的分类

5.创建树

创建出还未进行剪枝的树进行观察

def createTree(dataSet,labels):#类别完全相同则停止划分classList=[example[-1] for example in dataSet]if classList.count(classList[0])==len(classList):#print("发生了类别完全相同",classList[0])return classList[0]#遍历完所有特征时返回出现次数最多的类别if len(dataSet[0])==1:return majorityCnt(classList)bestFeat,bestData=chooseBestData(dataSet)bestFeatLabel=labels[bestFeat]myTree={bestFeatLabel:{}}#分支的多少和循环次数有关listJudge=["<="+str(bestData),">="+str(bestData)]subLabels=labels[:] #复制一份print(bestFeat,bestData)newDataSet_font=splitDataSet_bydata_font(dataSet,bestFeat,bestData)newDataSet_back=splitDataSet_bydata_back(dataSet,bestFeat,bestData)print(newDataSet_font)if(newDataSet_font!=[] and bestFeat!=-1):myTree[bestFeatLabel][listJudge[0]]=createTree(newDataSet_font,subLabels)if(newDataSet_back!=[] and bestFeat!=-1):myTree[bestFeatLabel][listJudge[1]]=createTree(newDataSet_back,subLabels)return myTree

将树的结构可视化的代码与上次的博客相同，这里就不列出了。树可视化为

6.进行预减枝

预减枝有多种方法，我在本文中采用的是限定树的深度进行预剪枝。

def createTree(dataSet,labels,depth):classList=[example[-1] for example in dataSet]#达到指定深度停止划分if depth==0:return majorityCnt(classList)#类别完全相同则停止划分if classList.count(classList[0])==len(classList):return classList[0]#遍历完所有特征时返回出现次数最多的类别if len(dataSet[0])==1:return majorityCnt(classList)bestFeat,bestData=chooseBestData(dataSet)bestFeatLabel=labels[bestFeat]myTree={bestFeatLabel:{}}#分支的多少和循环次数有关listJudge=["<="+str(bestData),">"+str(bestData)]subLabels=labels[:] #复制一份print(bestFeat,bestData)newDataSet_font=splitDataSet_bydata_font(dataSet,bestFeat,bestData)newDataSet_back=splitDataSet_bydata_back(dataSet,bestFeat,bestData)print(newDataSet_font)if(newDataSet_font!=[] and bestFeat!=-1):newDepth=depth-1myTree[bestFeatLabel][listJudge[0]]=createTree(newDataSet_font,subLabels,newDepth)if(newDataSet_back!=[] and bestFeat!=-1):newDepth=depth-1myTree[bestFeatLabel][listJudge[1]]=createTree(newDataSet_back,subLabels,newDepth)return myTreeif __name__ == '__main__':mytree=createTree(data,labels,3)createPlot(mytree)

效果如下

 

我们发现，将深度设置为3时，年级的分类就被剪枝去掉了。存在欠拟合的风险。

7.错误记录

（1）报错： 

AttributeError: 'dict' object has no attribute 'iteritems'

         原因：

python3中已经没有 “iteritems” 这个属性了，现在属性是：“ items ” 。

        解决办法：

将代码中的iteritems 修改为：items

 


http://chatgpt.dhexx.cn/article/UYxkSWF9.shtml

相关文章

关于剪枝对象的分类（weights剪枝、神经元剪枝、filters剪枝、layers剪枝、channel剪枝、对channel分组剪枝、Stripe剪枝）

关于剪枝对象的分类（weights剪枝、神经元剪枝、filters剪枝、layers剪枝、channel剪枝、对channel分组剪枝、Stripe剪枝）

文章目录 剪枝对象分析&#xff1a;1.weights剪枝&#xff1a;2.神经元剪枝&#xff1a;3.Filters剪枝&#xff1a;4.通道剪枝5.Group-wise剪枝6.Stripe剪枝 剪枝对象分析&#xff1a; 剪枝分为结构化剪枝和非结构化剪枝&#xff0c;细化可分为weights剪枝、神经元剪枝、filte…
阅读更多...
决策树——剪枝处理

决策树——剪枝处理

剪枝处理 1&#xff1a;剪枝处理的原因 “剪枝”是决策树学习算法对付“过拟合”的主要手段&#xff0c;因此&#xff0c;可通过“剪枝”来一定程度避免因决策分支过多&#xff0c;以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过拟合 2&#xff1a;剪…
阅读更多...
【ML】决策树--剪枝处理（预剪枝、后剪枝）

【ML】决策树--剪枝处理（预剪枝、后剪枝）

1. 剪枝&#xff08;pruning&#xff09;处理 首先&#xff0c;我们先说一下剪枝的目的——防止“过拟合”。 在决策树的学习过程中&#xff0c;为了保证正确性&#xff0c;会不断的进行划分&#xff0c;这样可能会导致对于训练样本能够达到一个很好的准确性&#xff0c;但是…
阅读更多...
深度学习剪枝

深度学习剪枝

一般来说&#xff0c;神经网络层数越深、参数越多&#xff0c;所得出的结果就越精细。但与此同时&#xff0c;问题也来了&#xff1a;越精细&#xff0c;意味着所消耗的计算资源也就越多。这个问题怎么破&#xff1f;这就要靠剪枝技术了。言下之意&#xff0c;把那些对输出结果…
阅读更多...
决策树后剪枝算法（一）代价复杂度剪枝CPP

决策树后剪枝算法（一）代价复杂度剪枝CPP

​  ​​ ​决策树后剪枝算法&#xff08;一&#xff09;代价复杂度剪枝CPP  ​​ ​决策树后剪枝算法&#xff08;二&#xff09;错误率降低剪枝REP  ​​ ​决策树后剪枝算法&#xff08;三&#xff09;悲观错误剪枝PEP  ​​ ​决策树后剪枝算法&#xff08;四&…
阅读更多...
机器学习-预剪枝和后剪枝

机器学习-预剪枝和后剪枝

一棵完全生长的决策树会面临一个很严重的问题&#xff0c;即过拟合。当模型过拟合进行预测时&#xff0c;在测试集上的效果将会很差。因此我们需要对决策树进行剪枝&#xff0c; 剪掉一些枝叶&#xff0c;提升模型的泛化能力。 决策树的剪枝通常有两种方法&#xff0c;预剪枝&a…
阅读更多...
【机器学习】Python实现决策树的预剪枝与后剪枝

【机器学习】Python实现决策树的预剪枝与后剪枝

决策树是一种用于分类和回归任务的非参数监督学习算法。它是一种分层树形结构&#xff0c;由根节点、分支、内部节点和叶节点组成。 从上图中可以看出&#xff0c;决策树从根节点开始&#xff0c;根节点没有任何传入分支。然后&#xff0c;根节点的传出分支为内部节点&#xff…
阅读更多...
决策树的预剪枝与后剪枝

决策树的预剪枝与后剪枝

前言&#xff1a; 本次讲解参考的仍是周志华的《机器学习》&#xff0c;采用的是书中的样例&#xff0c;按照我个人的理解对其进行了详细解释&#xff0c;希望大家能看得懂。 1、数据集 其中{1,2,3,6,7,10,14,15,16,17}为测试集&#xff0c;{4,5,8,9,11,12,13}为训练集。 2、…
阅读更多...
YOLOv5剪枝✂️ | 模型剪枝理论篇

YOLOv5剪枝✂️ | 模型剪枝理论篇

文章目录 1. 前言2. 摘要精读3. 背景4. 本文提出的解决方式5. 通道层次稀疏性的优势6. 挑战7. 缩放因素和稀疏性惩罚8. 利用BN图层中的缩放因子9. 通道剪枝和微调10. 多通道方案11. 处理跨层连接和预激活结构12. 实验结果12.1 CIFAR-10数据集剪枝效果12.2 CIFAR-100数据集剪枝效…
阅读更多...
决策树及决策树生成与剪枝

决策树及决策树生成与剪枝

文章目录 1. 决策树学习2. 最优划分属性的选择2.1 信息增益 - ID32.1.1 什么是信息增益2.1.2 ID3 树中最优划分属性计算举例 2.2 信息增益率 - C4.52.3 基尼指数 - CART 3. 决策树剪枝3.1 决策树的损失函数3.2 如何进行决策树剪枝3.2.1 预剪枝3.2.2 后剪枝3.3.3 两种剪枝策略对…
阅读更多...
剪枝

剪枝

将复杂的决策树进行简化的过程称为剪枝&#xff0c;它的目的是去掉一些节点&#xff0c;包括叶节点和中间节点。 剪枝常用方法&#xff1a;预剪枝与后剪枝两种。 预剪枝&#xff1a;在构建决策树的过程中&#xff0c;提前终止决策树生长&#xff0c;从而避免过多的节点产生。该…
阅读更多...
（剪枝）剪枝的理论

（剪枝）剪枝的理论

剪枝参考视频 本文将介绍深度学习模型压缩方法中的剪枝&#xff0c;内容从剪枝简介、剪枝步骤、结构化剪枝与非结构化剪枝、静态剪枝与动态剪枝、硬剪枝与软剪枝等五个部分展开。 剪枝简介 在介绍剪枝之前&#xff0c;首先来过参数化这个概念&#xff0c;过参数化主要是指在训…
阅读更多...
剪枝总结

剪枝总结

一、引子 剪枝&#xff0c;就是减小搜索树规模、尽早排除搜索树中不必要的分支的一种手段。 形象地看&#xff0c;就好像剪掉了搜索树的枝条&#xff0c;故被称为剪枝。 二、常见剪枝方法 1.优化搜索顺序 在一些问题中&#xff0c;搜索树的各个分支之间的顺序是不固定的 …
阅读更多...
搜索剪枝

搜索剪枝

目录 什么是剪枝 几种常见的剪枝 1.可行性剪枝 2.排除等效冗余 3.最优性剪枝 4.顺序剪枝 5.记忆化 运用实例 1.选数 2.吃奶酪 3.小木棍 什么是剪枝 剪枝&#xff1a;通过某种判断&#xff0c;避免一些不必要的遍历过程。搜索的时间复杂度通常很大&#xff0c;通过剪…
阅读更多...
【模型压缩】（二）—— 剪枝

【模型压缩】（二）—— 剪枝

一、概述 剪枝&#xff08;Pruning&#xff09;的一些概念&#xff1a; 当提及神经网络的"参数"时&#xff0c;大多数情况指的是网络的学习型参数&#xff0c;也就是权重矩阵weights和偏置bias&#xff1b;现代网络的参数量大概在百万至数十亿之间&#xff0c;因此…
阅读更多...
环形队列的基本运算算法-数据结构教程

环形队列的基本运算算法-数据结构教程

环形队列的基本概念 如图&#xff0c;其实它就是一个队列&#xff0c;就是有点难理解而已&#xff0c;它避免了普通队列的缺点&#xff0c;一样有队列头&#xff0c;队列尾&#xff0c;一样是先进先出的原则。我们采用顺时针的方式来对队列进行排序。 队列头(front) :允许进行删…
阅读更多...
一道亚马逊算法面试题的情景分析

一道亚马逊算法面试题的情景分析

阅读博客的朋友可以观看视频&#xff1a; http://study.163.com/course/courseMain.htm?courseId1002942008 我们聚焦于一道亚马逊的算法面试题&#xff0c;通过分析该题&#xff0c;复盘它的解题情景&#xff0c;我们可以初步体会到算法面试的应对步骤&#xff0c;并从中窥…
阅读更多...
LeetCode刷题笔记 标准模板库巧解算法题 优先队列

LeetCode刷题笔记 标准模板库巧解算法题 优先队列

优先队列简介 ​ 优先队列&#xff08;priority queue&#xff09;可以在 O(1) 时间内获得最大值&#xff0c;并且可以在 O(log n) 时间内取出最大值或插入任意值。 ​ 优先队列常常用堆&#xff08;heap&#xff09;来实现。堆是一个完全二叉树&#xff0c;其每个节点的值总…
阅读更多...
Python数据结构与算法（3.4）——队列相关应用与习题

Python数据结构与算法（3.4）——队列相关应用与习题

Python数据结构与算法（3.4）——队列相关应用与习题 0. 学习目标1. 使用两个栈实现一个队列2. 使用两个队列实现一个栈3. 栈中元素连续性判断4. 重新排列队列中元素顺序5. 反转队列中前 m 个元素的顺序相关链接0. 学习目标 我们已经学习了队列的相关概念以及其实现，同时也了…
阅读更多...
第十七章 优先队列优化Dijkstra算法

第十七章 优先队列优化Dijkstra算法

第十七章 优先队列优化Dijkstra算法 一、普通dijkstra算法的缺陷1、选出最小距离的过程&#xff1a;2、松弛所有点的过程&#xff1a; 二、如何优化1、代码模板&#xff08;1&#xff09;问题&#xff1a;&#xff08;2&#xff09;模板&#xff1a; 2、详细解读 三、优化分析1…
阅读更多...
推荐文章

Copyright @ 2022~2023