An Algorithmic Framework for Constructing Multiple Decision Trees by
  Evaluating Their Combination Performance Throughout the Construction Process
Keito Tajima Naoki Ichijo Yuta Nakahara Toshiyasu Matsushima
Predictions using a combination of decision trees are known to be effective
in machine learning. Typical ideas for constructing a combination of decision
trees for prediction are bagging and boosting. Bagging independently constructs
decision trees without evaluating their combination performance and averages
them afterward. Boosting constructs decision trees sequentially, only
evaluating a combination performance of a new decision tree and the fixed past
decision trees at each step. Therefore, neither method directly constructs nor
evaluates a combination of decision trees for the final prediction. When the
final prediction is based on a combination of decision trees, it is natural to
evaluate the appropriateness of the combination when constructing them. In this
study, we propose a new algorithmic framework that constructs decision trees
simultaneously and evaluates their combination performance throughout the
construction process. Our framework repeats two procedures. In the first
procedure, we construct new candidates of combinations of decision trees to
find a proper combination of decision trees. In the second procedure, we
evaluate each combination performance of decision trees under some criteria and
select a better combination. To confirm the performance of the proposed
framework, we perform experiments on synthetic and benchmark data.