Machine-learning methods have exciting potential to aid materials discovery, but their wider adoption can be hindered by the opaqueness of many models. Even if these models are accurate, the inability to understand the basis for the predictions breeds skepticism. Thus, it is imperative to develop machine-learning models that are explainable and interpretable so that researchers can judge for themselves if the predictions are consistent with their own scientific understanding and chemical insight. In this spirit, the sure independence screening and sparsifying operator (SISSO) method was recently proposed as an effective way to identify the simplest combination of chemical descriptors needed to solve classification and regression problems in materials science. This approach uses domain overlap (DO) as the criterion to find the most informative descriptors in classification problems, but sometimes a low score can be assigned to useful descriptors when there are outliers or when samples belonging to a class are clustered in different regions of the feature space. Here, we present a hypothesis that the performance can be improved by implementing decision trees (DT) instead of DO as the scoring function to find the best descriptors. This modified approach was tested on three important structural classification problems in solid-state chemistry: perovskites, spinels, and rare-earth intermetallics. In all cases, the DT scoring gave better features and significantly improved accuracies of ≥0.91 for the training sets and ≥0.86 for the test sets.