- ID3 algorithm
ID3 (Iterative Dichotomiser 3) is an
algorithm used to generate a decision tree invented byRoss 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 aheuristic . Occam's razor is formalized using the concept ofinformation 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 attributeAn 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 RootSee 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.
Wikimedia Foundation. 2010.