# bsnsing: A decision tree induction method based on recursive optimal boolean rule composition

arXiv: https://arxiv.org/abs/2205.15263 · HTML: https://mlsanity.com/paper/2205.15263/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 30 May 2022.

## Builds on (most cited first, 7 of 7)

- [Interpretable classifiers using rules and Bayesian analysis: Building a better stroke prediction model](https://mlsanity.com/paper/1511.01644/) (2015)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Generalized and Scalable Optimal Sparse Decision Trees](https://mlsanity.com/paper/2006.08690/) (2020)
- [Scalable Bayesian Rule Lists](https://mlsanity.com/paper/1602.08610/) (2016)
- [Learning Certifiably Optimal Rule Lists for Categorical Data](https://mlsanity.com/paper/1704.01701/) (2017)
- [A Scalable MIP-based Method for Learning Optimal Multivariate Decision Trees](https://mlsanity.com/paper/2011.03375/) (2020)
- [Box Drawings for Learning with Imbalanced Data](https://mlsanity.com/paper/1403.3378/) (2014)

## Built on by (most cited first, 3 of 3)

- [Optimal or Greedy Decision Trees? Revisiting their Objectives, Tuning, and Performance](https://mlsanity.com/paper/2409.12788/) (2024)
- [Experiments with Optimal Model Trees](https://mlsanity.com/paper/2503.12902/) (2025)
- [RS-ORT: A Reduced-Space Branch-and-Bound Algorithm for Optimal Regression Trees](https://mlsanity.com/paper/2510.23901/) (2025)

## Abstract (arXiv)

This paper proposes a new mixed-integer programming (MIP) formulation to optimize split rule selection in the decision tree induction process, and develops an efficient search algorithm that is able to solve practical instances of the MIP model faster than commercial solvers. The formulation is novel for it directly maximizes the Gini reduction, an effective split selection criterion which has never been modeled in a mathematical program for its nonconvexity. The proposed approach differs from other optimal classification tree models in that it does not attempt to optimize the whole tree, therefore the flexibility of the recursive partitioning scheme is retained and the optimization model is more amenable. The approach is implemented in an open-source R package named bsnsing. Benchmarking experiments on 75 open data sets suggest that bsnsing trees are the most capable of discriminating new cases compared to trees trained by other decision tree codes including the rpart, C50, party and tree packages in R. Compared to other optimal decision tree packages, including DL8.5, OSDT, GOSDT and indirectly more, bsnsing stands out in its training speed, ease of use and broader applicability without losing in prediction accuracy.