The ID3 algorithm describes how to build a decision tree for a given a set of sample facts. The tree asks the most important questions first. We have a set of criteria (such as “Is it a mammal?”) and an objective that we want to decide (such as “Can it swim?”). Each fact has a value for each criterion and the objective. Here is a set of five facts about animals. (Each row is a fact.) There are four criteria and one objective (the columns of the table). For simplicity, we assume that the values of the criteria and objective are binary (Y or N).

Therefore, we choose “Does it have fur?” as our first criterion.
In the left subtree, look at the animals with fur. There is only one, a non-swimmer, so you can declare “It doesn’t swim.” For the right subtree, you now have four facts (the animals without fur) and three criteria. Repeat the process.

Is it a mammal? Does it have fur? Does it have a tail? Does it lay eggs? N Y Y N Y Y Y Y N Y N N ZZZ N N Y Y ZZZZ N N N Y Can it swim? N Y Y Y N We now need several definitions. Given any probability value p between 0 and 1, its uncertainty is U(p)=-p log2(p)-(1-p)log(1-p) If p is 0 or 1, the outcome is certain, and the uncertainty U(p) is 0. Ifp = 1/2, then the outcome is completely uncertain and U(p) = 1.