​ 机器学习(九) ——构建决策树(离散特征值)

机器学习(九)

——构建决策树(离散特征值)

(原创内容,转载请注明来源,谢谢)

一、概述

1、概念

决策树,这个概念是一个很常见的概念,应该是机器学习中最好理解的一个算法。决策树是在已知训练结果的情况下,进行的分类。因此,决策树是一种监督学习方法。

根据分类的条件不同,决策树又可以分为离散特征值下的分类和连续特征值下的分类。

离散特征值,是每个特征值只有有限个结果,例如yes和no、0和1,或者多个结果如0、1、2、3,如下图所示:

连续特征值,是特征值是在一片连续的范围内,如0~10,这种情况下涵盖了0.0001等无穷多个数字的情况,如下图所示:

图形中,每个叶子节点表示分类的一个分支,即特征值按如此分类最终走向的结果。

连续特征值情况下,需要涉及到特征值的划分等,比较复杂,本文讨论的是离散特征值情况下的决策树分类。

2、比较其他算法

1)决策树和其他算法比起来,一大的优势在于,可以直观的看出样本每一列特征值的含义,而不仅仅是0、1这种数字形式。

2)决策树对中间值的缺失不敏感,且可以处理不相关特征数据。

3、决策树算法

决策树算法的过程,主要包括:决策树的构建、决策树的图形化绘制、决策树的存储与实际应用。每一部分都包含很多内容,故分三篇文章讨论。本文讨论的是决策树的构建。

4、构建决策树

构建决策树,步骤包括计算香农熵、递归选取最优划分特征切分数据集、递归构造决策树,下面逐一讨论。

决策树最主要的一点在于划分数据集。在决策树中,每个新的样本需要经过n次比较得出分类结果,不同的划分方式,会导致最终需要比较的次数有很大差异。因此,需要选取最优化的划分数据集的方式。

构造决策树,主要就是在得到最优化的划分方式,并且生成决策树。本文的划分方式采用ID3算法,另外比较流行的还有C4.5、CART等,后面学到连续特征值时,会采用CART算法进行回归。这里讨论ID3算法情况下的构造决策树。

二、测试构造决策树的数据集

为了便于理解,先把此次的测试数据集给出,如下:

其中,dataSet是样本集,每个样本的最后一个元素是分类的结果;labels是特征值含义集,每个元素对应样本的一个特征值。

三、香农熵

划分数据集的最大原则,是使数据由无序变得有序。香浓提出了熵的概念,熵表示信息的混乱程度,熵越大表示信息越杂乱,分类的目的是获取香农熵尽量小的结果。因此,首先需要一个计算香农熵代码。

熵定义信息的期望值,某个信息x的期望值公式:l(xi) = -log2 ,其中p(x)是x在这个信息中出现的概率。

总的香农熵,则是每个期望值乘以对应概率的和:

计算过程,即递归计算该数据集中,分类结果的熵。其中,概率计算,采用分别记录该分类数据集下,结果的类别数、每个类别结果出现的次数,并用这个次数除以总的结果数,得到该结果出现的概率。

代码如下:

另外,除了用熵,也可以用基尼不纯度来衡量数据集的无序程度,方法是从一个数据中随机选取子项,度量其被错误分到其他组的概率。这里不采用基尼不纯度方式。

四、给定特征划分数据集

这么做的目的是为下面递归获取最优划分服务。

根据给定的数据集、特征元素的在样本的下标、用于划分的特征值,遍历整个数据集,把该特征符合条件的样本都提取出来,并且删除掉这个特征,以便后面继续划分。

代码如下:

五、选择最好的划分方式

这里给定一个数据集,返回当前数据集的最优划分的特征值,实际上也是在给后面构建决策树时递归调用此方法服务。

选择最好的划分方式的算法,就是一个求最小值的算法,遍历数据集特征结果种类,并且去重,再遍历这个结果,计算出总的熵,并且比较得到最小的熵,则此时的特征值的下标就是最优的划分方式。

代码如下:

六、多数表决法

这个算法也是为构建决策树服务。当特征值都已经使用到划分决策树,但是仍有部分类别不相同,则采用此方法,将样本中出现次数最多的分类结果,作为最终的结果。

代码如下:

七、构建决策树

构建决策树,需要递归上面的划分。

1、递归结束的条件

递归结束的条件有两个:

1)类别完全相同,即本次递归下,样本集中的所有元素,分类结果都是同样的。

2)没有更多的特征值进行分类,则采用上述的多数表决法。

2、从特征值含义数组中获取当前最好的分类方式对应的值,并且删掉该特征值。

3、得到列表包含的所有属性,并且递归构造树。

代码如下:

八、测试

九、构造决策树小结

在理解构造决策树的过程中,我一开始有几个理解偏差,导致编码的时候遇到问题,分享如下:

1、labels

labels表示的是特征值的含义,而不是分类结果的含义,这个一定要搞清楚。我一开始就是这里理解错了,所以在尝试用不同的数据集来测试构造决策树的结果时,发现老是报labels数组下标超出。然后多次翻书查看,搞明白了含义。

2、构造的目的

一定要搞明白构造决策树的目的,这个是我在理解过程的另一大问题。其目的不是为了把样本进行分类,因为样本其实已经有分类结果了,再分类没有意义。构造决策树的目的,是通过现有的样本,构造出一个树,后面再有新的数据集且没有分类结果,可以直接拿这个树,通过样本特征的比对,得到结果。

因此,构造决策树的过程中,只需要记录分类的方式即可,并不需要得到分类结果。

——written by linhxx 2018.01.07

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2018-01-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏贾志刚-OpenCV学堂

对象检测网络中的mAP到底怎么计算出来的

mAP是英文mean Average Precision的全称,同时也是衡量深度学习中对象检测算法准确率的一个重要指标,mAP的计算涉及到很多专业的术语与解释,...

2254
来自专栏AI科技评论

深度 | Facebook翻译错误导致一名建筑工人被抓,机器翻译到底有多脆弱?

这是最近几年非常流行的一个句子,试试看能不能读懂—— “Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy, i...

3215
来自专栏ACM算法日常

第一篇:《机器学习之入门初探》

这是一篇帮助你了解和理解机器学习、神经网络、深度学习相关概念的文章,如果你对智能领域感兴趣并且想要未来投身AI方向的话,希望你可以耐下心来理解这些概念,以及我...

791
来自专栏AI研习社

循环神经网络的介绍、代码及实现

该文主要目的是让大家体会循环神经网络在与前馈神经网络的不同之处。 大家貌似都叫Recurrent Neural Networks为循环神经网络。 我之前是查维基...

3498
来自专栏专知

【干货】这8种神经网络结构,你掌握了几个?

【导读】近日,James Le撰写了一篇博文,全面阐述了神经网络中经典的八种神经网络结构。包括感知器、卷积神经网络、循环神经网络、LSTM、Hopfield网络...

3149
来自专栏统计学习方法

《统计学习方法》第八章-提升方法

在《统计学习方法》中第八章提升方法,包括四节,第一节介绍AdaBoost、第二节介绍AdaBoost的误差、第三节介绍从前向分布算法来实现AdaBoost、第四...

1886
来自专栏媒矿工厂

基于双流编码-解码深度网络的视频对象分割算法简介

背景介绍 视频对象分割(Video Object Segmentation),目的是将视频段中的物体连续地“抠”出来以得到视频每一帧的前景、背景分割结果。分割得...

3773
来自专栏量化投资与机器学习

深度学习理论系列之——基本理论方法与训练过程

深度学习的基本理论与方法 深度学习:一种基于无监督特征学习和特征层次结构的学习方法 可能的的名称: 1.深度学习 2.特征学习 3.无监督特征学习 2006年...

2318
来自专栏BestSDK

谷歌开放一种新的图像分类卷积神经网络模型

为了在该领域取得更多进展,今天我们非常高兴的宣布开放 Inception-ResNet-v2,这是一个在 ILSVRC 图像分类基准上取得顶尖准确率的卷积神经网...

2389
来自专栏张宏顺的专栏

对 HEVC CU深度快速选择方法的思考和实践

本文主要讲解了HEVC中CU深度的快速选择方法,分析了当前编码中存在的问题,提出解决方案,并给出了具体的实践流程,及得到的收益。

6292

扫码关注云+社区