Construction of Near-Optimal Axis-Parallel Decision Trees Using a Differential-Evolution-Based Approach

Abstract

In this paper, a differential-evolution-based approach implementing a global search strategy to find a near-optimal axis-parallel decision tree is introduced. In this paper, the internal nodes of a decision tree are encoded in a real-valued chromosome, and a population of them evolves using the training accuracy of each one as its fitness value. The height of a complete binary decision tree whose number of internal nodes is not less than the number of attributes in the training set is used to compute the chromosome size, and a procedure to map a feasible axis-parallel decision tree from one chromosome is applied, which uses both the smallest-position-value rule and the training instances. The best decision tree in the final population is refined replacing some leaf nodes with sub-trees to improve its accuracy. The differential evolution algorithm has been successfully applied in conjunction with several supervised learning methods to solve numerous classification problems, due to it exhibiting a good tradeoff between its exploitation and exploration skills, and to the best of our knowledge, it has not been utilized to build axis-parallel decision trees. To obtain reliable estimates of the predictive performance of this approach and to compare its results with those achieved by other methods, a repeated stratified ten-fold cross-validation procedure is applied in the experimental study. A statistical analysis of these results suggests that our approach is better as a decision tree induction method as compared with other supervised learning methods. Also our results are comparable to those obtained with random forest and one multilayer-perceptron-based classifier.

Keywords

• Decision trees
• differential evolution
• metaheuristics
• smallest-position-value rule
• supervised learning