تقرير
Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees
| العنوان: | Optimal Mixed Integer Linear Optimization Trained Multivariate Classification Trees |
|---|---|
| المؤلفون: | Alston, Brandon, Hicks, Illya V. |
| سنة النشر: | 2024 |
| المجموعة: | Computer Science Mathematics |
| مصطلحات موضوعية: | Computer Science - Machine Learning, Computer Science - Discrete Mathematics, Mathematics - Combinatorics |
| الوصف: | Multivariate decision trees are powerful machine learning tools for classification and regression that attract many researchers and industry professionals. An optimal binary tree has two types of vertices, (i) branching vertices which have exactly two children and where datapoints are assessed on a set of discrete features and (ii) leaf vertices at which datapoints are given a prediction, and can be obtained by solving a biobjective optimization problem that seeks to (i) maximize the number of correctly classified datapoints and (ii) minimize the number of branching vertices. Branching vertices are linear combinations of training features and therefore can be thought of as hyperplanes. In this paper, we propose two cut-based mixed integer linear optimization (MILO) formulations for designing optimal binary classification trees (leaf vertices assign discrete classes). Our models leverage on-the-fly identification of minimal infeasible subsystems (MISs) from which we derive cutting planes that hold the form of packing constraints. We show theoretical improvements on the strongest flow-based MILO formulation currently in the literature and conduct experiments on publicly available datasets to show our models' ability to scale, strength against traditional branch and bound approaches, and robustness in out-of-sample test performance. Our code and data are available on GitHub. Comment: arXiv admin note: text overlap with arXiv:2206.04857 |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2408.01297 |
| رقم الأكسشن: | edsarx.2408.01297 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |