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

Array

Mikhail Moshkov¹ 

[1] Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology (KAUST), Thuwal, 23955-6900, Saudi Arabia;

关键词: Information systems;    Decision trees;    Depth;   

DOI  :  

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown