ID3算法

ID3算法（Iterative Dichotomiser 3 迭代二叉树3代）是一个由Ross Quinlan发明的用于决策树的算法。

这个算法是建立在奥卡姆剃刀的基础上：越是小型的决策树越优于大的决策树（简单理论）。尽管如此，该算法也不是总是生成最小的树形结构。而是一个启发式算法。奥卡姆剃刀阐述了一个信息熵的概念：

这个ID3算法可以归纳为以下几点：

 使用所有没有使用的属性并计算与之相关的样本熵值
 选取其中熵值最小的属性
 生成包含该属性的节点

关于ID3算法的实现可以参考C4.5算法，它同时也是ID3的升级版。

 相关主题 
 C4.5算法

 参考文献 
 Mitchell, Tom M. Machine Learning. McGraw-Hill, 1997.

 外部链接 
 Seminars - http://www2.cs.uregina.ca/
 Description and examples - http://www.cise.ufl.edu/
 Description and examples - http://www.cis.temple.edu/
 An implementation of ID3 in Python
 An implementation of ID3 in Ruby
 An implementation of ID3 in Common Lisp
 Implementation of ID3 algorithm in C# - https://web.archive.org/web/20061109050158/http://www.codeproject.com/cs/algorithms/id3.asp
 An implementation of ID3 in Perl

Category:决策树
Category:机器学习
Category:算法