ID3算法

ID3算法（Iterative Dichotomiser 3 迭代二叉樹3代）是一個由Ross Quinlan發明的用於決策樹的算法。

這個算法是建立在奧卡姆剃刀的基礎上：越是小型的決策樹越優於大的決策樹（簡單理論）。儘管如此，該算法也不是總是生成最小的樹形結構。而是一個啟發式算法。奧卡姆剃刀闡述了一個信息熵的概念：

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

這個ID3算法可以歸納為以下幾點：

1. 使用所有沒有使用的屬性並計算與之相關的樣本熵值
2. 選取其中熵值最小的屬性
3. 生成包含該屬性的節點

關於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（頁面存檔備份，存於網際網路檔案館）