Optimization and analysis of decision trees and rules: dynamic programming approach

Abstract

This paper is devoted to the consideration of software system Dagger created in KAUST. This system is based on extensions of dynamic programming. It allows sequential optimization of decision trees and rules relative to different cost functions, derivation of relationships between two cost functions (in particular, between number of misclassifications and depth of decision trees), and between cost and uncertainty of decision trees. We describe features of Dagger and consider examples of this system’s work on decision tables from UCI Machine Learning Repository. We also use Dagger to compare 16 different greedy algorithms for decision tree construction.

Keywords:

• dynamic programming
• decision trees
• decision rules
• optimization

Acknowledgments

The authors wish to express their gratitude to anonymous reviewers for useful comments.