查看“︁ID3算法”︁的源代码

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

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

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

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

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

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

== 相关主题 ==
* [[C4.5算法]]

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

== 外部链接 ==
* Seminars - [http://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/dtrees/4_dtrees1.html http://www2.cs.uregina.ca/]{{Wayback|url=http://www2.cs.uregina.ca/~hamilton/courses/831/notes/ml/dtrees/4_dtrees1.html |date=20081025192401 }}
* Description and examples - [http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm http://www.cise.ufl.edu/]{{Wayback|url=http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm |date=20081205001124 }}
* Description and examples - [http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html http://www.cis.temple.edu/]{{Wayback|url=http://www.cis.temple.edu/~ingargio/cis587/readings/id3-c45.html |date=20081210074304 }}
* [http://www.onlamp.com/pub/a/python/2006/02/09/ai_decision_trees.html An implementation of ID3 in Python]{{Wayback|url=http://www.onlamp.com/pub/a/python/2006/02/09/ai_decision_trees.html |date=20081212042139 }}
* [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]{{Wayback|url=http://search.cpan.org/~kwilliams/AI-DecisionTree |date=20090130090457 }}

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