Source-linked AI summary
Improving the precision of classification trees
Wei-Yin Loh
TL;DR
Classification-tree precision is threatened by selection bias and failure to search beyond local main effects, which can impair variable selection and subgroup interpretation. The paper proposes four techniques addressing interaction searches, split selection, linear pairwise splits, and richer node models, and compares them with other algorithms and ensembles. The proposed single-tree methods can outperform Random Forest when interaction or linear effects are strong, while Random Forest is often more accurate overall.
Problem
Weak split-selection algorithms can select irrelevant variables or miss important ones by using biased searches or failing to detect effects beyond local main effects.
Method
The paper develops four techniques that control interaction searches, improve variable and split selection, add linear pairwise splits, and fit nearest-neighbor or kernel models at nodes.
Results
Random Forest often exceeds the accuracy of single-tree models S and K, but single-tree algorithms can be substantially more accurate when interaction or linear effects are strong.
Takeaways & Limitations
The preferred tree strategy depends on data complexity, because interaction and linear effects can favor the proposed single-tree algorithms over Random Forest.
Takeaways & Limitations
Error rates computed from the same data used to construct the trees are biased low, so the paper uses ten-fold cross-validation for algorithm comparisons.
Abstract
from arXiv · showhide
Besides serving as prediction models, classification trees are useful for finding important predictor variables and identifying interesting subgroups in the data. These functions can be compromised by weak split selection algorithms that have variable selection biases or that fail to search beyond local main effects at each node of the tree. The resulting models may include many irrelevant variables or select too few of the important ones. Either eventuality can lead to erroneous conclusions. Four techniques to improve the precision of the models are proposed and their effectiveness compared with that of other algorithms, including tree ensembles, on real and simulated data sets.
1. Introduction.
Classification trees are interpretable, but weak split-selection strategies can sacrifice predictive accuracy, parsimony, or reliable variable identification. The paper introduces four techniques designed to improve tree precision by controlling interaction searches, improving split selection, and fitting richer node models.
- Classification trees visualize multidimensional data more intuitively than models described only by mathematical equations.
- Interpretability does not ensure predictive accuracy or parsimony, and irrelevant variables can make a tree cumbersome and misleading.
- Exhaustive split searches can favor variables with more values, producing overly large or overly small trees and obscuring variable importance.
- QUEST avoids selection bias through main-effect tests but can miss strong local interactions, whereas CRUISE tests pairwise interactions and can uncover more structure.
- The paper proposes four techniques: controlled interaction testing, two-level split searches, linear splits on variable pairs, and nearest-neighbor or kernel node models.
- On mammography data, the proposed S-method tree has complexity between CRUISE and QUEST versus RPART and C4.5.
2. Controlled search for local interactions.
The paper controls local-interaction searches so interaction tests do not overwhelm main effects, while using chi-squared-based variable selection and two-level searches to detect important split structures. These adjustments address QUEST’s insensitivity to local interactions and CRUISE’s tendency to overemphasize them.
- Motivation: QUEST selects variables using local main-effect p-values, so it can miss strong interactions when local main effects are weak.It evaluates ANOVA or Pearson chi-squared p-values and chooses the smallest, avoiding selection bias but remaining insensitive to local interactions.
- Motivation: CRUISE tests K main effects and K(K −1)/2 pairwise interactions, allowing interaction tests to overwhelm main effects and select weak-main-effect variables.Because there are usually more interaction tests, the smallest p-value often comes from an interaction test.
- Motivation: In the diagonal-square example, the optimal tree requires a two-level search using both predictors, whereas CRUISE may need many more splits to classify accurately.The first split uses either X1 or X2 at the origin, followed by splitting each half on the other variable.
- Proposed control: The proposed adjustment tests interactions only when no main effect is significant and then performs a two-level split search when a significant interaction is found.This design prevents interaction tests from overwhelming main-effect tests while retaining a route to interaction-driven splits.
- Proposed control: Variable selection uses chi-squared statistics for main effects and interactions, with discretization for noncategorical predictors and separate split-point searches.The procedure applies Bonferroni-corrected thresholds and selects the largest qualifying main-effect or interaction statistic.
- Split selection: For a selected variable, the split is chosen by minimizing the weighted sum of the child-node Gini impurities.The procedure forms left and right subnodes and evaluates candidate value sets or split points for the selected variable.
3. Linear splits.
The proposed method uses linear splits selectively on pairs of variables when main-effect and interaction tests do not identify an adequate split. On fish data, this preserves simple tree structure while improving classification relative to several alternatives.
- Linear combinations can improve predictive accuracy, although univariate splits remain easier to interpret.
- Discriminant splits: For two noncategorical variables, the method trims class-specific outliers, derives a discriminant coordinate, projects observations onto it, and evaluates the resulting split.
- Split selection: The method first tests main effects and interactions, then considers a significant linear split only when those tests are not significant.Linear splitting is therefore reserved for nodes where simpler split options are insufficient.
- Split selection: The algorithm prioritizes main-effect splits, then interaction splits, and finally linear splits according to chi-squared thresholds.
- Fish-data example: Variable transformations changed the fish-tree results substantially, and same-data error rates were likely biased low before cross-validation.
4. Selection bias.
The paper evaluates whether its split-selection procedure avoids favoring variables by type or distribution under null and dependence scenarios. Simulation results indicate that overall variable-selection probabilities are close to the unbiased target.
- Simulation design: The simulation uses 10,000 trials with six predictors and a class variable independent of the predictors to assess selection bias.
- Simulation design: The predictors include categorical, chi-squared, normal, uniform, and dependent-variable scenarios.
- Results: Continuous variables were selected slightly less often in univariate splits, but linear-split selections offset this difference.
- Results: After halving linear-split counts before aggregation, all overall selection probabilities fell within two simulation standard errors of 1/6.
5. Kernel and nearest-neighbor node models.
The paper fits kernel-density or nearest-neighbor models within tree nodes, using at most two selected variables, to obtain more compact trees while retaining flexible local classification. In an artificial three-class example, these models produced unsplit pruned trees with low error.
- Motivation: Kernel and nearest-neighbor node models are introduced to reduce tree size while remaining more flexible than linear discriminant models.
- Kernel models: Kernel models estimate class-specific densities for one or two selected variables and predict the class with the largest estimated density.
- Kernel models: The kernel bandwidth was deliberately wider than the usual asymptotically optimal density-estimation value because discrimination can favor larger bandwidths.
- Nearest-neighbor models: Nearest-neighbor predictions use one-variable, conditional mixed-variable, or bivariate Mahalanobis-distance classifiers depending on the selected variables.
- Artificial example: In the artificial three-class problem, kernel and nearest-neighbor methods yielded pruned trees with no splits and misclassified 2 and 8 observations, respectively.
6. Comparison on forty-six datasets.
The comparison evaluates ten algorithms on 46 real and artificial data sets using ten-fold cross-validation. The proposed methods perform especially well on data with strong interaction or linear effects, while average tree size and computational comparisons vary by algorithm and data set.
- Evaluation: The study compares ten algorithms on 42 real and four artificial data sets using ten-fold cross-validation.
- Evaluation: The data sets span sample sizes from 97 to 45,222, two to eleven classes, and wide ranges of categorical and noncategorical predictors.
- Predictive accuracy: The proposed K, N, and S algorithms have a superior edge on the artificial int and cl3 data sets, where interaction detection matters.
- Tree size: C45 tends to produce the largest trees, whereas C2v and Rp often produce the shortest trees.
- Aggregate results: S has the smallest mean error rate, while Ct has the largest; Ct differs significantly from S, N, K, and Qu at the reported confidence level.
- Computation: Execution-time comparisons depend on implementation language and hardware, and Rp's mean time is dominated by two high-cardinality data sets.
7. Tree ensembles.
The paper compares single-tree models with bagged and forest ensembles, finding that ensembles can improve accuracy but may be less interpretable and that performance depends on data complexity.
- Ensemble construction: Tree ensembles predict by majority vote across collections of tree models.Bagging uses bootstrap samples, while Random Forest uses random subsets of variables at each split and unpruned trees.
- Interpretability: Ensemble classifiers are typically used for prediction only because interpreting many trees is practically impossible.
- Ensemble construction: BG contains 100 pruned GUIDE trees built with bootstrap samples, whereas GF contains 500 unpruned GUIDE trees using random variable subsets.
- Comparative evaluation: Figure 15 compares BG, GF, and RF error rates with those of the single-tree S and K methods across data sets.RF is not applicable to data sets with predictor variables exceeding 32 categorical levels or with unseen test-sample class labels.
- Comparative evaluation: Mean error-rate differences across the 46 data sets where RF is applicable are not statistically significant.
- Comparative evaluation: Single-tree methods can outperform Random Forest on data sets with strong linear or interaction effects, including cl3, fis, and int.BG does not share GF and RF’s difficulties on these data sets because BG permits linear and interaction splits.
8. Conclusion.
The paper balances conservative split searches against the need to detect interactions and linear structure, then extends trees with flexible node models and evaluates ensembles.
- Split selection: The method prioritizes main-effect tests, tests interactions only when main effects are nonsignificant, and tests linear structure only afterward.Bonferroni corrections control each group’s significance level, and significant interactions trigger a two-level split search.
- Flexible node models: Kernel or nearest-neighbor node models can substantially improve accuracy and tree compactness when main effects are weak but two-factor interactions are strong.These models require more computation, while empirical evidence indicates high prediction accuracy on ordinary data sets.
- Tree ensembles: Random Forest often exceeds the accuracy of single-tree models, but its average increase is only about 10% across 43 data sets.When interaction or linear effects are strong, the proposed single-tree algorithms can be substantially more accurate than Random Forest.
- Implementation: All proposed algorithms are implemented in version 8 of GUIDE for Linux, Macintosh, and Windows.
APPENDIX
The appendix specifies procedures for selecting splits involving categorical and noncategorical variables, including ordered searches, two-level searches, and LDA-based reductions.
- Noncategorical variables: For two noncategorical variables, the procedure searches two-level splits in both variable orders and selects the split with the smaller heterogeneity criterion.It searches c in one variable with separate d and e thresholds in the other, then reverses the roles.
- Mixed variable types: For a noncategorical and categorical pair, the procedure first searches a split on the noncategorical variable, then searches categorical splits within its two sides.The final choice compares the best values from the alternative split arrangements.
- Mixed variable types: The mixed-variable procedure selects the initial noncategorical split when its criterion is no worse than either alternative; otherwise it selects the better categorical split.
- Categorical variables: For categorical variables, small or binary problems permit exhaustive subset searches, while larger problems use superclass ordering or LDA after dummy-variable transformation.The selected threshold or subset is re-expressed as a split on the original categorical variable.
- Categorical interactions: For two categorical variables, the procedure searches one variable’s split with restricted conditional searches, repeats with roles reversed, and chooses the lower criterion.The restrictions depend on the number of classes and distinct values.