机器学习:谈谈决策树

前面谈了逻辑回归的基本原理及梯度下降推导过程,编码实现了逻辑回归的梯度下降算法,这是分类算法。今天,我们继续开启分类算法之旅,它是一种高效简介的分类算法,后面有一个集成算法正是基于它之上,它是一个可视化效果很好的算法,这个算法就是决策树。

1 一个例子

有一堆水果,其中有香蕉,苹果,杏这三类,现在要对它们分类,可以选择的特征有两个:形状和大小,其中形状的取值有个:圆形和不规则形,大小的取值有:相对大和相对小。现在要对其做分类,我们可以这样做:

首先根据特征:形状,如果不是圆形,那么一定是香蕉,这个就是叶子节点;

如果是圆形,

再进一步根据大小这个特征判断,如果是相对大的,则是苹果,如果否,则是杏子,至此我们又得到两个叶子节点,并且到此分类位置,都得到了正确划分三种水果的方法。

大家可以体会刚才这个过程,这就是一个决策分类,构建树的一个过程,说成是树,显得有点高大上,再仔细想想就是一些列 if 和 else 的嵌套,说是树只不过是逻辑上的一种神似罢了。

刚才举的这个例子,有两个特征:形状和大小,并且选择了第一个特征:形状作为第一个分裂点,大小作为第二个分裂点,那么不能选择第二个特征作为第一分裂点吗? 这样选择有没有公式依据呢?

2 分裂点选择依据

在上个例子中,有三类水果,现在假设杏都被我们家的宝宝吃完了,现在手里只有香蕉和苹果这两类水果了,并且这个时候要对它们做分类,此时机灵的你,一定会根据特征:形状对它们分类了,因为这样一下就会把它们分开了,此时我们说这类集合的纯度更高,与之前的那三类水果在形状这个特征上。

纯度这个概念是很好的理解的,种类越少纯度越高,自然两类纯度更高。 此时有人提出了一个和它相反的但是不那么容易理解的概念:熵。它们是敌对双方:熵越大,纯度越低;熵越小,纯度越高。

这是一种概念,那么如何用公式量化熵呢:

其中 i 等于苹果,香蕉,杏,P(i)是集合中取得某一个水果的概率。

试想一下,如果我们想更好地对某个集合完成分类,会怎么做呢?我们一定会优先选择一个特征,使得以这个特征做分类时,它们能最大程度的降低熵,提高分类的纯度,极限的情况是集合中100个元素(集合中只有两类水果),根据某个最优特征,直接将分为两类,一类都是苹果,一类都是杏,这样熵直接等于0。

这个特点就是所谓的信息增益,熵降低的越多,信息增益的就越多。很多时候都不会发生上述说的这个极限情况,就像文章一开始举的例子,根据形状划分后,熵变小了,但是未等于0,比如刚开始三类水果的熵等于0.69,现在根据形状分裂后,熵等于了0.4,所以信息增益为0.69 - 0.4 = 0.29 。如果根据大小划分,信息增益为0.1,那么我们回考虑第一个分裂特征:形状。

这种方法有问题吗?

3 信息增益越大,分类效果越好?

这是只根据信息增益选择分裂特征点的bug,请看下面举例。

如果某个特征是水果的唯一标示属性:编号,那么此时如果选择这个特征,共得到100个叶子节点(假设这堆水果一共有100个),每个叶子节点只含有1个样本,并且此时的信息增益最大为 0.69 - 0 = 0.69 。

但是,这是好的分类吗? 每一个样本作为单独的叶子节点,当来了101号水果,都不知道划分到哪一个叶子节点,也就不知道它属于哪一类了!

因此,这个问题感觉需要除以某个变量,来消除这种情况的存在。

它就是信息增益率,它不光考虑选择了某个分裂点后能获得的信息增益,同时还要除以分裂出来的这些节点的熵值,什么意思呢? 刚才不是分裂出来100个节点吗,那么这些节点自身熵一共等于多少呢:

再除以上面这个数后,往往信息增益率就不会那么大了。这就是传说中的从ID3 到 C4.5 的改进。

4 与熵的概念类似的基尼系数

只需要知道基尼系数和熵差不多的概念就行了,只不过量化的公式不同而已,这就说明理解了,至于公式长什么样子,用的时候去查就行了。

5 展望

以上介绍了决策树的一些概念和分裂点选取的基本方法。明天打算借助sklearn库的API,可视化出建立决策树的过程,以及分析决策树中不可或缺的最重要的部分:剪枝策略。

决策树在训练集上分类效果可以达到100%,那么在测试集上为什么分类效果不够好?

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2017-11-19

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏华章科技

这份深度学习课程笔记获吴恩达点赞

吴恩达在推特上展示了一份由 TessFerrandez 完成的深度学习专项课程信息图,这套信息图优美地记录了深度学习课程的知识与亮点。因此它不仅仅适合初学者了解...

9430
来自专栏华章科技

机器学习算法比较

机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。通常最开始...

12630
来自专栏SIGAI学习与实践平台

视频语义分割介绍

随着深度学习的发展,图像语义分割任务取得了很大的突破,然而视频语义分割仍然是一个十分具有挑战性的任务,本文将会介绍视频语义分割最近几年顶会上的一些工作。

52120
来自专栏机器之心

资源 | 从反向传播到迁移学习,盘点人工智能从业者必备的10个深度学习方法

33970
来自专栏大数据挖掘DT机器学习

SIFT特征提取分析(附源码)

SIFT(Scale-invariant feature transform)是一种检测局部特征的算法,该算法通过求一幅图中的特征点(interest poin...

54050
来自专栏数据科学与人工智能

【算法】逻辑回归(Logistic Regression) 模型

小编邀请您,先思考: 1 逻辑回归算法的原理是什么? 2 逻辑回归算法的有哪些应用? 逻辑回归(Logistic Regression)是机器学习中的一种分类模...

1.1K50
来自专栏机器之心

这是一份优美的信息图,吴恩达点赞的deeplearning.ai课程总结

机器之心整理 参与:思源、刘晓坤 吴恩达在推特上展示了一份由 TessFerrandez 完成的深度学习专项课程信息图,这套信息图优美地记录了深度学习课程的知识...

37860
来自专栏自然语言处理

一起走进条件随机场4(NLP重点理论)

条件随机场(CRF):是给定一组输入随机变量条件下,另一组输出随机变量的条件概率分布模型,其特点是假设输出随机变量构成马尔科夫随机场,条件随机场可用于不同预测问...

14310
来自专栏jeremy的技术点滴

机器学习课程_笔记06

29840
来自专栏机器学习、深度学习

人群计数--Cross-scene Crowd Counting via Deep Convolutional Neural Networks

Cross-scene Crowd Counting via Deep Convolutional Neural Networks CVPR2015 本文主...

35060

扫码关注云+社区

领取腾讯云代金券