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

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

: I_{E}(i) = - \sum^{m}_{j=1} f (i,j) \log_{2} f (i, j).

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

使用所有没有使用的属性并计算与之相关的样本熵值

选取其中熵值最小的属性

生成包含该属性的节点

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

相关主题

• C4.5算法

参考文献

• Mitchell, Tom M. Machine Learning. McGraw-Hill, 1997.

外部链接

• Seminars - [https://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/dtrees/4_dtrees1.html http://www2.cs.uregina.ca/]
• Description and examples - [http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm http://www.cise.ufl.edu/]
• Description and examples - [http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html http://www.cis.temple.edu/]
• [http://www.onlamp.com/pub/a/python/2006/02/09/ai_decision_trees.html An implementation of ID3 in Python]
• [https://web.archive.org/web/20081016040703/http://ai4r.rubyforge.org/machineLearning.html An implementation of ID3 in Ruby]
• [https://web.archive.org/web/20171225121804/http://www.pvv.ntnu.no/~oyvinht/static/OSS/cl-id3/ 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 https://web.archive.org/web/20061109050158/http://www.codeproject.com/cs/algorithms/id3.asp]
• [http://search.cpan.org/~kwilliams/AI-DecisionTree An implementation of ID3 in Perl]