4.3 DIVIDE-AND-CONQUER: CONSTRUCTING DECISION TREES 99
Before we created any of the nascent tree structures in Figure 4.2, the train-
ing examples at the root comprised nine yesand five nonodes, corresponding
to an information value of
Thus the tree in Figure 4.2(a) is responsible for an information gain of
which can be interpreted as the informational value of creating a branch on the
outlook attribute.
The way forward is clear. We calculate the information gain for each attri-
bute and choose the one that gains the most information to split on. In the sit-
uation of Figure 4.2,
so we select outlookas the splitting attribute at the root of the tree. Hopefully
this accords with your intuition as the best one to select. It is the only choice
for which one daughter node is completely pure, and this gives it a considerable
advantage over the other attributes.Humidityis the next best choice because it
produces a larger daughter node that is almost completely pure.
Then we continue, recursively. Figure 4.3 shows the possibilities for a further
branch at the node reached when outlookis sunny. Clearly, a further split on
outlookwill produce nothing new, so we only consider the other three attributes.
The information gain for each turns out to be
so we select humidityas the splitting attribute at this point. There is no need to
split these nodes any further, so this branch is finished.
Continued application of the same idea leads to the decision tree of Figure
4.4 for the weather data. Ideally, the process terminates when all leaf nodes are
pure, that is, when they contain instances that all have the same classification.
However, it might not be possible to reach this happy situation because there is
nothing to stop the training set containing two examples with identical sets of
attributes but different classes. Consequently, we stop when the data cannot be
split any further.
gain bits
gain bits
gain bits,temperature
humidity
windy( )=
( )=
( )=0 571
0 971
0 020.
.
.gain bits
gain bits
gain bits
gain bits,outlook
temperature
humidity
windy( )=
( )=
( )=
( )=0 247
0 029
0 152
0 048.
.
.
.gain(outlook)=info([]9 5)-info([][][]2 3 4 0 3 2)=-=0 940 0 693 0 247,,,,,,...bits,info([]9 5)=0 940,.bits.