ID3算法
外观
ID3算法(Iterative Dichotomiser 3 迭代二叉树3代)是一个由Ross Quinlan发明的用于决策树的算法。
这个算法是建立在奥卡姆剃刀的基础上:越是小型的决策树越优于大的决策树(简单理论)。尽管如此,该算法也不是总是生成最小的树形结构。而是一个启发式算法。奥卡姆剃刀阐述了一个信息熵的概念:
这个ID3算法可以归纳为以下几点:
- 使用所有没有使用的属性并计算与之相关的样本熵值
- 选取其中熵值最小的属性
- 生成包含该属性的节点
关于ID3算法的实现可以参考C4.5算法,它同时也是ID3的升级版。
相关主题
[编辑]参考文献
[编辑]- 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(页面存档备份,存于互联网档案馆)