This paper deals with the optimization of classification trees. We discuss the case of small training samples and large test samples so that the model accuracy on the test set is adequate for the characterization of the model’s predictive power. The idea of our approach is to repeatedly generate models on small subsamples of the overall learning sample and identify that model which is best on the corresponding test sample. In our application, not the number of misclassifications of the individual observations is relevant for the model accuracy, but the number of misclassified sequences of observations of a specified minimum length. This leads to an innovative optimization criterion. Our application belongs to Music Data Analysis.