机器学习(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