Tree ensemble construction using a GRASP-based heuristic and annealed randomness

• Two new tree ensemble construction methods are presented.
• The methods use the same solution generation strategy that is used by GRASP.
• One aims to increase the diversity while minimizing the effect on accuracy.
• The randomness is high at the root in order to encourage diversity.
• The randomness is low at leaves to reduce loss of accuracy.

Two new methods for tree ensemble construction are presented: G-Forest and GAR-Forest. In a similar way to Random Forest, the tree construction process entails a degree of randomness.The same strategy used in the GRASP metaheuristic for generating random and adaptive solutions is used at each node of the trees. The source of diversity of the ensemble is the randomness of the solution generation method of GRASP. A further key feature of the tree construction method for GAR-Forest is a decreasing level of randomness during the process of constructing the tree: maximum randomness at the root and minimum randomness at the leaves. The method is therefore named “GAR”, GRASP with annealed randomness.The results conclusively demonstrate that G-Forest and GAR-Forest outperform Bagging, AdaBoost, MultiBoost, Random Forest and Random Subspaces. The results are even more convincing in the presence of noise, demonstrating the robustness of the method.The relationship between base classifier accuracy and their diversity is analysed by application of kappa-error diagrams and a variant of these called kappa-error relative movement diagrams.