In this paper, we study decision trees, which solve problems defined over a specific subclass of infinite information systems, namely: 1-homogeneous binary information systems. It is proved that the minimum depth of a decision tree (defined as a function on the number of attributes in a problem’s description) grows – in the worst case – logarithmically or linearly for each information system in this class. We consider a number of examples of infinite 1-homogeneous binary information systems, including one closely related to the decision trees constructed by the CART algorithm.
Bibliographical noteKAUST Repository Item: Exported on 2021-04-05
Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST). The author is thankful to Dr. Michal Mankowski for the helpful comments. The author gratefully acknowledges the useful suggestions of the anonymous reviewers.