The Influence of Dimensions on the Complexity of Computing Decision Trees

Stephen G. Kobourov, Maarten Löffler, Fabrizio Montecchiani +5

A decision tree recursively splits a feature space ${\mathbb{R}}^d$ and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machi…