MLA Review之二： 决策树

2024-05-09 07:58
文章标签 之二 决策树 review mla

本文主要是介绍MLA Review之二： 决策树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

分类决策树是一种描述对实例进行分类的属性结构，决策树由内部节点和叶节点，内部节点表示一个特征或者属性，叶节点表示一个类。

 

Part 1 ：决策树生成

用决策树分类其实是一个if-then的过程，根据一个特征值的取值将原始的数据进行分类，比如，银行往往会根据个人情况和信用进行处理是否借贷，其评比条件如下图：



 那么可能其中的一个决策树就会如下：



 分类树也就是这样。

 

 

那么这个时候问题就来了，每次进行选取一个特征，如上面根节点是选取年龄还是选择有房子呢，这是第一个问题。

 

主要有两种算法进行计算，第一个是信息增益，另外一个是信息增益比，下面会来介绍一下这两种方式

 

1，信息增益

信息增益不用多介绍，在分类问题上被用了无数次，主要就是用来选取特征值，其本质就是尽量是各个类尽量平均，用在分类树上其实实质是为了减少分类树的不均衡，这一点其实在学习数据结构的时候我们都知道有个叫AVL树和红黑树，称之为平衡树，总体要求是使树的树枝高度不相差太多

 

信息增益计算公式：



 

 2，信息增益比

信息增益比很容易计算，和信息增益差不多，只不过是信息增益与H(D)的比：



 
与特征选取的两种算法对应，决策树的生成也有两种算法：ID3和C4.5

ID3分类使用信息增益方法，C4.5分类使用信息增益比算法。

 

下面根据MLA 一书中的决策树一章使用Python语言实现一下决策树，书中使用的决策树算法是ID3,也就是使用信息增益方法进行分类选取。

 

原始问题的数据集如下：

Python代码   收藏代码
  1. dataset=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]  
  2. labels=['no surfacing','flippers']  

 dataset每个项里面的最后一个数据是标签，也就是分类结果，前面两个是分类依据，第一个是代表是否有surfacing，第二个代表是否有flipper，现在需要根据这个数据集构建一颗决策树。

 

代码如下：

