ID3 algorithm

ID3 (Iterative Dichotomiser 3) is an algorithm used to generate a decision tree invented by Ross Quinlan.

The algorithm is based on Occam's razor: it prefers smaller decision trees (simpler theories) over larger ones. However, it does not always produce the smallest tree, and is therefore a heuristic. Occam's razor is formalized using the concept of information entropy:

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

The ID3 algorithm can be summarized as follows:

# Take all unused attributes and count their entropy concerning test samples
# Choose attribute for which entropy is minimum
# Make node containing that attribute

An explanation of the implementation of ID3 can be found at C4.5 algorithm, which is an extended version of ID3.

Algorithm

The actual algorithm is as follows:

ID3 (Examples, Target_Attribute, Attributes)
*Create a root node for the tree
*If all examples are positive, Return the single-node tree Root, with label = +.
*If all examples are negative, Return the single-node tree Root, with label = -.
*If number of predicting attributes is empty, then Return the single node tree Root, with label = most common value of the target attribute in the examples.
*Otherwise Begin
** A = The Attribute that best classifies examples.
** Decision Tree attribute for Root = A.
** For each possible value, $v\_i$, of A,
*** Add a new tree branch below Root, corresponding to the test A = $v\_i$.
*** Let Examples($v\_i$), be the subset of examples that have the value $v\_i$ for A
*** If Examples($v\_i$) is empty
**** Then below this new branch add a leaf node with label = most common target value in the examples
*** Else below this new branch add the subtree ID3 (Examples($v\_i$), Target_Attribute, Attributes – {A})
*End
*Return Root

See also

* C4.5 algorithm

References

* Mitchell, Tom M. "Machine Learning". McGraw-Hill, 1997.

External links

* Seminars - [http://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]
* [http://ai4r.rubyforge.org/machineLearning.html An implementation of ID3 in Ruby]
* [http://www.pvv.ntnu.no/~oyvinht/static/OSS/cl-id3/ An implementation of ID3 in Common Lisp]
* Implementation of ID3 algorithm in C# - [http://www.codeproject.com/cs/algorithms/id3.asp http://www.codeproject.com/cs/algorithms/id3.asp]
* Decision tree Perl Module - [http://search.cpan.org/~kwilliams/AI-DecisionTree An implementation of ID3 in Perl] atomic resolution.