Abstract
We study problems of optimization of decision and inhibitory trees for decision tables with many-valued decisions. As cost functions, we consider depth, average depth, number of nodes, and number of terminal/nonterminal nodes in trees. Decision tables with many-valued decisions (multi-label decision tables) are often more accurate models for real-life data sets than usual decision tables with single-valued decisions. Inhibitory trees can sometimes capture more information from decision tables than decision trees. In this paper, we create dynamic programming algorithms for multi-stage optimization of trees relative to a sequence of cost functions. We apply these algorithms to prove the existence of totally optimal (simultaneously optimal relative to a number of cost functions) decision and inhibitory trees for some modified decision tables from the UCI Machine Learning Repository.
Original language | English (US) |
---|---|
Pages (from-to) | 910-921 |
Number of pages | 12 |
Journal | European Journal of Operational Research |
Volume | 263 |
Issue number | 3 |
DOIs | |
State | Published - Jun 16 2017 |
Bibliographical note
KAUST Repository Item: Exported on 2020-10-01Acknowledgements: Research reported in this publication was supported by the King Abdullah University of Science and Technology (KAUST). We are greatly indebted to the anonymous reviewers for useful comments and suggestions.