ID3 Algorithm - Algorithm

Algorithm

The ID3 algorithm can be summarized as follows:

1. Take all unused attributes and count their entropy concerning test samples
2. Choose attribute for which entropy is minimum (or, equivalently, information gain is maximum)
3. Make node containing that attribute

The 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, of A,
    • Add a new tree branch below Root, corresponding to the test A = .
    • Let Examples be the subset of examples that have the value for A
    • If Examples 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, Target_Attribute, Attributes – {A})
• End
• Return Root