pytrees-rs
pytrees-rs learns anytime optimal decision trees. It is written mostly in Rust and comes with a Python wrapper that follows the scikit-learn API, so the estimators work with pipelines, grid search and cross-validation.
A greedy learner such as CART picks, at each node, the split that looks best right now, and never revisits it. That is fast, but the tree it builds can be much worse than the best tree of the same size. The learners here look further ahead:
| Estimator | Features | What it learns |
|---|---|---|
DL85Classifier | binary | The optimal tree of a given depth (DL8.5) |
LGDTClassifier | binary | A tree grown top-down whose tests are chosen with a depth-2 lookahead (LGDT) |
ConTreeClassifier | continuous | The optimal tree of a given depth (ConTree) |
DL85Cluster | binary | A clustering whose clusters are the leaves of an optimal tree |
An optimal tree is the tree with the fewest training errors among all trees
of at most max_depth levels with at least min_sup training rows per leaf.
Finding it is NP-hard, and on large datasets or deep trees the search may not
finish. Two things make that manageable:
- Every search has a time limit (
max_time) and returns the best tree found so far, withstatus_telling you whether it was proven optimal. - The anytime searches find a good tree early and keep improving it. For
DL8.5 they are configured with the search rules; for
ConTree with
use_lds=True. Both estimators have afit_anytimemethod that reports each improvement as it happens.
Small optimal trees are often as accurate as much larger greedy ones, and they are easy to read: a depth-3 tree is at most seven tests.
Where to go next
- Installation and the quick start.
- The estimators chapter documents every parameter.
- The command line tools and the Rust crates give access to the same algorithms without Python.
- Publications lists the papers behind each algorithm.