文档章节

机器学习 -- 决策树算法

大海201506
 大海201506
发布于 2017/05/13 18:40
字数 1860
阅读 42
收藏 0

1. 决策树

决策树是附加概率结果的一个树状的决策图,是直观地运用统计概率分析的图法。机器学习中决策树是一个预测模型,它表示对象属性和对象值之间的一种映射,树中的每一个节点表示对象属性的判断条件,其分支表示符合节点条件的对象。树的叶子节点表示对象所属的预测结果。

1.1 决策树的案例

通俗来说,决策树分类的思想类似于找对象。现想象一个女孩的母亲要给这个女孩介绍男朋友,这个女孩的决策是否去见面的过程就是典型的分类树决策。通过年龄、长相、收入和是否公务员对决策结果分为两个类别:见和不见。假设这个女孩对男人的要求是:30岁以下、长相中等以上并且是高收入或中等收入的公务员,那么可以用下图表示女孩的决策逻辑:

这幅图基本可以算是一颗决策树,说它基本可以算,是因为图中的判断条件没有量化,如收入高中低等等,不能算是严格意义上的决策树,如果将所有条件量化,则变成真正的决策树了。

1.2 决策树建立

选择一个合适的特征作为判断节点,可以快速地分类,减少决策树的深度。决策树的目标就是把数据集按对应的类标签进行分类。最理想的情况是,通过特征的选择能把不用类别的数据集贴上对应类标签。特征选择的目标使得分类后的数据集比较纯。如何衡量一个数据集纯度,这里需要引入数据纯度函数。信息熵是可以表示数据纯度的函数。

1.3 决策树的算法

构造决策树的关键性内容是进行属性选择度量,属性选择度量是一种选择分裂准则,是将给定的类标记的训练集合的数据划分。属性选择度量算法很多,一般使用自顶
而下递归分治法,并采用不回溯的贪心策略。这里介绍ID3和C4.5算法。

1.3.1 ID3算法

信息增益

信息熵表示的是不确定度。均匀分布时,不确定度最大,此时熵最大。当选择某个特征对数据集进行分类时,分类后的数据集信息熵会比分类前的小,其差值表示为信息增益。信息增益可以衡量某个特征对分类结果的影响大小。

假设在样本数据集D中,混有C中类别的数据。构建决策树时,根据给定的样本数据集选择某个特征值作为树的节点。在数据集中,可以计算出该数据的信息熵:

其中D表示训练数据集,m表示数据类别数,Pi表示类别i样本数量占所有样本的比例。

对应数据集D,选择特征A作为决策树判断节点时,在特征A作用后的信息熵为InfoA(D),计算如下:

而信息增益即为两者的差值:

总结:对于决策树节点最合适的特征选择,就是gain(A)值最大的特征。

ID3算法就是在每次需要分裂时,计算每个属性的增益率,然后选择增益率最大的属性进行分裂。下面我们继续用某社区不真实检测的例子说明如何使用ID3算法构造决策树。为了简单起见,我们假设训练集合包含3个元素:

日志密度 好友密度 是否使用真实头像 账号是否真实
s s no no
s l yes yes
l m yes yes
m m yes yes
l m yes yes
m l no yes
m s no no
l m no yes
m s no yes
s s yes no

其中,s、m、l分别代表小、中、大。 设L、F、H和R表示日志密度、好友密度、是否使用真实头像和账号是否真实

该数据的信息熵 :

对应数据集D,选择特征日志密度作为决策树判断节点时,在特征日志密度作用后的信息熵为InfoL(D),计算如下:

因此日志密度的信息增益是0.276:

用同样方法得到H和F的信息增益分别为0.033和0.553。

因此F具有最大的信息增益,所以第一次分裂选择F作为分裂属性,分裂后的结果如下图表示:

在上图的基础上,再递归使用这个方法计算子节点的分裂属性,最终就可以得出整棵决策树。

1.3.2 C4.5算法

ID3算法存在一个问题,就是偏向于多值属性,例如,如果存在唯一标识属性ID,则ID3会选择它作为分裂属性,这样虽然使得划分充分纯净,但这种划分对分类几乎毫无用处。ID3的后继算法C4.5使用增益率(gain ratio)的信息增益扩充,试图克服这个偏倚。

C4.5算法首先定义了"分裂信息",其定义可以表示成:

 其中各符号意义与ID3算法相同,然后增益率被定义为:

C4.5选择具有最大增益率的属性作为分裂属性,其具体应用与ID3类似,不再赘述。

