运维开发网

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

运维开发网 https://www.qedev.com 2021-04-02 16:01 出处:51CTO 作者:mob604756f49b91
ID3是什么?ID3算法是决策树的一种,基于奥卡姆剃刀原理,即用尽量用较少的东西做更多的事。ID3算法( Iterative Dichotomiser 3),迭代二叉树3代,是Ross Quinlan发明的一种决策树算法,这个算法的基础就是上面提到的奥卡姆剃刀原理,越是小型的决策树越优于大的决策树,尽管如此,也不总是生成最小的树型结构,而是一个启发式算法。在信息论中,期望信息越小,那么信息增益就越

ID3是什么?

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

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

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

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

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

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

Python实现

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

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

main.py

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

pre_processing.py

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

decision_tree.py

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

参考:

1. 周志华《机器学习》

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

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

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

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号