Multi-pruning of decision trees for knowledge representation and classification

We consider two important questions related to decision trees: first how to construct a decision tree with reasonable number of nodes and reasonable number of misclassification, and second how to improve the prediction accuracy of decision trees when they are used as classifiers. We have created a dynamic programming based approach for bi-criteria optimization of decision trees relative to the number of nodes and the number of misclassification. This approach allows us to construct the set of all Pareto optimal points and to derive, for each such point, decision trees with parameters corresponding to that point. Experiments on datasets from UCI ML Repository show that, very often, we can find a suitable Pareto optimal point and derive a decision tree with small number of nodes at the expense of small increment in number of misclassification. Based on the created approach we have proposed a multi-pruning procedure which constructs decision trees that, as classifiers, often outperform decision trees constructed by CART.

1. Introduction

Decision trees continue to be one of the most understandable ways to represent knowledge contained in data. They also serve as a basis for different kinds of classifier ensembles. The questions how to construct (i) more understandable and at the same time enough accurate decision trees and (ii) decision trees with better predictive performance are of great interest [1], [2].