Classification Trees

As described by Breiman et al. [11], classification trees are generated by making repeated binary splits in multi-class feature data such that the resulting two populations are more homogeneous than the original. Figure 1.8 shows a classification tree after the initial split of the data.

  

Figure 1.8: An example of a `good' split in a decision tree. The four numbers at each node represent the fraction of the samples at that node that belong to each of four classes. Samples are uniformly distributed among four classes in the root node and, in this example, are found to be best split using a value of 0.3 with feature 1 (f1). Samples with a value of f1 greater than 0.3 are sent to the left and the remaining samples are sent to the right. The samples in the leaf nodes are more homogeneous than the samples at the root because classes 1 and 2 are completely separated from classes 3 and 4.

The splits in the data are chosen such that they maximize a criterion designed to measure the difference in homogeneity between a node and its children. Breiman et al. [11] define two characteristics that such a criterion should meet:

1.

It should be at its maximum when all classes are equally mixed.

2.

It should be at a minimum when there is only one class present at a particular node.

A decision tree was among the first classifiers used because of its easy interpretation. Simply by traversing down the tree from the root to a leaf, one obtains a feature-based classification rule that defines which input values will cause a sample to end up at that leaf node.

One problem with decision trees is that their decision boundaries are not particularly complex (unless the tree itself becomes exceedingly complex). To improve upon the results obtained with a classification tree, other classifiers were developed.