1.4 关于剪枝

在分类模型建立的过程中,很容易出现过拟合的现象。过拟合是指在模型学习训练中,训练样本达到非常高的逼近精度,但对校验样本的逼近误差随着训练次数而呈现先下降后上升的现象。过拟合时训练误差很小,但是检验误差很大,不利于实际应用。

决策树的过拟合现象可以通过剪枝进行一定的修复。剪枝分为预先剪枝和后剪纸两种。

预先剪枝指在决策树生长过程中,使用一定条件加以限制,使得产生完全拟合的决策树之前就停止生长。预先剪枝的判断方法也有很多,比如信息增益小于一定阈值的时候通过剪枝使决策树停止生长。但如何确定一个合适的阈值也需要一定的依据,阈值太高导致模型拟合不足,阈值太低又导致模型过拟合。

后剪枝是咋决策树生长完成之后,按照自底向上的方式修剪决策树。后剪枝有两种方式,一种用新的叶子节点替换子树,该节点的预测类有子树数据集中的多数类决定。另一种用子树中最常使用的分支替代子树。

总结:预先剪枝可能过早地终止决策树的生长,后剪枝一般能够产生更好的效果。但是后剪枝在子树被剪掉后,决策树生长的一部分计算就被浪费了。

 

 

 


 

 

 

参考:http://blog.csdn.net/nieson2012/article/details/51314873

参考:http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html

© 著作权归作者所有

大海201506
粉丝 5
博文 96
码字总数 173986
作品 0
广州
程序员
私信 提问
《Sklearn 与 TensorFlow 机器学习实用指南》 第6章 决策树

来源:ApacheCN《Sklearn 与 TensorFlow 机器学习实用指南》翻译项目 译者:@Lisanaaa @y3534365 校对:@飞龙 和支持向量机一样, 决策树是一种多功能机器学习算法, 即可以执行分类任务也可...

ApacheCN_飞龙
2018/06/12
0
0
成为顶尖算法专家需要知道哪些算法?

机器学习算法简介 有两种方法可以对你现在遇到的所有机器学习算法进行分类。 第一种算法分组是学习风格的。 第二种算法分组是通过形式或功能相似。 通常,这两种方法都能概括全部的算法。但是...

【方向】
2018/10/11
0
0
决策树(Decision Tree)简介

决策树(Decision Tree)及其变种是另一类将输入空间分成不同的区域,每个区域有独立参数的算法。决策树分类算法是一种基于实例的归纳学习方法,它能从给定的无序的训练样本中,提炼出树型的分...

fengbingchun
2017/12/23
0
0
在opencv3中的机器学习算法

转载:https://www.cnblogs.com/denny402/p/5032232.html 在opencv3.0中,提供了一个ml.cpp的文件,这里面全是机器学习的算法,共提供了这么几种: 1、正态贝叶斯:normal Bayessian classi...

byxdaz
05/15
0
0
如何规划出完美的机器学习入门路径?| AI知识科普

书山有路勤为径,在学习进修的道路上,正确的路径比埋头勤奋要重要的多。 最近两年AI在线学习和教育呈喷涌式发展,机器学习的培训课程也是层出不穷,专业的教育和课程固然重要,但在这个过程...

AI研究所
2018/07/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
6
0
object 类中有哪些方法?

getClass(): 获取运行时类的对象 equals():判断其他对象是否与此对象相等 hashcode():返回该对象的哈希码值 toString():返回该对象的字符串表示 clone(): 创建并返此对象的一个副本 wait...

happywe
今天
6
0
Docker容器实战(七) - 容器中进程视野下的文件系统

前两文中,讲了Linux容器最基础的两种技术 Namespace 作用是“隔离”,它让应用进程只能看到该Namespace内的“世界” Cgroups 作用是“限制”,它给这个“世界”围上了一圈看不见的墙 这么一...

JavaEdge
今天
8
0
文件访问和共享的方法介绍

在上一篇文章中,你了解到文件有三个不同的权限集。拥有该文件的用户有一个集合,拥有该文件的组的成员有一个集合,然后最终一个集合适用于其他所有人。在长列表(ls -l)中这些权限使用符号...

老孟的Linux私房菜
今天
7
0
面试套路题目

作者:抱紧超越小姐姐 链接:https://www.nowcoder.com/discuss/309292?type=3 来源:牛客网 面试时候的潜台词 抱紧超越小姐姐 编辑于 2019-10-15 16:14:56APP内打开赞 3 | 收藏 4 | 回复24 ...

MtrS
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部