Here we describe, step by step, how an ID3 algorithm would construct a decision tree from the given data samples in the swim preference example. The initial set consists of six data samples:
S={(none,cold,no),(small,cold,no),(good,cold,no),(none,warm,no),(small,warm,no),(good,warm,yes)}
In the previous sections, we calculated the information gains for both and the only non- classifying attributes, swimming suit and water temperature:
IG(S,swimming suit)=0.3166890883
IG(S,water temperature)=0.19087450461
Hence, we would choose the attribute swimming suit as it has a higher information gain. There is no tree drawn yet, so we start from the root node. As the attribute swimming suit has three possible values {none, small, good}, we draw three possible branches out of it for each. Each branch will have one partition from the partitioned set S: Snone, Ssmall, and Sgood. We add nodes to the ends of the branches. Snone data samples have the same class swimming preference = no, so we do not need to branch that node by a further attribute and partition the set. Thus, the node with the data Snone is already a leaf node. The same is true for the node with the data Ssmall.
But the node with the data Sgood has two possible classes for swimming preference. Therefore, we will branch the node further. There is only one non-classifying attribute left - water temperature. So there is no need to calculate the information gain for that attribute with the data Sgood. From the node Sgood, we will have two branches, each with the partition from the set Sgood. One branch will have the set of the data sample Sgood, cold={(good,cold,no)}, the other branch will have the partition Sgood, warm={(good,warm,yes)}. Each of these two branches will end with a node. Each node will be a leaf node because each node has the data samples of the same value for the classifying attribute swimming preference.
The resulting decision tree has four leaf nodes and is the tree in the figure 3.1. - Decision tree for the swim preference example.