Mixed-Integer Linear Optimization for Semi-Supervised Optimal Classification Trees
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913168523001856 |
|---|---|
| author | Burgard, Jan Pablo Pinheiro, Maria Eduarda Schmidt, Martin |
| author_facet | Burgard, Jan Pablo Pinheiro, Maria Eduarda Schmidt, Martin |
| contents | Decision trees are one of the most popular methods for solving classification problems, mainly because of their good interpretability properties. Moreover, due to advances in recent years in mixed-integer optimization, several models have been proposed to formulate the problem of computing optimal classification trees. The goal is, given a set of labeled points, to split the feature spacewith hyperplanes and assign a class to each part of the resulting partition. In certain scenarios, however, labels are only available for a subset of the given points. Additionally, this subset may be non-representative, such as in the case of self-selection in a survey. Semi-supervised decision trees tackle the setting of labeled and unlabeled data and often contribute to enhancing the reliability of the results. Furthermore, undisclosed sources may provide extra information about the size of the classes. We propose a mixed-integer linear optimization model for computing semi-supervised optimal classification trees that cover the setting of labeled and unlabeled data points as well as the overall number of points in each class for a binary classification. Our numerical results show that our approach leads to a better accuracy and a better Matthews correlation coefficient for biased samples compared to other optimal classification trees, even if onlyfew labeled points are available. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09848 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Mixed-Integer Linear Optimization for Semi-Supervised Optimal Classification Trees Burgard, Jan Pablo Pinheiro, Maria Eduarda Schmidt, Martin Optimization and Control 90C11, 90C90, 90-08, 68T99 Decision trees are one of the most popular methods for solving classification problems, mainly because of their good interpretability properties. Moreover, due to advances in recent years in mixed-integer optimization, several models have been proposed to formulate the problem of computing optimal classification trees. The goal is, given a set of labeled points, to split the feature spacewith hyperplanes and assign a class to each part of the resulting partition. In certain scenarios, however, labels are only available for a subset of the given points. Additionally, this subset may be non-representative, such as in the case of self-selection in a survey. Semi-supervised decision trees tackle the setting of labeled and unlabeled data and often contribute to enhancing the reliability of the results. Furthermore, undisclosed sources may provide extra information about the size of the classes. We propose a mixed-integer linear optimization model for computing semi-supervised optimal classification trees that cover the setting of labeled and unlabeled data points as well as the overall number of points in each class for a binary classification. Our numerical results show that our approach leads to a better accuracy and a better Matthews correlation coefficient for biased samples compared to other optimal classification trees, even if onlyfew labeled points are available. |
| title | Mixed-Integer Linear Optimization for Semi-Supervised Optimal Classification Trees |
| topic | Optimization and Control 90C11, 90C90, 90-08, 68T99 |
| url | https://arxiv.org/abs/2401.09848 |