机器学习(5)之决策树ID3及Python实现

关键字全网搜索最新排名

【机器学习算法】:排名第一

【机器学习】:排名第二

【Python】:排名第三

【算法】:排名第四

ID3是什么?

ID3算法是决策树的一种,基于奥卡姆剃刀原理,即用尽量用较少的东西做更多的事。ID3算法( Iterative Dichotomiser 3),迭代二叉树3代,是Ross Quinlan发明的一种决策树算法,这个算法的基础就是上面提到的奥卡姆剃刀原理,越是小型的决策树越优于大的决策树,尽管如此,也不总是生成最小的树型结构,而是一个启发式算法。

在信息论中,期望信息越小,那么信息增益就越大,从而纯度就越高。ID3算法的核心思想就是以信息增益来度量属性的选择,选择分裂后信息增益最大的属性进行分裂。该算法采用自顶向下的贪婪搜索遍历可能的决策空间。

在1948年,香农引入了信息熵,将其定义为离散随机事件出现的概率,一个系统越有序,信息熵越低,反之越是混乱,它的信息熵越高。所以信息熵可以被认为是系统有序化程度的一个度量。

信息增益是针对一个一个特征而言的,就是看一个特征,系统有它和没有它时的信息量各是多少,两者的差值就是这个特征给系统带来的信息量,即信息增益。计算公式如下

Python实现

源代码下载请加入机器学习交流2群(634808033)在文件区中下载或者后台回复关键词:“20170711”下载。

这里采用的是从UCI上获得的一个名为agaricus-lepiota的数据集,它的属性全都是标称的,最终的分类效果不错,准确率达到了99.63%。代码在实现决策树节点的分枝时是用递归实现的。其中,递归的终止条件有两种:一是无法通过分枝产生信息增益,这样自然就不必再分枝了,二是节点本身分得的样本数达到了下限值minNumOfInstances,这种情况不再进行分枝的目的是为了避免造成过度拟合的问题。

main.py

pre_processing.py

decision_tree.py

参考:

1. 周志华《机器学习》

2. ACdreamers的博客:http://blog.csdn.net/acdreamers/article/details/44661149

3. stridehuan的博客:http://blog.csdn.net/u012822866/article/details/42419471

原文发布于微信公众号 - 机器学习算法与Python学习(guodongwei1991)

原文发表时间:2017-07-13

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏量子位

以为GAN只能“炮制假图”?它还有这7种另类用途

最近,AI方案设计师Alexandor Honchar在Medium网站上分享一篇文章。他认为生成对抗网络(GAN)目前在生成图像取得了巨大进展,生成的图像几乎...

1292
来自专栏机器之心

当前训练神经网络最快的方式:AdamW优化算法+超级收敛

Adam 优化器之旅可以说是过山车(roller-coaster)式的。该优化器于 2014 年推出,本质上是一个出于直觉的简单想法:既然我们明确地知道某些参数...

1502
来自专栏磐创AI技术团队的专栏

谷歌发布迄今最大注释图像数据集,190万图像目标检测挑战赛启动

1803
来自专栏目标检测和深度学习

谷歌发布迄今最大注释图像数据集,190万图像目标检测挑战赛启动

972
来自专栏新智元

谷歌发布迄今最大注释图像数据集,190万图像目标检测挑战赛启动

2219
来自专栏人工智能

计算图的微积分:反向传播

后向传播是训练深度模型在计算上易于处理的关键算法。对于现代神经网络,相对于单纯的实现,它可以使梯度下降的训练速度提高一千万倍。这相当于模型训练时间...

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

【算法】10 种机器学习算法要点

小编邀请您,先思考: 1 你熟悉那些机器学习算法? 2 你如何应用机器学习算法? 前言 谷歌董事长施密特曾说过:虽然谷歌的无人驾驶汽车和机器人受到了许多媒体关注...

3819
来自专栏ATYUN订阅号

【业界】Facebook发布开源“Detectron”深度学习库,用于对象检测

AiTechYun 编辑:nanan 在刚刚过去的一月份(2018年1月),Facebook的研究机构Facebook AI Research(FAIR)发布了...

3154
来自专栏AI研习社

不会做特征工程的 AI 研究员不是好数据科学家!上篇 - 连续数据的处理方法

眨眼间我们就从人工特征、专家系统来到了自动特征、深度学习的人工智能新时代,众多开源测试数据集也大大降低了理论研究的门槛,直接加载数据集就可以开始模型训练或者测试...

52510
来自专栏PPV课数据科学社区

R语言之kmeans聚类理论篇!

前言 kmeans是最简单的聚类算法之一,但是运用十分广泛。最近在工作中也经常遇到这个算法。kmeans一般在数据分析前期使用,选取适当的k,将数据分类后,然后...

68011

扫码关注云+社区

领取腾讯云代金券