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

Research output: Contribution to journalArticlepeer-review

Abstract

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.
Original languageEnglish (US)
Pages (from-to)100060
JournalArray
DOIs
StatePublished - Apr 2021

Fingerprint Dive into the research topics of 'On the depth of decision trees over infinite 1-homogeneous binary information systems'. Together they form a unique fingerprint.

Cite this