Decision trees are widely used for their interpretability and speed—but they are greedy. At each node, standard CART chooses the split that minimizes impurity on the training set, which can lead to unstable or overfit splits, especially in noisy settings.

Robust CART rethinks this by selecting splits that generalize better. Each node is chosen using a form of local stability selection: it evaluates candidate splits by how well they perform on multiple subsamples and held-out partitions of the data.

Standard CART greedily chooses the best split on the training data. But what if that split doesn’t generalize? Just as bagging improves tree ensembles by reducing variance, we seek to stabilize individual tree splits by preferring those that perform well across data resamplings.

This idea is inspired by:

• Stability selection (Meinshausen & Bühlmann, 2010)
• Subsampled cross-validation at nodes
• The intuition that a split that is “locally stable” across bootstraps is likely to be better out-of-sample

• A custom decision tree class RobustCART
• At each node:
  • Perform 100 subsamples (random ~30–70% of data, adaptively)
  • Train a decision stump on each and validate on the holdout
  • Record classification loss across all subsamples for each candidate split
  • Choose the split with the best average out-of-sample loss
• Tree building continues recursively as in CART
• Evaluation on synthetic and real-world datasets
• Time and memory profiling for comparison

Robust CART tends to outperform standard CART in noisy settings, and often modestly improves performance on clean real-world data. The cost is additional computation—each node performs hundreds of split evaluations—but remains feasible for moderate-sized datasets.