TY - JOUR

T1 - On the depth of decision trees over infinite 1-homogeneous binary information systems

AU - Moshkov, Mikhail

N1 - KAUST 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.

PY - 2021/4

Y1 - 2021/4

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/668498

UR - https://linkinghub.elsevier.com/retrieve/pii/S2590005621000084

U2 - 10.1016/j.array.2021.100060

DO - 10.1016/j.array.2021.100060

M3 - Article

SP - 100060

JO - Array

JF - Array

SN - 2590-0056

ER -