Python代码   收藏代码
  1. # -*- coding: UTF8 -*-  
  2. """ 
  3. author:luchi 
  4. date:16/2/17 
  5. theme:decision tree 
  6. desc:决策树的构建,使用ID3方法构建决策树 
  7. """  
  8.   
  9. from math import  log  
  10. import operator  
  11. #计算熵值  
  12. def computeEnt(dataset):  
  13.     m=len(dataset)  
  14.     labels=[]  
  15.     for i in range(m):  
  16.         labels.append(dataset[i][-1])  
  17.     labels=set(labels)  
  18.     countLabel={}  
  19.     for i in range(m):  
  20.         clabel=dataset[i][-1]  
  21.         if not countLabel.has_key(clabel):  
  22.             countLabel[clabel]=1  
  23.         else:  
  24.             t=countLabel[clabel]+1  
  25.             countLabel[clabel]=t  
  26.     retEnt=0.0  
  27.     for label in labels:  
  28.         prob=float(countLabel[label])/m  
  29.         retEnt-=prob*log(prob,2)  
  30.     return retEnt  
  31.   
  32. #产生数据集  
  33. def createDataset():  
  34.     dataset=[[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]  
  35.     labels=['no surfacing','flippers']  
  36.     return dataset,labels  
  37.   
  38.   
  39.   
  40.   
  41. """ 
  42. 根据标签分割数据集 
  43. params: 
  44.     dataset:原始数据集 
  45. """  
  46. def splitDataset(dataset,axis,value):  
  47.   
  48.     m=len(dataset)  
  49.     retDataset=[]  
  50.     for i in range(m):  
  51.         if dataset[i][axis]==value:  
  52.             l=dataset[i][:axis]  
  53.             l.extend(dataset[i][axis+1:])  
  54.             retDataset.append(l)  
  55.     return retDataset  
  56.   
  57.   
  58.   
  59.   
  60.   
  61. """ 
  62. 获取最好的分组条件 
  63. """  
  64. def getBestSlpit(dataset,labels):  
  65.     m=len(dataset[0])-1  
  66.     bestEnt=0.0  
  67.     bestAxis=0  
  68.     ent=computeEnt(dataset)  
  69.     length=len(dataset)  
  70.     for i in range(m):  
  71.         l=[example[i] for example in dataset] #计算每一个特征值的数组  
  72.         l=set(l) #不重复  
  73.         infoEnt=0.0  
  74.         for feature in l:  
  75.             tempSet=splitDataset(dataset,i,feature)  
  76.             size=len(tempSet)  
  77.             prob=float(size)/length  
  78.             infoEnt+=prob*computeEnt(tempSet)  
  79.         infoEnt=ent-infoEnt  
  80.         if(infoEnt>bestEnt):  
  81.             bestEnt=infoEnt  
  82.             bestAxis=i  
  83.     return bestAxis  
  84.   
  85. """ 
  86. 在选出了最好的分组之后,在分组终止之后,就需要判断其类别 
  87. 采用的是最大投票的方法,也就是哪个类别多就这个分组为其类别 
  88. """  
  89. def chooseClassLabel(dataset):  
  90.         labels=[example[-1] for example in dataset]  
  91.         labels=set(labels)  
  92.         labelCounts={}  
  93.         for i in range(len(dataset)):  
  94.             l=dataset[i][-1]  
  95.             if not labelCounts.has_key(l):  
  96.                 labelCounts[l]=1  
  97.             else:  
  98.                 m=labelCounts[l]+1  
  99.                 labelCounts[l]=m  
  100.         sortedLabelCounts=sorted(labelCounts.iteritems(),key=operator.itemgetter(1),reverse=True)  
  101.         return sortedLabelCounts[0][0]  
  102.   
  103. """ 
  104. 递归的构造决策树 
  105. """  
  106. def buildDecisionTree(dataset,labels):  
  107.     #判断终止条件  
  108.     classList=[example[-1] for example in dataset]  
  109.     uniClassList=set(classList)  
  110.     if len(uniClassList)==1 :  
  111.         return classList[0]  
  112.     if len(dataset[0])==1:  
  113.         return chooseClassLabel(dataset)  
  114.     bestFeat=getBestSlpit(dataset,labels)  
  115.     bestFeatLabel=labels[bestFeat] #最好的分类标签  
  116.     myTree={bestFeatLabel:{}}  
  117.     del(labels[bestFeat])  
  118.     featValues=[example[bestFeat] for example in dataset]  
  119.     uniFeat=set(featValues)  
  120.     for value in uniFeat:  
  121.         subLabels=labels[:]  
  122.         myTree[bestFeatLabel][value]=buildDecisionTree(splitDataset(dataset,bestFeat,value),subLabels)  
  123.     return myTree  
  124.   
  125.   
  126.   
  127. if __name__=="__main__" :  
  128.     dataset,labels=createDataset()  
  129.     # ent=computeEnt(dataset)  
  130.     # print ent  
  131.     # newdateset=splitDataset(dataset ,0,1)  
  132.     # print  newdateset  
  133.     # label=chooseClassLabel(dataset)  
  134.     # print label  
  135.     # bestEnt,bestAxis=getBestSlpit(dataset,labels)  
  136.     # print bestEnt  
  137.     # print bestAxis  
  138.     mytree=buildDecisionTree(dataset,labels)  
  139.     print mytree  

 运行结果如下：

 



 

使用图形表达出来就是下图：


 Part 2:决策树剪枝

决策树生成完毕，也会产生一些问题，就是和所有机器学习问题一样，会产生过拟合问题，表现在决策树上，就是分类的树过于复杂，对部分特征学习过度，忽略了整体特征。解决其问题就是剪枝。

 



 

 

如上图所示，如果一棵树的不剪枝的损失函数值大于剪枝后的损失函数值的话，那么就将子节点合并到其父节点上。决策树剪枝实质上是将一些叶节点合并到其父节点上，以此递归实现。

决策树剪枝算法也有很多种，具体见【1】P65-P67，这里不细述。

 

附1： 关于CART算法

 

CART算法可以用于决策树的生成，生成过程和上面的ID3算法大同小异，区别在于其特征选取的方法是基尼指数，听着挺高端，其实也不过是一种新的计算方法，没什么特殊的。也就是说上面的程序将信息增益的方法改变成基尼指数方法就可以了

 

附2：决策树与回归树

决策树是用来分类的，而回归树是一种预测模型。回归树和所有回归方法一样，根据已知的数据构造数据模型，然后根据需要预测对象的参数输出预测结果，回归问题会在后面的讲回归的章节中描述，所以这里不在具体描述。

 

 

参考文献：

【1】 统计学习方法，李航

【2】Machine Learning in Action

这篇关于MLA Review之二： 决策树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/972828。

相关文章

如何编写Linux PCIe设备驱动器 之二

如何编写Linux PCIe设备驱动器 之二

如何编写Linux PCIe设备驱动器 之二 功能(capability)集功能(capability)APIs通过pci_bus_read_config完成功能存取功能APIs参数pos常量值PCI功能结构 PCI功能IDMSI功能电源功率管理功能 功能(capability)集 功能(capability)APIs int pcie_capability_read_wo
阅读更多...
Pr 入门系列之二：导入与管理素材（下）

Pr 入门系列之二：导入与管理素材（下）

◆  ◆  ◆ 管理素材 导入素材后，项目面板中每一个媒体都只是原始素材的“链接”。 所以，视频编辑过程中一般情况下都不会破坏原始素材。 1、在不同视图模式下组织素材 项目面板提供了三大视图 View供选用：列表视图、图标视图以及自由格式视图。 A. 锁定 B. 列表视图 C. 图标视图 D. 自由格式视图 E. 缩放滑块 F. 排序图标 G. 自动匹配序列 H. 查找 I. 新建素材箱 J.
阅读更多...
J.U.C Review - ThreadLocal原理源码分析

J.U.C Review - ThreadLocal原理源码分析

文章目录 一致性问题一致性问题简介解决一致性问题的常见方法 ThreadLocal什么是 ThreadLocalThreadLocal 的 线程模型ThreadLocal 的工作原理使用场景ThreadLocal 的基本 API1. 构造函数 `ThreadLocal()`2. 初始化方法 `initialValue()`3. 访问器 `get()` 和 `set()`4. 回收方法 `re
阅读更多...
决策树的实现原理与matlab代码

决策树的实现原理与matlab代码

很久不写博客了，感觉很长一段时间只是一味的看书，疏不知一味地看书、写代码会导致自己的思考以及总结能力变得衰弱。所以，我决定还是继续写博客。废话不多说了，今天想主要记录数据挖掘中的决策树。希望能够将自己的理解写得通俗易懂。 决策树是一种对实例分类的树形结构，树中包含叶子节点与内部节点。内部节点主要是数据中的某一特性，叶子节点是根据数据分析后的最后结果。 先看一组数据： 这组数据的特性包含
阅读更多...
机器学习（西瓜书）第 4 章决策树

机器学习（西瓜书）第 4 章决策树

4.1 决策树基本流程 决策树模型 基本流程 在第⑵种情形下，我们把当前结点标记为叶结点，并将其类别设定为该结点所含样本最多的类别；在第⑶种情形下，同样把当前结点标记为叶结点，但将其类别设定为其父结点所含样本最多的类别.注意这两种情形的处理实质不同：情形⑵是在利用当前结点的后验分布，而情形⑶则是把父结点的样本分布作为当前结点的先验分布. 基本算法 由算法4 .2可看出，决策树学习
阅读更多...
【机器学习-监督学习】决策树

【机器学习-监督学习】决策树

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈Python机器学习 ⌋ ⌋ ⌋ 机器学习是一门人工智能的分支学科，通过算法和模型让计算机从数据中学习，进行模型训练和优化，做出预测、分类和决策支持。Python成为机器学习的首选语言，依赖于强大的开源库如Scikit-learn、TensorFlow和PyTorch。本专栏介绍机器学习的相关算法以及基于Python的算法实现。
阅读更多...
J.U.C Review - Stream并行计算原理源码分析

J.U.C Review - Stream并行计算原理源码分析

文章目录 Java 8 Stream简介Stream单线程串行计算Stream多线程并行计算源码分析Stream并行计算原理Stream并行计算的性能提升 Java 8 Stream简介 自Java 8推出以来，开发者可以使用Stream接口和lambda表达式实现流式计算。这种编程风格不仅简化了对集合操作的代码，还提高了代码的可读性和性能。 Stream接口提供了多种集合
阅读更多...
使用YOLOv10训练自定义数据集之二（数据集准备）

使用YOLOv10训练自定义数据集之二（数据集准备）

0x00 前言 经过上一篇环境部署的介绍【传送门】，我们已经得到了一个基本可用的YOLOv10的运行环境，还需要我们再准备一些数据，用于模型训练。 0x01 准备数据集 1. 图像标注工具 数据集是训练模型基础素材。 对于小白来说，一般推荐从一些开放网站中下载直接使用，官方推荐了一个名为Roboflow的数据集网站。Roboflow是一个免费开源数据集管理平台，它不仅提供免费的数据集，还
阅读更多...
UICollectionView 的研究之二 ：自定义 UICollectionViewFlowLayout

UICollectionView 的研究之二 ：自定义 UICollectionViewFlowLayout

UICollectionView 实现各式复杂布局核心在于 UICollectionViewLayout，需要我们去自定义实现。 通过各种layout 的自定义实现，以及它们之间的切换。可以实现一些酷炫的布局，例如 （图片选自：http://www.cnblogs.com/markstray/p/5822262.html） Cover Flow 布局 堆叠布局 圆形布局
阅读更多...
Spark2.x 入门：决策树分类器

Spark2.x 入门：决策树分类器

一、方法简介 ​ 决策树（decision tree）是一种基本的分类与回归方法，这里主要介绍用于分类的决策树。决策树模式呈树形结构，其中每个内部节点表示一个属性上的测试，每个分支代表一个测试输出，每个叶节点代表一种类别。学习时利用训练数据，根据损失函数最小化的原则建立决策树模型；预测时，对新的数据，利用决策树模型进行分类。 决策树学习通常包括3个步骤：特征选择、决策树的生成和决策树的剪枝。
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2