Complexity of Classification Problems and Comparative Advantages of Combined Classifiers

We studied a number of measures of the complexity of a classification problem and related them to the comparative advantages of two methods to create multiple classifier systems. We used decision trees as prototypical classifiers, and bootstrapping and subspace projection as classifier generation methods, to study a collection of 437 two-class problems from the UCI depository and an NIST image database. We observed that there are strong correlations between the classifier accuracies and a measure of length of class boundaries as well as a measure of the thickness of the class manifolds. Also, the bootstrapping method is better when subsamples yield more variable boundary measures and the subspace method excels when many features contribute evenly to the discrimination.