C4.5 decision forests

Much of previous attention on decision trees focuses on the splitting criteria and optimization of tree sizes. The dilemma between overfitting and achieving maximum accuracy is seldom resolved. We propose a method to construct a decision tree based classifier that maintains highest accuracy on training data and improves on generalization accuracy as it grows in complexity. Trees are generated using the well-known C4.5 algorithm, and the classifier consists of multiple trees constructed in pseudo-randomly selected subspaces of the given feature space. We compare the method to single-tree classifiers and other forest construction methods by experiments on four public data sets, where the method's superiority is demonstrated. A measure is given to describe the similarity between trees in a forest, and is related to the combined classification accuracy.