Projects

GA-Optimized Decision Trees

Repository · Docs · Zenodo

CART grows a tree one greedy split at a time and prunes it afterwards. This framework searches over whole trees instead, so the objective can be anything you can compute from a tree: accuracy, node count, features used, path length, or your own metric.

Two ways to run it

  • One weighted objective. Accuracy and a size penalty, combined into one fitness. You pick the weight before the run.
  • NSGA-II. Accuracy up, node count down, as two objectives. The run returns the whole Pareto front, and you pick the tree after you’ve seen the trade-off instead of guessing a weight.
populationwhole treesNSGA-IInext generationtrade-offaccuracy vstree size

What keeps the search honest

  • Pass a validation split and fitness is scored on rows the leaves weren’t fitted on. Without one, the search rewards whichever tree memorises the training rows best.
  • Given the training data, split thresholds are drawn from values that actually reach a node, so a mutation always changes how the data is split.
  • Four mutations (nudge a threshold, swap a split’s feature, prune a subtree to a leaf, grow a leaf into a split) plus subtree crossover.
  • Optional constraint repair keeps min_samples_split and min_samples_leaf true after every crossover and mutation, not only at the start.

The benchmarking harness

ga_trees.benchmark compares the GA with CART and random search on equal terms: nested cross-validation, the same tree space, and an exactly matched number of evaluations. It loads datasets from scikit-learn, OpenML, CSV and Excel, and every run is described by one YAML config.

It’s meant for objectives a greedy split rule can’t target: a cap on distinct features, a feature-cost budget, or the full accuracy–size front.

How it shipped

Python, built on DEAP and scikit-learn. v1.0.1 has 646 tests. CI runs the unit tests on Python 3.9 to 3.12 on Linux, and on 3.11 on macOS and Windows. MIT licensed, archived on Zenodo, with Abd Alrazak Qahwaji and Yousef Deeb as co-authors of the release.

pip install git+https://github.com/ibrah5em/ga-optimized-trees