ID3 Algorithm

• ID3( , , )
  1. Create a node for the tree
  2. If all are positive, Return the single-node tree , with label = +
  3. If all are negative, Return the single-node tree , with label = -
  4. If is empty, Return the single-node tree , with label = most common value of in
  5. Otherwise Begin
     • the attribute from that best classifies
     • The decision attribute for
     • For each possible value, , of ,
       • Add a new tree branch below , corresponding to the test
       • Let be the subset of that have value for
       • If is empty
         • Then below this new branch add a leaf node with label = most common value of in
         • Else below this new branch add the subtree
  6. End
  7. Return